CS 416: Introduction to Computer Science II
(Coordinator: Dan Bergeron)
Theory and practice of computer science. Algorithm development and analysis; data abstraction techniques; elementary data structures; dynamic memory manipulation; debugging; and program design issues. Computer systems and applications.
- Basic mastery of object-oriented concepts: classes, objects, inheritance, interfaces (program outcomes 1 and 4).
- Ability to write and debug programs using multiple classes (program outcomes 1 and 4).
- Understanding and use of good programming style (program outcome 1).
- Understanding of basic concepts of event-based programming (program outcomes 1 and 4).
- Understanding recursion; experience implementing a significant number of recursive methods (program outcomes 1, 2, and 4).
- Knowledge of and experience using elementary data structures: arrays, lists, stacks, queues, hashtables, trees, simple graphs (program outcome 2).
- Sorting and searching algorithms; game tree algorithms; depth-first and breadth-first tree traversal algorithms; string processing algorithms; regular expressions (program outcome 3).
- Basics of algorithm analysis; O-notation; analysis of searching and sorting algorithms (program outcomes 3 and 8).
- Weekly programming assignments (50%)
- Semi-weekly labs, weekly recitations (20%)
- Weekly written quizzes and 1 written exams (15%)
- Weekly programming quizzes and 1 programming exams (15%)
This course meets 6 hours per week, 2 hours in lecture, 3 hours in a supervised lab, and 1 hour of group work in a recitation. The pair of approximate hour designations represent lecture / lab-recitation time devoted to the topic:
- SWING/Awt event programming (4/8 hours)
- Stacks: abstraction, array implementation, ArrayList/Vector implementation (2/2 hours)
- Postfix evaluation, infix to postfix conversion algorithms (3/1 hours)
- Queues: abstraction, array impl, ArrayList/Vector impl (1/1 hours)
- Lists: abstraction, array impl, chain impl, sentinels (3/6 hours)
- User defined enumerated types (0.5/0.5 hour)
- Trees: binary search trees, game trees; tree balancing algorithms (4/6 hours)
- Graphs: digraph, graph search (2/3 hours)
- Recursion (2/7 hours)
- Searching and sorting (4/2 hours)
- Analysis of algorithms (3/1 hours)
- Regular expressions (4/4 hours)
- Sanders and van Dam, Introduction to Object-Oriented Programming in Java: A Graphical Approach. This text is used for CS415 and about one-half of CS416. The remainder of CS416 has no formal text.