COT 5405, Analysis of Algorithms, Spring 2012

Instructor:
Prof. Arunava Banerjee
Office: CSE E336.
E-mail: arunava@cise.ufl.edu.
Office hours: Tuesday 2:00 p.m.-4:00 p.m.

TA: Office: CSE Exxx. E-mail: xxx@cise.ufl.edu. Phone: 392-xxxx. Office hours: Tuesday 9:30 a.m.-10:30 a.m.                     Thursday 2:00 p.m. - 4:00 p.m.

TA: Office: CSE Exxx. E-mail: xxx@cise.ufl.edu. Phone: 392-xxxx. Office hours: Tuesday 10:30 a.m.-11:30 a.m.                     Friday 11:30 a.m.-1:30 p.m

TA: Office: CSE Exxx E-mail: xxx@cise.ufl.edu Phone: 392-xxxx Office hours: Monday 2:00 pm - 4:00 pm

Visit the announcement and homework pages at least once a week for updates on handouts, assignments and other time sensitive documents.

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 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: 35% (25% regular + 10% star problems)
• One midterm exam: 25% (50 minute 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).

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/honestybrochure.htm 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.