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

Office: |
201 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, increasing their ability to apply
formal mathematical reasoning 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 usually be due at the beginning of the next class. 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.** As always, it is a
violation of academic integrity for a student to turn in work that is
substantially someone else's as his or her own.

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 one-page paper responding to the issues that were discussed. This
semester's schedule is as follows:

Wednesday, September 13, 5:30 pm (Massengill)

Dr. Jeffrey Spielman,
"Statistical Analysis of Two Contemporary Issues: Global Warming and The Battle
of the Sexex"

Thursday, September 21, 7:00 pm (location TBA)

Dr. Matthew Fleenor, (title
TBA)

Wednesday, September 27, 5:30 (location TBA)

Dr. B. Sidney Smith, Radford
University, "The Mathematical Art of MC Escher"

Thursday, October 12, 7:00 (location TBA)

Dr. George Brooks, Virginia
Military Institute (title TBA)

Thursday, November 2, 7:00 (Massengill)

Erin Hackett (Roanoke alum), Johns
Hopkins University, "The Blue Planet: Exploring Earth?ǳ Oceans"

Friday, November 3, 3:30 (Trexler 372)

Erin Hackett, Johns Hopkins
University, "Flow Measurements on the Atlantic Continental Shelf using PIV"

Thursday, November 16, 7:00 (Massengill)

Dr. Chris Lee, "The Tainted
Truth: The abuse of statistics by pollsters, politicians, advertisers, and even
academic researchers!"

Updates to this schedule will be announced in class and available on the MCSP web site.

**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,3,4,6,7,8,10 (!) | |

Sept 4 | Sorting and Searching | Chapter 11 | |

Sept 11 | More Sorting and Searching | Chapter 11 | |

Sept 18 | Trees | Chapter 12 | |

Sept 25 | ** TEST 1 ** Binary Search Trees | Chapter 13 | |

Oct 2 | More Binary Search Trees | Chapter 13 | |

Oct 9 | Multiway search trees | Chapter 16 | |

Oct 16 | Fall Break!! | ||

Oct 23 | Heaps | Chapter 15 | |

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

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

Nov 13 | Graph algorithms | 18.4 | |

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

Nov 27 | ** TEST 3 ** Advanced algorithms | ||

Dec 4 | Wrap-up and catch-up | ||

FINAL EXAM: Wednesday, Dec 13, 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 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.