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

Office: | 110 Administration Bldg | TTh: 2:30 - 3:30 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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 fundamentals of efficient sorting and searching
and the mathematical
theory underlying tree and graph structures. Students will also
apply formal mathematical reasoning, including inductive proof techniques
and complexity analysis based on recurrence relations, to such structures and
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,
2nd edition*, by
John Lewis and Joseph Chase, Addison Wesley, 2005.
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 the text or
in class.
Homework will be assigned frequently and will be due at the
beginning of the next
class unless otherwise specified.
Late homework will not
be accepted for credit except by special arrangement.
Students are encouraged to
work together on homework assignments, but it is never permissible
for a student to turn in work that is substantially someone else's
as his or her own.

**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 individual work.** Students may discuss general program design
and may seek input from other students on syntax errors, but
programs are NOT to be constructed jointly or with substantial help
from anyone but the instructor -- each student is
responsible for his or her own design and code. **Students are strongly
encouraged to seek help from the instructor.** Code or algorithms
taken from any outside source
must be documented by citing the source.

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 may 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.

**MCSP Conversation Series**: The Math, Computer
Science and Physics department offers a series of discussions that appeal to
a broad range of interests related to these fields of study. These sessions
will engage the community to think about ongoing research, novel
applications and other issues that face our disciplines. Students
in this class are required
to participate in at least two of these sessions this semester and, within
one week, submit a 1-2 page paper discussing and responding to the issues that were raised. Consult the MCSP web site for this semester's schedule of talks.

**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 (subject to change with notice)**

Week of
| Topics
| Sections in Text
| |

Aug 29 | Introduction and review of linear collections; begin sorting and searching | Most of chapters 2,3,4,6,7,8,10 (!) | |

Sept 3 | Sorting and searching | Chapter 11 | |

Sept 10 | Introduction to trees | Chapter 12 | |

Sept 17 | Binary search trees | Chapter 12 | |

Sept 24 | ** TEST 1 ** Formal reasoning about trees | Supplemental materials | |

Oct 1 | More formal reasoning about trees | Supplemental materials | |

Oct 8 | Multiway search trees | Chapter 16 | |

Oct 15 | Fall Break!! | ||

Oct 22 | Heaps | Chapter 15 | |

Oct 29 | ** TEST 2 ** Hashing | Chapter 17 | |

Nov 5 | Introduction to graphs | Section 18.1-18.3, 18.5 | |

Nov 12 | Graph algorithms | 18.4 | |

Nov 19 | More graph algorithms and applications Thanksgiving break | Supplemental materials | |

Nov 26 | ** TEST 3 ** Advanced algorithms | ||

Dec 3 | Wrap-up and catch-up | ||

FINAL EXAM: Wednesday, Dec 12, 8:30-11:30 |

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. They may discuss programming projects in a limited way as
described above. However, copying any portion of someone else's work or
turning in work that is substantially someone else's is never allowed.
Consultation
with the instructor is always encouraged.
**Unless otherwise announced in class, tests and exams are to be the work of the individual student.**

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