Solving recurrence equations
- 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?
Insertion sort – algorithm, complexity and benefits
Selection sort – algorithm, complexity and benefits
Quicksort – algorithm, complexity and benefits
Mergesort – algorithm complexity and benefits
- 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?
Complexity of operations in splay trees
Algorithms for find(key), min(), max(), remove(key)
- Algorithms for inserting, deleting and finding a key in a splay tree?
- Compare splay tree with binary search tree.
Relationships between priority queues, selection sort, and the heap data structure.
Operations: min(), insert(key), removeMin(), bottomupHeap(), heapsort()
In-place heap sort
- 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).
Representations: Adjacency matrix, Adjacency list
Graph traversals (DFS, BFS)
Shortest path algorithm
- 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.
Hashcoding and compression function
Examples of bad and good hash-coding
Examples of bad and good compression function
- 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
- Given two strings, find the longest common substring.
- Given a text T, find the longest palindrome as a substring of T.