CS340 Home Page
Date Structure and Algorithms
Winter, 1996, Ming Li
Contents
-
Ming Li
- Office: DC 2339
- Phone: x4659
- E-mail: mli@math
- Office Hours: Wednesday & Friday, 3:30 -- 5:00 PM.
- Karsten Verbeurgt, DC3145, x3497, kaverbeurgt@neumann,
Office Hours: Wednesday 1-2pm.
- Ka Yee Yeung, DC2127, x3299, kyyeung@neumann,
Office Hours: Tuesday 1-2pm.
- Hao Zhang, DC3529, x3590, hzhang@neumann,
Office Hours: Monday 1-2pm.
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.
-
Big-O 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 Lempel-Ziv algorithm.
Including prefix codes, Morse code (no need to memorize the
actual code).
- Optimal linked list. Dynamic linked list (move-to-front
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.
- AVL-trees. Single/double rotations.
- Skip lists.
- B-trees.
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.
-
B-trees. 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. Depth-first search
(Topological sort), breadth-frist 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.