Interesting Algorithms

1. Let A be a list of n elements in non-decreasing order where some elements are replicated.
The problem is to find the element that appear most frequently. Give an O(k log n) time
algorithm to solve the problem where k denotes the number of distinct elements in A.


2. You are given a list A = [a1; a2; - - - ; an] of n distinct numbers in an arbitrary order.
You are supposed to find two numbers _i and _j from A such that (i) i < j, (ii) _j > _i, and
(iii) satisfying (i) and (ii), aj - ai is minimum over all possible such pairs. Give an O(n) time
algorithm.


3. A carpenter has a piece of wood of a certain length that must be cut at positions a₁, a₂ ..., a_n where a_i is the distance from the left end of the original piece of wood. Notice that after making the first cut, the carpenter now has two pieces of wood; after making the second cut, the carpenter has three pieces of wood, etc. Assume that the cost of making a cut in a piece of wood of length l is equal to l, and is the same no matter which position in that piece of wood is being cut. Let L be the length of the original piece of wood.
Derive the recurrence relation which could be used to design a recursive algorithm to find the minimum total cost for making all the cuts.


4. Describe a Θ(n lg n)-time algorithm, that given a set of n integers and another
integer x, determines whether or not there exist two elements in S whose sum is exactly x. Write
pseudocode.
Hint: Sort using mergesort and iterate once after sorting. Θ(n lg n+n) = Θ(n lg n)


5. Suppose you are given an array A containing n sorted elements followed by lgn unsorted elements. Thus, entire array contains N = n+lgn elements. Can the entire array sorted in O(n) time.

6.  You are given an array of n numbers. Write an algorithm with O(n)=nlogn  that returns the number of distinct numbers in the array.   

Minimum Spanning Tree - True or False

1. In an undirected graph, the shortest path between two nodes lies on some minimum spanning
tree.
A: False.

2. If the edges in a graph have different weights, then the minimum spanning tree is unique.
A: True.

3. If the edge with maximum weight belongs to a cycle, then there exists some MST that
does not contain this edge.
A: True

4. Adding a constant to every edge weight does not change the minimum spanning tree.
A: True

5. There can be more than one minimum spanning trees if the weight of the edges are all distinct
A.False

6. If all weights are the same, every spanning tree is minimum.
A. True

7. Greedy algorithm runs in exponential time
A. False

8. A minimum spanning tree should contain all edges of the graph
A. False

9. A minimum spanning tree should contain all vertices of the graph
A.True

10.Adding an edge to a spanning tree of a graph G always creates a cycle.
A.False

11. Adding an edge to a spanning tree connecting two existing vertices of a graph G always creates a cycle.
A. True

12. For any cycle in a graph, the cheapest edge in the cycle is in a minimum spanning tree.
A. False

Big O, Big Omega, Big Theta

For each of the following pairs of functions f(n) and g(n), state whether f(n) =
O(g(n)), f(n) = ­Ω(g(n)), or f(n) = Θ(g(n)), or none of the above:


(a) f(n) = n2 + 3n + 4, g(n) = 6n + 7
Sol: f(n) = ­Ω(g(n).


(b) f(n) = n √n , g(n) = n2 - n
Sol: f(n) = O(g(n)).


(c) f(n) = 2**n - n**2, g(n) = n**4 + n**2
Sol: f(n) = ­­Ω(g(n).


(d) Assume you have five algorithms with the running times
listed below (these are the exact running times). How much slower do each of these
algorithms get when you double the input size
i) n²
Sol: 4T(n)

ii) n³
Sol: 8T(n)

iii) 100n²
Sol: 4T(n)

iv) nlgn
Sol: 2n(lg2n) = 2n(1+lgn) ~ 2n lgn
T(n) = 2T(n)

v) 2ⁿ
Sol:  [T(n)]² 


(e)  Write a big-O expression for 1+2+3+...+n?
Sol:  O(n²)


True or false:
(f) An algorithm with worst case time behavior of 3n takes at least 30 operations for every input of size n=10.
Sol : False


(g)  n! = O(nⁿ)
Sol: True


(h) n^O(1) = O(n²)
Sol: False.  O(1) can be any large constant .


(i) All of the following are true.

• f(n) = O(f(n))
• c * O(f(n)) = O(f(n)), if c is constant
• O(f(n)) + O(f(n)) = O(f(n))
• O(O(f(n))) = O(f(n))
• O(f(n)) * O(g(n)) = O(f(n)g(n))
• O(f(n)g(n)) = f(n) * O(g(n))