COT 5405, Analysis of Algorithms, Spring 2008

Place:NEB 102
Time:Tuesday 4 (10:40-11:30 p.m.) and Thursday 4,5 (10:40-12:35 p.m.)

Instructor:
Prof. Arunava Banerjee
Office: CSE E336.
E-mail: arunava@cise.ufl.edu.
Phone: 392-1476.
Office hours: Wednesday 2:00 p.m.-4:00 p.m. or by appointment.

TA:
Ravindranath Jampani
Office hours: M 7,8

TA:
Arsalan Bekir
Office hours: Th 8,9

TA:
Ferhat Ay
Office hours: Tu 8,9

TA:
Parbati Kumar Manna
Office hours: F 7,8

Common TA E-mail: cot5405sp08@cise.ufl.edu . You may not correspond with any TA using his personal email id.

Visit the announcement page at least once EVERY DAY for time sensitive announcements.

Pre-requisites:

  1. COP 3530, Data Structures and Algorithms: Arrays, Linked lists, Stacks, Queues, Binary tree and Search trees.
  2. COT 3100, Applied Discrete Structures: Proof by induction and contradiction, Graphs, Trees, Permutations, Combinations, Counting and Probability.
Textbook: Introduction to Algorithms, 2nd Edition, Cormen, Leiserson, Rivest and Stein, McGraw-Hill, ISBN 0-07-013151-1.

Tentative list of Topics to be covered

  • Growth Functions: Asymptotic Notation (Big-Oh, Big-Omega, Theta, Small-oh, Small-omega).
  • Best, Worst, and Average case analysis of time complexity of algorithms; Recurrence relations.
  • Sorting: Quick-Sort, Merge-Sort.
  • Order Statistics: Selection in worst case linear time.
  • Priority Queues: Heaps
  • Amortized analysis
  • Graph Algorithms: DFS, BFS, Strongly connected components, Single source shortest path (Dijkstra), All pairs shortest path (Floyd-Warshall), Minimum spanning tree (Prim, Kruskal).
  • String matching, String editing.
  • NP-Completeness.

The above list is tentative at this juncture and the set of topics we end up covering might change due to class interest and/or time constraints.

Evaluation:

  • ~5 homework assignments: 30%
  • One midterm exam: 30% (2 hrs, in-class)
  • Final exam: 40% (comprehensive)
  • There will be no makeup exams (Exceptions shall be made for those that present appropriate letters from the Dean of Students Office).
The final grade will be on the curve.

Course Policies:

  • Late assignments: All homework assignments are due before class. No late submissions will be accepted as solutions shall be handed out during class or be posted on this web-site.
  • Plagiarism: You are expected to submit your own solutions to the assignments. Please keep in mind while discussing problems with friends and colleagues that such activity can potentially result in very similar answers being handed in and leave you open to the charge of plagiarism.
  • Attendance: Their is no official attendance requirement. If you find better use of the time spent sitting thru lectures, please feel free to devote such to any occupation of your liking. However, keep in mind that it is your responsibility to stay abreast of the material presented in class.
  • Cell Phones: Absolutely no phone calls during class. Please turn off the ringer on your cell phone before coming to class.

Academic Dishonesty: See http://www.dso.ufl.edu/judicial/academic.php for Academic Honesty Guidelines. All academic dishonesty cases will be handled through the University of Florida Honor Court procedures as documented by the office of Student Services, P202 Peabody Hall. You may contact them at 392-1261 for a "Student Judicial Process: Guide for Students" pamphlet.

Students with Disabilities: Students requesting classroom accommodation must first register with the Dean of Students Office. The Dean of Students Office will provide documentation to the student who must then provide this documentation to the Instructor when requesting accommodation.

Your web browser needs to support HTML4.01, CSS2 and JavaScript to correctly view these webpages.

Valid CSS! Valid HTML 4.01!