COT 5405, Analysis of Algorithms, Spring 2007
Time:Tuesday 4 (10:40-11:30 a.m.) and Thursday 4,5 (10:40-12:35 a.m.)
Prof. Alin Dobra
Office: CSE E474.
Office hours: Wednesday 1:00 p.m.-3:00 p.m. or by appointment.
Parbati Kumar Manna
Office: CSE E402.
Office hours: F 7,8
Office: CSE E309.
Office hours: M 8,9
Visit the announcement and homework pages at least once a week for updates on handouts, assignments and other time sensitive documents.
Textbook: Algorithm Design, Jon Kleinberg and Eva Tardos, Addison Wesley, ISBN 0-321-29535-8.
- COP 3530, Data Structures and Algorithms.
- COT 3100, Applied Discrete Structures.
Specific Prerequisite Knowledge
Please brush on these specific topics in the first few weeks of class. They will be assumed known and understood in the lectures.
- Basic data-structures: arrays, linked lists, stacks, queues,
priority queues, heaps, trees, binary trees, graphs.
- Use of basic data-structures (finding, inserting, deleting and updating elements).
- Basic algorithm complexity (big-O notation)
- Tree based search (binary search, some notion of advanced search trees like avl and red-black trees)
- Sorting (quick sort, merge sort, insertion sort, bubble sort)
- Ability to prove (and write proofs): proof by induction and contradiction
- Discrete structures: permutations, combinations, counting, set theory.
- Basic probability theory
- Basic calculus: series, limits, summation by integration
Tentative list of Topics to be covered
- Priority Queues
- Graphs: connectivity and traversal
- Greedy Algorithms
- Shortest Path
- Minimum Spanning Trees (with cut and cycle properties)
- Kruskal's Algorithm + union-find data-structure
- Huffman Codes and Data Compression
- Divide and Conquer
- Mergesort algorithm
- Integer multiplication
- Convolutions and Fast Fourier Transform
- Dynamic Programming
- Weighted interval scheduling
- Matrix chain multiplication
- Segmented Least Squares
- Sequence Alignment
- Network Flows
- Ford-Fulkerson algorithm
- Max flows and min cuts in a network
- Bipartite matching problem
- Disjoint Paths
- Other applications of network flow
- NP and Computational Intractability
- Polynomial-time reductions
- Satisfiability Problem
- NP-Complete Problems
- Sequencing Problems
- Partitioning Problems
- Graph Coloring
- Co-NP and the Asymmetry of NP
- Advanced topics:
- Approximation Algorithms
- Local Search
- Randomized Algorithms
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.
The final grade will be on the curve.
- ~4 homework assignments: 15%
- One midterm exam: 35% (2 hrs, in-class)
- Final exam: 50% (comprehensive)
- There will be no makeup exams (Exceptions shall be made for those that present appropriate letters from the Dean of Students Office).
- Homework: Rarely in your professional life you will have to work alone on a hard algorithmic problem. For this reason, collaboration will be encouraged in this class by allowing students to share ideas while working on the homework. Specifically, you are allowed to talk and brainstorm with your peers for finding solutions to the homework problems as long as you indicate on the assignment you submit who did you collaborate with (the size of the collaboration group will not influence your grade). What you are not allowed though is to write or share your written solution with anybody. Writing the solution together or showing your solution to another student will result be reprimanded according to university rules. In order to avoid getting in the above situation, I suggest you keep the discussion about the solution high level and never get a complete solution when you collaborate.
- Late assignments: All homework assignments are due before class; EDGE students are allowed to submit the homework up to 1 week late (still due at 10:40 when the classes start). No late submissions will be normally accepted. In exceptional situations late submissions will be allowed but not latter than 1 week from the original due date. Solutions to the problem will be handed in 1 week from the homework due date. For EDGE/FEEDS students, solutions will be emailed on the same day.
- 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.
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.