CS35 — Data Structures and Algorithms

Announcements | Schedule | Grading | Clinicians | Style | Integrity | Links | Javadocs
Data Structures and Algorithms

Introduction

Welcome to CS35. This course continues the broad introduction to computer science begun in CS21. It is also provides a good general background for further study in the field. The underlying themes of the course will be program design, abstraction, analysis, and correctness. We will use the object-oriented programming language Java to implement and test programs. A brief introduction to Java will be provided, but some familiarity with programming is a pre-requisite usually satisfied by CS21. Topics covered in CS35 include data structures (queues, stacks, trees, hash tables, graphs, etc.), algorithms, software design and software verification.

Numerous homework exercises and a number of programming projects help illustrate the concepts presented. We will use the Computer Science Labs (running Linux) in the Science Center as the classroom/laboratorys for this course. If you work somewhere else, you are responsible for obtaining and learning how to use the software. Since one of the goals of the course is to learn how to write large, reliable programs, we emphasize (in class and grading) the development of clear, modular, well-documented programs that are easy to read, verify, analyze, debug, and modify.

Announcements

Class info

Room: Science Center 240
Time: MWF 10:30am-11:20am
Text: Data Structures and Algorithms in Java (4th edition) by Michael T. Goodrich and Roberto Tamassia

Instructional staff

Professor: Andrew Danner
Office: Science Center 253
Phone: (610) 328-8665
Office hours:Tuesday 9-11am, Wednesday 1:30-2:30pm, or by appointment


Clinicians: Alex Benn (Sunday 7-9pm) and Meggie Ladlow (Monday 7-9pm)

Schedule

WEEK DAY ANNOUNCEMENTS TOPIC & READING HOMEWORK
1 Sep 03   Intro to Java
Chapters 1 and 2
HW #1
Sep 05  
Sep 07  
2 Sep 10   More Java
Chapters 2 and 3
HW #2
Sep 12  
Sep 14 Drop/Add ends
3 Sep 17   Complexity Analysis
Chapter 4
HW #3
Sep 19  
Sep 21  
4 Sep 24   Stacks and Queues
Chapter 5
HW #4
Sep 26  
Sep 28  
5 Oct 01   Vectors, Lists, Iterators
Chapter 6
HW #5
Oct 03  
Oct 05  
6 Oct 08   Trees
Chapter 7 and 10
 
Oct 10    
Oct 12    
 

Oct 15

Break

Oct 17

Oct 19

7 Oct 22   Trees
Chapter 7 and 10
 
Oct 24    
Oct 26    
8 Oct 29   Priority Queues and Heaps
Chapter 8
HW #6
Oct 31  
Nov 02  
9 Nov 05   Dictionaries and Hashing
Chapter 9
project 1

Nov 07

Midterm in class

Nov 09 Last day to declare CR/NC or
Withdraw with a "W"
Dictionaries and Hashing
Chapter 9 (continued)
10 Nov 12  
Nov 14   Dictionaries and Hashing
Chapter 9
 
Nov 16    
11 Nov 19   Sorting
Chapter 11
 
Nov 21    

Nov 23

Thanksgiving Break

12 Nov 26   Graphs
Chapter 13
HW #8
Nov 28  
Nov 30  
13 Dec 03   Graph Algorithms
Chapter 13
project 2
Dec 05  
Dec 07  
14 Dec 10   Wrapup  
 

Dec 17

Final Exam 9am

Grading

Grades will be weighted as follows:
35%Homework assignments
10%Midterm Project
10%Midterm Exam
20%Final Project
20%Final Exam
5%Class Participation

Homework policy

Programming assignments will typically be assigned in class at the beginning of the week and will be due before midnight the following Tuesday night. You are strongly encouraged to start early.

You will submit you assignments electronically using the handin35 program. You may submit your assignment multiple times, but each submission overwrites the previous one and only the final submission will be graded. Late assignments will not be accepted except in extreme situations and only if you contact me before the deadline. Even if you do not fully complete an assignment, you may submit what you have done to receive partial credit.

Clinicians

Student clinicians will be available to help answer questions you may have. Alex Benn and Meggie Ladlow will be the clinicians this semester. Alex is available from 7-9pm on Sundays and Meggie is available from 7-9pm on Mondays. Feel free to stop by and ask them nicely for assistance during these hours.

Programming Style

Programming is not a dry mechanical process, but a form of art. Well written code has an aesthetic appeal while poor form can make other programmers and instructors cringe. Programming assignments will be graded based on style and correctness. Good programming practices usually include many of the following principles:

Academic Integrity

Academic honesty is required in all work you submit to be graded. With the exception of your lab partner on 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. 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.

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 which parts of the assignment you received help on, and what your sources were.

``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 (2007-2008, Section 7.1.2)

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

Links that are related to the course may be posted here. If you have suggestions for links, let me know.

Using Unix Improved
Textbook site
Vim quick reference
Vim tips and tricks
From Python to Java
Sun's Java tutorial
Professor Newhall's Tips on How to Compile, Run and Debug Java Programs
Common Java Error Messages
ACM Programming Contest Oct 27

Javadocs

java.util.* 1.5.0 Local Copy
java.util.Scanner 1.5.0 Local Copy
java.util.List<E> 1.5.0 Local Copy
java.util.ArrayList<E> 1.5.0 Local Copy
java.util.LinkedList<E> 1.5.0 Local Copy
java.util.Iterator<E> 1.5.0 Local Copy
java.util.ListIterator<E> 1.5.0 Local Copy
java.util.PriorityQueue<E> 1.5.0 Local Copy
java.util.Comparator<E> 1.5.0 Local Copy
java.util.Hashtable<K,V> 1.5.0 Local Copy
java.util.Collection<E> 1.5.0 Local Copy
java.lang.* 1.5.0 Local Copy
java.lang.Character 1.5.0 Local Copy
java.lang.Integer 1.5.0 Local Copy
java.lang.Math 1.5.0 Local Copy
java.lang.String 1.5.0 Local Copy
java.io.* 1.5.0 Local Copy
java.io.File 1.5.0 Local Copy
java.io.FileInputStream 1.5.0 Local Copy
java.io.Serializable 1.5.0 Local Copy
java.awt.* 1.5.0 Local Copy
java.awt.Color 1.5.0 Local Copy
java.awt.FlowLayout 1.5.0 Local Copy
java.awt.BorderLayout 1.5.0 Local Copy
java.awt.GridLayout 1.5.0 Local Copy
java.awt.GridBagLayout 1.5.0 Local Copy
javax.swing.* 1.5.0 Local Copy
javax.swing.JFrame 1.5.0 Local Copy
javax.swing.JPanel 1.5.0 Local Copy
javax.swing.JLabel 1.5.0 Local Copy
javax.swing.JButton 1.5.0 Local Copy
javax.swing.JComboBox 1.5.0 Local Copy
Thanks to Richard Wicentowski for this table format.