CSc 72700: Analysis of Algorithms
Gradute Center, City University of New York
Fall 2001

Announcements:

• Information about the final exam.
• In Homework 8, there was a typo on the last graded problem. As stated in the ungraded problems, LFU is not competitive and the subject of the graded problem (instead of LRU).
• Lecture on Tuesday, 11 December will begin with a quick review of the topics covered this term and questions about the final. The second half of class will be on an application that uses several concepts discussed in lecture, chosen from the following:
  • Euclid's Algorithm
  • RSA Encryption
  • Graham's Scan (computational geometry)
  While the topic itself will not appear on the final, the concepts it embodies will appear. More information about each is found in the topics section of the book. The topic covered will be up to a vote of the class.
• Upcoming Office Hours:
  • Tuesday, 11 December, after class.
  • Friday, 14 December, 3-4pm.
• We have a new lecture room!!!
  Thanks to Joe, we have been assigned the room, 6495, next door to our old room. It's larger and better set up for lectures. We will meet there for the rest of the semester.
• If submitting your homework electronically, you can send it directly to the grader at: ivm3@columbia.edu.
  For the programming part of assignments, send the source code separately from the rest of the assignment, in plain text with a comment on what platform it was built (windows or unix/linux). That way, Igor can compile and run your program without re-typing!
• This course assumes that you have completed an undergraduate algorithms course. See suggested guidelines for more details.

Handouts:

• Syllabus
• Outline
• Guidelines for Submitting Homework
• Homework 1 (due date: Wednesday, 5 September): postscript, pdf, latex
• Homework 2 (due date postponed to Friday, 28 September): postscript, pdf, latex
• For lecture on 2 October:
  
  • Notes on red-black trees by Prof. Cartwright from Rice University.
• Homework 3 (due date postponed to Wednesday, 10 October): postscript, pdf, latex
• For lecture on 16 October:
  
  • Notes on B-trees by Prof. Gurari from Ohio State University.
• Homework 4 (due date postponed to Wednesday, 17 October): postscript, pdf, latex
  Useful links for the homework:
  • Notes on AVL trees by Prof. Morris from University of Western Australia.
  • AVL tree applet
• Information about the midterm exam.
• For lecture on 30 October:
  
  • Dynamic Programming for sequence alignment:
    • Basic Algorithm by Prof. Pers Kraulis, Stockholm Bioinformatics Center.
    • Dynamic Programming Tutorial by Eric Rouchka, Washington University, St. Louis.
    • Advanced Dynamic Programming Tutorial by Eric Rouchka, Washington University, St. Louis.
  • Graph Theory Review by Prof. Jeremy Siek, University of Notre Dame.
• Homework 5 (due date postponed to Wednesday, 7 November): postscript, pdf, latex
  
• For lecture on 6 November:
  
  • Huffman Codes:
    • Overview of Huffman codes by Professor Michael Mascagni, Florida State University.
    • Huffman code applet by Tony Xinging Yin.
• For lecture on 13 November:
  
  • Minimum Spanning Trees:
    • Kruskal's Algorithm Applet by Prof. Arvo, CalTech.
    • Prim's Algorithm Applet by Papagelis Athanasios, U. Patras, Greece.
  • Shortest Paths:
    • Dijkstra's Algorithm Applet by Prof. Freeman at UC Irvine.
  • Maximum Flow:
    • Overview of Network Flow, Class Group Project, U. Saskatchewan.
    • Maximum Flow Algorithms Applet by Prof. Hochbaum and Dr. Goldschmidt, UC Berkeley.
• For lecture on 27 November:
  
  • Prof. Lenore Cowen's first lecture on approximation algorithms, Johns Hopkins University.
• Homework 6 (due date postponed to Wednesday, 28 November): postscript, pdf, latex
  
• For lecture on 4 December:
  
  • Notes for lecture.
  • Dr. Rabini's notes notes for an advanced topics course at the Technion, lecture 2.
  • Dr. Suzanne Albers' lecture series notes on on-line algorithms, Center for Basic Research in Computer Science (BRICS), Universities of Aarhus and Aalborg, Denmark.
• Homework 7 (due date: Wednesday, 5 December): postscript, pdf, latex
  
• Homework 8 (due date: Wednesday, 12 December): postscript, pdf, latex
  

Useful Links:

• The book's home page at MIT Press and at McGraw Hill.