Rooted trees
- Given a binary tree, print the elements in a reversed level order.
- Find the nearest match of a given value in a binary search tree.
- Write a function to check whether two binary trees are structurally identical.
- Write a function to find the size of a BST.
- Write a function to compute the sum of all the elements in a BST.
Complexity analysis
- Write down the lower bound, upper bound, and order functions for the following timing function:
f(n) = 0.5 * n^3 + 2 * n^2 + log n - Solve the following recurrence equation:
T(1) = 1; T(n) = T(n-1) + n(n-1), n > 1
Answer
- For the sorting algorithm below, compare the time complexity for partitioning in the middle vs the beginning.
L' = Sort (L, n)
begin
if (n == 1) L' = L;
else
Split L into two non-empty sets L1 and L2;
L1' = Sort(L1);
L2' = Sort(L2);
L' = MERGE(L1', L2');
end
end
Sorting
- Discuss the sorting algorithms covered in the class. Analyze the time complexity for each sorting algorithm.
- Given an array of n numbers, design 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, design an algorithm for efficiently sorting the array.
Heaps
- 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 inplace sort in descending order: 3, 5, 2, 9, 20.
- Given a big file containing billions of numbers, design an algorithm to find the max 10 numbers.
Graphs
- Write an algorithm for checking whether a given graph has a simple path from a given source node to a given destination node.
- Assuming an adjacency matrix representation of a graph, count all the simple paths from a source to a destination.
- Given a directed graph, write an algorithm to detect whether there is a cycle.
- Given an undirected graph, write an algorithm to detect whether there is a cycle.
- Assuming that there are only non-negative weights, suggest an algorithm for computing the single-source shortest path.
Hashing
- Design an efficient algorithm to find the first non-repeated character in a string.
- Design 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 to find whether there exists a pair of elements, one from A and one from B that adds up to K.