COMP 5112/COMP4900G: Algorithms for Data Science (Fall 2024
Term)
Weekly Schedule
Instructor: Anil Maheshwari
Office: Herzberg Building 5125B
Email: 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:1511: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:
 Approximation algorithms design
techniques
 Dimensionality
Reduction
 Online
Algorithms (including the role of PrimalDual LPs in
their analysis)
 Finding
Similar Items using LocalitySensitive 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 (Onotation,
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 NPCompleteness)
 Linear Algebra (Eigenvalues/vectors,
RankNullity, 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:
Useful references related to various topics. This
will get modified as we go along in the course.
 Locality Sensitive Hashing
 Online Bipartite
Matching
 Karp,
Vazirani, and Vazirani, An
optimal algorithm for online
birpartite matching ACMSTOC
1990
 Devanur,
Jain and Kleinberg, Randomized
primaldual analysis of ranking
for bipartite matching, ACMSIAM
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 bmatching, Theoretical
Computer Science 233(12):
319325, 2000.
 Chapter on Advertisement on the Web from the
MMDS Book.
 Eden, Feldman, Fiat, and Segal, An
EconomicsBased Analysis of RANKING for Online Bipartite
Matching, arXiv, 2020.
 Echenique, Immorlica, and Vazirani, Online
and MatchingBased Market Design, Cambridge University
Press, 2023.
 See Section 11.1
 11.4 of My
Notes
 Randomized Load Balancing & Perfect
Hashing
 http://pages.cs.wisc.edu/~shuchi/courses/787F09/scribenotes/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):193195, 1978.
 Mulmuley,
Vazirani and Vazirani, Matching is as
easy as matrix inversion,
Combinatorica 7(1):105113, 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): 142159, 2015.
 Even more Approximation Algorithms
 Turning down the noise in blogosphere,
ElArini, Veda, Shahaf, Guestrin, KDD 2009.
 An analysis of approximations for maximizing
submodular set function. Mathematical Programming 14,
265294, 1978.
 MultiplicativeWeight Update Method
 Arora, Hazan and Kale, The multiplicative
weights update method: a metaalgorithm and
applications, Theory of Computing 8(1): 121164, 2012.
 Chapter 11 of my notes.
 LocalitySensitive Orderings
 Chan, HarPeled, Jones, On
localitysensitive orderings and their applications, SIAM
Jl. on Computing 49(3): 583600, 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): 6065, 2003.
 Johnson and Lindenstrauss,
Extensions of Lipschitz mappings into a
Hilbert space, Contemporary Mathematics
26:189206, 1984.
 Chapter 12 of my notes
 Color Coding
 Alon, Yuster, and Zwick: Color Coding, Jl.
ACM 42(4): 844856, 1995.
 Clustering
 Arthur and Vassilvitskii, k++Means:
the advantages of careful seeding, ACMSIAM SODA 2017.
 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. HarPeled, Chapter 5, Geometric
Approximation Algorithms, AMS 2011
 S. HarPeled, Chapter 15,
Geometric Approximation Algorithms, AMS 2011
 Agarwal, HarPeled, 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 EconomicsBased
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
nearoptimal 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): 485497, 2004.

R. Kupfer and N. Nisan, Finding a hidden edge, arXiv
2022.

Grading Scheme: (Tentative)

COMP 4900 G 
COMP 5112

Assignments

30%

30%

End Term Quiz

15%

15%

Project

55%

55%

There are four components:
 End Term Quiz:
An End Term Quiz
will take place on the last day of classes. It will
encompass the course material as well as seminars
presented by students.
 Assignments:
A couple of assignments during the course. Please only refer to
class notes and the reference material listed on
the webpage and/or during lectures for solving
assignment problems. Please do not collaborate.
Please cite all the references used for solving
each of the problems. All assignments need to be
submitted electronically using the brightspace
system.
 Project (COMP5112): (Initial proposal
and presentation 10% + Final Report 25% + Final
Presentation 20%).
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
ACMSIAM 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
24. Your 5
minute presentation is scheduled
on September 25 during the class
time slot.
 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).
 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:
 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
webpage. 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/CCCG2020textemplate.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): (initial proposal and presentation 10% +
Final Report 25% + Talk 20%)
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 ACMSIAM
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
24. Your 5
minute presentation is scheduled
on September 25 during the class
time slot.
 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).
 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:
 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 4 pages long
