Computing Science 422

Self Quiz 0

Due: Sept 5 or 6 tutorial


Objective
To understand how much you remember of the material relating to algorithms: algorithmic paradigms, algorithm correctness (how to prove), and running time analysis.

  1. (10 marks) Order the following running times in order of asymptotically fastest first. If two or more of the functions are equivalent, asymptotically, then put parens around the group that are all asymptotically the same, as an entry in the list.

    5n + log n
    log 2n
    2n
    n2
    5n - log n + 3 log log n
    5n + log n - 3 log log n

    22n
    1.6n
    2n+2
    n!
    ln n

  2. (6 marks) If you have to visit every vertex in a graph, two algorithms to accomplish this are called:

    They run in time:

    The one that uses a stack is:

    The other one uses a (name the data structure):

  3. (4 marks) A graph can be represented in a number of ways; the two most imporant data structures for representing a graph are:

    A sparse graph is:

    It is natural to use the following data structure for sparse graphs:

    If n is the number of vertices in a graph, the number of edges in an undirected graph is ≤
    The number of edges in a directed graph is ≤
  4. (5 marks) Besides the Abstract Data Types (ATDs) discussed in 422 already, I am familiar with the following ADT(s):



    And one of them that has multiple useful implementations with different running time behaviour is the following:



  5. (5 marks) I can code up a mergeSort with one hand tied behind my back. Supposing a Merge subprogram is already supplied, the pseudocode for my MergeSort would look like this:







    MergeSort uses a programming paradigm called:

  6. (4 marks) The Stack ADT has the following interface (including descriptions of behaviour).





  7. (8 marks) An algorithm to determine the depth of a rooted binary tree is the the following:






  8. The running time of the above algorithm is:

    Proof:




The Array ADT:

Operations:
init(n): initializes a new Array, of size n, where n is a non-negative integer.

item get(i) : returns item at position i, if 1 ≤ i ≤ n and if there has been a "set(i,*)" operation since the last "init" operation. Otherwise, returns the sentinal item NO_ITEM.

set(i, k): sets item at position i to be item k. Overwrites whatever was in position i.

Previous Assignment            Next Self Quiz