Course Introduction

Introduction to basic data structures

Complexity Analysis:
1. Model of computation
2. Worst-case and average-case analysis
3. Big-O Notation

Complexity Analysis:
4. Running time calculation
5. Iteration and Integration
6. Recursion and recurrence equations

To demonstrate how divide-and-conquer is used to solve problems, and how to analyze the time and stack complexity of recursive programs:
1. Mergesort, Quicksort, divide and conquer, and recursion
2. Developing recurrence equations for recursive programs

To demonstrate how divide-and-conquer is used to solve problems, and how to analyze the time and stack complexity of recursive programs:
3. Techniques for solving recurrence equations
4. Divide-and-conquer for computational geometry

To demonstrate how incremental insertion is used to solve problems, and counting techniques for analyzing incremental insertion.
1. Introduction Incremental Insertion
2. Incremental insertion for sorting and computational geometry
3. Counting techniques for analyzing increment insertion

To demonstrate how to prove nontrivial lower bounds for comparison sort and geometric problems.
1. Decision tree and lower bound for comparison sort
2. Countsort and Radixsort

Midterm Exam

Greedy algorithms, amortized analysis :
1. Greedy algorithms vs Dynamic Programming
2. Greedy Choice Property
3. Activity selection
4. Hoffman code

Greedy algorithms, amortized analysis :
5. Knapsack problem
6. Task scheduling
7. Greedy used as a heuristic for finding “good” solutions

Graph Search and Connectivity :
1. Representations and Basics of Graphs
2. Graph search: DFS, BFS, and PFS
3. DFS and Topological Sort
4. DFS for computing strongly connected components
5. DFS for computing biconnected components, bipartite matching

Minimum Spanning Trees:
1. Greedy Choice Theorem
2. Kruskal’s Algorithm
3. Data structures for disjoint sets
4. Prim’s Algorithm

Single-Source shortest paths :
i. Single-source shortest paths in weighted graphs
ii. Shortest-Path Problems
iii. Properties of Shortest Paths, Relaxation
iv. Dijkstra’s Algorithm
v. Bellman-Ford Algorithm
vi. Shortest-Paths in DAGs

All-Pair Shortest Paths
i. Recursive formulation of all-pairs shortest paths
ii. Shortest paths and matrix multiplication
iii. Floyd-Warshall Algorithm
Johnson’s Algorithm for Sparse Graphs

P, NP, and NP-Complete :
1. Class P and NP
2. NP algorithms

P, NP, and NP-Complete :
3. NP-Complete
4. Approximation Algorithms

Final Exam