Syllabus Detail
For each specific data type, we considered:
 implementation in C (data structures, functions)
 operations (e.g. new, insert, delete, search, traverse)
 analysis of efficiency of operations
 applications of the data type
Abstract data types
 interface vs implementation
 defining ADOs, ADTs and GADTs in C
Problemsolving approaches
 recursion, divideandconquer, generateandtest
Sorting methods
 simple sorts: selection, insertion, bubble
 better sorts: mergesort, quicksort
 complexity of various sorting algorithms
Linear structures
 linkedlists: singly linked, doubly linked
 sets, stacks, queues, priority queues, heaps
Trees
 tree terminology, tree properties
 binary search trees, recursive algorithms
 tries, radix searching
Balanced search trees
 varieties of balanced trees: splay, redblack, ...
 tree rotations, tree joins, tree merge
Hash tables
 hash functions
 implementation/use of hash tables
 collision handling: chains, linear probe, double hash
Graphs
 graph terminology, graph properties
 implementation of graphs: adjacency matrix, ...
 graph search: depthfirst, breadthfirst
 minimum spanning tree, shortest path
