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

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

Lectures: Lectures on Mondays and Wednesdays 10:05 - 11:25 AM. See public class schedule/Brightspace for the room location in Tory.

Office hours: Mondays 08:30-09:45 AM (HP 5125b). All general announcements will be made during the class and/or via the Brightspace system.

Teaching Assistant: Office hours in HP4125 on Thursdays from 13:00-14:00

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:

Approximation algorithms design techniques
Dimensionality Reduction
Online Algorithms (including the role of Primal-Dual LPs in their analysis)
Finding Similar Items using Locality-Sensitive Hashing
Nearest Neighbor Searching
Clustering
FPT Algorithmic Design Techniques
Algorithmic Aspects of Social Networks (Graph Partitioning, Searching various substructures)

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:

Analysis of algorithms (O-notation, recurrences, and complexity analysis)
Elementary probability theory including expectation, indicator random variables, Variance, Markov's Inequality (contents of COMP 2804)
Basic data structures (lists, trees, hashing, BST)
Discrete mathematics (counting, permutations and combinations, graph theory, proof techniques: induction, contradiction, ..)
Algorithmic techniques (divide and conquer, greedy, dynamic programming, BFS, DFS, Connectivity, Shortest Paths, and what is NP-Completeness)
Linear Algebra (Eigenvalues/vectors, Rank-Nullity, Vector Spaces, Norms).

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:

Foundations of Data Science by Blum, Hopcroft and Kanan.
My Notes on Topics in Algorithm Design (We refer to them as Notes)
Mining of Massive Data Sets: mmds.org
Several Research Articles that will be mentioned during the course.

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

Linear Algebra:

Eigenvalues (1 2)
Video Lectures and the book of Gilbert Strang
Chapter on Matrices for CS in Notes

Probability:

Locality Sensitive Hashing

Chapter 3 in Mining of Massive Data Sets by Stanford Group (mmds.org)
Useful references on LSH
STOC98 paper of Indyk-Motwani
Chapter 9 on LSH in Notes

Data Streaming

Mining Data Streams chapter of MMDS
Wikipedia Article
DGIM Article
Count-Min Sketch Article
AMS Article (Approximating frequency moments)
Knuth's Article - CVM Algorithm
Flajolet and Martin's Article on number of distinct elements in a stream
Some parts are covered in the Chapter in Notes
My talk on Bloom Filters and Count-Min-Sketch

Online Bipartite Matching

Karp, Vazirani, and Vazirani, An optimal algorithm for online birpartite matching ACM-STOC 1990
Devanur, Jain and Kleinberg, Randomized primal-dual analysis of ranking for bipartite matching, ACM-SIAM SODA 2013.
Mehta, Saberi, Vazirani and Vazirani, AdWords and generalized online matching, Jl. ACM Vol. 54, 2007.
Kalyanasundaram and Pruhs, An optimal deterministic algorithm for online b-matching, Theoretical Computer Science 233(1-2): 319-325, 2000.

Chapter on Advertisement on the Web from the MMDS Book.
Eden, Feldman, Fiat, and Segal, An Economics-Based Analysis of RANKING for Online Bipartite Matching, arXiv, 2020.
Echenique, Immorlica, and Vazirani, Online and Matching-Based Market Design, Cambridge University Press, 2023.
See Section 11.1 - 11.4 of Notes

Randomized Load Balancing & Perfect Hashing

http://pages.cs.wisc.edu/~shuchi/courses/787-F09/scribe-notes/lec7.pdf

Kleinberg&Tardos Algorithm Design Book, Chapter 13.

Polynomial Identity Testing

DeMillo and Lipton, A probabilistic remark on algebraic program testing, Information Processing Letters 7(4):193-195, 1978.
Mulmuley, Vazirani and Vazirani, Matching is as easy as matrix inversion, Combinatorica 7(1):105-113, 1987.
Mitzenmacher and Upfal, Probability and Computing, Cambridge.
Motwani and Raghavan, Randomized Algorithm, Cambridge.

MWIS

U. Feige and D. Reichman, Recoverable values for independent sets, Random Structures and Algorithms 46(1): 142-159, 2015.

