COT 6405: Analysis of Algorithms -- Fall 19
Course Homepage
Office: ECS 254B; Phone: (305) 348-3748;
Class Schedule: MW 2:00 - 3:15 PM, CASE 235
Office Hours: By Appointment Only
e-mail: giri@cs.fiu.edu
ANNOUNCEMENTS
- Final Evaluation Scheme
- Exams: 15% + 5% (retake) + 25% = 45%
- Homework: 40%
- Quizzes: 10% (best 4 out of 5)
- Class Participation: 5%
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
- READ THIS FIRST: Updated on Sep 1: Homework Guidelines & Policies
- Homework #1 [Updated on Sep 1:pdf];
- Homework #2 [pdf];
- Homework #3 [pdf];
- Homework #4 [pdf];
Due by Tuesday, Oct 23, 11:59 PM
- Homework #5 [pdf];
Due by Sunday, Nov 17, 11:59 PM
- Homework #6 [pdf];
Due by Tuesday, Dec 3, 11:59 PM
LECTURES (pdf format)
- Aug 26: Lecture #1 - General Introduction
[pdf]
- Aug 28: Lecture #2 - Sorting, Invariants, Analysis, Big-Oh Notation
[pdf]
- Sep 02: LABOR DAY
- Sep 04: Lecture #3 - Recurrence Relations, Complexity
[pdf]
- Sep 09: Lecture #4 - Upper and Lower Bounds, k-Selection
[pdf]
- Sep 11: Lecture #5 - k-Selection, Augmented DS, Rank/Select
[pdf];
[pdf]
- Sep 16: Lecture #6 - Greedy Algorithms
[pdf]
- Sep 18: Lecture #7 - Dynamic Programming
[pdf]
- Sep 23: Lecture #8 - DP
[pdf]
- Sep 25: Lecture #9 - DP; Amortized Analysis
[pdf]
- Sep 30: Lecture #10 - Online Algorithms and Analysis
[pdf]
- Oct 02: Lecture #11 - Binary Heaps, Binomial Heaps
[pdf]
- Oct 07: Lecture #12 - Union-Find for Disjoint sets
[pdf]
- Oct 09: Lecture #13 - review
[pdf]; Lecture on DP based on text by Kleinberg and Tardos created by Kevin Wayne [DP]
- Oct 14: Lecture #14 - Visiting lecture by Yekun Xu on
probabilistic data structure called SkipLists;
Slides by Andres Medez-Vazquez (Oct 2015):
[SkipLists]
- Oct 16: Lecture #15 - Midterm Exam
- Oct 21: Lecture #16 - Graphs
[pdf]
- Oct 23: Lecture #17 - More Graphs ...
[pdf]
- Oct 28: Lecture #18 - Class Cancelled!
- Oct 30: Lecture #19 - More Graphs ...
[pdf]
- Nov 04: Lecture #20 - More Graphs ...
[pdf]
- Nov 06: Lecture #21 - More Graphs ... used slides from Lec 20 -- Dijkstra's algorithm;
- Nov 11: VETERAN'S DAY
- Nov 13: Lecture #22 - Graphs ... used slides from Lec 20; APSP -- Floyd-Warshall's algorithm
- Nov 18: Lecture #23 - Connectivity and Biconnectivity
[pdf]
- Nov 20: Lecture #24 - More on Biconnectivity (Lec 23 updated; see link above)
- Nov 25: Lecture #25 - Network Flow
[pdf]; Slides by Wayne based on Kleinberg and Tardos
[pdf]
[pdf]
- Nov 27: Lecture #26 - NP-Completeness
[pdf]
- Dec 02: Lecture #27 - More on NP-Completeness
(same lecture as in Lec 26)
- Dec 04: Lecture #28 - Final Exam Review
[Part 1];
[Part 2];
[Part 3];
- Dec 11: FINAL EXAM 12:00 PM -- 2:00 PM
USEFUL LINKS
TEXT:
Standard Text
"Introduction to Algorithms", (Third Edition) by Cormen, Leiserson, Rivest, Stein
[ISBN 0-262-03384-8] (MIT Press)
This book is published by both MIT Press and McGraw Hill Publishers with different ISBN numbers! Both versions have the exact same content. You may want to find a copy with a CD-ROM containing Java implementations of the algorithms from the book.
Other Useful Books
- Algorithm Design, Kleinberg and Tardos.
- Algorithms, Dasgupta, Papadimitriou and Vazirani.
- Introduction to Algorithms, Manber.
- Algorithms, 4th Edition, Sedgewick and Wayne.
- 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
- Asyptotics, Recurrence
- Divide-and-Conquer (Strassen, FFT)
- Advanced Data Structures
- Graphs & Graph Algorithms
- Network Flow
- Dynamic Programming
- Greedy Algorithms
- NP-Completeness
- Randomization
- Combinatorial Optimization
- Advanced Topics
OLD ANNOUNCEMENTS