CSCI 2952T: An Algorithmist’s Toolkit

Fall 2024, Brown University

Time and Location
Tuesday, Thursday, 9:00AM – 10:20AM, CIT 477 (Lubrano)

Instructor
Ellis Hershkowitz, CIT 507

Office Hours

Teaching Assistants
Richard Huang
Jay Sarva

Course Description

Doing research in theory and algorithms is often inaccessible because it requires an eclectic mathematical toolkit that is spread over many areas. The goal of this course is to consolidate many of these tools into a single course. Namely, this course will equip students with a mathematical foundation that will allow them to jumpstart their own theory research, particularly in algorithms. The course will cover not only many of the recurring mathematical tools in algorithms but also the ways in which these tools are used to design algorithms with rigorous guarantees. It is intended mainly for early-stage theory graduate students and advanced undergraduates. Some planned topics include polyhedral methods, metric embeddings, techniques from graph theory and the multiplicative weights framework.

Prerequisites:

The only official pre-requisite for the class is CSCI1570.

That said, you should be “mathematically mature” and have a strong background with formal proofs. Ideally, you have some background in and comfort with proof-based algorithm design and analysis. You will also have to know the basics of probability, NP-completeness, linear algebra and calculus.

If you’re unsure if you have an appropriate background feel free to reach out and we can discuss!

Schedule

The class is broken into 7 sections as below.

Date Topic Class Notes Additional Resources
Basic Tools      
Sep 5 (Thurs) Overview of Class + Learning, Doing and Writing Theory Slides on Class Overview and Slides on Learning, Doing and Writing Theory See below links in “Other Resources “
Sep 10 (Tues) Asymptotics Ellis’ notes Asymptopia by Spencer and Florescu or Asymptotic Methods in Analysis by N.G. de Brujin
Sep 12 (Thurs) Common Inequalities Ellis’ notes Cauchy-Schwarz Master Class by J. Michael Steele
Sep 17 (Tues) Common Proof Strategies Ellis’ notes  
Randomization      
Sep 19 (Thurs) Probability Review and Gaussians Ellis’ notes Probability and Computing by Mitzenmacher and Upfal
Sep 24 (Tues) Concentration and Common Randomized Paradigms Ellis’ notes Concentration of Measure for the Analysis of Randomized Algorithms by Panconesi and Dubhashi
Sep 26 (Thurs) Using Randomization: Hypercube Routing Ellis’ notes  
Oct 1 (Tues) The Probabilistic Method, Union Bounds and the LLL Ellis’ notes The Probabilistic Method by Spencer and Alon
Polyhedral Methods      
Oct 3, Oct 8 (Thurs+Tues) Linear Programs: the Algebraic View Ellis’ notes Understanding and Using Linear Programming by Matoušek and Gärtner or Theory of Linear and Integer Programming by Alexander Schrijver or Geometric Algorithms and Combinatorial Optimization by Grötschel, Lovász and Schrijver (if you want to go deep)
Oct 10 (Thurs) Linear Programs: the Linear Algebraic View Ellis’ notes Ellis’ Linear Algebra Review or Linear Algebra Done Right by Axler
Oct 15 (Tues) Linear Programs: the Geometric View Ellis’ notes A Course in Convexity by Barvinok
Oct 17 (Thurs) Using LPs: LP Integrality Ellis’ notes  
Oct 22 (Tues) Duality + Hyperplane Separation Theorems Ellis’ notes  
Oct 24 (Thurs) The Ellipsoid Algorithm Ellis’ notes  
Oct 29 (Tues) Using LPs: Randomized Rounding + Primal-Dual   Approximation Algorithms by Williamson and Shmoys
Geometry and Metric Embeddings      
Oct 31 (Thurs) LPs Meet Metrics: LDDs and Rounding the Multicut LP    
Nov 5 (Tues) No Class, Election Day    
Nov 7 (Thurs) Bourgain’s Embedding   Lecture Notes on Metric Embeddings by Matoušek
Nov 12 (Tues) Random Projections and Johnson-Lindenstrauss    
Cuts and Flows      
Nov 19 (Tues) Multi-Commodity Flow-Cut Gap and Sparsest Cut    
Nov 21 (Thurs) Expanders and Expander Decompositions    
Graph Sparsification      
Nov 21 (Thurs) Cut Sparsification: Gomory-Hu Trees (+ Uncrossing)    
Nov 26 (Tues) Distance Sparsification: Probabilistic Tree Embeddings    
Nov 28 (Thurs) No Class, Thanksgiving Break    
Dec 3 (Tues) Flow Sparsification: Oblivious Routing via Raecke Trees    
Multiplicative Weights      
Dec 5 (Thurs) The Experts Framing   Survey by Arora, Hazan and Kale
Dec 10 (Tues) Fast Multi-Commodity Flow    
Dec 12 (Thurs) Online Set Cover    

Homeworks

The homeworks will be posted on Gradescope. You can ask questions about the homeworks on the Ed Discussion Board.

Exam

The exam will be posted on Gradescope.

Student Responsibilities

Students in the course will be responsible for the following:

Grading

The breakdown of grades is as follows:

with the usual grade assignments (an A is 90% or higher, a B is 80% or higher and not an A etc.). Note the >100% sum above. I may also curve (upwards) depending on averages.

Homework Policies

Homeworks must be typeset in LaTeX. You may discuss problems together in groups of up to four but you must type-up and submit your own original homework. You may use computational mathematics tools to assist you (e.g. WolframAlpha, Maple, etc.). You may not search for answers to homework problems online. You may not use ChatGPT or other LLM tools. Each of your homeworks must state with whom, if anybody, you discussed problems. Homeworks should be turned in via Gradescope. Any homework that does not abide by the above will receive a 0.

Homework Late Days

You have five (5) late days to use on homeworks as you see fit. If you have no remaining late days and your homework is turned in late, you will receive a 0 for it.

Other Resources

Here are some additional resources that you may find useful.

Similar Classes

Some Links About Doing Theory/Math:

Here are some more general links to both talks and blog-post-type writings of various theoreticians and mathematicians that you might find useful.

Accommodations

If you feel you have a disability that could affect your performance in the course, please contact SAS and ask them to contact me. I’ll do whatever I can to support recommended accommodations.

Student Well-Being

Doing theory is extremely difficult if you aren’t feeling physically and mentally well, included and supported by your peers and mentors or otherwise marginalized.

My hope is that this is a welcoming and inclusive course. If you feel you have been mistreated please feel free to contact me directly or consider reaching out to some of the student advocates in the department. If you feel you might be the victim of harassment, consider reaching out to the Brown Title IX Office.

If you feel you are overstretched or otherwise psychologically distressed I encourage you to reach out to Brown CAPS. You may also find these resources from Brown Health and Wellness (and links therein) useful.