-
You should copy any
necessary reference material such as algorithms from the text or notes,
definitions of W, Q, O
and summation formulas.
-
You can bring one page of
notes on the front and back of an 8.5x11 inch paper.
-
No cell phones. Please
plan to disable your cell phone during the test and make arrangements
accordingly.
- Know the following
terminology:
- heap property,
min-heap, max-heap, tail-recursive operation, binary tree height,
complete binary tree, priority queue
- binary-search-tree
property
- division method of hashing
- direct access table
- dictionary operations
- From Chapter 11 - Direct
Addressing and Hashing
- Chapter 11/Exercise 6
- Know how division method of hashing works.
- Write a simple algorithm to perform an
operation on a direct address or hash table.
- From
Chapter 12/Exercise 7/Homework 6
- Binary Trees
- Be able to execute Tree-Insert,
Tree-Delete, Inorder-Tree-Walk
- Write a simple algorithm to perform an
operation on a binary search tree.
- Transform a
tail-recursive operation into an iterative operation
- From
Chapter 6/Exercise 5/Homework 5
- Binary Heap -
its abstract representation and how its actually represented
- What these
operations do, their performance with an explanation:
Heapify,
Build-Heap, Heapsort
- Transform a
tail-recursive operation into an iterative operation
- Write a simple algorithm to
perform an operation on a heap.
§
How a heap is used to implement a
Priority Queue
§
What these operations do, their
performance with an explanation:
Heap-Maximum, Heap-Extract-Max,
Heap-Increase-Key, Max-Heap-Insert