How to prep for the exam

About the exam:

• The exam is closed-book, closed-notes, closed everything, in the same room as our class (SEH 1300/1400) for all students including extended-time students.
• You will need to put away everything (all devices, bags, laptop etc). You are advised to visit the facilities before starting, and to come early.
• Questions will be mostly multiple choice.
• Questions will be distributed on paper and answers expected on an answer sheet.
• You will need to turn in both the questions and answers. Note: the exam/questions will not be returned to you.
• The material for the exam is everything from Module 1 to 11 (except Module 6), and parts of modules 12 and 14, but with an emphasis on the most important concepts from these modules.
• The normal time for the exam is 40 minutes. The extended time is 60 minutes. Everyone will get 5 additional minutes to collect stuff together and turn in BOTH the answers and the exam questions.

How to prep:

• Review your own solutions to the non-programming module exercises. A slightly tweaked module exercise is fair game for the exam.
• Review at least the following core concepts:
  • Module 1: Big-Oh, the well-known functions, the "upper triangle" argument.
  • Module 2: The main sorts (bubble, quick, merge, heap), the binary heap data structure.
  • Module 3: The main operations (insert, search) on the different trees in this module, and deletion for binary trees.
  • Module 4: Hashing, tries.
  • Module 5: Rabin-Karp, Boyer-Moore-Horspool, using DFAs, regular expressions.
  • Module 6: No questions on Module 6.
  • Module 7: Graph data structures, BFS, DFS (and variations), visit order, DAGs.
  • Module 8: Union-find, Kruskal, Prim, Dijkstra algorithms.
  • Module 9: How dynamic programming works, Floyd-Warshall, distributed routing, optimal binary trees.
  • Module 10: Everything except the mathematics of simulated annealing.
  • Module 11: Everything except permutation generation.
  • Module 12: Alignment, genetic algorithm.
  • Module 13: sections 13.2, 13.4, 13.5.
  Note: for any of the data structures above, you should know how they work, and how to assess the running time for each operation.

Sample questions

One set of sample questions are the non-programming module exercises, or slightly modified versions of them.

Here are some others:

1. Consider this snippet of code (without worrying about syntactic correctness):

     int[][] A = new int [n][];
     for (int i=0; i<n; i++) {
         if (i % 2 == 0) 
             A[i] = new int [n];
         else
             A[i] = new int [1];
     }
   
     for (int i=0; i<A.length; i++) 
         for (int j=0; j<A[i].length; j++) 
             sum = sum + A[i][j]; 
     

   It's running time is:
   1. \(O(n\log n\)
   2. \(O(n)\)
   3. \(O(n^2)\).
   4. \(O(\frac{n}{2})\)

2. Suppose \(f(n) = 3n^3 + 2n^2 + n\). Consider these statements:
        I: \(f(n) = O(n^3)\).
        II: \(f(n) = O(n^4)\).
   1. Only I is true.
   2. Only II is true.
   3. I and II are both true.
   4. I and II are both false.

3. The ratio of the running time of Bubble-Sort to that of Merge-Sort is:
   1. \(O(n\log n)\)
   2. \(O(\frac{n}{\log n})\)
   3. \(O(\log \frac{n^2}{\log n})\).
   4. \(O(1)\).

4. Consider the following input with 10 keys (each is a letter) to QuickSort.

       K  G  I  K  N  V  S  S  W  Q
     

   Assume the leftmost element is the partitioning element. Show the array after the partitioning step is complete.

5. Insert the bitstrings 100, 110, 011 and 010 into a simple trie. Show the trie at each step.

6. Draw an NDFA for the regular expression C(AB)*(A|C)

7. A ring is a connected undirected graph in which all the nodes form a ring (thus, each node has exactly two neighbors). The running time of Prim's algorithm, using an adjacency list, on this graph is:
   1. \(O(V \log V)\)
   2. \(O(V^2 \log V)\)
   3. \(O(V^2)\)
   4. \(O(V^3)\)

8. Consider the following two statements about an undirected graph with n vertices:
        I: If every pair of vertices has an edge, there are exactly \(\frac{n(n+1)}{2}\) edges.
        II: If the graph has a spanning tree, the tree must have \(\Theta(n)\) edges.
   1. I and II are both true.
   2. Only I is true.
   3. Only II is true.
   4. I and II are both false.

9. Suppose the shortest path from node i to node j goes through node k and that the cost of the subpath from i to k is \(D_{ik}\). Consider these two statements:
        I: Every shortest path from i to j must go through k.
        II: Every shortest path from i to k has cost \(D_{ik}\).
   1. I and II are both true.
   2. Only I is true.
   3. Only II is true.
   4. I and II are both false.

10. Consider the following statements about NP-completeness:
         I: NP-completeness only applies to combinatorial optimization problems.
         II: An NP-complete problem cannot be solved in polynomial-time.
    1. I and II are both true.
    2. Only I is true.
    3. Only II is true.
    4. I and II are both false.