Upper bound function
Lower bound function
Solving recurrence equations
Insertion sort – algorithm, complexity and benefits
Selection sort – algorithm, complexity and benefits
Quicksort – algorithm, complexity and benefits
Mergesort – algorithm complexity and benefits
Complexity of operations in splay trees
Algorithms for find(key), min(), max(), remove(key)
Relationships between priority queues, selection sort, tournament sort and the heap data structure.
Operations: min(), insert(key), removeMin(), bottomupHeap(), heapsort()
In-place heap sort
Graph traversals (DFS, BFS)
Hashcoding and compression function
Examples of bad and good hash-coding
Examples of bad and good compression function
C++ templates and STL
Converting existing programs into parameterized programs
What STL to use when?
- 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.