## COT 5405, Analysis of Algorithms, Spring 2007Place:CSE E107Time:Tuesday 4 (10:40-11:30 a.m.) and Thursday 4,5 (10:40-12:35 a.m.)
Visit the announcement and homework pages at least once a week for updates on handouts, assignments and other time sensitive documents.
**COP 3530**, Data Structures and Algorithms.
**COT 3100**, Applied Discrete Structures .
Textbook: Algorithm Design, Jon Kleinberg and Eva Tardos, Addison Wesley, ISBN 0-321-29535-8.
- 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
- 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.
- ~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.
Your web browser needs to support HTML4.01, CSS2 and JavaScript to correctly view these webpages. |