CS 466/666 - Fall 2010 Design and Analysis of Algorithms Lectures

To help in motivation, the lectures are organized around problems instead of techniques. We usually devote more than a lecture to each problem and then explore different ideas to devise an efficient algorithm. Along the way, we will indeed encounter new design techniques and variations on the analysis model (themes like amortization, randomization, approximation, online computation, etc., as promised in the handbook description), but the main emphasis is how to think about problems.

Lecture Topics: (this list of specific problems is subject to change; though the techniques as given in the course outline will all be covered ... through at least one application)

Problem of Sept 14,16: Finding triangles in graphs and transitive closure
This topic gives the opportunity to review a number of basic algorithm design techniques/issues in the context of developing methods for determining the number of triangles in a graph. These include divide and conquer, NP-hardness and reductions..

• Triangle counting algorithms: brute-force (O(n³)), matrix multiplication (O(n^2.376)), edge-based (O(mn)), high-low trick (O(m^1.5) or O(m^1.41))
• Illustrates: the "algorithm development cycle", reduction to something you know, setting "tradeoff" parameters, open problems
• Transitive closure: standard methods, using fast Boolean matrix multiplication, reduction in the opposite direction
  
• References: CLRS sections 4.3, 22.3-5, 25.2, 28.2, 34.2, 34.3; Alon, Yuster, and Zwick (1994); Munro (1971). 

Problem of Sept 21, 23: Optimal binary search trees
This topic gives the opportunity to review dynamic programming, taking advantage of a "telescoping series" that improves runtime, (amazingly good) greedy approximation algorithms and amortized runtime.

• Recursive and dynamic programming solutions; reducing O(n³) solution to O(n²)
• Quality of solution in terms of entropy of the distribution
• Greedy approximation
• Amortized cost of range splitting
• References: CLRS sections 15.5, 16.1; Munro (2009); Bayer (1975); Mehlhorn (1977); Knuth (1971);

Problem of Sept 28, 30: Convex hull

• Algorithms: brute-force (O(n^3)), Graham's scan (O(n log n)), Jarvis' march (O(nh)), Timothy's (O(n log h))
• Illustrates: primitive operations, incremental algorithms, sweep algorithms, (anticipation of) amortized analysis, lower bounds, "output-sensitive" algorithms, guessing, ...
• Reference: CLRS sections 33.1, 33.3  Chan(1996), Chan pseudocode
  

Problem of Oct 5, 7, 12: Priority Queues

• Van Emde Boas layout and prioity queque
• Using balanced trees to include union as an operation
• Reference: CLRS chapter 19,  Wikipedia entry, Gudmond Notes, vEB et al, vEB space reduction class notes
  

Problem of Oct 14, 19: Union Find

• Approaches to the problem: list based union approach; tree based union by size; union by size with path compresssion
• Amortized runtime
• O(lg*n) amortized runtime bound for union by size with path compression
• References: CLRS chapters 17, 21 (note section 21.4 gives a harder bond than covered in class), Union Find notes

Problem of Oct 21, 26: Selection

• Finding second largest, finding maximum and minimum and general selection (median finding)
• Lower bounds on selection
• Probabilistic methods for selection
  
• References: CLRS chapters 5, 9, Selection notes, Matula 2nd Largest

Problem of Nov 2: Primality Testing

• Key elements of number theory helpful in primality testing
• Miller-Rabin probabilistic method
• References: CLRS sections 31.8

Problem of Nov 4, 9: NP-Completeness and SAT

• Review of Notions of P, NP, CoNP, NP complete
• Satifiability of Boolen expressions; outline of proof of Cook's Theorem
• NP Completeness of CNF 3SAT
• Linear algorithm for CNF 2SAT 
• References: CLRS Chapter 34, NP-Completeness Notes 

Problem of Nov 11, 16, 18, 23: Dealing with NP-Completeness: Approximation Algorithms

• Notions of approximation algorithms including (fully) polynominal approximations schemes
• 2 -approximation for vertex cover
• Inapproximabilty of travellingsalesman problem without triangle inequality
• 2 and 1.5-approximation methods (hence minimum spanning tree and minimum weight matching) for travelling salesman problem with triangle inquality
• Fully polynomial approximation schemce for subset sum
• References: CLRS Chapters 34 amd 35, Dealing with NPC
  

Problem of Nov 25: Online Algorithms

• Online Algorithms 
• Selforgaizing linear search: Move to Front, Transposition, Offline optimal
• Competitive ratio, issues with models
• References: CLRS Problem 17-5, Online algorithms
  

Problem of Nov 30, Dec 2: More dealing with NP-Hardness

• Randomization and derandomization
• Parameterized complexity
• References: CLRS section 35.4, More coping with NP-Hardness