Approximation Algorithms using Local Search
- A. Gupta and K. Tangwongsam, Simpler Analyses of Local Search Algorithms for Facility Location (arXiv Paper)
- Arya et al., Local search heuristics for k-median and facility location problems, SIAM Jl. Computing 33(3): 544-562, 2004.
- N.H. Mustafa and S. Ray, Improved results on geometric hitting set problems, Discrete and Computational Geometry 44:883-895, 2010
- R. Aschner, M.J. Katz, G. Morgenstern and Y. Yuditsky, Approximation schemes for covering and packing, WALCOM, Lecture Notes in Computer Science 7748: 89-100, Springer, 2013.
More Approximation Algorithms (using LP)

Min Cost st-cuts, Multiway Mincuts, Multicuts in Graphs
Garg, Vazirani and Yannakakis, Primal-dual approximation algorithms for integral flow and multicuts in trees, Algorithmica 18(1): 3-20, 1997.
Garg, Vazirani and Yannakakis, Multiway cuts in node weighted graphs, Journal of Algorithms 50(1): 49-61, 2004.
Calinescu, Karloff and Rabani, Approximation algorithms for the 0-extension problem, ACM-SIAM SODA 2001.
Fakcharoenphol, Rao and Talwar, A tight bound on approximating arbitrary metrics by tree metrics, JCSS 69(3): 485-487, 2004
The design of approximation algorithms, Williamson and Shmoys, Cambridge University Press, 2011.

Even more Approximation Algorithms

Turning down the noise in blogosphere, El-Arini, Veda, Shahaf, Guestrin, KDD 2009.
An analysis of approximations for maximizing submodular set function. Mathematical Programming 14, 265-294, 1978.

Multiplicative-Weight Update Method

Arora, Hazan and Kale, The multiplicative weights update method: a meta-algorithm and applications, Theory of Computing 8(1): 121-164, 2012.
Chapter 11 of Notes.

Locality-Sensitive Orderings

Chan, Har-Peled, Jones, On locality-sensitive orderings and their applications, SIAM Jl. on Computing 49(3): 583-600, 2020.

Dimensionality Reduction

Matousek, Lectures on Discrete Geometry, Volume 212 of Graduate Texts in Mathematics. Springer, New York, 2002.
Dubhashi and Panconesi, Concentration of Measure for the Analysis of Randomized Algorithms, Cambridge University Press, 2009.
Dasgupta, and Gupta, An elementary proof of a theorem of Johnson and Lindenstrauss" Random Structures & Algorithms, 22 (1): 60-65, 2003.
Johnson and Lindenstrauss, Extensions of Lipschitz mappings into a Hilbert space, Contemporary Mathematics 26:189-206, 1984.
Chapter 12 of Notes

Color Coding

Alon, Yuster, and Zwick: Color Coding, Jl. ACM 42(4): 844-856, 1995.

Max k-coverage

Maximizing the Spread of Influence through a Social Network, by Kempe, Kleinberg and Tardos.

Clustering

Arthur and Vassilvitskii, k++-Means: the advantages of careful seeding, ACM-SIAM SODA 2017.

Greedy Peeling - Densest Subgraphs

C. Chekuri, K. Quanrud and M. Torres, Densest Subgraphs: Supermodularity, iterative peeling, ACM-SIAM SODA 2022.
T. Lanciano et al., A survey on densest subgraph problem and its variants, arXiv, 2024.
A. Goldberg, Finding a maximum density subraph, Technical Report, University of California, Berkley, 1984.

Articles worth pursuing for projects in addition to above references

