## Asymptotic complexity

Upper bound function

Lower bound function

Order function

Solving recurrence equations

## Sorting

Insertion sort – algorithm, complexity and benefits

Selection sort – algorithm, complexity and benefits

Quicksort – algorithm, complexity and benefits

Mergesort – algorithm complexity and benefits

## Splay trees

Splay operations

- Zig-zag
- Zig-zig
- Zig

Complexity of operations in splay trees

Algorithms for find(key), min(), max(), remove(key)

## Heaps

Relationships between priority queues, selection sort, tournament sort and the heap data structure.

Operations: min(), insert(key), removeMin(), bottomupHeap(), heapsort()

In-place heap sort

## Graphs

Representations

Graph traversals (DFS, BFS)

## Hashing

Hashcoding and compression function

Examples of bad and good hash-coding

Examples of bad and good compression function

Collision, load-factor

## C++ templates and STL

Converting existing programs into parameterized programs

What STL to use when?

# Problems

- What are the minimum and maximum number of elements in a heap of height h?
- Given a min-heap, how would you find the max element? What is the complexity of such an algorithm?
- Insert the following numbers into a heap for an in-place sort in descending order: 3, 5, 2, 9, 20
- Algorithms for inserting and deleting an entry in a heap?
- Algorithms for inserting, deleting and finding a key in a splay tree?
- Discuss the sorting algorithms covered in the class.
- Give an efficient algorithm to find the first non-repeated character in a string.
- Give an efficient algorithm to find the first repeated character in a string.
- Given a directed graph, give an algorithm to detect whether there is a cycle.
- Given an undirected graph, give an algorithm to detect whether there is a cycle.
- Given a directed acyclic graph, give an algorithm to topologically sort the nodes.