Design and Analysis of Algorithms (Fall 2026)
Design and Analysis of Algorithms (Fall 2026)
Algorithms are easy to overlook in the current computing landscape, but they remain fundamental. Many modern computation applications are closely related to algorithms, e.g., memory management and I/O scheduling, query planning in databases, routing in networks, and training and inference of neural networks. For applications in machine learning in particular, techniques including matrix multiplication, nearest-neighbor search, clustering, and graph partitioning appear throughout. Algorithms with provable guarantees tell us what these tasks cost, how to design an efficient method, and when no such efficient method can exist.
This course presents the fundamental techniques that produce those guarantees. We will study several design principles in depth — greedy algorithms, divide and conquer, dynamic programming, network flow, randomization, and approximation — along with the theory of computational hardness, which tells us when to stop looking for an exact efficient algorithm. After completing this course, students should be able to design and analyze efficient algorithms for a variety of computational problems and to understand algorithms with rigorous proofs.
Course Number: CSCI 4020
Credit Hours: 4.0
Semester / Year: Fall 2026
Lectures: Monday/Thursday noon - 1:50 pm
Room Location: Carnegie 206
The official prerequisites for the course are CSCI 2300 and either MATH 2800 or CSCI 2200 (implied by CSCI 2300). We will assume that everyone has seen the material in these courses and will use it as necessary.
Specifically, from CSCI 2300 this includes elementary data structures, binary search, sorting, big-O notation, and basic terminology involving graphs (including the concepts of depth-first search, breadth-first search, and connectivity). Some topics in CSCI 4020 are similar to those covered in CSCI 2300: we will cover them in much greater depth and consider much more complex applications of these algorithm design techniques than in CSCI 2300.
The prerequisites for this course also include a background in discrete mathematics, including order of function growth, sets, recurrence relations, and proof techniques such as induction and contradiction. This also includes strong and structural induction. The lectures and homework involve the analysis of algorithms at a fairly mathematical level. We expect everyone to be comfortable reading and writing proofs.
If you did not take a corresponding course, you must contact the instructor by the first week of classes.
You can follow this handout to test your knowledge of the prerequisites for the course.
Upon completion of the course, students are expected to have the following skills.
Be able to understand the analysis of commonly used algorithms
Understand algorithm design principles, including greedy algorithms, divide and conquer, and dynamic programming, and their analysis
Understand the model of computation and the conditional time lower bounds
Understand the notion of approximation algorithms and their analysis
Understand the roles of randomization in algorithm design
Chen Wang
Email: wangc33@rpi.edu (please only use this email address for course-related communications)
Office hours: Wednesdays 3:00 - 5:00 pm
Office location: MRC 310
Rohit Muralitharan,
Email: muralr@rpi.edu
TA duties include grading and Q&A via email. No dedicated office hours.
If you need 1:1 meetings with the TA, send emails to book appointments.
In-class quizzes (20%):
5 in-class quizzes
We will use the 4 highest in the final assessment
(If we ended up having X quizzes, we use the highest X-1)
Homeworks (10%):
One homework every 2-3 weeks
The value of homework: midterm and final questions are closely related to homework problems; some questions are homework questions with additional constraints and/or changed parameters that essentially follow the same proof ideas
You'll get grades, and more importantly, feedback and comments for your solutions
Midterms I & II (20% + 20%):
Please see the detailed schedule for midterm dates
Questions are closely related to homework problems
Final (30%):
Final exam date TBD
Attendance (5% extra credit):
Attendance is not mandatory, but they carry 5% of additional credits
A proof is something that is absolutely convincing to you. Most of the homework and exam questions should admit short proofs when you know the ideas. The purpose of writing a proof is to communicate what has convinced you to the readers. If you do NOT know the proof, you should not talk about the problem over and over as if something has convinced you.
If you genuinely cannot prove something, write "I don't know" on homework or exam problems, and it will give you 25% credit. If you answer anything worth partial credit, it will give you more than 25%. However, a completely wrong and irrelevant answer will lead to 0%.
Homework 1
Homework 2
Homework 3
Homework 4
Homework 5
Homework 6
Homework 7 (for excercise only)
Greedy Algorithms: interval scheduling; the exchange argument; minimum spanning trees; linkage-based clustering; set cover
Divide and Conquer: recurrences and the master theorem; integer multiplication; closest pair of points; fast matrix multiplication (Strassen algorithm).
Dynamic Programming: weighted interval scheduling; memoization; knapsack and subset sum; pseudo-polynomial time algorithms; sequence alignment; shortest paths with negative weights (Bellman-Ford algorithm).
Network Flow: Maximum flow and minimum cut; Ford-Fulkerson and augmenting paths; capacity scaling and Edmonds-Karp; bipartite matching: Hall's theorem, edge-disjoint paths and Menger's theorem; applications.
Randomized Algorithms: linearity of expectation and concentration inequalities; randomized selection and quicksort; Karger's algorithm for minimum cut; dimensionality reduction (Johnson-Lindenstrauss) and locality-sensitive hashing for nearest-neighbor search.
NP-Completeness and Intractability: polynomial-time reductions; Turing machine; P, NP, and NP-completeness; the Cook-Levin theorem; reductions for independent set, vertex cover, clique, dominating set, Hamiltonian cycle, traveling salesperson, and subset sum.
Approximation Algorithms: Approximation ratios. Greedy approximation for k-center and set cover; algorithms for maximum cut; approximation schemes and PTAS
Selected Additional Topics (if time): online algorithms and competitive ratio analysis; algorithms with predictions.
Schedule: A tentative schedule of the topics can be found here (RPI internal access only). The schedule is not final and is subject to changes.
Lecture 1: Introduction and math refresher. (Slides for RPI internal access only)
Lecture 2: Greedy Algorithm: interval scheduling and minimizing lateness (notes).
Lecture 3-4: Greedy Algorithm: MST and hierarchical clustering (notes).
Lecture 4-5: Greedy Algorithm: approximate set cover (notes).
We will mostly use the following two textbooks, although having them is not mandatory.
Algorithm Design by Jon Kleinberg and Eva Tardos.
Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
The following textbooks are also helpful.
The Design and Analysis of Computer Algorithms by Alfred Aho, Jeffrey Ullman, and John Hopcroft
Algorithms by Christos Papadimitriou, Sanjoy Dasgupta, and Umesh Vazirani
The Rensselaer Handbook of Student Rights and Responsibilities and The Graduate Student Supplement define various forms of Academic Dishonesty, and you should make yourself familiar with these. In this class, all assignments that are turned in for a grade must represent the student’s own work. Discussion and resorting to external resources are allowed; however, a notation on the assignment should indicate your collaboration.
Submission of any assignment that is in violation of this policy may result in a penalty of a direct F grade in the course and/or referral to the appropriate Dean (Dean of Students for undergraduate students or the Dean of Graduate Education for graduate students, respectively).
Discussion between the students and between groups is allowed and encouraged. However, you cannot let another person do your homework and claim they are your answers. In other words, you must demonstrate that you understand what you wrote on the homework.
Large language models (LLMs) policy: Using LLMs to produce solutions to homework problems is prohibited. Using LLMs to help you understand course material is permitted (and encouraged). Ask them to explain a definition, work through an example, or check whether you have understood a proof from lecture. The distinction is whether the model is doing the reasoning or you are, and whether you are using LLMs as learning resources or "agents" to cheat.
LLMs will produce plausible-looking solutions to most problems in this course, and reading that solution will feel like understanding it. It is not the same thing, and the difference will show up on the exams, which account for the majority of your grade.
If you are suspected of copying from LLMs and/or other students, you will receive a notification from me, and it is your responsibility to justify why it is not the case.
Discrepancies in Understanding: Since there are significant overlaps between the homework and exam questions, if there is a significant difference between your performance on the homework and the exam, you'll need to explain this discrepancy.
If you have any questions concerning this policy before submitting an assignment, please ask for clarification.
Rensselaer Polytechnic Institute strives to make all learning experiences as accessible as possible. If you anticipate or experience academic barriers based on a disability, please let me know immediately so that we can discuss your options. To establish reasonable accommodations, please register with The Office of Disability Services for Students. After registration, make arrangements with the Director of Disability Services as soon as possible to discuss your accommodations so that they may be implemented in a timely fashion. DSS contact information: dss@rpi.edu; +1-518-276-8197; 4226 Academy Hall.