Instructor: | Dr. Adrienne Bloss | Office Hours: |
MWF: 10:50 - 11:50 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Office: | 201 Administration Bldg | Thurs: 2:00 - 3:00 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Phone: | 375-2434 | Also by appointment | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

E-Mail: |
bloss@roanoke.edu |

**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 software structures: designing and using data structures*, by
John Lewis and Joseph Chase, Addison Wesley, 2004.
Additional materials may also
be provided.

**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 |

**Course Topics and Schedule (Tentative)**

Week of
| Topics
| Sections in Text
| |

Aug 30 | Introduction and review of linear collections | Most of chapters 2-8 (!) | |

Sept 6 | Trees | Chapter 9 | |

Sept 13 | Binary search trees | Chapter 10.1-10.3 | |

Sept 20 | Heaps and priority queues | Chapter 11 | |

Sept 27 | ** TEST 1 ** Balanced trees | Sections 10.4-10.7 | |

Oct 4 | Multiway search trees | Chapter 12 | |

Oct 11 | Hashing | Chapter 13 | |

Oct 18 | Fall Break!! | ||

Oct 25 | Introduction to servlets | Supplemental materials | |

Nov 1 | ** TEST 2 ** Introduction to graphs | Chapter 14 | |

Nov 8 | Graph algorithms | Section 14.4 | |

Nov 15 | NlogN sorts (quicksort, mergesort) | Section 5.2 | |

Nov 22 | More sorting algorithms and applications Thanksgiving break | Supplemental materials | |

Nov 29 | ** TEST 3 ** Advanced algorithms | ||

Dec 6 | Wrap-up and catch-up | ||

FINAL EXAM: Friday, Dec 17, 8:30-11:30am |

Exact test dates will be announced at least one week in advance.

**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 may work together on homework assignments, and are encouraged
to do so. However, copying someone else's work or
turning in work that is substantially someone else's is never allowed.
**Tests, exams, and programming projects are to be the work of the individual student.**Consultation is permitted only with the instructor.

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.