COT 6405: Analysis of Algorithms -- Spring 02
Course Homepage

• Apr 23: Final Exam is at 3:30 PM on April 25, Room PC213. Please note the special time!!!! This is as per the university's scheduled time.
• Apr 23: Homework #4 has been graded and you can pick it up from my office.
• Apr 18: Homework #5 is now available. See below.
• Mar 25: Note that a minor correction was made to homework #4. Corrected version has now replaced the old version.
• Mar 24: Homework #4 is now available. See below.
• Mar 13: No office hours for tomorrow (Thursday) afternoon. If you have questions please see me before 11:30 AM.
• Mar 12: For the review session today, I hope to discuss the following problems in class today: Problems 9-1 (pg 194), 14.1-7 (pg 308), 15-1 (pg 364). Think about them before coming to class.
• Mar 10: MidTerm #1 is now re-scheduled for March 14, during class time.
• Feb 11: Here you will find answers to select "Frequently Asked Questions" (FAQs) about your assignments: FAQs.
• Feb 6: Read the "Homework Submission Guidelines and Policies" again to remind yourself about how to work on your homework. Very Important!

HANDOUTS AND HOMEWORK ASSIGNMENTS

• Homework #5; Due Apr 18 in my office before class
• Homework #4; Due Apr 4 in my office before class
• Homework #3; Due Mar 7 in my office before class
• Homework #2; Due Feb 14 in class
• Homework #1; Due Feb 5 in class
• Homework Submission Guidelines and Policies: Read This! It is important
• Review Homework; Not For Submission

• Jan 15: Lecture #2 [pdf format]
• Jan 24: Lecture #5 [pdf format]

• Algorithm Animation Website

TEXT:

Other Useful Books

• Computer Algorithms S. Baase and A. van Gelder, 3rd Edition, Addison Wesley, 2000. ISBN: 0-201-61244-5.
• Computers and Intractability: A Guide to the Theory of NP-Completeness, by M. Garey and D.S. Johnson, 1979 (Publishers: W. H Freeman and Company).
• Approximation Algorithms for NP-hard Problems, by Dorit Hochbaum, PWS Publishing Co., 1997.
• Computational Geometry, by de Berg, van Kreveld, Overmars, Schwazkopf
• Randomized Algorithms, by Motwani and Raghavan
• Algorithm on Strings, Trees, and Sequences, by Gusfield
• Handbook of Discrete and Computational Geometry, by Goodman and O'Rourke
• Combinatorial Optimization, by Papadimitriou and Steiglitz
• Algorithms in C++ (Parts 1-4; Part 5), by Sedgewick
• Data Structures, Algorithms, and Applications in Java, by Sahni.

PREREQUISITE KNOWLEDGE EXPECTED (From Text)

• Chapter 1, 2, 3, 4, 5, 10, 11, 12, 22
• Appendices A, B, C.

SYLLABUS

• Sorting and Order Statistics
• Augmented Data Structures
• Dynamic Programming & Greedy Algorithms
• Amortized Analysis
• Graphs & Graph Algorithms
• String Matching
• Geometric Algorithms
• Linear Programming
• NP-Completeness
• Approximation Algorithms
• Randomized & On-line Algorithms
• Lower Bound Arguments
• Experimental Algorithmics

• Feb 22: MidTerm #1 is scheduled for March 7, during class time. (Now rescheduled)
• Feb 22: Homework #3 is now available. See below.
• Feb 6: Homework #2 is now available. See below.
• Jan 25: Homework #1 is now available. See below.
• Jan 25: Read the "Homework Submission Guidelines and Policies" before you start on homework #1. Very Important!
• Jan 21: Check out the Algorithm Animation websites. See below.
• Lecture Transparencies for Jan 15 are now available. See below.