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
Problem-solving approaches
- recursion, divide-and-conquer, generate-and-test
Sorting methods
- simple sorts: selection, insertion, bubble
- better sorts: mergesort, quicksort
- complexity of various sorting algorithms
Linear structures
- linked-lists: 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, red-black, ...
- 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: depth-first, breadth-first
- minimum spanning tree, shortest path
|