EECS 3101 E: Design and Analysis of Algorithms

## Lecture Schedule ( Fall 2019):

• Lectures: 4:00 - 5:30 pm, Mondays and Wednesdays at LSB 103
• Tutorials: 4:00 - 5:30 pm, Thursdays at LSB 103
• Instructor: Andy Mirzaian

## Course Description:

This course is intended to teach students the fundamental techniques in the design of algorithms and the analysis of their computational complexity. Each of these techniques is applied to a number of widely used and practical problems. At the end of this course a student will be able to: choose algorithms appropriate for many common computational problems; to exploit constraints and structure to design efficient algorithms; and to select appropriate tradeoffs for speed and space. Topics covered may include the following:

• Review: Mathematical Induction, asymptotic notation.
• Analysis techniques: summations and recurrence relations.
• Lower Bound Techniques: (Algebraic) Decision Trees, Adversary Arguments, Problem Reduction (or Transformation).
• Correctness proofs via assertions, pre and post conditions, loop invariants, (weak & strong) induction on these assertions.
• Sorting and order statistics: Heapsort and Priority Queues, Randomised QuickSort and its expected case analysis, Special Purpose Sorting Algorithms, Linear-Time Selection.
• Prune-&-Search: Binary Search, Linear Time Selection Algorithm.
• Incremental methods: VLSI Cheap Testing, In-Place Tri-Partition, Maximum Sum Subarray, Longest Smooth Subarray.
• Divide-and-conquer: MergeSort, Recursive Doubling, Euclid's (extended) GCD algorithm (and its applications in number theory and encryption techniques), arithmetic with large numbers and matrices, Closest Pair of Points in 2D.
• Greedy methods: Coin Change Making, Activity Selection (or Event Scheduling), Point-Interval Cover Problems, some graph algorithms.
• Dynamic Programming: Matrix Chain Product, Optimal Static Binary Search Trees, Scheduling, Knapsack Problems, Longest Common Subsequence, some graph algorithms.
• Graph algorithms: Depth First Search, Breadth First Search, Biconnectivity and Strong Connectivity, Topological Sort, Minimum Spanning Trees, Shortest Paths, Network Flow, Matching.
• Theory of NP-completeness. 