CPSC 327, Spring 2004
Information about the First Test

The first test in this course will take place on Friday, February 20. It will cover material from the first four chapters as well as the lab and assignments. You can expect a mixture of different types of problems: definitions, short-answer essays, longer conceptual essays, and programming. Programming questions might, for example, ask you to use an abstract data type to accomplish some task or to write an implementation for an ADT. You should expect at least one question where you are given some code and asked to analyze its run time. You are not responsible for any details of C++ templates and the standard template library, but you should understand the basic concepts (which might be tested in definitions and essay questions).

Important terms and ideas for this test include:

implementation of an algorithm
analysis of algorithms
run-time efficiency
worst-case, best-case, average case
growth rate of a function
"Big Theta"
growth rates of common functions
   (power, exponential, logarithm)
linear search and binary search
"Big Omega" and "Big Oh"
empirical testing of run times
abstract data type
implementation of an ADT
ADT's in C++
C++ header (.h) files
dynamic array implementation of stacks
standard template library
linked lists
header node for a linked list
tail pointer for a linked list
doubly-linked list
linked list implementation of list ADT
priority queues
a heap as a full binary tree
array representation of a heap
heap implementation of priority queues
using heaps for heapsort
the "Heapify" algorithm
the heap insert algorithm
fields in a record
key field in a record
sorting by key
stable sort
in-place sort
the QuickSortStep algorithm
using a stack instead of recursion
comparison sort
linear time sorting
run-time analysis of sort algorithms
comparing various sort algorithms
     selection sort
     insertion sort
     bubble sort
     merge sort
     radix sort

     the stack ADT
        push, pop, isEmpty
     the queue ADT
        enqueue, dequeue, isEmpty
     the list ADT
        begin, end, next, prev,
        get, set, insert, remove;
        "position" in a list
     the priority queue ADT
        insert, remove