Course Objectives: This is the third and final course in the introductory computer science sequence. This course focuses on the design, implementation and analysis of elementary data structures. Students will learn the mathematical theory underlying tree and graph structures and increase their ability to apply formal mathematical reasoning to such structures and associated algorithms. Programming will emphasize object-oriented design and will be done in Java.
Prerequisite: CPSC 170.
Text: Java, A Framework for Program Design and Data Structures, by Kenneth A. Lambert and Martin Osborne, Brooks/Cole, 2000. Additional materials may also be provided.
Course Topics (Schedule Tentative)
| Week of | Topics | Sections in Text | |
| Aug 26 | Introduction; review of classes and linked structures; Breezy GUI | 2.1-2.7, 3.1-3.2, 5.3-5.4 | |
| Sept 2 | Collections; review of stacks, queues, and lists | 6.1-6.6 | |
| Sept 9 | Introduction to trees | 11.1-11.5 | |
| Sept 16 | Binary search trees | 12.2 | |
| Sept 23 | ** TEST 1 ** Heaps | 12.1 | |
| Sept 30 | Sets, maps, and bags; hashing | 13.1-13.5 | |
| Oct 7 | Network concepts | 15.2 | |
| Oct 14 | Fall Break!! | ||
| Oct 21 | Introduction to graphs | 14.1-14.3 | |
| Oct 28 | ** TEST 2 ** Graph traversals, embedded trees | 14.5 | |
| Nov 4 | Elementary graph algorithms | 14.6-14.7 | |
| Nov 11 | NlogN sorts | 10.3 | |
| Nov 18 | Backtracking algorithms | 10.4 | |
| Nov 25 | ** TEST 3 ** Thanksgiving break | ||
| Dec 2 | Wrap-up and catch-up | ||
| FINAL EXAM: Wednesday Dec 11, 2:00-5:00 | |||
Any changes in test dates will be announced at least one week in advance.
Homework Assignments: Homework assignments are small theoretical or applied problems that are designed to reinforce the material covered in class. Students are encouraged to work together on homework assignments; however, it is never permissible for a student to turn in work that is substantially someone else's as his or her own. Homework will be assigned as needed. Homework is due at the beginning of class on the specified date; late homework will not be accepted for credit except by special arrangement.
Programming Projects: Programming projects are designed to give students the opportunity to apply the problem solving and programming skills they have learned to larger projects. Programming projects are to be done individually. Students may not discuss any aspect of the design or coding of a programming project with anyone except the instructor. Unless otherwise specified, projects are to be turned in by 4 pm on the due date. Five percent per calendar day (24 hours) will be deducted for late work; work more than 5 days late will usually receive no credit. A student who anticipates being unable to meet a deadline should talk to me before the deadline; in extenuating circumstances we may be able to make special arrangements.
Attendance Policy: Class attendance is a very important aspect of a student's success in this course. The student is expected to attend every class and is accountable for any missed classes.
Grading Policy: The course grade will
be based on three tests, homework assignments,
programming projects,
and a comprehensive final examination.
The course grade is
determined using the following
weights:
| Grading Scale: | 93-100 | A | 83-86 | B | 73-76 | C | 63-66 | D | |||
| 90-92 | A- | 80-82 | B- | 70-72 | C- | 60-62 | D- | ||||
| 87-89 | B+ | 77-79 | C+ | 67-69 | D+ | below 60 | F |
Make-up Policy: Everyone is expected to take tests and the exam at the scheduled time. Make-ups may be available at the discretion of the instructor in case of medical emergency, and under other extenuating circumstances if the instructor is notified ahead of time. Make-up tests, if given, may be oral.
Academic Integrity
Students who need help with any aspect of the course are encouraged to contact the instructor.
Computer Use Policies: All students must abide by the Computer Use policies of Roanoke College. Failure to do so will result in involuntary withdrawal from the course.