CPSC 170 Spring 2004
Exam Topics

• Arrays
  • 1-dim,2-dim
  • non-rectangular
  • physical representation
  • logical vs. physical length

• Linked structures

• Sorting -- selection sort, insertion sort

• Searching -- sequential search, binary search

• Collections -- Bags, Stacks, Queues, Lists
  • array implementations
  • linked implementations (singly linked, doubly linked, header/trailer nodes)
  • use as ADTs

• Representation of expressions
  • Infix/prefix/postfix
  • Stack evaluation of postfix expressions

• Sets and set operations (union, intersection, difference, powerset, cartesian product)

• Computational complexity -- big-O

• 1 + 2 + ... + N, and similar sums.

• Recursion
  • writing recursive methods
  • understanding/tracing recursive methods

• Mathematical induction -- 1st, 2nd principle

• Recurrence relations
  • Writing
  • Finding closed form

• Exceptions
  • try/catch
  • checked vs. unchecked
  • throw, throws

• Java I/O
  • stream model
  • byte vs. char streams
  • data vs. processing streams

• Interfaces; abstract methods and classes

• Inheritance
  • Defining subclasses
  • Polymorphism
  • Dynamic method binding

• GUIs
  • listening for events
  • using inner classes to define event listeners
  • general understanding of GUI components