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 nbit numbers, multiplication as repeated addition. Running time analysis  recall of asymptotic notation, bigoh, theta, bigomega, and introduce littleoh and littleomega. 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).

NPcompleteness: reduction amongst problems, classes NP, P, NPcomplete, 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, McGrawHill 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.