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 various sorting algorithms
• Review of  induction and other tools
• Asymptotic notation (Ch. 3)
• Recurrences and the Master Theorem (Ch. 4)

Algorithm Design Techniques 

• Divide and Conquer (Ch. 9.3, 33.4)
• Selection in worst-case linear time
• Finding the closest pair in a set of points
• Dynamic Programming (Ch. 15)
• Assembly-line scheduling
• Matrix chain multiplication
• Longest common subsequence
• Knapsack
• Greedy (Ch. 16)
• Activity selection
• Fractional knapsack
• Scheduling
• Randomized (Ch. 5, 7.3, 9.2)  and Streaming Algorithms 
• Selection in expected linear time
• Online hiring problem
• Examples of one- and two-pass streaming algorithms
  

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
• 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)
• 2-dimensional searching and range queries 
  

More Graph Algorithms 

• Fundamental graph explorations (Ch. 22)
• 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
• Other graph algorithms

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 P and NP (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)