CS 381: Detailed Syllabus

The course plans to follow the syllabus outlined below. Changes and adjustments may be made during the semester.

Mathematical Concepts for Algorithm Analysis

• General introduction to algorithm design (Ch. 2)
• Review of the analysis of sorting algorithms
• Review of  mathematical induction and other analysis tools
• Asymptotic notation and complexity classes (Ch. 3)
• Recurrences and the Master Theorem (Ch. 4)

Algorithm Design Techniques 

• Divide and Conquer (Ch. 9.3, 4.1)
• Problems include Skyline problem, Maximum subarray problem, Counting inversions, Selection in linear time
• Dynamic Programming (Ch. 15)
• Problems include Assembly-line scheduling, rof cutting, Matrix chain multiplication, Longest common subsequence, Sequence alignment, Knapsack
• Greedy  (Ch. 16)
• Problems include Activity selection, Fractional knapsack, Scheduling
• Randomized (Ch. 5, 7.3, 9.2)  and Streaming Algorithms 
• Selection in expected linear time 
• Online hiring problem

Using Data Structures in Algorithms 

• Review data structures including heaps as priority queues  (Ch. 10-12)
• Binary heaps (Ch. 6)
• Application: Prim’s algorithm (Ch. 23)
• Balanced Binary Search Trees (Ch. 13, 14.1-2) 
• Overview of balanced tree structures and Red-Black Trees
• Augmenting data structures
• Disjoint set union-find
• Union by rank and path compression techniques (Ch. 21)
• Introduction to amortized analysis (Ch. 17)    
• Kruskal’s algorithm (Ch. 23)  
• Fibonacchi Heaps
• 2-dimensional searching and range queries 

Graph Algorithms 

• Fundamental graph explorations (Ch. 22)
• Review of Breadth-first search, Depth-first search
• Topological sorting
• Graph connectivity  (Ch.22)
• Connected and bi-connected components
• Strongly connected components
• Shortest Paths (Ch. 24.1-3, 25.2)
• Bellman-Ford
• Dijkstra, Floyd-Warshall
• Maximum Flow (Ch. 26)
• Ford-Fulkerson method
• Relationship between max-flow and min-cut
• Applications of Max Flow

Lower bounds

• What are lower bounds?
• Comparison based sorting lower bound (Ch. 8.1)
• Radix sort and bucket sort  (Ch. 8.2, 8.3)    
• Problem reduction in lower bounds

Parallel Algorithms

• Embarrisingly parallel algorithms
• Parallel design techniques and paradigns

NP-completeness 

• Introduction to classes P and NP, NP-complete, polynomial time verification (Ch. 34.1-3)
• Reductions (Ch. 34.4)

Approximation Algorithms

• Vertex Cover, Set Cover, Traveling Salesman (Ch. 35.1-3)
• Fully polynomial time approximation scheme (Ch. 35.5)