E. Lee, Partitioning a graph into small pieces with applications to path transversal, SODA 2017.
J. Matousek, Chapter 10: Transversals and Epsilon Nets in Lectures in Discrete Geometry, Springer, 2002.
S. Har-Peled, Chapter 5, Geometric Approximation Algorithms, AMS 2011
S. Har-Peled, Chapter 15, Geometric Approximation Algorithms, AMS 2011
Agarwal, Har-Peled, R. Raychaudhry and S. Sintos, Fast approximation algorithms for piercing boxes by points, SODA 2024.
Articles on bounded treewidth graphs
A. Eden, M.Feldman, A. Fiat and K. Segal, An Economics-Based Analysis of RANKING for Online Bipartite Matching, SOSA 2021.
N. Alon, M. Yossi and M. Szegedy, The space complexity of approximating frequency moments, Jl Comp. System Science 58(1), 1999. Also in ACM STOC 1996.
R. Moser and G. Tardos, Constructive Proof of Lovasz Local Lemma, Jl. ACM 57(2), 2010.
G. Bodwin, An alternate proof of near-optimal light spanners, SOSA 2024.
A. Gupta. E. Lee and J. Li, Local search based approach for set covering, SOSA 2023.
J. Fakcharoenphol, S. Rao, and K. Talwar, A tight bound on approximating arbitrarily metrics by tree metrics, JCSS 69(3): 485-497, 2004.
R. Kupfer and N. Nisan, Finding a hidden edge, arXiv 2022.
Basu et al., A sublinear algorithm for approximate shortest paths in large networks, WSDM 2025.

Grading Scheme: (Tentative)

There are three components:

Final Exam (20%, Scheduled by Exam Services): Final Exam will encompass the course material as well as the key ideas from the seminars presented by students.

In Class Test (15%):
In Class test will cover all the lecture material before the Fall break. This will be held in the class on October 27th.

Project (COMP 5112): (Written project proposal (10%), 3-Minute Proposal Presentation 5% + Final Report 25% + Final Presentation 25%).

Outline is as follows:

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.

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 29. Your 3-minute presentation is scheduled on October 1 during the class time slot.

Final Project Presentation: Scheduled in last 3-4 weeks of the class. Presentation is for approximately 15 minutes duration.

Project Report: Due couple of days before your presentation. The report format will likely be a research article. Its best to use LaTeX (e.g. see Overleaf). The sections will include:

Introduction (Motivation, Problem Statement, Related Work, Short Summary of what you did).
Preliminaries (In case you need to discuss some notation, definitions, etc. as background)
Main Section - How did you solve the problem; State Algorithm; State its Analysis; State its Correctness.
Experiments (in case you performed any simulation etc.)
Conclusions (Summary + What did you learn? + What do you think can be done in future?)
References
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.
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
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.

Project (COMP 4900): Same as above, except that the final project report is of 4 pages and the final presentation is for about 12 minutes.

Fall 2025 Schedule

Sep 03: Course Logistics + MWU Method

Arora, Hazan and Kale, The multiplicative weights update method: a meta-algorithm and applications, Theory of Computing 8(1): 121-164, 2012.
Chapter 11 in Notes.
Summary on MWU (with extra material)

Sep 08: MWU (Cont.) Randomized Schemes

Sep 10: Greedy Algorithms

MWIS
- U. Feige and D. Reichman, Recoverable values for independent sets, Random Structures and Algorithms 46(1): 142-159, 2015.

Section 13.1.2 in Notes
Summary on MWIS

Densest Subgraphs - Greedy Peeling
- C. Chekuri, K. Quanrud and M. Torres, Densest Subgraphs: Supermodularity, iterative peeling, ACM-SIAM SODA 2022.
- T. Lanciano et al., A survey on densest subgraph problem and its variants, arXiv, 2024.
- A. Goldberg, Finding a maximum density subraph, Technical Report, University of California, Berkley, 1984.
- Summary on Densest Subgraphs

Sep 15: Proofs of MWIS and Greedy Peeling for Densest Subgraphs

Sep 17: Locality-Sensitive Hashing

Chapter 8 in Notes.

Useful references on LSH

STOC98 paper of Indyk-Motwani

Summary on LSH

Sep 22: LSH Continued (Metric Space, Sensitive Family of Functions)

Sep 24: Local Search - k-Median and Weighted MaxCut

