COT 6405: Analysis of Algorithms -- Spring 04
Course Homepage
Office: ECS 389; Phone: (305) 348-3748;
Office Hours: Tue & Thu, 12-1PM
e-mail: giri@cs.fiu.edu
ANNOUNCEMENTS
- Apr 18: Homeworks 2 & 3 have been graded and can be picked
up from outside my door after 1:00 PM on Sunday Apr 18.
- Apr 18: Take Home Final Exams can be mailed to you upon
request any time between Apr 19 (Monday) 11:59PM and Apr 22
(Thursday) 7:00 AM to be returned exactly 24 hours later (by email).
Send me an email request stating what time you want it sent to you.
- Apr 18: A social event for the class is being planned either
for Friday Apr 23 or Sunday Apr 25. I hope you will plan to attend.
- Apr 06: Visit the Course Evaluation Website
to evaluate your courses.
- Apr 06: Homework #5 is ready. See below.
- Mar 30: Homework #4 is ready. See below.
- Mar 11: Homework #3 is ready. See below.
- Feb 24: Patricia Buendia has volunteered to be a teaching
assistant and is willing to answer questions by
email. Her email address is pbuen001@fiu.edu
- Feb 13: Midterm exam is set for Feb 24.
- Feb 10: For project information, see below.
- Feb 04: Homework #2 is ready. See below.
- Jan 18: Homework #1, Sample Solutions, and Homework
Guidelines/Policies are ready. See below.
- Jan 12:
Visit this web page regularly for announcements. New ones will be
marked as
until
newer ones arrive. Answers to select "Frequently Asked Questions" (FAQs) about your
assignments can be found by clicking here: FAQs.
Read the section below on expected "PREREQUISITE KNOWLEDGE".
HANDOUTS AND HOMEWORK ASSIGNMENTS
One must learn by doing the
thing; for though you think you know it, you have no certainty until
you try. Sophocles
LECTURES (pdf format)
- Jan 5: Introductory lecture By Dr. Smith [Matrix Chain Mutliplication &
Dynamic Programming]
- Jan 8: Lecture #1 [pdf]
[Introduction, Doubling Search, Horner's Rule, Celebrity Problem]
- Jan 13 & 15: Lecture #2 & #3 [pdf]
[Data Structures, Recurrences, Invariants, Sorting]
- Jan 20: Lecture #4 [pdf]
[QuickSort, ShellSort, BucketSort, RadixSort]
- Jan 22: Lecture #5 [pdf]
[LowerBounds]
- Jan 27: Lecture #6 [pdf]
[Selection, Binary Search Trees]
- Jan 29: Lecture #7 [pdf]
[RB-Trees]
- Feb 03: Lecture #8 [pdf]
[Augmented RB-Trees]
- Feb 05: Lecture #9 [pdf]
[Augmented RB-Trees, Interval Trees]
- Feb 10: Lecture #10 [pdf]
[Greedy Algorithms]
- Feb 12: Lecture #11 [pdf]
[Dynamic Programming]
- Feb 17: Lecture #12 [pdf]
[Dynamic Programming]
- Feb 24: Midterm Exam
- Feb 26: Lecture #14 [pdf]
[Dynamic Programming]
- Feb 26: Lecture #14 [pdf]
[Dynamic Programming]
- Mar 02: Lecture #15 [pdf]
[Graphs]
- Mar 04: Lecture #16 [Same as Lecture 15] [Graphs]
- Mar 09: Lecture #17 [Same as Lecture 15] [Graphs]
- Mar 11: Lecture #18 [pdf]
[More on Graphs]
- Mar 16: Lecture #19 [Same as Lecture 18] [Graphs]
- Apr 06: Lecture #22 [pdf]
[Amortized Analysis, NP-Completeness]
USEFUL LINKS
TEXT:
Standard Text
"Introduction to Algorithms", (Second Edition) by Cormen, Leiserson, Rivest, Stein
[ISBN 0-07-013151-1]
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
OLD ANNOUNCEMENTS
