Final review

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

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

 

This entry was posted in Data-structures. Bookmark the permalink.

Comments are closed.