A. Gupta and K. Tangwongsam, Simpler Analyses of Local Search Algorithms for Facility Location (arXiv Paper)
Arya et al., Local search heuristics for k-median and facility location problems, SIAM Jl. Computing 33(3): 544-562, 2004.
N.H. Mustafa and S. Ray, Improved results on geometric hitting set problems, Discrete and Computational Geometry 44:883-895, 2010
R. Aschner, M.J. Katz, G. Morgenstern and Y. Yuditsky, Approximation schemes for covering and packing, WALCOM, Lecture Notes in Computer Science 7748: 89-100, Springer, 2013.
Chapter 14.2 in Notes
Summary on Local Search

Sep 29: Project Proposal Due, Geometric Hitting Sets, Online Algorithms for Matching

Oct 01: 3-Minute Proposal Presentation

Oct 06: Geometric Hitting Sets + Online Algorithms for Matching

LP Duality and Proof of Greedy Matching

Randomized Ranking with Economics-based analysis

Fractional Matching

Waterlevel Algorithm for Fractional Matching

Balance Algorithm

Chapter 10 in Notes

Summary on Online Matching

Oct 08: Online Algorithms for Matching

Oct 15: Separator Theorems in Graphs (Bobby Miraftab)

https://drive.google.com/file/d/111xuRafoIHmX6rDDmOyXBA5nyE8ft02H/view

See also Section 7.1-7.3 in Notes.

Oct 27: In Class Test

Oct 29: Online Algorithms for Matching (Contd.)

Nov 03: Online Algorithms for Matching (Contd.)

Nov 05: Approximation Algorithms (using Metric LPs)

Min Cost st-cuts, Multiway Mincuts, Multicuts in Graphs

Garg, Vazirani and Yannakakis, Primal-dual approximation algorithms for integral flow and multicuts in trees, Algorithmica 18(1): 3-20, 1997.

Garg, Vazirani and Yannakakis, Multiway cuts in node weighted graphs, Journal of Algorithms 50(1): 49-61, 2004.

Calinescu, Karloff and Rabani, Approximation algorithms for the 0-extension problem, ACM-SIAM SODA 2001.

Fakcharoenphol, Rao and Talwar, A tight bound on approximating arbitrary metrics by tree metrics, JCSS 69(3): 485-487, 2004

The design of approximation algorithms, Williamson and Shmoys, Cambridge University Press, 2011.

Chapter 13.3 of Notes

Summary on Approximation Algorithms using Metric LPs

Nov 10: Approximation Algorithms (using Metric LPs)

Nov 12: Seminar Talks + Clustering

K-Means

K-Means++

Chapter 15 in Notes

Summary on Clustering

Nov 17: Seminar Talks + Clustering

Nov 19: Seminar Talks + Clustering

Nov 24: Seminar Talks + Dimensionality Reduction

Matousek, Lectures on Discrete Geometry, Volume 212 of Graduate Texts in Mathematics. Springer, New York, 2002.

Dubhashi and Panconesi, Concentration of Measure for the Analysis of Randomized Algorithms, Cambridge University Press, 2009.

Dasgupta, and Gupta, An elementary proof of a theorem of Johnson and Lindenstrauss" Random Structures & Algorithms, 22 (1): 60-65, 2003.

Johnson and Lindenstrauss, Extensions of Lipschitz mappings into a Hilbert space, Contemporary Mathematics 26:189-206, 1984.

Chapter 12 in Notes.

Summary Notes

Nov 26: Seminar Talks + Dimensionality Reduction

Dec 01: Dimensionality Reduction (to L_\infty norms)

Dec 03: Dimensionality Reduction (JL Lemma)

Partial List of Seminar From Previous Terms

