Instructor & Texts

Instructors:

Dave Kauchak
224 Edmunds
Office Hours: M 10iam-12, F 10-11:30am, 3-4pm
david.kauchak@pomona.edu
www.cs.pomona.edu/~dkauchak/

Alexandra Papoutsaki
222 Edmunds
Office Hours: T 2:30 pm - 5:00 pm, W 11:00 am - noon, R 2:30 pm - 4:00 pm
Alexandra.Papoutsaki@pomona.edu
www.cs.pomona.edu/~apapoutsaki/

Lectures: TR 01:15 pm - 02:30 pm, Seaver Commons 103
TAs: Jack Bernstein, Mercy Bickell, Alex Franklin, Pei Qin, Huey Sun, Ino Tsichrintzi, Jack Weber, Pei Pei Barth Wu
TA hours: M 7-9 pm, T 7-9 pm, Th 7-9 pm, Sat 10am-noon, Su 7-9 pm in Edmunds 105
Labs: W 1:15 pm - 4:00 pm in Edmunds 219 and Edmunds 229
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.
Piazza site: Most dynamic information (grades, announcements, etc.) will be posted on the piazza site

Schedule

Students 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 studying. Some of these will show up in 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 21 Introduction & Java basics
2) Jan 23 Classes
3) Jan 28 Inheritance
4) Jan 30 GUIs and graphics
5) Feb 4 Generics, File I/O
6) Feb 6 Big O
7) Feb 11 ArrayLists
Analysis slides (pdf)
8) Feb 13 Singly linked lists
9) Feb 18 Doubly linked lists
10) Feb 20 Stacks and queues
11) Feb 25 Midterm I review (midterm in Wednesday lab) Previous midterm problems (solutions)
more questions
12) Feb 27 Sorting Fundamentals
13) Mar 3 Mergesort
14) Mar 5 Quicksort
15) Mar 10 Iterators and Comparators
16) Mar 12 Binary Trees
17) Mar 17 Spring Break
18) Mar 19 Spring Break
19) Mar 24 Priority Queues and Heapsort
20) Mar 26 Symbol Tables and Binary Search
21) Mar 31 Binary Search Trees
22) Apr 2 2-3 Binary Search Trees
23) Apr 7 Red-Black Binary Search Trees
24) Apr 9 Geometric Applications of BSTs
25) Apr 14 Midterm II review (midterm in lab)
26) Apr 16 Hashtables I
27) Apr 21 Hashtables II
28) Apr 23 Undirected Graphs
29) Apr 29 Directed Graphs
30) May 1 Minimum Spanning Trees
31) May 5 Shortest Path

Assignments & Labs

Lab Date Lab Assignment Due Assignment
Jan 22 Introduction
Jan 29 Silver Dollar Game Feb 4 Graphic Silver Dollar Game
Feb 5 Debugger Darwin
Feb 12 Timing Arraylists Feb 18 Darwin, cont.
Feb 19 JUnit Singly linked lists Feb 25 Text Calculator
Feb 26 Midterm I Compression
Mar 4 Linked Lists implementation Mar 10 Compression, cont.
Mar 11 Mergesort Mar 24 On-disk sort
Mar 25 TBD Mar 31 TBD
Apr 1 Binary Trees Apr 7 Autocomplete
Apr 8 Git Apr 14 Hex-A-Pawn
Apr 15 Midterm II Apr 21 Text Generator
Apr 22 Profiling Maps
Apr 30 Concurrency May 5 Maps, cont.

Exams

There will be two in-lab midterm exams plus a scheduled final exam. There will also be quizzes every Thursday except the first week of classes and during the weeks of the midterms. The quizzes will be during the first five 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: Wednesday, February 26, in lab.
  • Midterm examination 2: Wednesday, April 15, in lab.
  • Final examination: Monday, May 11 2:00 pm - 5:00 pm, in class.

We will place sample midterm exams on-line approximately a week before each exam.

Grading Summary

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

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 and implementing efficient computer programs, we will be using the object-oriented programming language, Java. We will see that the object-oriented style of programming is extremely useful in designing large, complex programs and supporting reusable software.

Students 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 for correctness and 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 have a good understanding of how one might analyze programs for correctness and 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.

Two parallel labs for this course will be held on Wednesday afternoons from 1:15 pm to 4 pm in 219 and 229 Edmunds. The rooms are equipped with iMac computers. Attendance at these 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 about 10 weekly 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. You can use two late assignment passes, each giving you the ability to submit your assignment up to two days after the extension. Please notify the instructors before the deadline if you plan to use one of the passes. All projects should be submitted electronically. The procedure will be explained in lab.

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.

Use of electronics in the classroom

