Lecture Summaries  for COMP 251                   Winter 2012

      also check:  announcements      course outline       return to:  course home page

Text: Algorithm Design, J. Kleinberg and E. Tardos, Pearson 2006.
         Discussion group to be set up on  WebCT 
                       

Jan 9 : Introduction. The stable marriage problem. Read: Section 1.1 and this fun article. demo   slides
Exercises: P. 22, Ex. 2, P.23 Ex. 4
Jan 11: Review of basics of algorithm analysis. All of this was covered in COMP250. Read: Sections 2.1-2.4   slides
Exercises: P.67 Ex. 2,3
Jan 16, 18  Review of graph theory: undirected and directed graphs.Breadth first search and applications. Testing bipartiteness, connectivity, acyclic graphs and topological ordering. Read: Chapter 3. slides
Exercises: P. 107 Ex 4,  P. 110 Ex 10. For each problem give an non-trivial example that illustrates your algorithm
Assignment 1: All exercises from Jan 9,11,16,18  above, collected on January 23 in class. 

Jan 23: Greedy algorithms- I. Three scheduling problems solvable optimally by a greedy algorithm. Three types of proof techniques: stay ahead, exchange, structure. Read: Sections 4.1, 4.2  slides   (first 24 slides)
Exercises: P. 189 Ex. 3, P. 190 Ex 5. In both cases you should include a proof of correctness using one of the three techniques discussed.
Jan 25: Dijkstra's shortest path algorithm. Efficient implementation by heap. Read 4.4 and review pp.59-65  slides 34-40, demo heapsort
Exercise: P.198 Ex. 19.
Graded assignments will be handed back at the tutorials:
Tutorial 1A: 2pm Tues January 31, TR 3060     Wanru Lin
Tutorial 1B: 4pm Wed February 1, TR 3060     Bentley Oakes
Jan 30. Minimum spanning trees. Prim and Kruskal's algorithms. Read 4.5. slides      animation  animation
Exercise: P. 200 21,22
Feb 1: Solution to the bandwidth problem: P. 198 Ex. 19 (password: birds). Divide and conquer. Review of mergesort.Counting inversions.
Read: Sections 5.1-3. slides   (up to slide 20)
Exercise: P. 192, Ex. 9.  P. 246, Ex 2.
Assignment 2: All exercises from Jan 23, 25, 30 and Feb 1 collected on Feb 13 in class.
Feb 6: Three more problems solved by divide and conquer: closest pair, integer multiplication, matrix multiplication  slides   (Slides 21-47)
No exercise, but please read carefully the text Sections 5.4, 5.5 and review the slides.
Feb 8: Introduction to dynamic programming: weighted interval selection. Dijkstra fails with negative edge weights.
Read Sections 6.1,6.2  slides 1-16
No exercise.
Feb 13: Bellman-Ford shortest path algorithm. Negative weight cycles. Read Sections 6.8, 6.9. slides
Exercise: Ch 6, P. 314, Ex. 3.
Feb 15: We solved Ch 6 Ex. 17. solution. Segmented least squares. Knapsack AKA  sushi problem. Read: Sections 6.3,6.4,  slides
Tutorial 2A: 4pm Wed February 15, TR 3060     Wanru Lin
Tutorial 2B: 2pm Thurs February 16, TR 3060   Yam Chettri
Feb 27: Pseudopolynomial time vs polynomial time. RNA secondary structure. Sequence alignment. Read: Sections 6.5,6.6    slides  29-46
Exercises: (a) Compute the OPT(i,j) values (similar to those shown in Figure 6.16, p. 277) for the RNA sequence CACCGGUAGU
(b) Compute the OPT(i,j) values (similar to those shown in Figure 6.18, p. 284) for aligning the words "clean" and "lance". Show the shortest paths as a tree as in Figure 6.18.
Feb 29: Can computers think (part I). Computer game playing programs, min-max trees, alpha-beta search, Nim, computer chess.
Read:  Luc Devroye's notes
A documentary on the Kasparov-Deep Blue match is Endgame. A fascinating movie giving Kasparov's viewpoint is Game Over.
Mar 5: Review session. Please send suggestions in advance to avis@cs.mcgill.ca.
Mar 7: Midterm. All material and exercises above up to and including Feb 15.
Mar 12: Introduction to Network flows and Min Cut.  Ford-Fulkerson algorithm.  Read: pp. 337-341 first few slides
Exercises: Ch 7, Ex. 1,2, p 415
Mar 14: Ford-Fulkerson algorithm and optimality conditions using min-cut. Read: pp 341-350. Up to slide 25 of slides   and   demo
Exercises: Ch 7, Ex 3,4. For Ex.3 also try starting with a zero flow and run the Ford-Fulkerson algorithm to optimality and find the min cut.
Mar 19:  Applications to bipartite matching and network connectivity. Read sections 7.5,7.6  and first 21 slides  
Exercises: Ch 7, Ex 14, 15.
Mar 21: Circulations and lower bounds. Applications to survey design and census rounding. Read sections 7.7,7.8 and slides 22-32, 58-62.
Exercise: Ch 7, Ex 39
Mar 26: The complexity of the Ford-Fulkerson method. Exponential time example. Polynomial time algorithm via scaling. Read: Section 7.3
              slides (26-34). (Scaling for the approximate knapsack problem is in Section 11.8 but not covered on the final exam)
Exercise: Consider the network in Fig. 7.27, P. 416 and reset all flow values to zero. Now solve the max flow problem using the scaling approach using values of Delta=4,2,1. For each value of Delta show the maximum flow/min cut at the end of the outer loop of  the algorithm on pp. 353,354  (or slide 31)
Mar 28: Data structures for graph traversal: stack for DFS, queue for BFS, priority queue for Prim's algorithm. Introduction to Union-Find. Read 17.3,4,5 of Jeff Erickson's  notes.  He has lots of other useful materials here.
Exercise: Do Ex. 6 of the notes. Hint: try DFS on some small examples of directed graphs and see how to modify it.
Apr 2: Tree-structures for union find and path compression. slides  Read: Sections 16.1-3 of Jeff Erickson's notes. We also looked at problem 6.8, a space invaders variant.    problem.  solution 
Exercise: Do exercise 1 of Jeff Erickson's notes.
Final exam covers all material above (except Feb 29 and if otherwise noted)
Apr 4: Can computers think (part II).  The Turing test and Loebner prize. Read: Turing's historic 1950 paper. Try the Turing test yourself with the 2008 winner Elbot . Elbot seemed to be pretty lazy today, a transcript of the more interesting Tohoku 2010 test is here. I forgot which were Elbot's  answers but will try to reconstruct them and post them later.
Tutorial 4A: 4pm Wed April 4, TR 3060     Rami Aladdin
Tutorial 4B: 2pm Thurs April 5, TR 3060   Raphael Mannadiar
2012.4.5   Assignment 5: Exercises from lectures Mar 26, 28, Apr 2,4 collected on April 11 in class.  (April 9 is a holiday)
                A tutorial on this assignment will be given by Rami and Raphael, in class, April 16.
Apr 11: Mark Wilde's guest lecture on quantum computation
Apr 16: In class tutorial on Assignment 5. Any written material (midterms, assignments) that you did not pick up yet have will be available at this time.
Apr 30: Final exam at 2 pm. Good luck!  The announcements page has a Final Exam FAQ.