COMP 5112/COMP4900G: Algorithms for Data Science (Fall 2024 Term)

Weekly Schedule      

Instructor: Anil Maheshwari
Office: Herzberg Building 5125B
E-mail: anil@scs.carleton.ca

Lectures: Lectures on Wednesdays 14:35 - 17:25 AM. See public class schedule/Brightspace for the room location in River Building Ground Floor.
Office hours:   Wednesdays 10:15-11:45 AM (HP 5125b). All general announcements will be made during the class and/or via the Brightspace system.

Teaching Assistant: Very unlikely
Course objectives:   

To learn some of the algorithmic techniques to handle data science problems. Emphasis is on providing correctness proofs, establishing competitive ratios, and analyzing computational complexity for each of the algorithms discussed during the course.

Topics may include:

These topics may be adjusted based on the background, interests of the students, and the amount of lecture time available.
Required Background:
 
We will cover a spectrum of techniques from the design and analysis of algorithms. It is assumed that you have an excellent grasp on:
 Note that there will not be sufficient time to review the background material to a satisfactory level during the course. (In nutshell you must have a background that is equivalent to the following Carleton Courses:  COMP 1805, COMP 2402, COMP 3804, and a course in Linear Algebra.)
Reference Material:

Useful references related to various topics. This will get modified as we go along in the course.


Grading Scheme: (Tentative)

COMP 4900 G COMP 5112
Assignments
 30%
 30%
End Term Quiz
 15%
 15%
Project
 55%
 55%

There are four components:

Outline is as follows:

  1. Pick a topic. (Look at references under "Reference Material"  and conferences in related areas. Also, use Google Scholar to see who refers to those papers etc.) You may look for papers/citations in recent proceedings of the ACM-SIAM Symposium on Discrete Algorithms conference and SIGKDD Conference for relevant topics.
  2. Initial Proposal: Submit one page draft.  What is the topic you chose? Why? What problem(s) you will look at? What you plan to do? Outline of sections of your report? Main References. Due (in pdf format) by September 24. Your 5 minute presentation is scheduled on September 25 during the class time slot.
  3. Final Project Presentation: Scheduled on November 20 & 27 during the class.  (BTW, we may have to schedule the presentations outside the class time slot.) Presentation is for approximately 15 minutes duration.  (End Term Quiz will have questions from these reports/presentations).
  4. Project Report: Due by November 26. The report format will likely be a research article. Its best to use LaTeX (e.g. see Overleaf). The sections will include:
      1. Introduction (Motivation, Problem Statement, Related Work, Short Summary of what you did).
      2. Preliminaries (In case you need to discuss some notation, definitions, etc. as background)
      3. Main Section - How did you solve the problem; State Algorithm; State its Analysis; State its Correctness.
      4. Experiments (in case you performed any simulation etc.)
      5. Conclusions  (Summary + What did you learn? + What do you think can be done in future?)
      6. References
      7. Report will be approximately 6 pages long and will be posted on the course web-page. Final Exam will have some questions from these reports.  
      8. You may use a double column format - for example the style file from Canadian Conference in Computational Geometry Style File from here:  http://vga.usask.ca/cccg2020/CCCG2020-tex-template.zip
      9. It will also help the community if you update/create the relevant Wikipedia page relevant to your project. You will be suitably rewarded with bonus marks. 

Outline is as follows:

  1. Pick a topic. (Look at references under "Reference Material"  and conferences in related areas. Also, use Google Scholar to see who refers to those papers etc.)
    You may look for papers/citations in recent proceedings of the ACM-SIAM Symposium on Discrete Algorithms conference and SIGKDD Conference for relevant topics.
  2. Initial Proposal: Submit one page draft.  What is the topic you chose? Why? What problem(s) you will look at? What you plan to do? Outline of sections of your report? Main References. Due (in pdf format) by September 24. Your 5 minute presentation is scheduled on September 25 during the class time slot. 
  3. Final Project Presentation: Scheduled on November 20 & 27 during the class.  Presentation is for approximately 12 minutes duration.  (End Term Quiz may have questions from these reports/presentations).
  4. Project Report: Due by November 26. The report format will likely be a research article. Its best to use LaTeX (e.g. see Overleaf). The sections will include:
      1. Introduction (Motivation, Problem Statement, Related Work, Short Summary of what you did).
      2. Preliminaries (In case you need to discuss some notation, definitions, etc. as background)
      3. Main Section - How did you solve the problem; State Algorithm; State its Analysis; State its Correctness.
      4. Experiments (in case you performed any simulation etc.)
      5. Conclusions  (Summary + What did you learn? + What do you think can be done in future?)
      6. References
      7. Report will be approximately 4 pages long and will be posted on the course web-page.
      8. You may use a double column format - for example the style file from Canadian Conference in Computational Geometry Style File from here:  http://vga.usask.ca/cccg2020/CCCG2020-tex-template.zip

