CS 416: Introduction to Computer Science II

(Coordinator: Dan Bergeron)

Catalog description

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.

Outcomes

  • 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).

Evaluation

  • 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%)

Topics

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)

Textbooks

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