CSCI 0500: Data Structures, Algorithms, and Intractability: An Introduction (Fall 2026)

Basic Information

• Lectures: Tue/Thu 2:30-3:50 pm in Friedman Hall 102.
• Instructor: Yu Cheng.
  • Email: yu_cheng@brown.edu
  • Office Hours: after each lecture (until all questions are answered), or by appointment
• TAs:
  • Gabriel Chen (Head TA). Office Hours: TBD.
  • Sophia Li (Head TA). Office Hours: TBD.
  • Andrew Kim. Office Hours: TBD.
  • Chien-Yu Xiong. Office Hours: TBD.
  • Alan Zheng. Office Hours: TBD.
• Textbook:
  • Algorithmic Foundations: Data Structures, Algorithms, and Intractability. Philip N. Klein.

Course Description

This course will cover the basics of how to design and analyze data structures and algorithms. We will develop algorithmic intuition through rigorous analysis of algorithmic correctness and performance. We will also study the theory of NP-completeness, which helps us understand which problems are computationally intractable.

Assignments

• Assignment 0 (Introduction), due on Sep 18 (Fri).
• Assignment 1 (Sorting and Selection).
• Assignment 2 (Arithmetic).
• Assignment 3 (Hash Tables).
• Assignment 4 (Binary Trees).
• Assignment 5 (Matching and 2-Satisfiability).
• Assignment 6 (Shortest Paths and Dynamic Programming).
• Assignment 7 (NP-Completeness).

Labs

• Lab 1 (Sorting and Selection).
• Lab 2 (Arithmetic).
• Lab 3 (Hash Tables).
• Lab 4 (Binary Trees).
• Lab 5 (Bipartite Matching).
• Lab 6 (2-Satisfiability).
• Lab 7 (Shortest Paths).
• Lab 8 (Dynamic Programming).

Schedule

• Week 1 (Sep 7): Introduction.
  • Introduction to the Course, Polynomial Evaluation (Lecture 1).
• Week 2 (Sep 14): Asymptotic Notations.
  • Asymptotic Notations, Insertion Sort (Lecture 2).
  • Merge Sort, Quickselect (Lecture 3).
• Week 3 (Sep 21): Sorting and Selection.
  • Quicksort, Lower Bound on Sorting (Lecture 4).
  • Modular Exponentiation, Integer Multiplication (Lecture 5).
• Week 4 (Sep 28): Arithmetic.
  • Quotient and Approximate Reciprocal (Lecture 6).
  • Hash Tables, Chaining (Lecture 7).
• Week 5 (Oct 5): Hash Tables.
  • Hash Functions, Universal Hashing (Lecture 8).
  • Midterm Exam 1 (in person): Oct 8th (Thu), 2:30pm - 3:50pm.
• Week 6 (Oct 12): Data Structures I.
  • Priority Queues, Binary Heaps (Lecture 9).
  • Binary Search Trees, Range Search (Lecture 10).
• Week 7 (Oct 19): Data Structures II.
  • Range Aggregation Queries, Treaps (Lecture 11).
  • Graphs, Bipartite Matching (Lecture 12).
• Week 8 (Oct 26): Graphs I.
  • Augmenting Paths, 2-SAT (Lecture 13).
  • Strongly Connected Components, Kosaraju's Algorithm, Topological Sorting (Lecture 14).
• Week 9 (Nov 2): Graphs II.
  • Shortest Paths, Dijkstra's Algorithm (Lecture 15).
• Week 10 (Nov 9): Graphs III.
  • Midterm Exam 2 (in person): Nov 10th (Tue), 2:30pm - 3:50pm.
  • Minimum Spanning Trees, Prim's Algorithm (Lecture 16).
• Week 11 (Nov 16): Dynamic Programming.
  • Widest Paths, Dynamic Programming, Longest Common Subsequence (Lecture 17).
  • Decision Problems, Polynomial-Time Reductions (Lecture 18).
• Week 12 (Nov 23): AMA.
  • Ask Me Anything (Lecture 19).
• Week 13 (Nov 30): Intractability I.
  • 3-SAT, Gadget-Based Reductions (Lecture 20).
  • P, NP, NP-Completeness (Lecture 21).
• Week 14 (Dec 7): Intractability II.
  • Cook-Levin Theorem (Lecture 22).
  • TBD (Lecture 23).
• Final Exam (in person): Dec 21st (Mon), 9:00am - 11:00am.

Grading

• Assignments (15%): There are written assignments with proof-based questions.
• Labs (10%): There are lab sessions where students program and test algorithms for correctness and performance.
• Workshops (10%): There are short sessions during lecture time where students are asked to solve a problem and produce a short write-up.
• Midterm Exam 1 (20%): Oct 8th (Thu), 2:30pm - 3:50pm.
• Midterm Exam 2 (20%): Nov 10th (Tue), 2:30pm - 3:50pm.
• Final Exam (25%): Dec 21st (Mon), 9:00am - 11:00am.

Academic Integrity

Academic achievement is evaluated on the basis of work that a student produces independently. A student who obtains credit for work, words, or ideas that are not the products of their own effort is dishonest. Such dishonesty undermines the integrity of the academic standards of the University. Infringement of the Academic Code entails penalties ranging from reprimand to suspension, dismissal, or expulsion from the University. Students who have questions about any aspect of the Academic Code should consult the instructor or an academic dean.

Disability Policies

Brown University is committed to full inclusion of all students. Students who need accommodations should reach out to Student Accessibility Services (SAS) for assistance (sas@brown.edu, 401-863-9588, Brown SAS Website).

Religious Holidays

Students who wish to observe their religious holidays shall inform the instructor within the first four weeks of the semester, unless the religious holiday is observed in the first four weeks. In such cases, students shall notify the instructor at least five days in advance of the date when they will be absent. The instructor shall make every reasonable effort to honor the request.