CS35 - Data Structures and Algorithms
Fall 2012

Schedule | Study sessions | Grading | Quiz policy | Lab policy | Succeeding in CS35


  • Final Exam Study Guide is posted. The final exam is Saturday, December 15 from 7-10pm in SC 199.
  • Review session is Thursday, December 13 from 10am to noon in SC 256
  • Ninja review session on Friday, December 14 from 6-9pm in SC 240
  • Course evaluations are posted on Moodle. Please complete your evaluation by December 18.
  • Final Written Report is due Tuesday, December 11 with a maximum extension date of December 18

Provide anonymous course feedback here. Please be constructive in any comments

This syllabus is a living document; please be aware that many elements on this page will change throughout the semester, including the course schedule. It is the student's responsibility to review this page periodically for updates.

Class information

       Lecture Section 1: TR 9:55 - 11:10am SC 256
       Lecture Section 2: TR 2:40 -  3:55pm SC 240
       Lab: F 1:40-3:10pm OR 3:20-4:50pm, SC 256
       Required textbook: Data Structures and Algorithms in C++, 2nd edition
            by Goodrich, Tamassia, and Mount.

Instructor information

       Professor: Ameet Soni
       Office: Science Center 253
       Phonei: 610-957-6288
       Office hours: Mondays, 10:00am - noon OR by appointment

Welcome to CS35. This course continues the broad introduction to computer science begun in CS21, providing a general background for further study in the field. By concentrating on data structures and algorithms, you will obtain the basic building blocks by which all large software are built. These topics are central to every sub-discipline in computer science, and also connect to central concepts across the sciences. Topics to be covered include object-oriented programming in C++, advanced data structures (such as priority queues, trees, hash tables, and graphs), advanced algorithms, as well as software design and verification. At the end of this course, you will have obtained the ability to successfully analyze problems in the discipline. You will also take your first steps towards developing the skills necessary to synthesize and evaluate the must fundamental questions in the field.

To enroll in this course you must have completed CPSC 21 or obtain permission from the instructor. This course is designated as a natural sciences and engineering practicum.

Course Promises / Learning Objectives

By the end of the course, you will have developed the following knowledge and skills:

Student support

Student Support Coordinator: Frances Ruiz (Office: Science Center 257, Phone: 6062)

CS35 Ninjas (student mentors): Jonathan Cronin, Samantha Goldstein, Chris Magnano, and Sophie Libkind

The CS Ninjas will assist me in our in-class lab sessions and run study sessions in the main CS lab (Science Center 240) on Monday evenings from 7 - 11 p.m.

You are encouraged to participate in these study sessions to prepare for quizzes, to discuss programming concepts, and to get friendly assistance in working on homework assignments.

Assessment (Grading)

40%Lab assignments (11)
30%Quizzes (4) and Final Report
5%Class participation
25%Final exam

Student Responsbilities

I have outlined the skills and objects this course promises to provide you. For this promises to be upheld, you will need to commit towards the policies outlined below.

Attendance and Participation

Lecture attendance is required. While I am more than happy to help with any material in office hourse, priority will be given to students who show up and participate regularly in class. Office hourse are not to make up for a missed lecture.

Unlike CS21, lab attendance in CS35 is required. New lab assignments will be introduced in our Friday lab sessions, and lab sessions will sometimes contain new course material, required practice exercises, and written quizzes.

Merely showing up to class, however, is not sufficient for success in this course. Students are expected to be active in the learning process. This includes asking and answering questions as well as working with classmates during small group break sessions. Students are expected to r eview the previous lecture's notes and the reading prior to showing up to class. Studies have shown that active involvement is the number one determinant of student success.

Quiz policy

Quizzes will be given at the beginning of class on the days posted in the Announcements section of the Schedule. Please look over these dates carefully and contact the professor in at least one week in advance if you cannot be in class for a quiz. If you do not show up for the quiz, you will receive a zero for that quiz.

In addition to quizzes, you will be asked to produce a written report at the end of the semester detailing a data structure and/or algorithm that was not covered in the course. You will write a medium-length scientific paper on the topic and present an overview of your findings to your classmates during the final week of classes.

Lab assignment policy

Lab assignments are submitted electronically using the handin35 program, and are typically due by 11:59 p.m. on Wednesday nights. You may submit your assignment multiple times, but each submission overwrites the previous one and only the final submission will be graded. Unless otherwise stated, you should assume that a lab assignment is to be done individually. Most of the assignments after the first month will provide the option of working in pairs. Any written assignment, however, must be done individually, even if the main programming assignment for the week allowed paired programming.

Late Policy: Each individual will be given 2 late days for the semester. This will encompass any reason - illness, interviews, paper deadlines, etc. You must notify me by the original lab deadline that you plan on using late days. Since handin35 won't accept late submissions, you must also notify me when your lab is finished so that I can grab the files in your directory. Past these days, late assignments will not be accepted except in very rare, extreme circumstances. You should budget your 2 days to account for future illnesses or assignment deadlines for other courses. Even if you do not fully complete a lab assignment you should submit what you have done to receive partial credit.

