Principles of Computer Science

Computer Science 151

Spring, 2005

• Instructor: John L. Donaldson
• Lab Instructors:  Esmail Bonakdarian (Monday), John Donaldson (Tuesday)
• Student Assistants:  Wes John-Alder, Thomas Mayfield
  
• Office: King 223C
• Office hours: MWF 11 am-noon, 2:30-3:30 pm (or by appointment)

Course Information

• Prerequisite: CS 150
• Text:  Carrano and Savitch, Data Structures and Abstractions with Java, Prentice Hall, 2003.
• Course Objectives:
• To study fundamental data structures and algorithms.
• To gain further experience in object-oriented programming and design.
• To introduce basic methods of algorithm analysis.

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 weekly labs and and three exams.

Point breakdown (tentative):
Labs	220
Exam 1 (March 11)	80
Exam 2 (April 20)	80
Final Exam (May 18 - 7 pm)	120
Total	500

Policies

The results of each Monday and 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.

All late assignments must be submitted by the end of the reading period (May 17).

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. Review of object-oriented programming in Java:  classes, methods, and inheritance.  (Chapters 1-3)
2. The List ADT.  Linked lists.  (Chapters 4-6)
   
3. Foundations of algorithm analysis:  measuring run time.  (Chapter 9)
4. Sorted lists (Chapter 13)
   
5. Limited-access lists:  stacks, queues, deques, and priority queues.  (Chapters 20-23)
6. Binary trees and binary search trees.  (Chapters 24-26, 28)
7. Dictionaries and hash tables.  (Chapters 17-19)
8. Sorting algorithms.  (Chapter 11-12)