Laptops, tablets, and cell phones may not be used during lecture without advance permission of the instructor. Several studies (and our personal experience) have shown that these devices are a distraction and interfere with learning. Other studies have shown that taking notes by hand is more effective for learning than taking notes on a computer. We recommend that you print out the lecture notes before class (they should be posted by 1 pm each class day) and annotate them by hand.

Pomona College prohibits video or voice recording of any lecture or discussion, except in cases that the office of the Dean of Students has granted a student permission according to the College’s Disability Accommodations Policy, or when permission is granted by the instructor. Please see one of the instructors if you wish to record lectures or lab sessions.

Collaboration & Academic Honesty

The Computer Science Department seeks to create a friendly and supportive learning environment. We encourage students to work in groups to review material from the lectures and readings, to work practice problems from the text, to study for exams, and to discuss the general ideas and approaches to assignments. However, work submitted for a course must be done independently, unless collaboration on a particular assignment is explicitly permitted. Effective learning is compromised when this principle is violated. As explained in the Pomona College Student Handbook, this means that the work you turn in must represent only your own work. It must not be based on help from others or information obtained from sources other than those approved by the instructors.

The following discussion reflects our general understanding of academic honesty in the Computer Science Department. Any exceptions or differences will appear in the course syllabus or the instructions for an assignment. Ask an instructor if you are ever unsure about what constitutes acceptable behavior.

Collaboration policies

The types of work and the level of expected collaboration vary from course to course and assignment to assignment. In this section, we describe some typical expectations. Instructors will often indicate that an assignment falls into a particular category, occasionally with additional remarks about the use of specific materials or sources. Students may freely use any resource that is provided by the instructor for an assignment.

Individual work

Most work in our courses is to be completed individually. In general, the work that is submitted for an assignment must be the student's own. Students may not submit work under their own name that is done by, or in collaboration with, someone else. Copying solutions from any source, including the web or students in previous offerings of the course, is not allowed.

Students should not read or possess copies in any form—physical or electronic—of another student's work. There is no legitimate reason for a student to possess a copy of another student's assignment, to send a copy of student work from one computer account to another, or to be logged-on to another student's account. Providing one's own work to another student is also a violation of these policies.

We routinely use software and other tools to detect similarities between submissions. Identical, or nearly identical, submissions will be considered conclusive evidence of plagiarism.

For programming assignments, students may normally discuss general approaches to assignments, and they may give or receive "consulting" help for specific problems with software or computer programs. A student may look at another student's work only when help is requested. In that situation, the student takes on the role of mentor, and the interaction must be limited to the immediate problem. Two students sitting side-by-side and working through a program step-by-step will certainly produce work that will be considered evidence of illegal collaboration.

On problem sets, group discussion of the general ideas and approaches is permitted, provided the group members are noted on the submitted solutions. However, each student must write the solutions apart from the group, without consulting notes or other artifacts from the discussion. Although papers are less common in computer science classes, when they are assigned they must adhere to the usual levels of academic integrity. The prose must be the student's own, and all external sources must be properly cited.

Group assignments

Sometimes assignments are to be done by small teams of students. In these situations, the team takes on the role of an individual in the preceding discussion. The members of a team may communicate with one another, but collaboration with members of a different team is not permitted.

Exams and test programs

As stated in the Pomona College Student Handbook, "Students neither give nor receive assistance with examinations." Each examination will have a clear statement of what resources are permitted. Any use of material beyond those limits is not allowed. During examinations students may ask the instructor questions of clarification. The instructor will decide how complete an answer can be given.

Practice exercises

Some assignments are intended to give students comfort with a programming language feature or software environment. On these, any kind of assistance is permitted. The point is to get the work done.

Use of course materials

Course materials that are distributed in class, on Github, on the web, or by other means are provided solely for students in the class. Students are encouraged to use them to the fullest extent, but they are not to publish or distribute them to other people or organizations.

Responsibility of mentors and graders

Course assistants are routinely provided with solution sets to assignments. The solutions are intended to be an aid to effective mentoring and grading. Course assistants are not to distribute the solutions, in whole or in part, at any time. Graders who encounter suspicious similarities between submissions must report those instances to the instructor in the course.

Penalties

Failure to abide by our rules will be considered a violation of the college's academic honesty policy and will result in severe penalties. Instances of plagiarism are easy to identify and will be handled promptly. The first offense typically results in failure in the course and is always reported to the Dean of Students Office. A second offense is automatically referred to the College's Board of Academic Discipline. See the Academic Honesty Policy in the Pomona College Student Handbook for further information. Students from other Claremont Colleges will be treated according to the procedures of their home campus. Please do not put us, yourself, or anyone else in an unpleasant situation.

In this class, the default penalty for any sort of academic dishonesty shall be failure in the course. Please do not put yourself or any of your classmates in this position.