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 inheritance, 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 by identifying which data structures to use and applying them. 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 Worksheet Code | Course survey (EOD) |
| 1L | Jan 22 | Set up Music video | |
| 1B | Jan 23 | More Classes Worksheet Code | |
| 2A | Jan 28 | Encapsulation & I/O Streams Worksheet Code | HW1: Beginner Problems |
| 2L | Jan 29 | Bag of Tokens Quiz 1 Music video | |
| 2B | Jan 30 | Memory Management; Inheritance Worksheet Code | |
| 3A | Feb 4 | Interfaces & Generics Worksheet Code | HW2: Flippycard |
| 3L | Feb 5 | Silver Dollar Quiz 2 Music video | |
| 3B | Feb 6 | ArrayLists Worksheet Code History | |
| 4A | Feb 11 | Algorithmic analysis Worksheet Code History | HW3.1: Darwin pt. 1 |
| 4L | Feb 12 | Timing Arraylists Quiz 3 Music video | |
| 4B | Feb 13 | Linked Lists pt 1 Worksheet Code | |
| 5A | Feb 18 | Linked Lists pt 2, Stacks Worksheet Code | HW3.2: Darwin pt. 2 |
| 5L | Feb 19 | Debugger Quiz 4 Music video | |
| 5B | Feb 20 | Stacks & Queues Worksheet Code History | |
| 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 | Minimum Spanning Trees (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 | May 7 | (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
- 30% final project
- 5% quizzes (lowest dropped)
- 5% labs
Completing (i.e., turning in) every assignment is required to pass the course. This course may be taken for a letter grade only. Similiar to CS51P, there might be a slight curve at the end of the semester to bump up grades or more cleanly distribute grades. The curve will never hurt you based off of the raw points percentage.
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.
- Labs are strictly due before Thursday morning (i.e., Wednesday night) if you do not finish them during lab time.
- 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: Students may use ChatGPT/Claude/other LLMs in the course under limited circumstances. First, every usage of generative AI needs to be properly cited and documented, i.e., students should provide a hyperlink to their chat session log in the header comments of their code. Second, students should treat LLMs as the metaphor of a TA. This means the following actions are allowed:
- Asking to generate practice problems
- Asking to explain high level concepts
- Including “do not generate any Java code. Only explain the concepts.” in the prompt.
Students may not use LLMs for:
- Solving homework problems by pasting in the instructions
- Debugging their code by pasting in the code directly
- Generating any code for assignments (please include a ‘do not generate code’ prompt if you are getting assignment help).
Appropriate response to a violation of the AI policy will be determined on a case-by-case basis with a meeting with the instructor.
Resources
This is no required textbook for the course, but students may read Algorithms, 4th edition which loosely follows the structure of the course.
Calendar
- 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
- Mentor Hours7:30–9:30 PMAdrian
-
-
Tuesday
- Lecture2:45–4 PMEdmunds 101
- Office Hours11 AM–12 PMEdmunds 111
- Mentor Hours8–10 PMKellie
-
-
Wednesday
- Lab7–9:50 PMEdmunds 105
- Office Hours4–5 PMEdmunds 111
-
-
Thursday
- Lecture2:45–4 PMEdmunds 101
- Office Hours1–2 PMEdmunds 111
-
-
Friday
- Mentor Hours4–5 PMFrancisco
-
-
Sunday
- Mentor Hours2–4 PMDylan
-
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.