Course Description

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. Because we will be interested in studying more modern techniques for designing large, complex, and reusable code, we will be using the object-oriented programming language, Java.

You will be expected to write a collection of programs, ranging from very short programs to more elaborate systems. Since one of our goals in this course is to teach you how to write large, reliable programs composed from reusable pieces, we will be emphasizing the development of clear, modular programs that are easy to read, debug, verify, analyze, and modify.

Equally important is the ability to analyze programs using big-"O" notation to understand their runtimes. This will help us evaluate the trade-offs in different choices of algorithms and data structures.

The formal pre-requisite for this course is Pomona CS 54. 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, Python, or Grace. The knowledge assumed is generally equivalent to that of CSCI 051 as offered at either Pomona or CMC or the Computer Science advanced placement exam. Be aware that neither CS 5 at HMC or CS 30 at Pomona satisfy the prerequisites for this course. If you have any doubts as to whether your programming experience is sufficient for this course, please see us as soon as possible.

By the end of this course, you should have a good understanding of object-oriented design, coding and debugging of programs in Java, and of how one might analyze programs for efficiency. In particular, you will understand the trade-offs involved in selections of different data structures and algorithms to solve computational problems.

This course is a prerequisite for most upper level Computer Science courses. As part of continuing curricular changes in CS, sections of CS 62 will no longer teach C or C++. Instead that material will be taught in CS 105 taught at Pomona. Students should be aware, however, that sections of CS 105 taught at HMC will assume programming background in C. Thus students wishing to take that course at HMC will be required to learn C on their own.

Academic Accommodations

If you are seeking academic accommodations, you must contact your home college’s disability coordinator to establish accommodations. You should plan to meet with your coordinator to discuss appropriate accommodations and may be asked to provide documentation necessary to verify disabilities. Further information is available from the Student Disability Resource Center at CUC. Once your coordinator verifies your status, we will receive an email from them indicating what accommodations are recommended.

Use of electronics in the classroom

Several studies (and our in-person personal experience) have shown that use of electronic devices can be distracting and interfere with learning. We understand that after more than a year of remote learning this might have changed. We ask you to use laptops, tablets, and cell phones only if they are necessary for classroom activities, e.g., to take notes.

COVID-19 Safety Awareness

The faculty at Pomona College knows that person-to-person interaction provides the best liberal arts education. The best learning occurs in small communities. This year we are gathering in person and online for what we do best: create, generate, and share knowledge. During the past academic year, we built community remotely, and this year we will build on the pedagogical improvements we acquired last year. For example, some of our office hours and written Q&As will be online.

Our health, both mental and physical, is paramount. We must consider the health of others inside and outside the classroom. All Claremont Colleges students have signed agreements regulating on-campus behavior during the pandemic; in the classroom, we will uphold these agreements. We need to take care of each other for this course to be successful. We ask you therefore to adhere to the following principles:

  • there is a mask mandate for all indoor spaces on campus. You must wear a mask for the entire class; eating and drinking are not permitted. If you need to drink water, please do quickly so and put back your mask. Your mask must cover your mouth and nose. The college has zero-tolerance for violations of this policy, and our shared commitment to the health and safety of our community members means if you come to class unmasked you will have to leave class for the day.
  • If you need to miss class or lab for health reasons, concerning symptoms, suspected Covid exposure, unexpected dependent care, technology issues, or other emergency reasons we will work with you. Let us underscore this: please make your decisions always based on health, safety, and wellness—yours and others—and we will work with you at the other end. Take any potential symptoms seriously; we’re counting on each other.
  • When not in class, avoid closed public spaces, and if you can't avoid them: wear your mask properly, wash your hands, and maintain social distance. If you, or a family member, are experiencing hardship because of the pandemic, talk to us or to someone in the Dean of Students office. You are not alone during this time.

The pandemic is fast-moving, and we might have to adjust these principles as the semester evolves. We are always happy to receive your feedback to make this course work.

Let’s care for each other, show empathy, and be supportive. While there will likely be some community transmission and breakthrough infections, together, we can minimize their effect on our community and on your learning.

Instructor & Texts

Instructors:

Thomas Yeh
128 Edmunds
Remote Office Hours on Gathertown: TR 11am-11:45am, F 2pm-4pm
thomas.yeh@pomona.edu

Lectures: TR 1:20-2:35 p.m., Edmunds 101 (Online on Zoom through Sakai)
TAs: Adeena Liang, Aidan Garton, Carl Bell, George Johnson, Ino Isichrintzi, Kacie Lee, Naomi Amuzie, Max Rose
Mentor sessions: M 2-4pm (), T 7-10pm (), T 7-8pm (), R 7-9pm (), F 1-3pm (), F 12-2pm (), Sa 3-5pm (), Su 6-8pm ()
Learning Communities: 1: M 2-4pm (w/ at 2-3pm), 2: M 7-9pm (w/ at 7-8pm), 3: R 7-9pm (w/ at 7-8pm), 4: M 9-11am (w/ at 10-11am), 5: F 10am-noon (w/ at 11am-noon), 6: F 1-3pm (w/ at 2-3pm), 7: F 7-9pm (w/ at 7-8pm)
BBICS: (Naomi Amuzie)
Labs: W 1:20-4:20 p.m., in Edmunds 219 and 229 (On Gathertown while Online)
Textbook: Robert Sedgewick and Kevin Wayne, Algorithms, 4th edition. Addison Wesley Press.
The book is available for purchase at the Huntley Bookstore.
Textbook companion: The textbook comes with a companion website that contains chapter summaries, code, and exercises.