Research Article	Talk Slides
M. Belkin and P. Niyogi. Towards a theoretical foundation for Laplacian-based manifold methods. Proceedings of the Conference on Learning Theory (COLT), 2005.	Laplacian Eigenmaps for Dimensionality Reduction
O. Durmaz and H. Sakir Bilge, Fast image similarity search by distributed locality sensitive hashing, Pattern Recognition Letters, Volume 128, 2019, Pages 361-369. https://doi.org/10.1016/j.patrec.2019.09.025	Fast image similarity search using distributed LSH
Muniz, M., & Flamand, T. (2022). A weighted network clustering approach in the NBA. Journal of Sports Analytics, 8(4), 251-275. https://doi.org/10.3233/JSA-220584	NBA Analytics - Clustering Analysis
Deng, S., Li, J., & Rabani, Y. (2023). Generalized Unrelated Machine Scheduling Problem. Society for Industrial and Applied Mathematics, 2898-2916.	Approximation Algorithm for a Generalized Load-Balancing Problem
Chaplick, S., De, M., Ravsky, A., & J. Spoerhase, Approximation schemes for geometric coverage problems. 26th Annual European Symposium on Algorithms (ESA 2018), August 20-22, 2018, Helsinki, Finland.	PTAS for the Maximum Coverage problem in geometric and graph settings
N. Shahbazi, S. Sintos, and A. Asudeh. Fair-count-min: Frequency estimation under equal group-wise approximation factor. arXiv preprint arXiv:2505.18919, 2025.	Fair-Count-Min Sketch
M. G. Herold, E. Kipouridis, and J. Spoerhase. Clustering to minimize cluster-aware norm objectives, 2024.	Clustering to Minimize Cluster-Aware Norm Objectives
From Notes	Online Algorithms for Bipartite Matching
	Twin Width
R. A. Moser. A constructive proof of the Lovasz local lemma. Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), pages 343-350, Bethesda, MD, USA, 2009. ACM.	LLL Talk
Alon, N., Yuster, R., Zwick, U. (1995). Color-coding. Journal of the ACM, 42(4), 844-856.	Color Coding
C. Chekuri, K. Quanrud, and M. R. Torres. 2022. Densest subgraph: supermodularity, iterative peeling, and flow. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1531-1555	Densest Subgraph Problem
D. Dorfman et al., Minimum-cost paths for electric cars, Symposium on Simplicity in Algorithms (SOSA). SIAM. 2024, pp. 100-101.	Min Cost Paths
J. Fakcharoenphol, S. Rao, and K. Talwar. A tight bound on approximating arbitrary metrics by tree metrics. Journal of Computer And System Sciences, 69:485-497, 2004.	Tree Metrics
M. Dorigo and T. Stutzle. Ant Colony Optimization. The MIT Press, 2004.	TSP Ant Colony
S. Chakraborty, N. V. Vinodchandran, and K. S. Meel. Distinct Elements in Streams: An Algorithm for the (Text) Book. 30th Annual European Symposium on Algorithms (ESA 2022), volume 244 of Leibniz International Proceedings in Informatics (LIPIcs), pages 34:1-34:6,	CVM
M. Cygan, F.V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer International Publishing, 2015. D. Lokshtanov, P. Misra, M. S. Ramanujan, S. Saurabh, and M. Zehavi. FPT-approximation for FPT Problems, pages 199-218.	FPT-Approximations
S. Baswana and A. Pandey. Sensitivity oracles for all-pairs mincuts. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 581-609. SIAM, 2022.	Sensitivity-Oracle
K. G. Larsen and J. Nelson. Optimality of the Johnson-Lindenstrauss lemma. 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017	Lower-Bound

Contents From Previous Offerings that weren't covered in Fall 2025 offering.

Locality-Sensitive Orderings

Chan, Har-Peled, Jones, On locality-sensitive orderings and their applications, SIAM Jl. on Computing 49(3): 583-600, 2020.
Quadtrees, DFS Traversal Permutations - Orderings
Summary Note

FPT Algorithm

Summary on FPT

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:

Students are NOT allowed to collaborate on assignments. Please avoid using search engines to look for answers etc. Just a word of caution - in theoretically oriented courses, it is important to come up with your own ideas for the proof/an algorithm/a contradiction/etc. Sometimes these are like logical puzzles - if somebody tells you a solution then they are trivial and hard part is to come up with a solution. What we want to learn is how to solve them ourselves.
Past experience has shown conclusively that those who do not put adequate effort into the assignments do not learn the material and have a probability near 1 of doing poorly on the exams/tests.
Penalties for academic offences can be found on the ODS webpage: https://science.carleton.ca/academic-integrity/.

Important Considerations:

Late submissions are not accepted. 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:

periodically upload your progress (e.g. upload your progress at least daily)
attempt to submit your final submission at least one hour in advance of the due date and time.