CS62: Data Structures and Advanced Programming
Spring 2025 • Pomona College
Lecture: Tues/Thurs 2:45-4:00pm • Edmunds 101
Lab: Weds 7:00-9:50pm • Edmunds 105
Overview
This course couples work on program design, analysis, and verification with an introduction to the study of data structures that are important in the construction of sophisticated computer programs. Students are expected to program in the object-oriented programming language Java. Students will learn to design complex and reliable software engineering systems through writing code modules that are easy to read, debug, test, verify, analyze, and modify.
Students will learn to analyze programs using big-“O” notation to understand their runtimes, as well as apply affordance analysis, to understand the technical and the ethical trade-offs of using different algorithms and data structures to solve computational problems. This course focuses on the efficiency of writing programs (design) and running programs (runtime).
This course is a prerequisite for most upper level Computer Science courses.
Prerequisites: The formal prerequisite for this course is CS54 at Pomona. We also assume that all students enrolled are comfortable writing small to medium-sized programs (around 500 lines of code with several interacting classes) in either Java or Python. The knowledge assumed is generally equivalent to the different versions of CS51 as offered at Pomona or the Computer Science advanced placement exam. Be aware that neither CS5 nor CS60 at HMC satisfy the prerequisites for this course.
This course is divided into three rough modules (each roughly corresponding to a checkpoint):
-
Java & Basic Data Structures (Weeks 1-5) Let’s transition over from Python to our object-oriented programming (OOP) language Java. We’ll learn the basics of syntax, review classes, and introduce new topics important in OOP design such as inheritence, static versus instance variables, and interfaces. We’ll learn that data structures are abstract and theoretically sound ways for holding and processing data, and we’ll see and analyze our first basic data structures: array lists, singly linked lists, doubly linked lists, stacks, and queues.
-
Sorting & Searching (Weeks 6-11) We’ll cover canonical algorithms that help with sorting data (selection sort, insertion sort, mergesort, quicksort, heapsort) in detail. We’ll talk about data structures for keeping data quickly searchable (namely, lots of different kinds of trees: binary search trees, 2-3 trees, red-black trees…). Along with trees, dictionaries and hash tables are good data structures for solving searching problems.
-
Graphs & Software Engineering (Weeks 12-16) Graphs, as a data structure, do so much for computer scientists. We’ll learn how they’re represented, and several algorithms for traversing them (breadth first versus depth first search), and traversing them efficiently, such as calculating the shortest path between two nodes in a graph. Lastly, we’ll end the class by talking about career paths in software engineering. Your final project will use human-centered design methods to solve real world problems with data structures (TODO: edit this). Hopefully, by the end of this course, you can feel confident in tackling Leetcode problems! (And if you want to learn even more algorithms, take CS140.)
The course website will contain links to the lecture slides (posted before lecture). We will use Gradescope and Github Classroom for lab/assignment submission and grading. The assignments are not posted on the website; they will be released on Canvas (a link to Github Classroom). Please come prepared to lab by fully reading the lab’s README file before the lab session.
The assignments in this class are:
- 10 labs
- 10 weekly coding homeworks, released in lab and due 11:59pm the following Tuesday (some can be done in pairs)
- 10 short quizzes (given at the start of lab)
- 3 checkpoints
- 1 final project (can be done in pairs)
Unlike CS51, the lab section of CS62 is not for starting your homework assignments. Labs are their own assignments that either apply theortical concepts learned in lecture, or teach general software engineering skills, and are to be completed during the evening lab session. If you finish the lab assignment early, you are welcome to stay and get started on your homework in an environment where the course staff are available to help.
In general, students should bring their laptop and something to write with to every class.
Schedule
Schedule subject to change (especially after checkpoint 1 and lab ordering) due to feedback and student needs.
| Week | Date | Topic | Due (11:59pm) |
|---|---|---|---|
| 1A | Jan 21 | Intro & Java Basics | Course survey (EOD) |
| 1L | Jan 22 | Set up | |
| 1B | Jan 23 | Classes & Objects | |
| 2A | Jan 28 | Control Flow & Arrays in Java | HW1: Java Basics |
| 2L | Jan 29 | Bag of Tokens Quiz 1 | |
| 2B | Jan 30 | Memory Management; Inheritence | |
| 3A | Feb 4 | Interfaces & Generics | HW2: Flippycard |
| 3L | Feb 5 | Silver Dollar Quiz 2 | |
| 3B | Feb 6 | ArrayLists | |
| 4A | Feb 11 | Algorithmic analysis | HW3.1: Darwin pt. 1 |
| 4L | Feb 12 | Timing Arraylists Quiz 3 | |
| 4B | Feb 13 | Singly Linked Lists | |
| 5A | Feb 18 | Doubly Linked Lists | HW3.2: Darwin pt. 2 |
| 5L | Feb 19 | Debugger Quiz 4 | |
| 5B | Feb 20 | Stacks & Queues | |
| 6A | Feb 25 | Selection & Insertion Sort | HW4: Calculator |
| 6L | Feb 26 | Checkpoint 1 review Quiz 5 | |
| 6B | Feb 27 | Iterators & Comparators | |
| 7A | Mar 4 | Checkpoint 1 | HW5.1: Compression pt. 1 |
| 7L | Mar 5 | JUnit & Singly Linked Lists | |
| 7B | Mar 6 | Mergesort | |
| 8A | Mar 11 | Quicksort | HW5.2: Compression pt. 2 |
| 8L | Mar 12 | The Unix shell Quiz 6 | |
| 8B | Mar 13 | Heapsort & Priority Queues | |
| 9A | Mar 18 | Spring break 🌱 | |
| 9L | Mar 19 | Spring break 🌷 | |
| 9B | Mar 20 | Spring break 🐣 | |
| 10A | Mar 25 | Binary search trees | HW6: On Disk Sort |
| 10L | Mar 26 | Timing sorting Quiz 7 | |
| 10B | Mar 27 | Dictionaries | |
| 11A | Apr 1 | 2-3 Trees | HW7: Autocomplete |
| 11L | Apr 2 | Checkpoint 2 review Quiz 8 | |
| 11B | Apr 3 | Red-Black Trees | |
| 12A | Apr 8 | Checkpoint 2 | None! |
| 12L | Apr 9 | Version Control | |
| 12B | Apr 10 | Hashtables (pt 1) | |
| 13A | Apr 15 | Hashtables (pt 2) | HW8: Hex-A-Pawn |
| 13L | Apr 16 | Shell scripting Quiz 9 | |
| 13B | Apr 17 | Graphs (BFS & DFS) | |
| 14A | Apr 22 | Shortest paths, Dijkstra's | HW9: Transplant manager |
| 14L | Apr 23 | Binary Search Trees Quiz 10 | |
| 14B | Apr 24 | MST, Kruskal's, Prim's | |
| 15A | Apr 29 | SWE careers panel (Zoom) | HW10: Textgenerator |
| 15L | Apr 30 | Checkpoint 3 review (Zoom) | |
| 15B | May 1 | Final project check-ins (Zoom) | |
| 16A | May 6 | Checkpoint 3 | |
| 16L | Apr 30 | (Optional) Project work time | |
| May 14 | Final project |
Course Staff
More from Prof. Li: This is my second year at Pomona College! I’m happy to be teaching students I taught my very first semester here :) My role in this course is to help you learn data structures (and how to learn data structures), to help facilitate learning from and teaching your peers, and to emotionally and academically support you through the material.
Outside of the classroom, I do human-computer interaction research on various art related things in the Doodle Lab. I’ve lived in the Bay Area for the past decade (I have a BS in EECS from UC Berkeley and a PhD in CS from Stanford) and consider it my home.
My preferred method of contact is the course Slack channel. Slack is great for asking and answering questions: your classmates may have the same questions as you, you may have the answers to your classmates’ questions, and I can upvote and expand on student responses. I will be posting course announcements through Slack as well. Feel free to DM me for individual requests; I will try my best during the weekdays to respond within 24 hours.
Grading
- 30% checkpoints (10% each)
- 30% weekly homework assignments
- 25% final project
- 10% quizzes
- 5% labs
Course Policies
- All homework assignments are due by Tuesday 11:59pm on Gradescope. Like in CS51P, homework assignments have an automatic 19 hour extension to 6:59pm Wednesday (i.e., before lab). If you find yourself struggling to finish the last few parts of the assignment and too tired to focus, go to bed so you can take a fresh look Wednesday morning. If you need an additional extension due to extenuating circumstances (e.g., physical or mental health), please email or Slack the instructor explaining your circumstances before the assignment is due. Work turned in past 6:59pm Wednesday without prior instructor consent will receive 20% off each 24 hours it is past due.
- I strongly believe in mastery based grading and second chances: maybe you had a bad day when you took an exam, which shouldn’t unfairly impact your grade. As such, students may redo their checkpoints for up to 50% of their points lost back within a week of receiving their checkpoint grade. Answer keys will be released after regrades are due. Students are also able to retake up to 5 quizzes by showing up to the instructor’s office hours within a week of originally taking the quiz.
- While lab attendance is required and lecture attendence is highly encouraged, students may have 3 excused absences throughout the semester as long as they inform the instructor prior to their absence.
- Students with disabilities should contact the Student Disability Resource Center (SDRC) to request accommodations, particularly around finding SDRC proctored times for the checkpoints. I am happy to have a conversation with you to help establish the best plan.
- I expect everyone to be an active and engaged member during our class activities. I strive to create an inclusive classroom where every student feels comfortable and safe sharing their thoughts. If I believe you are not participating and learning to the best of your ability, I will send you a message (or please feel free to initiate a conversation with me) so we can brainstorm ways to reduce your barriers to participation.
- All policies are flexible. If you are facing an extenuating circumstance, I am happy to listen and help however possible.
CS62 is a class that is a lot of work: what do you mean we have assignments on top of labs!? Scaling up from writing CS51 sized programs (~100 lines of code) to our larger programs (500-1000 lines) can be intimidating, but the course staff are here to help! If you need support, please come to office/mentor hours or post on Slack. I truly believe that everyone can learn—and excel in—computer science, and that every student should be accomodated to learn at their own pace.
AI Policy: To be discussed and agreed upon in the first lab!
Calendar
(To be filled out by the end of the first week of class)
- 10:00 AM
- 10:30 AM
- 11:00 AM
- 11:30 AM
- 12:00 PM
- 12:30 PM
- 1:00 PM
- 1:30 PM
- 2:00 PM
- 2:30 PM
- 3:00 PM
- 3:30 PM
- 4:00 PM
- 4:30 PM
- 5:00 PM
- 5:30 PM
- 6:00 PM
- 6:30 PM
- 7:00 PM
- 7:30 PM
- 8:00 PM
- 8:30 PM
- 9:00 PM
- 9:30 PM
-
Monday
-
Tuesday
- Lecture2:30 PM–4:00 PMEdmunds 101
- Office Hours11:00 AM–12:00 PMEdmunds 111
-
-
Wednesday
- Lab7:00 PM–10:00 PMEdmunds 105
- Office Hours4:00 PM–5:00 PMEdmunds 111
-
-
Thursday
- Lecture2:30 PM–4:00 PMEdmunds 101
- Office Hours1:00 PM–2:00 PMEdmunds 111
-
-
Friday
Credits
Thank you to Alexandra Papoutsaki (and the long lineage of other Pomona faculty who worked on CS62 before me) for most of the course material. Site theme based on Just the Class, a documentation theme for Jekyll.