Schedule

You should consult this page regularly to see the most current version of the schedule of topics and readings.

You should complete all assigned readings and attempt to work all the problems at the end of each section as you are reading. They will be good practice for the regular quizzes during the first ten minutes on Thursday mornings, and may also appear on the midterm or final.

Lecture Date Topic Code and Handouts
1) Jan 18 Introduction & OOP Bicycle Demo
2) Jan 20 Java Basics Basic Java Syntax
3) Jan 25 Inheritance, Interfaces, and Generics Basic Inheritance
4) Jan 27 The Catch-All Java Lecture I/O and Java GUIs
5) Feb 1 Analysis of Algorithms
6) Feb 3 ArrayLists
7) Feb 8 Singly Linked Lists
8) Feb 10 Doubly Linked Lists
9) Feb 15 Stacks, Queues, and Iterators
10) Feb 17 Midterm I
11) Feb 22 Sorting Basics and Comparators
12) Feb 24 Insertion Sort
13) Mar 1 Mergesort
14) Mar 3 Quicksort, Binary Trees
15) Mar 8 Binary Trees and Heap
16) Mar 10 Heap, Priority Queues and Heapsort
17) Mar 22 Symbol Tables and Binary Search
18) Mar 24 Binary Search Trees, 2-3 Search Trees
19) Mar 29 Left-leaning Red-Black BSTs, Midterm Topics + Practice
20) Mar 31 Hash Tables
21) Apr 5 Hash Tables
22) Apr 7 Midterm 2
23) Apr 12 Graphs
24) Apr 14 Graph cont'd
25) Apr 19 Shortest Paths
26) Apr 21 Minimum Spanning Trees
27) Apr 26 TBD
28) Apr 28 TBD
29) May 3 Summary

Assignments & Labs

Labs for this course will be held on Wednesday afternoons from 1:20 p.m to 4:20 p.m. in 219 and 229 Edmunds. The rooms are equipped with iMac computers.
Attendance of the lab sessions is mandatory. Please arrive well prepared for the lab, having read the description thoroughly.

Unlike in CS 51 at Pomona, lab work will be distinct from the weekly programming assignments, though the lab work will generally be relevant to the longer assignments. Instead, we will often use lab time to introduce you to new software tools and techniques that require more hands-on experience to understand. You will usually need to submit your results from the lab by end of the lab day.

There will be two types of weekly programming assignments: individual programs and team programs. All programs assigned during the semester should be completed following the guidelines in the Academic Honesty Policy.
There will be 9 programs due. All programs will be graded on design, documentation and style, correctness, and efficiency. The elements of a good program are very much like the elements of a good paper. It must be correct, but it should also be written in a style that is clear and elegant. Most programs will be tested using automated tools, so it is essential that your program meet all of the specifications provided in the project handout. You will also receive written comments on all of your programs by the TAs.

Weekly assignments will generally be due on Tuesday evenings at 11:59 p.m. There will be a penalty assessed of 3n % for a program that is n days late. Programs will not be accepted more than four days late. It is usually better to turn in a correct and well-documented program one or two days late than a non-functioning or non-documented program on time.
All projects should be submitted electronically. The procedure will be explained in lab.

Lab Date Lab Assignment Due Assignment
Jan 18 Introduction Jan 18 Introduction
Jan 25 Silver Dollar Game Feb 1 Graphic Silver Dollar Game
Feb 2 Timing Feb 8 Darwin
Feb 9 Debugger Feb 15 Darwin, cont.
Feb 16 Midterm I prep Feb 22 Calculator
Feb 23 JUnit Mar 1 Compression
Mar 2 Linked Lists implementation Mar 8 Compression, cont.
Mar 9 Mergesort Mar 22 Compression, cont.
Mar 23 Binary Trees Mar 29 On-disk sort
Mar 30 Git Apr 5 Autocomplete
Apr 6 Midterm II prep Apr 12 Hex-A-Pawn
Apr 13 Profiling Apr 19 Text Generator
Apr 20 No lab Apr 26 Maps
Apr 27 Ethics May 3 Maps, cont.

Exams

There will be two in-class midterm exams plus a scheduled final exam. We will place sample midterm exams on-line approximately a week before each exam. There will also be quizzes every Thursday except the first week of classes. The quizzes will be during the first ten minutes of class. No make-ups will be allowed, but the lowest score will be dropped to make up for illness or other absences.

  • Midterm examination 1: Thursday, Feb 17.
  • Midterm examination 2: Thursday, Apr 7.
  • Final examination: Friday, May 13, 2-5 p.m., in class.

Grading Summary

Component Weight
Weekly Programming Assignments 35%
Midterm 1 15%
Midterm 2 15%
Final Exam 25%
Labs 5%
Quizzes 5%
Total 100%

Collaboration & Academic Honesty

In general, collaboration is encouraged in CS62. This means that you may discuss approaches to solving problems with anyone in this class, including students, faculty, and TAs. As specified in the department policy, you may help, or receive help, in using systems and tools, in debugging code, and in working with high-level design issues. However, using material from any external source—web page or person or book—is forbidden. The actual solutions to the assignments and labs and the code you submit must be your own (and your partner's, if applicable). Except for material from the textbook or lecture, you may not copy, retype, view, or share a copy of any file. If you have any questions about what is appropriate or inappropriate collaboration, please speak with the instructor. When in doubt, credit your sources. Course materials provided to you, including graded papers and exam summaries, are for your use in the course. You are encouraged to use them to the fullest extent, but you are not to publish them or distribute them to other people or organizations.