CS35 — Data Structures and Algorithms
Announcements | Schedule | Grading | Style | Integrity | Links | JavadocsIntroduction
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 lab 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
- Lab 9 due Wednesday, 23 April at 11:59pm
- Final Project due Friday, 2 May at 11:59pm
Class info
Room: Science Center 240Time: TR 2:40pm-3:55pm
Text: Data Structures and Algorithms in Java (4th edition) by Michael T. Goodrich and Roberto Tamassia
Instructional staff
Professor: Andrew DannerOffice: Science Center 253
Phone: (610) 328-8665
Office hours:by appointment
Ninjas: Megan Schuster, Anne-Marie Frassica, Carey Pietsch, and Joel Tolliver
Hours: Thursday 7-9pm (Megan and Anne-Marie) Sunday 9-11pm (Carey and Joel)
Schedule
| WEEK | DAY | ANNOUNCEMENTS | TOPIC & READING | HOMEWORK |
| 1 | Jan 22 | Intro to Java Chapters 1 and 2 |
LAB1 | |
| Jan 24 | ||||
| 2 | Jan 29 | More Java Chapters 2 and 3 |
LAB2 | |
| Jan 31 | Drop/Add ends (Feb 01) | |||
| 3 | Feb 05 | Complexity Analysis Chapter 4 |
LAB3 | |
| Feb 07 | ||||
| 4 | Feb 12 | Stacks and Queues Chapter 5 Also review 2.4, 2.5, 3.3 |
LAB4 | |
| Feb 14 | ||||
| 5 | Feb 19 | Vectors, Lists, Iterators Chapter 6 |
LAB5 | |
| Feb 21 | ||||
| 6 | Feb 26 | Trees Chapter 7, 8.1.1-8.1.2, 10.1,10.4,10.5 |
LAB6 | |
| Feb 28 | ||||
| 7 | Mar 04 | Trees Chapter 7 and 10 |
||
| Mar 06 | ||||
Mar 11 |
Spring Break |
|||
Mar 13 |
||||
| 8 | Mar 18 | Priority Queues and Heaps Chapter 8 |
Midterm Project | |
| Mar 20 | ||||
| 9 | Mar 25 |
Midterm Exam Sample Questions |
||
| Mar 27 | Last day to declare CR/NC or Withdraw with a "W" (Mar 28) |
Dictionaries and Hashing Chapter 9 |
||
| 10 | Apr 01 | |||
| Apr 03 | LAB8 | |||
| 11 | Apr 08 | Sorting Chapter 11 |
||
| Apr 10 | ||||
| 12 | Apr 15 | Graphs Chapter 13.1-13.3 |
LAB9 | |
| Apr 17 | ||||
| 13 | Apr 22 | Graph Algorithms Chapter 13 |
Final Project | |
| Apr 24 | ||||
| 14 | Apr 29 | |||
| May 01 | ||||
May 15 |
Final Exam 2pm Sci 240 |
|||
Grading
Grades will be weighted as follows:| 35% | Lab assignments |
| 10% | Midterm Project |
| 10% | Midterm Exam |
| 25% | Final Project |
| 15% | Final Exam |
| 5% | Class Participation |
Lab 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.
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:
- A comment at the top of the program that includes
- Program authors
- Date or Dates
- A brief description of what the program does
- Concise comments that summarize major sections of your code
- Meaningful variable and function names
- Well organized code
- White space or comments to improve legibility
- Avoidance of large blocks of copy-pasted code
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.
External Links
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