Data Structures and Algorithm Analysis (CSC317)

• Problem set 1: Aug 23 (due Aug 30 in class). Read chapters 1 and 2 of textbook.
  1. Come up with a real-world problem in which only the best solution will do (example, only the exact right answer). Then come up with a real-world problem in which a solution that is approximately the best is good enough.
  2. Do exercises 1.2-2, 2.1-1.
  3. On the first birthday, we light one candle; on the second birthday 2 candles; and on the 120th birthday 120 candles. How many candles do we light total in all 120 birthdays? Use the proper summation formula.
• Problem set 2: Aug 30 (due Sept 6). 1. Write an algorithm to compute the maximum of an array of n numbers. Write down the loop invariant and prove correctness of the loop invariant by initialization, maintenance, and termination. 2. How can we modify almost any algorithm to have a good best-case running time? You can first give an example (e.g., for sorting) and then a more general answer. 3. Explain why the statement, “The running time of algorithm A is at least O(n^3),” is meaningless. 4. Do exercises 2.1-3, 2.2-1.
• Problem set 3: Sept 6 (due Sept 13). See the following link: problemset3_fall18.pdf
• Problem set 4: Sept 13 (due Sept 20).
  1. Exercise 4.3-1 [Hint: use the substitution method, guessing that T(n) <= cn^2 (reads n squared) for constant c].
  2. Argue that the solution to the recurrence T(n) = T(n/4)+T(3n/4) + cn, where c is a constant, is Omega of nlogn by appealing to a recursion tree. Draw the recursion tree and show how you obtain this answer.
  3. Do the following problem: 4-1 a,c (use the Master Theorem, and explain the link with a recursion tree in terms of where most of the work is being done).
  
• Problem set 5: Sept 20 (due Sept 27). 1. In many of the earlier algorithms in class, we analyzed worst case performance. What are we typically analyzing with randomized algorithms? Why do we randomize the candidates in the hiring problem of the textbook before running the algorithm and analysis?
  2. Exercises 5.2-1, 5.2-4, 5.2-5 [Hint: define xij indicator random variable on inverted pairs]. Explain all your steps, including reference to the equations we wrote in class.
• Problem set 6: Sept 27 (due Oct 4).
  1. Exercise 9.2-4. Also, what is the run time for the worst case performance you described in 9.2-4 as a function of the array size n? How does this compare to the average performance of Randomized-select? How does this compare to the average performance of Quicksort?
  2. What is the run time of Randomized-select algorithm if on every iteration the pivot divides the array into 1/5th and 4/5th pieces, and the recursion is on the larger side? Write out a recursive equation and solve it. How does this compare to the average performance of randomized-select?
  3. Consider a hash table with collisions resolved by chaining. Assume uniform hashing and that the number of elements n stored in the hash table is 10 times the number of slots. What is the average time for an unsuccessful search?
  4. Consider an open-address hash table with uniform hashing. What is the expected number of probes (at most) in an unsuccessful search when the load factor is 7/8?
• Oct 4: no problem set!
• Problem set 7: Oct 16 (due Oct 25). (a) Draw all valid Binary Search Trees for the four nodes 1, 2, 3, 5; (b) Draw all valid Binary Red Black Trees for the four nodes 1, 2, 3, 5. Note the corresponding Black Height of each node to help convince yourself it is a valid Red Black tree; (c) Exercises 13.1-5, 13.3-1, 13.3-3.
• Problem set 8: Oct 25 (due Nov 1)
  1. What is the running time of DFS if we represent its input graph by an adjacency matrix and modify the algorithm to handle this form of input?
  2. 22.3-2 (just show start and finish; not edge classification)
  3. 22.5-1
  4. Is the topological sort in the Cormen textbook fig 22.7 unique? Are there other ways of sorting? Explain why or why not considering the DFS approach.
  
• Problem set 9: Nov 1 (Due Nov 8)
  1. 22.5-3
  2. Run Dijkstra’s algorithm on the directed graph of Figure 24.2(a) in the book, first using vertex s as the source and then using vertex z as the source.
  3. Explain the example we showed in class (or make up your own) that for a graph with both positive and negative edge distances, Dijkstra will not necessarily find the shortest path.
• Problem set 10: Nov 8 (due April 15)
  1. What are the main properties of problems that can be solved with dynamic programming, and how is the dynamic programming approach better than brute force?
  2. 15.4-1 (explain your solution by showing the table)
  3. We developed a bottom up solution to the Longest Common Subsequence (see LCS-LENGTH o n page 394 in the text book). Write pseudo-code for a Memoized version and explain what you did.
  4. 15.1-3
• Problem set 11: Nov 15 (due Nov 29)
  1. For the dynamic programming formulations of the rod cutting problem, Fibonacci, and Longest Common Subsequence: (a) how many subproblems are there (this is the size of the matrix we saved)?; (b) how many choices for each subproblem?; (c) What is the total run time?.
  2. Explain why dynamic programming fails to speed up a good divide-and-conquer algorithm such as merge sort. Illustrate this by considering the sub-problems for an array of size 16.
  3. Not just any greedy approach to the activity-selection problem produces a maximum-size set of mutually compatible activities. Give an example to show that the approach of selecting the activity of least duration from among those that are compatible with previously selected activities does not work.
  4. 16.3-3 (Explain all steps of generating the Huffman code tree for the given set. There are two ways to combine nodes of equal frequency, such as when you combine 2 and 2. Combine them in a way that gives an obvious pattern to the Fibonacci sequence.)