CS14a  Midterm Topics 


Text: chapters 1-3 (background) 4, 6, 7, 9 (first section only), 10


Running times and complexity.
-----------------------------
- Big-Oh notation; determining the running time of code segments;
- Big-Oh -- know the definition.
- comparing program performances.

Lists 
-----
- implementations: array, singly linked lists, doubly linked lists. 
- operations: inserting, removing, searching.
- advantages/disadvatages of the different implementations; time bounds for    
  operations in each.
- list traversal: sequential, can go only forward (sll) both ways (array, dll).
- dummy head/tail nodes and their uses.
- uses of lists: maintaining sorted data.
  
Stacks
------ 
- operations: push, pop, top, ...
- implementations: array, linked lists; advantages/disadvatages of each;
  time bounds for operations in each.
- uses of stacks: function calls, evaluation of postfix expressions,
  translating expressions to postfix,   checking for balanced parentheses
  
Queues 
------
- operations: enqueue, dequeue, front, ...
- implementations: array, linked lists; advantages/disadvatages of each;
  time bounds for operations in each.
- uses of queues: printer queue, simulation of real life situations,
  e.g. line at a checkout lane.
  
Trees 
-----
- general terminology: root, leaves, internal nodes, path, child,
  parent, height. 
- structure of a tree node
- uses: binary search trees, expression trees, treesort.

Expression trees 
----------------
- operands at leaves, operators in internal node
- evaluating expressions: by combining leaf nodes; by postorder
  traversal then stack. 
     
Binary search trees 
-------------------
- basic properties
- operations: insert, remove, search, ...
- tree traversal (preorder, inorder, postorder)
- height of BST: average case, worst case.
- running time of tree operations
- implementation issues
- uses of BSTs: data storage.


C++ Issues
----------
- classes, objects and methods
- dynamic memory allocation
- deleting lists through node destructors
- exception handling