CompSci 260 - Fundamentals of the Design and Analysis of Algorithms

CompSci 260 - Fundamentals of the Design and Analysis of Algorithms - Winter, 2020 (Dillencourt)

Midterm 2 topics. The midterm will focus on the following material:

Chapters 4, 5, and 6 in the text.
Class note 4, 5, and 6.

The second midterm is intended to focus on material not covered on the first midterm and is not deliberately cumulative. But there could be some overlap. For example: there will not be questions focusing exclusively on your knowledge of asymptotic analysis as there were on the first midterm. Nevertheless, it would be perfectly reasonable to ask you to give the asymptotic worst-case running time of an algorithm in the context of dynamic programming or one of the other topics on which this midterm focuses.

You should be prepared to be demonstrate knowledge of and be asked about the following topics.

Greedy Algorithms
- Scheduling Problems: Scheduling a maximum number of intervals on a single processor, scheduling all intervals using a minimum number of processor, scheduling jobs to minimize the maximum lateness.
- Shortest paths in weighted graphs. Dijkstra's algorithm.
- Minimum spanning trees: Prim's algorithm, Kruskal's algorithm. (As part of Kruskal's algorithm, you should know the mechanics of Union-Find with size balancing and path compression.)
- Huffman coding: prefix codes, Huffman trees, how to determine the code of each symbol from the tree.
- Minimum cost arborescence: definition of an arborescence, the algorithm for constructing a minimum-cost arborescence.
Divide and conquer
- The basic divide and conquer recurrence equation.
- The simplified method and the master method
- Examples discussed in class: constructing a binary heap, planar closest-pair problem, integer multiplication, discrete Fast Fourier Transform, Strassen's method for multiplying matrices
Dynamic Programming
- Recursion vs. Memoized recursion vs. Dynamic programming
- Memoization tables and expressing a dynamic programming solution as described in the notes
- Specific instances of dynamic programming algorithms:
  - Weighted interval scheduling
  - Segmented least-squares problem
  - Truck loading problem (also known as Subset-Sum Problem)
  - (Zero-One) Knapsack problem (you should also know the greedy method for solving the fractional knapsack problem)
  - Optimal sequence alignment
  - Bellman-Ford shortest-path algorithm
  - All-pairs shortest path problem (Floyd's algorithm)
  - Optimal matrix chain multiplication

Some sample generic questions. This is not an exhaustive list.

Given an instance of maximum number of intervals on a single processor (a collection of jobs with specified start and finishing times), list the jobs in the order in which they would be processed and give an optimal set of intervals.
Questions analogous to the previous sample question for scheduling all intervals using a minimum number of processors or scheduling to minimize the maximum lateness.
For a given weighted graph (directed or undirected) and source vertex, run Dijkstra's algorithm. Draw the resulting tree. State the distance from the source vertex to each vertex in tree. List the vertices in the order in which they are added to the tree. List the tree edges in the order in which they are added to the tree.
For a given weighted undirected graph and start vertex, run Prim's algorithm. Draw the resulting tree. List the vertices in the order in which they are added to the tree. List the tree edges in the order in which they are added to the tree.
For a given weighted undirected graph, run Kruskal's's algorithm. Draw the resulting tree. List the tree edges in the order in which they are added to the tree. List the graph edges in the order in which they are considered and indicate which ones are added to the tree. Draw the corresponding union-find structure as it would look immediately [before/after] a specified edge is considered for addition to the tree.
For a given collection of symbols and frequencies, draw the Huffman tree. Give an optimal set of prefix codes consistent with the tree you just drew. Compute the weighted average symbol length for this encoding.
For a given weighted directed graph and root vertex, compute a minimum cost arborescence using the algorithm described in class and in the text.
Consider [a given problem and a proposed greedy algorithm for solving the problem.] Does the proposed algorithm always correctly solve the problem? (YES/NO). If NO, given a specific example where it fails.
Solve a given divide-and-conquer recurrence relation. (Note: if either the simplified method or the master method can be applied, it is fine to use either one.)
Set up and solve a divide-and-conquer recurrence equation to analyze a given algorithm.
Give an algorithm that uses a divide-and-conquer approach to solve a given problem. Analyze your algorithm by setting up and solving the appropriate divide-and-conquer recurrence equation.
Suppose we were to take [one of the divide-and-conquer algorithms discussed in class] and modify it [in a manner to be described]. Analyze the modified algorithm by setting up and solving the appropriate divide-and-conquer recurrence equation.
Consider [a given problem]. Describe a dynamic programming solution to the problem, expressing your solution as described in the notes. (Note: if I give such a problem, I will provide a space for each of the five components of the solution together with a brief prompt for each component. I might also give you a specific instance of the problem and ask you to construct the memoization table that your solution would construct for that instance.)
Consider [a specific instance] of [one of the dynamic programming problems we discussed in class.] Fill in the memoization table (it might be blank or it might be partially filled in). Based on the filled-in memoization table, give the solution to the problem.

Last modified: March 2, 2020