• Learning how to design and  analyze algorithms.

Course References:
(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-Wesley.
(Kozen) Dexter Kozen, "The design and analysis of Algorithms", Springer 1992
(Tarjan) Robert Tarjan, " Data structures and algorithms", SIAM Press.
(Motwani/Raghavan) R. Motwani and P. Raghavan, "Randomized Algorithms".
(CLRS) Introduction to Algorithms, Cormen Leiserson Rivest and Stein
(Dasgupta, Papadimitriou, Vazirany. "Algorithms", McGraw.
33 Miniatures - Mathematical and Algorithmic Applications of Linear Algebra, Matousek, AMS 2010.
(LRU) Mining of Massive Data Sets, Cambridge 2015.

Several Journal/Conference Articles.

Course evaluation (tentative):

Final Exam: 50% (or Optional Assignments up to  20% + {Final Exam 50% - Optional Assignments %})

Assignment 1 (PDF-File       LaTeX-File)

Assignment 2 (PDF-File       LaTeX-File)

Project: 50% (Seminar - 20%; Report: 20%;  Contribution to Public Knowledge: 10%)

Contributions to Public Knowledge - Please update the relevant part of Wikipedia articles/pages related to your seminar topic. You should take a snapshot of before and after in terms of what you have updated.

Seminar Schedule

Contents: In the first two weeks we will decide about a detailed outline, depending upon the class interest and the background.
Presently, I plan to cover Stable Marriages, MSTs, Flow Problems, Planar Separators, Locality-sensitive Hashing, Dimensionality Reduction, LCA and Submatrix-minima queries, Approximation Algorithms (including FPTs, LP-ILP relaxation), Probabilistic Methods.  If time permits we may venture a bit into some of the algorithms inspired by web-applications.

Sept 12: Stable Matchings,  LCA
My Notes on Stable Marriages,
Also look at the Chapter in the Notes for a better coverage.
A simulator for you to try,
Have also look at this link related to Nobel Prize
Original Article by Gale and Shapley in American Mathematical Monthly (69, Vol 1, pp 9-15, 1962)
A survey on Stable Marriages

My Notes on LCA
Also look into the chapter on LCA in Notes.
Link to the paper by Bender and Farach-Colton

Sept 19: Why proposal algorithm computes stable matchings? RMQ - preprocessing with +-1 property. MST - Boruvks'a algorithm.

Refer to Course Notes for LCA and Randomized MST

Sept 26: MST - Randomized. Statement of Planar Separator Theorem with Applications. Eigenvalues/Eigenvectors and its connection to Page Rank. Planar Separator theorem is in the course notes. For Page rank, you may refer to the LRU book - mining of Massive Data Sets. For Eigenvalues/vectors you may look into Gilbert Strang - Linear Algebra with Applications book.

Oct 03: Planar Separator Theorem.  More details on Eigenvalues, Eigenvectors,  and Page Rank Algorithm.
Oct 17: Finishing the proof of Planar Separator Theorem,  Approximation Algorithms
Oct 31: LSH + Talks

Nov 07: LSH + Talk
Nov 14: Approximation Algorithms by Ahmad Biniaz
Nov 21: Finishing LSH; k-means and k++-means overview;  and Talks.
Nov 28: Assignment 2 is Due. Talk on Matching. Permanent of a Adjacency Matrix. Approximation Algorithms - ILP-LP relaxation for weighted vertex cover. FPT for vertex cover. Introduction to recommendation systems.

Dec 05: Talk + Recommendation Systems.

Dec 09: FINAL EXAM - FRIDAY - In the class.
Please bring a calculator in case you need to compute something.
Content: All the material covered in the course so far including the main ideas in the Talks/Seminars.

Recommendation Systems, LSH, Fingerprinting, and Page Rank and Some ideas on SVDs are covered in the LRU Book which is online.
Other topics including LSH, LCA/RMQ, Stable Marriages, Randomized MST, and Planar Separators,  are covered in my notes.

1. Topics in the book on Mining Massive Data Sets of Leskovec, Rajaram and Ullman.
   
2. Stable Marriages - Gale+Shapley's algorithm with some extensions.
3. Scan First Search and Sparse Certificates - A paper by Cheriyan, Kao and Thurimella. [Background:  A distributed computing course]
   
4. Preflow-Push Max-Flow Algorithm
5. ILP-LP Relaxation - Some approximation algorithms using that framework.
   
6. Generalizations of Planar-Separator Theorem
7. Submatrix-Maxima Queries in Monge Matrices: A paper by Haim Kaplan, Shay Mozes, Yahav Nussbaum and Micha Sharir
   
8. Applications of Planar Separator Theorem
9. Tree Decomposition and Bounded Tree-width
10. Bottleneck Spanning Trees
11. Applications of Max-Flow
12. LSH Applications (Need to have taken COMP 4804 or equivalent)
13. Applications of Dimensionality Reduction [i.e. J-L Thm]  (preferable to have CG background + COMP 4804)n
14. Perfect Matching in Graphs
15. Luby's Parallel algorithm for Maximal independent set - also an alternate analysis by Vazirani.
    
16. Alon, Matias and Szegedy's classical paper on Space Complexity of Approximating Frequency Moments [JCSS 58: 137--147, 1999] - Key paper for data streaming.
    
17. Linial, London and Rabinovich classical paper on Geometry of Graphs [Combinatorica 15(2): 215--245, 1995]
    
18. A topic from the book by Mung Chiang's Networked Life, with the focus on Math & algorithmic ideas.
19. Any chapter from the 33 Miniatures book by Matousek.
20. Any topic from the book on Geometric Approximation by Har-Peled.

1. All the Carleton's standard rules on Equity, Students with special needs, Plagiarism, Academic Integrity etc. hold for this course. All these matters will be handled by appropriate authorities. You should look into the relevant university publications, and if you have questions regarding any of this, you can ask the School of Computer Sciences Administrative Staff. 
2. It will be your responsibility to adhere to all deadlines. Missing a deadline amounts to receiving a Mark of `zer0' on that component.
3. Note that several University of Ottawa Students, as part of the OCICS Joint Institute, take this course, The academic deadlines (e.g. academic with drawl date)  and the academic calender (e.g. Fall break, Start/end of classes) in both the universities are not in sync. For Academic Calender you need to follow Carleton's academic calendar and for Academic Deadlines, you need to respect the deadlines of your home university.
   
4. Seminars will be evaluated with respect to content, delivery, clarity, presentation, in-depth knowledge, use of appropriate illustrations, background literature,  and whether the main point came across clearly. Note that you will have about 25 minutes for your seminar, and possibly 5 minutes for questions.  Your report basically will be evaluated using the same criteria.
5. Assignment 1 is posted.
6. Please e-mail your seminar topic by Wednesday Oct 5th for sure.
   
7. Seminar Topics/Dates have been posted.
8. Contributions to Public Knowledge component is due on Dec. 12th
   

---

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