Logistics:
| Course Code: | CS-2212-1 |
| Credits: | 4 |
| Classes: | Tuesdays and Thursdays, 8:30am |
| Classroom: | TBD |
| Teaching Staff: | Satpreet Makhija (teaching fellow) |
Links:
| Course Outline and Seminars |
| Resources and Reading List |
Course Description:
Niklaus Wirth titled his 1976 book Algorithms + Data Structures = Programs, an equation as close to a definition of our discipline as we are likely to get. Computing is, in no small part, the art of choosing well between these intertwined halves. But the equation, taken at face value, is misleading in its symmetry. It suggests that the two summands are independent contributions, to be developed in parallel and combined at the end. They are not. The choice of data structure is, more often than not, the choice of algorithm in disguise: settle the representation, and the procedure is half-written before you have begun.
This course begins from that unity. Data structures and algorithms are not two subjects placed side by side, but two perspectives on the same act of thought: the organization of information and the transformations that organization permits.
From there, we turn to a disunity: the separation of interface (what a thing does, its purpose) from implementation (what a thing is, its form). This separation is arguably the most revolutionary idea in software engineering. It is what makes large-scale systems possible, what lets us write modular code, reason about one component without holding the rest of the program in our heads, and swap a library for a better one without rewriting the programs that depend on it. The distinction builds on Introduction to Computer Science, where we looked at specifications through pre- and post-conditions. A specification is a contract between a piece of code and its user: the interface states the promise, the implementation keeps it. A discipline that holds these two apart rigorously is a discipline that can build things too large for any single mind to grasp. This separation also gives us the right way to define correctness for a data structure: an implementation is correct when it is faithful to its interface, when the contract is kept.
Finally, we will look at efficiency. Efficiency is never absolute; it is a negotiation among competing costs: time against space, worst case against expected case, the cost of building a structure against the cost of querying it. We will examine different implementations of the same interface and compare them along several axes, including time, memory, ease of design, ease of understanding, and ease of reasoning about correctness. Learning to navigate this space of choices is one of the central intellectual habits this course aims to build.
These three goals, namely unity, separation, and tradeoff, will be pursued through a sequence of structures of increasing subtlety: the linear (lists, arrays, dynamic arrays and the amortized analysis they invite); the hierarchical (abstract data types, binary and balanced search trees, heaps both eager and lazy); the probabilistic (hashing and its theory, skip lists); the string-oriented (tries and range queries); and the relational (graphs and their fundamental traversals). At its core, this course will show you how data can be represented and transformed. It will give you a way of thinking precisely about computation, and hand you the epistemological tools of a computer scientist: the discipline of separating what from how, the habit of analysing before believing, the instinct to ask not whether a thing works but at what cost, and, in the end, the strange and durable pleasure of thinking like one.
A note on languages: I will use OCaml throughout. Its type system makes abstract data types literally abstract, and its blend of functional and imperative styles lets us discuss the tradeoff between sharing and mutation without ideology. That said, the concepts in this course are language-independent, and students are welcome to implement their programs in any of Python, C, C++, Java, OCaml, or Rust. Each teaches something different about the same structure.
Learning Outcomes: By the end of this course, students will be able to:
- Separation of Interface and Implementation: Specify a data structure as an interface, give multiple implementations of it, and establish correctness as fidelity of the implementation to the interface.
- Efficiency and Tradeoffs: Analyze data structures along axes of time, space, worst case, and expected case using asymptotic, amortized, and probabilistic methods, and defend a choice of implementation in context.
- Algorithmic Thinking: Identify the structural features of a problem that admit an efficient solution, design an algorithm that leverages them, and prove its correctness and complexity.
- Programming: Implement the data structures and algorithms of the course in a programming language, and verify their behavior through testing and empirical measurement.
Grading:
- In-class assessments (42%): Short assessments conducted during regular class hours.
- Final exam (25%): Comprehensive end-of-semester assessment.
- Programming tests (16%): Timed practical tests implementing course structures and algorithms.
- Mid-semester viva (9%): Oral examination on course material at the midpoint of the semester.
- Daily problems (8%): Short problems set with regular coursework.
Grading Rubric:
| Grade | Quality Points | Faculty Rubric |
|---|---|---|
| A | 4.00 | 90–100 |
| A− | 3.70 | 85–89 |
| B+ | 3.30 | 80–84 |
| B | 3.00 | 75–79 |
| B− | 2.70 | 70–74 |
| C+ | 2.30 | 65–69 |
| C | 2.00 | 60–64 |
| C− | 1.70 | 55–59 |
| D+ | 1.30 | 50–54 |
| D | 1.00 | 45–49 |
| D− | 0.70 | 40–44 |
| F | 0.00 | 0–39 |
Attendance: 3 excused absences are allowed in this course lecture. 3 additional excused absences are allowed for sportspersons. Attendance is mandatory. To take a course is to engage with its material, not merely to pass its tests. That said, there are no incentives for attendance and no penalties for absence. You are responsible for your own learning. If you choose to skip a lecture, or cannot attend for any reason, that decision is yours: the consequences, whatever they may be and however they may affect your grade, are yours as well. This course does not offer any accommodations for missed classes or assessments. Class recordings and slides will not be shared.
Policies: From Ashoka's Academic Integrity Policy (MyAshoka → Information and Documents → Office of Academic Affairs): plagiarism—which is a matter of producing academic work that borrows, without acknowledging, from another person's work—is a serious academic offense. All violations of Academic Integrity Policy (including but not limited to plagiarism and the use of AI or other tools) will result in an F grade for the course. Please familiarize yourself with the policies and sanctions.
Support: Students are encouraged to reach out to University offices such as the Office of Learning Support, Ashoka Center for Well-Being, and Center for Writing and Communication for additional support.