CS35: Data Structures and Algorithms

Announcements | Schedule | Grading | Integrity | Links
 

Announcements

Introduction

This course continues the broad introduction to computer science begun in CS21. It 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 lab exercises and a number of programming projects will help illustrate the concepts presented. We will use the Computer Science Labs (running Linux) in the Science Center as the classroom/laboratory 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.

Class information

Professor: Douglas Turnbull
Office: Science Center 255
Phone: (610) 597-6071
Office hours: TBA or by appointment

Ninjas: Ninja Session: TBA

Room: Science Center 240
Time: Monday, Wednesday, Friday 9:30pm–10:20pm
Text: Goodrich and Tamassia. Data Strucutures and Algorithms in Java (4th edition).

Schedule

WEEK DAY ANNOUNCEMENTS TOPIC & READING LAB
1 Jan 19   Intro to Java
Chapters 1,2
Lab 1
Jan 21  
Jan 23  
2 Jan 26   More Java
Chapters 2,3
Lab 2
Jan 28  
Jan 30 Drop/Add Ends
3 Feb 02   Complexity Analysis
Chapter 4
Lab 3
Feb 04  
Feb 06  
4 Feb 09   Stacks & Queues
Chapter 5
Lab 4
Feb 11  

Feb 13

Java Quiz

5 Feb 16   Vectors, Lists, Iterators
Chapter 6, 9.3.3, 9.4
Lab 5
Feb 18  
Feb 20  
6 Feb 23   Trees
Chapter 7, 8.1.1, 8.1.2, 10.1, 10.4, 10.5
Lab 6
Feb 25  
Feb 27  
7 Mar 02   More Trees
Chapter 7,10
Lab 7
Mar 04  
Mar 06  
 

Mar 09

Spring Break

Mar 11

Mar 13

8 Mar 16   Priority Queues & Heaps
Chapter 8
 
Mar 18    
Mar 20    
9

Mar 23

Midterm exam (Sample Midterm 1, Sample Midterm 2 - Solutions)

Mar 25   Maps & Hashing
Chapter 9
Lab 8
Mar 27 Last Day for
CR/NC or Withdraw
10 Mar 30    
Apr 01    
Apr 03    
11 Apr 06   Sorting
Chapter 11
Lab 9a
Apr 08  
Apr 10  
12 Apr 13   Graphs
Chapter 13.1-13.3
 
Apr 15    
Apr 17    
13 Apr 20   Graph Algorithms
Chapter 13
Lab 9b
Apr 22  
Apr 24  
14 Apr 27    
Apr 29    
May 01    
 

May 11

Final exam :: May 11 :: 9am-12pm :: SC 240

Grading

Your overall grade in the course will be determined as follows:
35%Lab Assignments
10%Midterm Project
15%Midterm Exam
15%Final Project
20%Final Exam
5%Class Participation

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

Javadocs

java.util.*
java.util.Scanner
java.util.List
java.util.ArrayList
java.util.LinkedList
java.util.Iterator
java.util.ListIterator
java.util.PriorityQueue
java.util.Comparator
java.util.HashMap
java.util.Collection
java.lang.*
java.lang.Character
java.lang.Integer
java.lang.Math
java.lang.String
java.io.*
java.io.File
java.io.FileInputStream
java.io.Serializable
java.awt.*
java.awt.Color
java.awt.FlowLayout
java.awt.BorderLayout
java.awt.GridLayout
java.awt.GridBagLayout
javax.swing.*
javax.swing.JFrame
javax.swing.JPanel
javax.swing.JLabel
javax.swing.JButton
javax.swing.JComboBox
Thanks to Richard Wicentowski for this table format.