CSC263: List of Topics for the Exam

* Asymptotic notation.

* Worst-case, Best-case and Average case complexity.

* Sorting algoruthms. QuickSort.

* Dictionary ADT. Search Trees. Height-balanced trees. AVL trees. How all 
  operations are being implemented.

* Priority Queues. Min-heaps. Understand the tree structure as is stored in an 
  array (note the notion of a "complete tree"). How all operations are being
  implemented. Inparticular, understand up-heap down-heap bubbles.

* binomial heaps. The concept of Binomial trees. Understand the implementation 
  of all operations. Understand 
  the unique composition of binomial trees of a binomial heap that holds a 
  certain number of keys. 

* Hashing. The concept of collisions. Closed and open hashing. Worst case 
  behaviour. Average case behaviour (and under what assumptions). Issues with 
  for different choices of hash functions functions.

* disjoint-set ADT. Differnt data structures. analysis of their worst 
  case time and amortized time. 

* Graphs. Different representations. Advantages and disadvantages of these.

* travesal algorithms. DFS and BFS. Why is the running time O(m+n). In which
  graph representation does this hold?

* connected componenets in undirected graphs. Strongly connected components in
  directed graphs. The "reachability relation". Cycles in directed/undirected 
  graphs and their detection.