CS340 Home Page
Date Structure and Algorithms
Winter, 1996, Ming Li
Contents

Ming Li
 Office: DC 2339
 Phone: x4659
 Email: mli@math
 Office Hours: Wednesday & Friday, 3:30  5:00 PM.
 Karsten Verbeurgt, DC3145, x3497, kaverbeurgt@neumann,
Office Hours: Wednesday 12pm.
 Ka Yee Yeung, DC2127, x3299, kyyeung@neumann,
Office Hours: Tuesday 12pm.
 Hao Zhang, DC3529, x3590, hzhang@neumann,
Office Hours: Monday 12pm.
The following assignments will be readable on the handout dates.
The midterm exam will cover topics we covered in the class
till Friday, Feb 9, inclusive. These include

Abstract data types: List, Array, Queue, Stack, Tree, Dictionary, Set,
Priority Queue.

Level of data abstraction. Data representation.

BigO notation

Analyze time/space complexity of a simple algorithm/program.

Divide and Conquer technique.

Binary search, sequential search, interpolation search.

Binary search trees. Tree traversal.

Data Compression: Huffman's algorithm and LempelZiv algorithm.
Including prefix codes, Morse code (no need to memorize the
actual code).
 Optimal linked list. Dynamic linked list (movetofront
strategy).
 External/internal path length. Average successful/unsuccessful
search cost on a (random) binary search tree.
 Optimal binary search trees. Dynamic programming technique.

Insert/delete on binary search trees.
 AVLtrees. Single/double rotations.
 Skip lists.
 Btrees.
30% of the final exam will cover topics we covered before
the midterm exam, and 70% of the final exam will cover
topics we taught after the midterm. Here is a list
of topics in the latter category.

Btrees. Also B+ trees.

Splay trees, splay operations (zigzig, zigzag, zig).

Tries, patricia trees, and digital search trees.

Hashing. Hashing schemes, principles, how to design hash
functions, how to solve collisons. Open addressing. Double hashing.
Secondary clustering.

External hashing techniques.

Sorting. All algorithms. Analysis of heapsort (priority queue, heap)
and quicksort. Time complexity of sorting algorithms. Lower bounds for
sorting (model). Stable sorts.

External sorting algorithms. Mergesort, radix sort, bucket sort,
counting sort.

Pattern matching, KMP algorithm, understand skip table.

Union/find data type.

Graph search algorithms. Depthfirst search
(Topological sort), breadthfrist search.
Minimum spanning trees. Sortest paths.

Basic ideas on what is feasibly computable and what is not.
And how to cope with problems that are difficult to compute.

We will also test your ability of designing your own data structure
to solve problems. (Say 1 question on this.)
As promised, all Lecture Notes are now ready.
These are probably all the lecture notes we will be using, although it
is possible I will be adding some more material, depending on
whether we have time left by the end of the semester.
It is usually not the case that one lecture corresponds to one set of
notes. I divided them more according to logical topics rather than
physical lectures.