EECS 3101: Tentative
SYLLABUS
I: INTRODUCTION and RELEVANT MATHEMATICS (6 hours):
- Lecture Slides 1, 2, 3 and Lecture Notes 1, 2, 3.
- General course description
- Overview of algorithmic design and analysis
- Mathematical induction
- Asymptotic notations and their properties
- Time complexity analysis of algorithms
- Summations and Recurrence Relations
II: ITERATION and RECURSION (5 hours):
- Lecture Slide 4 and Lecture Note 4.
- Assertions: Pre and Post Conditions
- Iterative Algorithms: Loop invariants
- VLSI Chip Testing
- In-Place Tri-Partition
- Maximum Sum Subarray
- Longest Smooth Subarray
- Recursive Algorithms: Strong Induction
- The Divide-&-Conquer Method
- Recursive Doubling
- Operations on integers and matrices
- Algorithms for trees
- The Planar Closest Pair of Points Problem
III: SORTING and SELECTION (6 hours):
- Lecture Slide 5 and Lecture Notes 5, 6.
- Review basic sorting algorithms
- Randomized QuickSort and its expected running
time
- Heaps, HeapSort and Priority Queues
- Lower bound on general sorting
- Special sorting algorithms: CountingSort, BucketSort,
RadixSort, RadixExchangeSort
- Selecting the k-th smallest item
- The Prune-&-Search Method
- Lower Bound Proof Techniques for Problem Time Complexity:
- (Algebraic) Decision Trees,
- Adversary Arguments,
- Problem Reduction (or Transformation).
IV: ALGORITHM DESIGN TECHNIQUES (8 hours):
- Lecture Slides 6, 7 and Lecture Notes 7, 8, 9.
- Review: Incremental, Divide-&-Conquer, Prune-&-Search,
...
- Greedy Methods
- Dynamic Programming
V: GRAPH ALGORITHMS (12 hours):
- Lecture Slide 8 and Lecture Note 10.
- Review definitions and graph terminology
- Breadth-First-Search (BFS)
- Depth-First-Search (DFS)
- Dags and Topological Sorting
- Strongly Connected Components
- Biconnected Components
- Minimum Spanning Trees
- Shortest Paths
- Network Flow
- Matching
VI: NP-COMPLETENESS (3 hours):