Professor Anil Maheshwari School of Computer Science 573 Design and Analysis of Algorithms

This is the 95.573 home page "http://www.scs.carleton.ca/~maheshwa/573.html". Check it regularly for new information, assignments, etc. 

Office: School of Computer Science, Carleton University, Ottawa, Canada K1S 5B6, room 5364, Herzberg Physics Building,

Phone: (613) 520-4333, Fax: (613) 520-4334,

OFFICE HOURS:

E-mail: maheshwa@scs.carleton.ca, WWW:http://www.scs.carleton.ca/~maheshwa.

Classroom:

• Understand parts of section VI and VII of the text book.
• Learning how to design and  analyse algorithms.

Course References:

• (Reif) John Reif, "Synthesis of Parallel Algorithms", Morgan Kaufman.
• (JaJa) Joseph JaJa, "Introduction to Parallel Algorithms", Addison-Weseley.
• (Leighton) F.T. Leighton, "Introduction to parallel architectures and algorithms", Morgan Kaufman.
• (Knuth) D.E. Knuth, "The art of computer programming", Vol. 1,2,3  Addison-Weseley.
• (Kozen) Dexter Kozen, "The design and analysis of Algorithms", Springer 1992
• Several Journal Articles.

1. Background
2. Graph Algorithms
3. Greedy Algorithms and Matroids
4. Analysis of Algorithms: Amortized analysis
5. Binomial and Fibonacci Heaps.
6. Maximum Flow
7. Linear Programming
8. FFTs
9. Randomized Algorithms
10. NP Completeness
11. Approximation Algorithms
12. Special Topics

2 Assignments, 1 Seminar, 1 Report and a FINAL EXAM (on the last day of our class).

For Seminars/Reports - if you haven't chosen a topic so far, please choose a paper (e.g see Jl. of Algorithms, SIAM Jl. Comput.) and immediately decide and let me know.
This should be positively be done by Oct 4th or you will loose your marks.

Seminar - will be for 25-30 minutes during the class, and it should present what is problem - techniques - data structures and algorithms - main contribution of that paper.

Report - should briefly describe (in your own words) what is there in the paper. Proof of the main theorem - and discuss the key ideas. Report should be atleast 4 page long, and will be due the same date as your seminar. It will be put up on the web - as you will be asked questions from that in your final exam/assignments.

Assignment 1 (Due on Oct 29) (Drop it in my office or SCS office)
Assignment 2 (Due on Nov 22 in the class)
 

• Sept 6: Introduction, O Notation, Masters Theorem, Matrix Multiplication,      Basic Graph Terms.
• Sept 13: Adjacency list and matrix representation. How to initialize matrix quicker, BFS, Topological Sort, DFS, Articulation Point, Equivalence Relation, Biconnectivity, Low(v).
• Sept. 15 (SATURDAY  CLASS -- 9:30 AM to 12:00) :  Binomial  Heaps, Amortized Analysis  and settling the seminar topics.
• Sept. 20 NO CLASS
• Sept 27 MST and Dijkstra's SSSP
• Oct. 4: Dijkstra's + Fibonacci Heaps and two seminars (LEDA & Algorithm Mechanism Design - Papadimitriou et al.)
• Oct 11: Fibonnaci Heaps and Network Flow. (Randomized Search Trees - Seidel)
• Oct 18: Network Flow
• Oct 25: Linear Programming (Network Flow - Goldberg/Tarjan)(Correctness)
• Nov 1: LP (Klien et al. linear time SP) (Randomized Rounding)
• Nov 8: NP Completeness Video (Fredricksons Shortest Path) (R-Trees) (Bipartite-Matching)
• Nov 15: Approximation for Vertex Cover and TSP (bubble-partition) (planar-separators) (Max-Satisfiability)
• Nov 22: Approximation for TSP (Applications of Planar Separators) (Gene Trees) (Dynamic Shortest Paths) (String Matching)
• Nov 29 : FINAL EXAM &:30 to 10:00 PM

  Basic Idea about randomized LP in 2-dimensions
  Main results+ Techniques of all talks (don't worry about the details).
  

---

http://www.scs.carleton.ca/~maheshwa