Course Objectives
The objective of the course is to teach techniques for effective problem solving in computing. The use of different paradigms of problem solving will be used to illustrate clever and efficient ways to solve a given problem. In each case emphasis will be placed on rigorously proving correctness of the algorithm. In addition, the analysis of the algorithm will be used to show the efficiency of the algorithm over the naive techniques.
Syllabus
- Introduction: Problem solving -- adding 2 n-bit numbers, multiplication as repeated addition. Running time analysis -- recall of asymptotic notation, big-oh, theta, big-omega, and introduce little-oh and little-omega. Worst case and average case complexity (3 lectures + 1 tutorial).
- Basic paradigms with illustrative examples -- incremental design (e.g., incremental sorting, interpolating polynomials), decremental design (e.g., GCD with discussion on input size, factorial), and pruning (e.g., order statistics).
Divide and Conquer: Integer multiplication revisited with an efficient algorithm that motivates and leads into recurrences. Solving recurrences using recurrence trees, repeated substitution, statement of master theorem. Brief recall of merge sort and its recurrence. Median in worst case linear time. (7+2)
-
Application of Graph Traversal Techniques: Recall representation of graphs, BFS (as a method for SSSP on unweighted graphs), DFS, connected components, topological sorting of DAGs, biconnected components, and strongly connected components in directed graphs. (4+1)
-
Greedy Algorithms: Greedy choice, optimal substructure property, minimum spanning trees -- Prims and Kruskals, Dijkstra’s shortest path using arrays and heaps, fractional knapsack, and Huffman coding (use of priority queue). (9+3)
Dynamic Programming: Integral knapsack (contrasted with the fractional variant), longest increasing subsequence, edit distance, matrix chain multiplication, and independent sets in trees. (The instructor may choose a subset that fits within the time frame.) (6+2)
-
String Matching: Boyer Moore algorithm. (3).
-
NP-completeness: reduction amongst problems, classes NP, P, NP-complete, and polynomial time reductions (3+1)
Textbooks
- Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein, MIT Press, Third Edition, 2009.
References
- Algorithms, by Dasgupta, Papadimitrou and Vazirani, McGraw-Hill Education, 2006.
- Computer Algorithms, by Horowitz, Sahni, and Rajasekaran, Silicon Press, 2007.
-
Algorithm Design, by Kleinberg and Tardos, Pearson, 2005.
-
Algorithm Design, by Goodrich and Tamassia, Wiley, 2001.
