# Post-midterm review

## Asymptotic complexity

Big-oh notation

Big-omega notation

Big-theta notation

Solving recurrence equations

Problems:

• Solve the recursive equation: T(1) = 1; T(n) = T(n-1) + n(n-1), n>1.
• What is the min number of comparisons needed to find both max and min of n integers?
• What is the min number of comparisons to find the max and the second max of n integers?

## Sorting

Insertion sort – algorithm, complexity and benefits

Selection sort – algorithm, complexity and benefits

Quicksort – algorithm, complexity and benefits

Mergesort – algorithm complexity and benefits

Problems:

• Discuss the sorting algorithms covered in the class.
• Discuss the comparison of computational complexities of these sorting algorithms.
• Given an array of n numbers, give an algorithm for checking whether there are repeated elements, without any additional space overhead.
• Given an array consisting of 0’s, 1’s and 2’s, given an algorithm for sorting the array.
• Given an array of 1M pixel color values and each of which is an integer in the range [0,255], which sorting algorithm is preferable for such an array?

## Splay trees

Splay operations

• Zig-zag
• Zig-zig
• Zig

Complexity of operations in splay trees

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

Problems:

• Algorithms for inserting, deleting and finding a key in a splay tree?
• Compare splay tree with binary search tree.

## Heaps

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

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

In-place heap sort

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?
• Given a big file containing billions of numbers, how do we find the max 10 numbers?
• Show that the bottomUpHeapConstruction() strategy would take O(n) and not O(n lg n).

## Graphs

Graph traversals (DFS, BFS)

Shortest path algorithm

Problems:

• Give an algorithm for checking whether a given graph has a simple path from a source node (s) to a destination node (t).
• Assuming an adjacency matrix representation of a graph, count all the simple paths from source (s) to destination (t).
• 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.
• Find the shortest graph distances between every pair of vertices in a given graph. Assume there the graph only has non-negative weights on the edges.

## Hashing

Hashcoding and compression function

Examples of bad and good hash-coding

Examples of bad and good compression function

Problems:

• 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 an array of n numbers, present an algorithm which displays all pairs whose sum is S.
• Given two sets A and B, and a number K, present an algorithm for finding whether there exists a pair of elements, one from A and one from B, that add up to K.
• How would you implement an ordered/unordered set/map?

## Tries and Suffix Trees

Trie and suffix tree representations and applications

Nifty solutions based on suffix trees to various string matching problems

Problems:

• Given two strings, find the longest common substring.
• Given a text T, find the longest palindrome as a substring of T.