Advanced Principles of Computer Science

Computer Science 160

Fall, 2004

• Instructor: John L. Donaldson
• Office: King 223C
• Office hours: MWF 10 am-noon (or by appointment)

Course Information

• Prerequisite: CS 150 or consent of instructor
• Text:  Carrano and Savitch, Data Structures and Abstractions with Java, Prentice Hall, 2003.
• Course Objectives:
• To study the principles of object-oriented programming.
• To study fundamental data structures.
• To introduce basic methods of algorithm analysis.
• To introduce basic design patterns.
  

References

• Flanagan, Java in a Nutshell, O'Reilly.
• Eckel, Thinking in Java, third edition, Prentice-Hall, 2002.  (A free electronic version is available at www.mindview.net.)
• Cooper, Java Design Patterns, Addison-Wesley, 2000.

Grading Procedures

Your grade will be based on labs, homework, and three exams.

Point breakdown (tentative):
Labs/Homework	250
Midterm Exam (October 15)	100
Final Exam (December 18 - 7 pm)	150
Total	500

Policies

The results of each Tuesday lab session are to be handed in electronically by midnight the following Sunday.  Late assignments will be assessed a penalty of 10% per day.

Regular class attendance and participation is expected.

The Honor Code

The Honor Code has a straightforward application to this class.  On all of the exams you are responsible for your own work; you may neither give nor receive aid during the course of the exam.  If someone takes an exam at a different time than the rest of the class there may be no communication concerning the exam between that person and anyone else in the class, not even about whether the exam was easy or difficult.  The atmosphere is much more relaxed for the labs.  You may discuss the lab exercises, including details of the programming code, with anyone else in the class, but in the end you must write your own code.

Course outline

1. Basics of Java programming:  classes and methods.  (Chapter 1)
2. Using other people's code:  composition and inheritance.  (Chapters 2-3)
3. The List ADT.  Linked lists.  (Chapters 4-6)
   
4. Foundations of algorithm analysis:  measuring run time.  (Chapter 9)
5. Sorted lists (Chapter 13)
   
6. Limited-access lists:  stacks, queues, deques, and priority queues.  (Chapters 20-23)
7. Binary trees and binary search trees.  (Chapters 24-26, 28)
8. Dictionaries and hash tables.  (Chapters 17-19)
9. Sorting algorithms.  (Chapter 11-12)