# 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

Representations: Adjacency matrix, Adjacency list

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

Collision, load-factor

**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.