CPSC 220: Fundamentals of Computer Science III

Fall 2005

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

MCSP Colloquium 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. After attending, each student will submit a one-page paper reflecting on the discussion. This semester's schedule is as follows:

All sessions will be 5:30-6:30 in Trexler 372 (refreshments at 5:15).

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:

tests.....40%     homework.......10%     projects.......23%     colloquia......2%     final exam......25%

Grading Scale: 93-100A        83-86B        73-76C        63-66D
90-92A-        80-82B-        70-72C-        60-62D-
87-89B+        77-79C+        67-69D+        below 60F

Course Topics and Schedule (Tentative)

Week of Topics Sections in Text
Aug 31 Introduction and review of linear collections Most of chapters 2,3,4,6,7,8,10 (!)
Sept 5 Sorting and Searching Chapter 11
Sept 12 Trees Chapter 12
Sept 19 Binary Search Trees Chapter 13
Sept 26 Finish Binary Search Trees
** TEST 1 **
Oct 3 Multiway search trees Chapter 16
Oct 10 Heaps Chapter 15
Oct 17 Fall Break!!
Oct 24 Introduction to servlets Supplemental materials
Oct 31 ** TEST 2 **
Chapter 17
Nov 7 Introduction to graphs Section 18.1-18.3, 18.5
Nov 14 Graph algorithms 18.4
Nov 21 More graph algorithms and applications
Thanksgiving break
Supplemental materials
Nov 28 ** TEST 3 **
Advanced algorithms
Dec 5 Wrap-up and catch-up  
FINAL EXAM: Thursday, Dec 15, 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

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

  2. Unless otherwise announced in class, tests, exams, and programming projects are to be the work of the individual student. Consultation is permitted only with the instructor.
Using someone else's work or ideas as your own is plagiarism and an academic integrity offense. Examples of academic integrity violations include copying a program or part of a program (even one line) from someone else or from any unauthorized source, writing code for someone else, telling someone else how to solve a problem or having someone tell you how to solve a problem.

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.