SCHEDULE OF FALL 2024 Term

Sep 04: Introduction + MWU Method

Sep 11: MWU - Randomized Schemes +  MWIS Analysis + LSH

Sep 18: LSH + LP's using MWU + Local Search

Sep 25: Short Presentations on Projects + Local Search

Oct 02: Proof of k-Median + Geometric hitting sets via local improvement

Oct 09: Clustering

Oct 16: BM Talks about Graph Separation

Oct 30:  Dimensionality Reduction + Locality-Sensitive Orderings

Nov 06:  Dimensionality Reduction + Locality-Sensitive Orderings (Contd.)

Nov 13: LLL Talk  + Approximation Algorithms (using Metric LPs) + Online Algorithm for Matching

Nov 20: Presentations on Projects (Tree Metrics, Densest Subgraph Problem) +  Online Algorithm for Matching

Nov 27: Presentations on Projects (Color Coding (pptx),  MinCostPaths, Twin Width) + Approximation/FPT Algorithms

Dec 04: End Term Quiz

Undergraduate & Graduate Academic Advisor:

The Undergraduate Advisor for the School of Computer Science is available in Room 5302 HP; or by email at scs.ug.advisor@scs.carleton.ca.  The undergraduate advisor can assist with information about prerequisites and preclusions, course substitutions/equivalencies, understanding your academic audit and the remaining requirements for graduation. The undergraduate advisor will also refer students to appropriate resources such as the Science Student Success Centre, Learning Support Services and Writing Tutorial Services.

Similarly, we have Graduate Advisors. Depending on your program of study and the university, you may contact the relevant graduate advisors.
University Policies

We follow all the rules and regulations set by Carleton University, Dean of Science, and the School of Computer Science regarding accommodating students with any kind of need(s). Please consult with the appropriate authorities to see how you can be accommodated and please follow their procedures. For information about Carleton's academic year, including registration and withdrawal dates, see Carleton's Academic Calendar. Following is a standard list of recommendations that we have been advised to provide you with respect to whom to contact for the appropriate action(s). It is possible that some of these are out of date, please consult the latest recommendations from the Science Faculty.

Pregnancy Obligation. Please contact your instructor with any requests for academic accommodation during the first two weeks of class, or as soon as possible after the need for accommodation is known to exist. For more details, visit Equity Services.

Religious Obligation. Please contact your instructor with any requests for academic accommodation during the first two weeks of class, or as soon as possible after the need for accommodation is known to exist. For more details, visit Equity Services. 

Academic Accommodations for Students with Disabilities If you have a documented disability requiring academic accommodations in this course, please contact the Paul Menton Centre for Students with Disabilities (PMC) at 613-520-6608 or pmc@carleton.ca for a formal evaluation or contact your PMC coordinator to send your instructor your Letter of Accommodation at the beginning of the term. You must also contact the PMC no later than two weeks before the first in-class scheduled test or exam requiring accommodation (if applicable). After requesting accommodation from PMC, meet with your instructor as soon as possible to ensure accommodation arrangements are made. For more details, visit the Paul Menton Centre website.
 
Survivors of Sexual Violence. As a community, Carleton University is committed to maintaining a positive learning, working and living environment where sexual violence will not be tolerated, and survivors are supported through academic accommodations as per Carleton's Sexual Violence Policy. For more information about the services available at the university and to obtain information about sexual violence and/or support, visit: carleton.ca/sexual-violence-support.

Accommodation for Student Activities. Carleton University recognizes the substantial benefits, both to the individual student and for the university, that result from a student participating in activities beyond the classroom experience. Reasonable accommodation must be provided to students who compete or perform at the national or international level. Please contact your instructor with any requests for academic accommodation during the first two weeks of class, or as soon as possible after the need for accommodation is known to exist. For more details, see the policy.

Student Academic Integrity Policy. Every student should be familiar with the Carleton University student academic integrity policy. A student found in violation of academic integrity standards may be awarded penalties which range from a reprimand to receiving a grade of F in the course or even being expelled from the program or University. Examples of punishable offences include: plagiarism and unauthorized co-operation or collaboration.

Plagiarism. As defined by Carleton University Senate, "plagiarism is presenting, whether intentional or not, the ideas, expression of ideas or work of others as one's own". Such reported offences will be reviewed by the office of the Dean of Science.  More information and standard sanction guidelines can be found here: https://science.carleton.ca/students/academic-integrity/.
Unauthorized Co-operation or Collaboration. Senate policy states that "to ensure fairness and equity in assessment of term work, students shall not co-operate or collaborate in the completion of an academic assignment, in whole or in part, when the instructor has indicated that the assignment is to be completed on an individual basis". 
For this course, the following also holds:

Important Considerations:

Late assignments are not accepted. Assignments submissions are handled electronically using the Brightspace system and there is no "grace period" with respect to a deadline. Technical problems do not exempt you from this requirement. You are advised to: