CS3000 Algorithms and Data – 2023 Summer 2
Dates: [3rd July — 17 August] 2023
Location: Richards 165 (all in-person)
Instructor: Akshar Varma (varma.ak@northeastern.edu)
| Time | Mon | Tue | Wed | Thu | Type |
|---|---|---|---|---|---|
| 0950 – 1130 | ✓ | ✓ | ✓ | ✓ | Lectures |
| 1140 – 1245 | 💁 | ✓ | 💁 | ✓ | Recitations |
💁 – Akshar's OH
Attendance is expected and strongly encouraged in both lectures and recitations but is not mandatory.
| Canvas (Piazza link) | discussion forum, primary class announcement medium |
| Gradescope | problem set submissions, quizzes, solution feedback, re-submissions |
| Syllabus and Schedule | each day's topics, lecture slides, readings, problem set/quiz dates |
| Assessment Summary | summary of assessment criteria |
| Grading, Policies, Logistics | more detailed assessment philosophy and other logistics |
| Recommended programming problems | suggested programming problems for practice (ungraded) |
Office Hours:
| Staff | Name | Office Hours | Location |
|---|---|---|---|
| Instructor | Akshar Varma | 1130 – 1300 MW | Richards 165 |
| TA | Nolan Lemery | TBD | TBD |
| TA | Ankit Ramakrishnan | TBD | TBD |
Discussion Forum: Piazza
We will be using Piazza as a common forum for class discussion which will make it possible to get help quickly and efficiently from all participants in the course. To promote efficient and collaborative discussions within the course, I strongly encourage you to post on Piazza before emailing questions to the teaching staff (unless you are certain your query only applies to you).
You should all have been automatically added on Canvas, if not, please contact me and I will add you. You'll also find the Piazza link there and it should have the option to enroll without needing the access code.
Assessment: Gradescope
All problem set submissions (typeset using LaTeX), quizzes, and all feedback you receive from on your solutions will be on Gradescope. You should all have been automatically added on Gradescope, if not, please contact me and I will add you.
Assessment Summary and Grading, Policies, Logistics:
See the first page for a summary of assessment criteria for problem sets, quizzes, exams, collaboration, programming problems and course grade. The second contains more detailed assessment philosophy and details about various other logistical matters including LaTeX, academic integrity, accessibility and DRC among others.
Textbooks and references
I do not believe you will need to buy any textbook for this course (unless you really want to). Most of the required material can be found online for free, in various places. I will try my best to link to relevant material as and when they become relevant. The lecture slides are also acceptable as a reference.
The following are the books I'll recommend. I'll often link to (chapters/sections from) the first three ([KT], [DPV], [JE]) as readings for specific lectures (as seen in Syllabus and Schedule). One of these always show up as textbooks or references in any Algorithms course taught at this level, so you won't go wrong using any of these; beyond that it depends on your taste and learning style.
| Abbreviation | Name | Authors | Notes |
|---|---|---|---|
| [KT] | Algorithm Design | Kleinberg and Tardos | Official Slides |
| [DPV] | Algorithms | S. Dasgupta, C. H. Papadimitriou and U. V. Vazirani | Official, free PDF |
| [JE] | Algorithms | Jeff Erickson | freely available online (CC BY 4.0) |
| [CLRS] | Introduction to Algorithms | Cormen, Leiserson, Rivest, Stein | quite verbose (which can be good) |
| but considered to be the reference text | |||
| [Sk] | Algorithm Design Manual | Steven Skiena | focus on the thought process behind algorithm design |
| also, recommended by TeachYourselfCS.com folks | |||
| [LLM] | Mathematics for Computer Science (2018) | Lehman, Leighton, and Meyer | PDF (2018); on Wikimedia Commons (2017); on OCW (2010) |
| [MMF] | Building Blocks for Theoretical Computer Science | Margaret M. Fleck | freely available online |
| Study Problems (offshoot of [MMF]) | Margaret M. Fleck | freely available online |
The last book is a useful resource to brush up on basic discrete mathematics that is ubiquitous in this course (particularly induction (see the study problems as well)).
Also useful: Vamanos demos which contains visualizations for: mergesort, factorial, Karatsuba, LIS (simplified), BFS, DFS, Dijkstra, Prim, Kruskal, Bellman-Ford, Ford-Fulkerson
Manim: Master Theorem (MP4), Quicksort (YouTube), Mergesort (YouTube).
Magic systems in fantasy are mysterious in the same way as computer systems are.
Feel free to use anything else that you find useful; you are also encouraged to share nice resources on Canvas. Please include a short description of what it helped you with and why.
Course Description
This is an introductory undergraduate course in algorithms. Every computer program can be viewed as an implementation of an algorithm for solving a particular computational problem. The focus of this course is on learning algorithm design techniques for solving the underlying computational problems. While we will look at how algorithms translate to programs, our emphasis will be on the algorithm design and analysis. In this class, you will
- Come across a range of computational problems that arise in diverse applications
- Learn to formulate precise problem statements from vague/informal descriptions
- Build a repertoire of common algorithmic design techniques/paradigms
- Learn proof techniques critical for reasoning about (the correctness of) algorithms
- Learn analysis techniques critical to determine the (time and space) efficiency of algorithms
Specific topics covered in the course (also see Syllabus and Schedule) will be a subset of:
- Basics tools for reasoning about and analysis of algorithms: asymptotic notation, proofs by induction and contradiction.
- Number theoretic algorithms: GCD, modular arithmetic, fast exponentiation, Diffie-Hellman(-Merkle) key exchange
- Divide-and-conquer algorithms: merge sort, closest-pair, $k$-selection, etc.
- Dynamic programming: Edit distance, RNA folding, Knapsack, Traveling salesman
- Basic graph algorithms: BFS, DFS, topological sorting, strongly connected components
- Graph optimization: shortest paths, minimum spanning trees
- Greedy algorithms: interval scheduling, fractional knapsack, graph coloring, proof strategies
- Network flow: max-flow-min-cut, Ford-Fulkerson, reducing problems to max-flow and min-cut
- Linear Programming: using LP as a tool by formulating problems as an LP.
- Randomized algorithms: primality testing, quicksort, LP randomized rounding, etc.
- Approximation algorithms: Traveling salesman, LP based
- Reductions and NP-completeness
Map of CS3000 Algorithms Landscape
