[prev] 4 [next]

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