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

Basic Information

• Lectures: Mon/Wed 3:00-4:20 pm in Friedman Hall 108.
• Instructor: Yu Cheng.
• Email: yu_cheng@brown.edu
• Office Hours: after each lecture (until all questions are answered), or by appointment
• TAs:
• Ethan Park (Head TA). Office Hours: Wed 1-2pm in CIT 201.
• Jacob Schmidman (Head TA). Office Hours: Thu 12-1pm in CIT 269.
• Lisa Baek. Office Hours: Tue 4-5pm in CIT 348, Thu 12-1pm in CIT 269.
• Phila Dlamini. Office Hours: Mon 1-2pm in CIT 201, Fri 5-6pm in CIT 209.
• Kevin Luo. Office Hours: Mon 1-2pm in CIT 201, Wed 1-2pm in CIT 201.
• Akshaya Minupala. Office Hours: Tue 12-1pm in CIT 210, Thu 7-8pm in CIT 367.
• Benjamin Pomeranz. Office Hours: Tue 4-5pm in CIT 348, Thu 7-8pm in CIT 367.
• Eric Xia. Office Hours: Tue 12-1pm in CIT 210, Fri 5-6pm in CIT 209.
• Textbook:
  • Algorithmic Foundations: Data Structures, Algorithms, and Intractability. Philip 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, due on Sep 24 (Wed).

Labs

• Lab 1 (Sorting).

Schedule

• Week 1 (Sep 1): Introduction I.
  • Introduction to the Course (Lecture 1).
• Week 2 (Sep 8): Introduction II.
  • Polynomial Evaluation, Fast Exponentiation (Lecture 2).
  • Asymptotic Notations, Insertion Sort (Lecture 3).
• Week 3 (Sep 15): Sorting.
  • Merge Sort, Counting Inversions (Lecture 4).
  • Quickselect, Quicksort (Lecture 5).
• Week 4 (Sep 22): Arithmetic.
  • Integer Multiplication, Fast Fourier Transform (Lecture 6).
  • Quotient and Remainder, Approximate Reciprocal (Lecture 7).
• Week 5 (Sep 29): Hashing.
  • Hash Tables, Chaining (Lecture 8).
  • Hash Functions, Universal Hashing (Lecture 9).
• Week 6 (Oct 6): Data Structures I.
  • Priority Queues and Heaps (Lecture 10).
  • Binary Search Trees, Treaps (Lecture 11).
• Week 7 (Oct 13): Data Structures II.
  • Range Search, Range Aggregation Queries (Lecture 12).
• Week 8 (Oct 20): Graphs I.
  • Midterm Exam (in person): Oct 20th (Mon), 3:00pm - 4:20pm.
  • Bipartite Matching (Lecture 14).
• Week 9 (Oct 27): Graphs II.
  • More on Bipartite Matching (Lecture 15).
  • Boolean Formulas, Satisfiability (Lecture 16).
• Week 10 (Nov 3): Graphs III.
  • 2-SAT, Topological Sorting (Lecture 17).
  • Shortest Path, Dijkstra's Algorithm, Bellman-Ford Algorithm (Lecture 18).
• Week 11 (Nov 10): Graphs IV.
  • Minimum Spanning Tree, Prim's Algorithm (Lecture 19).
  • Kruskal's Algorithm, Union-Find, Traveling Salesman Problem (Lecture 20).
• Week 12 (Nov 17): Intractability I.
  • Decision Problems, Polynomial-Time Reductions (Lecture 21).
  • Vertex Cover, 3D Matching, Hamiltonian Cycle, Graph Coloring (Lecture 22).
• Week 13 (Nov 24): Intractability II.
  • Finite Automata, Turing Machines (Lecture 23).
• Week 14 (Dec 1): Intractability III.
  • Nondeterministic Turing Machines, P and NP (Lecture 24).
  • NP-Completeness, Cook-Levin Theorem (Lecture 25).
• Week 15 (Dec 8).
  • Ask Me Anything (Lecture 26).
• Final Exam (in person): Dec 20th (Sat), 2:00pm - 4:00pm.

Grading

• Assignments (30%): There are weekly written assignments with proof-based questions.
• Labs (10%): There are weekly lab sessions where students program and test algorithms for correctness and performance.
• Workshops (10%): There are 10-minute workshop sessions during lecture time where students are asked to solve a problem and produce a short write-up, often on material that will appear later in the lecture.
• Midterm exam (20%): Oct 20th (Mon), 3:00pm - 4:20pm.
• Final exam (30%): Dec 20th (Sat), 2:00pm - 4:00pm.

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 which are not the products of his or her own effort is dishonest. Such dishonesty undermines the integrity of 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 on any aspect of the Academic Code should consult the instructor or one of the deans of the Graduate School to avoid the serious charge of academic dishonesty.

Disability Policies

Brown University is committed to full inclusion of all students. Any student with a documented disability is welcome to contact the instructor as early in the semester as possible so that reasonable accommodations can be arranged. If you need accommodations around online learning or in-classroom accommodations, please be sure to reach out to Student Accessibility Services (SAS) for their assistance (sas@brown.edu, 401-863-9588, Brown SAS Website). Students may also speak with Student Accessibility Services at 401-863-9588 to discuss the process for requesting accommodations.

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, the students shall notify the faculty member at least five days in advance of the date when he/she will be absent. The instructor shall make every reasonable effort to honor the request.