Basic Information

About this course

This course is an introductory course on the design and analysis of algorithms. The emphasis is on understanding some basic design techniques that can be applied in a variety of algorithmic questions. While this cannot be considered exhaustive, the students, once they finish this course, will have sufficient background to think in a systematic and rigorous about algorithm design when the face newer situations.

Prerequisites:

The course on programming and data structures (CS2700/CS2705) and the course on Discrete Mathematics (CS1200) are pre-requisites for this course. In particular the following topics are assumed in this course:

• Discrete mathematics: High-school algebra, logarithm identities, naive set theory, Boolean algebra, first-order predicate logic, sets, functions, equivalences, partial orders, modular arithmetic, recursive definitions, trees (as abstract objects, not data structures), graphs (vertices and edges).
• Proof techniques: direct, indirect, contradiction, exhaustive case analysis, and induction (especially “strong” and “structural” induction).
• Iterative programming concepts: variables, conditionals, loops, records, indirection (possibly addresses/pointers/references), subroutines, recursion.
• Fundamental abstract data types: sequences, vectors, sets, stacks, queues, priority queues.
• Fundamental data structures: arrays, linked lists (single and double, linear and circular), binary search trees, hash tables, heaps.
• Fundamental computational problems: elementary arithmetic, sorting, searching, enumeration, tree traversal (preorder, inorder, postorder, level-order, and so on).
• Fundamental algorithms: elementary algorithm, sequential search, binary search, sorting (selection, insertion, merge, heap, quick, radix, and so on), breadth-first and depth-first search in (at least binary) trees, and most importantly, the difference between this list and the previous list.
• Elementary algorithm analysis: Asymptotic notation, translating loops into sums and recursive calls into recurrences, evaluating simple sums and recurrences.

Learning Outcomes

The course will require you to design algorithms, and then mathematically prove their correctness. There will not be any programming component for this course. You will be required to implement a few of the algorithms if you take the lab course Object-Oriented Analysis, Implementation and Algorithms (OOAIA, CS2810).

Course contents

The course will look at some basic algorithm design techniques using examples. The contents of the course include the following topics:

• Recursion & Divide-and-conquer Strategy
• Incremental & Decemental Strategy
• Greedy Algorithm Strategy
• Dynamic Programming Strategy
• Limitations and Intractability

As a part of the analysis techniques, we will see data structures, amortization. The officially approved syllabus for the CS2800 course is as follows, where exactly the above set of topics are distributed in a different way. The above remodularizing is just the way the instructor prefers to teach the same set of topics given in the official 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)