Academic accommodations

If you believe that you need accommodations for a disability, please contact Leslie Hempling in the Office of Student Disability Services, located in Parrish 130, or e-mail lhempli1 to set up an appointment to discuss your needs and the process for requesting accommodations. Leslie Hempling is responsible for reviewing and approving disability-related accommodation requests and, as appropriate, she will issue students with documented disabilities an Accommodation Authorization Letter. Since accommodations may require early planning and are not retroactive, please contact her as soon as possible. For details about the Student Disabilities Service and the accomodations process, visit http://www.swarthmore.edu/student-life/academic-advising-and-support/student-disability-services.xml. You are also welcome to contact me privately to discuss your academic needs. However, all disability-related accommodations must be arranged through Leslie Hempling in the Office Of Student Disability Services. To receive an accommodation for a course activity, you must have an Accomodation Authorization letter from Leslie Hempling and you need to meet with me to work out the details of your accommodation at least two weeks prior to any activity requiring accomodations.

Academic integrity

Academic honesty is required in all work you submit to be graded. With the exception of your lab partner on approved lab assignments, you may not submit work done with (or by) someone else, or examine or use work done by others to complete your own work. Your code should never be shared with anyone; you may not examine or use code belonging to someone else, nor may you let anyone else look at or make a copy of your code. This includes sharing solutions after the due date of the assignment.

All code you submit must be your own with the following permissible exceptions: code distributed in class, code found in the course text book, and code worked on with an assigned partner. In these cases, you should always include detailed comments that indicates on which parts of the assignment you received help, and what your sources were.

Discussing ideas and approaches to problems with others on a general level is fine (in fact, we encourage you to discuss general strategies with each other), but you should never read anyone else's code or let anyone else read your code. You may discuss assignment specifications and requirements with others in the class to be sure you understand the problem. In addition, you are allowed to work with others to help learn the course material. However, with the exception of your lab partner, you may not work with others on your assignments in any capacity.

``It is the opinion of the faculty that for an intentional first offense, failure in the course is normally appropriate. Suspension for a semester or deprivation of the degree in that year may also be appropriate when warranted by the seriousness of the offense.'' - Swarthmore College Bulletin (2008-2009, Section 7.1.2)

Please see me if there are any questions about what is permissible.

How to succeed in CS35

CS35 is substantially faster-paced than CS21, covering a broad range of topics. To succeed you should:


For the reading assignments the section numbers are inclusive, so "1.1-1.1.2" means you should read all the sections from 1.1 up to and including section 1.1.2. This is a tentative schedule, it may change as we go.

1 Sep 04   Introduction to C++
Ch1: 1.1-1.1.2,
page 10(strings),
page 16(using), 1.2-1.4.1
Lab 1 - Image Editor
Sep 06  
2 Sep 11   Object-oriented design in C++
Ch1: 1.5-1.5.2, 1.6-1.7.4
Ch2: 2.1-2.2.5
Lab 2 - Chicken
Sep 13 Drop/Add ends (Sep 14)
3 Sep 18 Quiz 1 study guide Complexity analysis
Ch4: (all)
Lab 3 - Algorithm Analysis
Sep 20 Quiz 1
4 Sep 25   Lists
Ch6: 6.1-6.1.3
Ch3: 3.2-3.2.4
Ch6: 6.2-6.2.3
gdb commands
gdb guide
Lab 4 - Popcorn and Linked Lists
Sep 27  
5 Oct 02   Stacks and queues
Ch5: 5.1-5.2.5
Lab 5 - A-maze-ing Stacks and Queues
Oct 04  
6 Oct 09 Quiz 2 study guide Sorting
Ch11: 11.1-11.3
Lab 6 - Sorting
Oct 11 Quiz 2

Oct 16

Fall break

Oct 18

7 Oct 23   Trees
Ch7: 7.1-7.3.3, 7.3.6
Ch10: 10.1-10.1.2
Lab 7 - Morse Code Encoder
Oct 25  
8 Oct 30   Balanced search trees
Ch10: 10.2-10.2.1
Lab 8 - Web page indexing
Nov 01  
9 Nov 06 Quiz 3 study guide Priority queues
Ch8: 8.1-8.1.3, 8.1.5, 8.3-8.3.3, 8.3.5
Lab 9 - Ordered Search Results
Nov 08 Quiz 3
Last day to declare CR/NC or withdraw with a "W"
(Nov 09)
10 Nov 13   Dictionaries and hash tables
Ch9: 9.1-9.1.1, 9.2-9.2.6, 9.5-9.5.1
Lab 10 - Scrabble Solver
Nov 15  
11 Nov 20   Introduction to graphs
Ch13: 13.1-13.3.2, 13.3.5-13.5

Nov 22


12 Nov 27 Quiz 4 study guide Shortest paths
Ch13: 13.6
Lab 11 - Oracle of Bacon
Nov 29 Quiz 4
13 Dec 04   More graphs
Dec 06  
14 Dec 11 Final study guide Course wrap-up Final Written Report

Dec 15

Final 7:00pm–10:00pm Science Center 199