and will be posted on the course
webpage.
 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/CCCG2020textemplate.zip
SCHEDULE OF FALL 2024 Term
Sep 04: Introduction + MWU Method
 MWU
 Arora, Hazan and Kale, The multiplicative
weights update method: a metaalgorithm and
applications, Theory of Computing 8(1): 121164,
2012.
 Chapter 11 in Notes.
 Summary
on MWU (with extra material)
 MWIS
 U. Feige
and D. Reichman, Recoverable
values for independent sets,
Random Structures and Algorithms
46(1): 142159, 2015.
Sep 11: MWU
 Randomized
Schemes +
MWIS Analysis + LSH
 LocalitySensitive Hashing
Sep 18: LSH + LP's using MWU
+ Local Search
 LPs using MWU
 See Section 11.3 of Notes
 Sensitive Family
Sep 25: Short Presentations on Projects + 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 kmedian and facility location
problems, SIAM Jl. Computing 33(3): 544562, 2004.
 N.H. Mustafa and
S. Ray, Improved results on geometric hitting set
problems, Discrete and Computational Geometry
44:883895, 2010
 R. Aschner, M.J.
Katz, G. Morgenstern and Y. Yuditsky, Approximation
schemes for covering and packing, WALCOM, Lecture
Notes in Computer Science 7748: 89100, Springer,
2013.
 Chapter 14.2 in
Notes
Oct 02: Proof of kMedian +
Geometric hitting sets via local
improvement
 Analysis of 5approximation for kmedian in metric graphs.
 (1+\epsilon)approximation for hitting set of disks.
 Summary
on Local Search
Oct 09: Clustering
Oct 16: BM Talks about Graph
Separation
 Planar Graph Separators
 Fredrickson's rpartitioning
 Applications
 Cycle Separators
 See Bobby's Notes
 Also, refer to Chapter 7 of
Notes for some of the topics in this
lecture.
Oct 30: Dimensionality
Reduction +
LocalitySensitive
Orderings
Nov 06: Dimensionality
Reduction +
LocalitySensitive
Orderings
(Contd.)
Nov 13: LLL Talk +
Nov 20: Presentations on Projects
Nov 27: Presentations on Projects
Dec 04: End Term Quiz
PREVIOUS TERM Schedule:
W1: Introduction + MWU Method
(Deterministic Schemes) + LSH (Jaccard
Similarity and Signatures)
W2: MWU  Randomized Schemes
+ LSH
W3: LPs using MWU + Sensitive
Family of LSH functions + MWIS
W4: Short Presentations on Projects +
MWIS +
Approximation
Algorithms 
Local Search
(Weighted
MaxCut)
W5:
Approximation
via Local
Search
(kmedian) +
Max kcoverage
W6:
Locality
Sensitive
Orderings +
Dimensionality
Reduction
W7:
Locality
Sensitive
Orderings +
Dimensionality
Reduction
W8:
Dimensionality
Reduction and
Online
Bipartite
Matching
W9:
Dimensionality
Reduction +
Online
Matching
 Proof
of JL Theorem
 LP
Duality and
Proof of
Greedy
Matching
 Fractional
Matching
W10:
Waterlevel
Algorithm for
Fractional
Matching + LP
rounding
Algorithms
 MaxWeight Independent Set of Intervals using
LP Rounding (see Exercises 14.1214.20 in Notes)
W11:
Approximation
Algorithms
(using LP)
 Min Cost stcuts,
Multiway Mincuts, Multicuts in
Graphs
 Garg, Vazirani and Yannakakis,
Primaldual approximation algorithms for
integral flow and multicuts in trees,
Algorithmica 18(1): 320, 1997.
 Garg, Vazirani and Yannakakis,
Multiway cuts in node weighted graphs,
Journal of Algorithms 50(1): 4961, 2004.
 Calinescu, Karloff and Rabani,
Approximation algorithms for the 0extension
problem, ACMSIAM SODA 2001.
 Fakcharoenphol, Rao and Talwar, A
tight bound on approximating arbitrary metrics
by tree metrics, JCSS 69(3): 485487, 2004
 The design of approximation
algorithms, Williamson and Shmoys, Cambridge
University Press, 2011.
 Chapter 14.3 of Notes