COT 5407: Introduction to Algorithms -- Fall 07
Course Homepage

Professor: Giri Narasimhan

skala001cis.fiu.edu

• Dec 13 Your grades have been submitted via PantherSoft. I am extremely busy today. I do not wish to be disturbed.
• Dec 3 Exam #2 is scheduled for Thursday, Dec 6, from 3:30 PM to 6:15 PM in VH 131.
• Dec 3 THIS IS DIFFERENT FROM WHAT WAS ANNOUNCED EARLIER. Homework #5 and the programming assignment are due by 6:30 PM, Friday, Dec 7. I will accept late submissions until Saturday 5 PM. (You will lose 25% for submitting late.) Saturday deadline is a firm deadline after which no homework or programming assignments will be accepted. All extra credit problems have the same deadline of Friday, Dec 7.
• Nov 30 Special Class: We will meet tomorrow, Sat Dec 1, at 10AM in Room ECS 141. Bring all the questions you always wanted to ask me.
• Nov 19 Homework #5 is ready. See below.
• Nov 3 Office hours for the rest of the semester will be Tue 11-12 & Thu from 3:30-4:30 PM.
• Nov 1 Homework #4 and Programming assignment #1 are ready. See below.
• Nov 1 Email me if you have absolutely have to have the quiz graded by morning of Nov 2.
• Oct 24 Extra Credit Question Solve the following problem by Thursday, Oct 25, class time: [pdf]
• Oct 23 Office hours for this week: Wed (12-12:30PM; 4:30-5:30PM)
• Oct 17 Deadline for Homework #3 has been extended to Friday, Oct 19 at 6:30 PM. Please arrange for a print out of your submission to be dropped off at my office before the deadline.
• Oct 10 The first midterm is on Oct 16. The exam will be held in VH 131 and will be from 4:30 PM to 6:15 PM.
• Oct 9 Office hours for this week: Tu (11:30-12:30; 3-4:30 PM); Wed (9-10AM; 12-12:30PM; 4:30-6:30PM); Thu (11:30-12:30; 3-4:30 PM) please come only during office hours. Note that I will be out of town from this Friday through the following Wednesday.
• Sep 27 Office hours for this week and next: F (12-1PM; 4-5PM); M (11:30-12:30); Tu (11:30-12:30; 3-4:30 PM). If you have questions about the grading for HW 1, please come only during office hours.
• Sep 27 First Midterm Exam on October 16 in class.
• Sep 20 Homework 2 is ready. It is due on October 2.
• Sep 18 YET ANOTHER REMINDER: NO CLASS TODAY!
• Sep 4 There will be no class on September 18.
• Sep 4 For some lectures detailed notes will be available. Below you can find notes for Lecture 1.
• Sep 4 Under "Useful Links" below, I have provided a link to the website for your text. (Thanks to a diligent student in the class!) Do visit the website and read as much as you can.
• Sep 4 Your first homework is ready. It will be due on September 13. Read the guidelines for your homework. In particular, read the "cheating policy" very carefully.
• Aug 24 This is a difficult class. While planning for the semester, make sure you have enough time to spend on homework assignments!
• Aug 24 The class will meet in Room VH 131 (and NOT in ECS, as announced earlier).

• Homework 5: [pdf] -- Due Dec 4, 2007.
• Programming Assignment 1: [pdf] -- Due Dec 4, 2007; Data File: Data.txt;
  You may use the following test file of sum values to test your program: Test_p1.txt (Courtesy: Justin Schechter).
• Homework 4: [pdf] -- Due Nov 13, 2007.
• Homework 3: [pdf] -- Due Oct 18, 2007.
• Homework 2: [pdf] -- Due Oct 2, 2007.
• Homework 1: [pdf] -- Due Sep 13, 2007.
• Guidelines for Written Homework Assignments: [pdf] -- READ!!

• Aug 28: [pdf] [Introduction, Doubling Search, Horner Rule, Celebrity Problem]; Notes; Read Chapter 1;
• Aug 30: [pdf] [Celebrity Problem, Recurrence Relations]; Notes; Read Chapters 2, 3;
• Sep 4: [pdf] [Big-Oh Notation, Recurrence Relations]; Read Chapters 3, 4;
• Sep 6: [pdf] [Sorting, SelectionSort, InsertionSort, BubbleSort, MergeSort]; Read Chapter 4;
• Sep 11: [pdf] [SelectionSort, InsertionSort, BubbleSort, MergeSort]; Read Chapter 4;
• Sep 13: [pdf] [MergeSort, QuickSort]; Read Chapter 4, 7;
• Sep 18: NO CLASS
• Sep 20: [pdf] [HeapSort]; Read Chapter 6;
• Sep 25: [pdf] [Comparison-based algorithms; lower and upper bounds; bucket & radix sort; counting sort]; Read Chapter 8;
• Sep 27: [pdf] [k-Selection (k=1; k=n; k=1&N; k=1&2; k=N/2; k=arbitrary]; Read Chapter 9;
• Oct 2: [pdf] [Linear-time k-Selection; Evolution of Data Structures]; Read Chapter 9;
• Oct 4: [pdf] [Binary Search Trees]; Read Chapter 12;
• Oct 9: [pdf] [Red-Black Trees]; Read Chapter 13;
• Oct 21: [pdf] [Augmented Data Structures]; Read Chapter 14;
• Oct 23: [pdf] [Geedy Algorithms]; Read Chapter 16;
• Oct 28: [pdf] [Dynamic Programming]; Read Chapter 15;
• Nov 1: [pdf] [Dynamic Programming]; Read Chapter 15;
• Nov 6, 8: [pdf] [Graphs; DFS; BFS]; Read Chapter 22;
• Nov 13: [pdf] [DFS; BFS]; Read Chapter 22;
• Nov 15, 20: [pdf] [Minimum Spanning Trees; Dijkstra's Algorithms]; Read Chapter 23, 24;

• Aug 28: Chapters 1 & 2, CLRS text.
• Aug 30: Chapters 2 & 3, CLRS text.
• Sep 4: Chapters 3 & 4, CLRS text.
• Sep 6: Chapters 4, CLRS text.
• Sep 11: Chapters 4, CLRS text.
• Sep 13: Chapters 4 & 7, CLRS text.
• Sep 20: Chapters 6, CLRS text.
• Sep 25: Chapters 8, CLRS text.
• Sep 27: Chapters 9, CLRS text.
• Oct 2: Chapters 9, CLRS text.
• Oct 4: Chapters 12, CLRS text.

• Learn about Al-Khwarizmi click here
• Website for your text: click here
• Sorting animation website: click here

Standard Text

Other Useful Books

• Algorithms in C++ (Parts 1-4; Part 5), by Sedgewick
• Data Structures, Algorithms, and Applications in Java, by Sahni.
• 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).
• Algorithm Design, by Kleinberg and Tardos.
• 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, by Dasgupta, Papadimitriou, and Vazirani

• Sorting and Order Statistics
• Balanced Trees
• Augmented Data Structures
• Dynamic Programming & Greedy Algorithms
• Graphs & Graph Algorithms
• String Algorithms
• Geometric Algorithms
• NP-Completeness
• Lower Bound Arguments
• Experimental Algorithmics