CmSc 250: Intro to Algorithms

Sample Final Exam

  1. Which of the following are true (circle the correct answers, there may be more than one correct answer)

N2 +logN = O((logN) 3) N2 + logN = O(NlogN) ,

N2+N2logN = O(N2)N2+ logN = O(N2logN),

NlogN = O(N2)NlogN = O(N2 + logN)

N2logN = O(N2) N2 = O(NlogN)

  1. Give an analysis of the running time for the following loops, using the Big-Oh notation. Explain your reasoning:

a)

for( i = 1; i < n-1; i=2*i)

if(2*i < n & a[i] > a[2*i])

{

temp = a[i];

a[i] = a[2*i];

a[2*i] = temp;

}

b)

for( i = 0; i < n; i++)

for( j = n-1; j >=0 ; j--)

if( a[i][j] == 0)

for(k = j; k < n-1 ; k++)

a[i][k] = a[i][k+1];

  1. What is the complexity of search in Binary Search trees, provided they are kept balanced?
  1. What is the worst complexity of search in Binary Search trees, provided they are not kept balanced? When does it happen?
  1. Which traversal order would retrieve the elements in a Binary Search Tree in sorted order?
  1. What is depth of a node?
  1. What is height of a node?
  1. In a perfect binary tree with N nodes how many leaves are there?
  1. In a perfect binary tree, how many nodes are there at level p?
  1. Construct a complete binary tree with 8 nodes and assign the letters of PORTLAND to the nodes so that the name can be read in a post-order traversal
  1. In the AVL tree below insert 1. Indicate the violated node (the node whose left and right subtrees differ in depth by more than 1) and the type of rotation
  1. In the AVL tree below insert 27. Indicate the violated node and type of rotation
  1. What does a hash function do?
  1. What is the expected complexity of search in hash tables?
  1. What is the difference between separate chaining and open addressing?
  1. What is a load factor of a hash table? What should be the value of the load factor with open addressing so that we have good performance?
  1. What is rehashing? When is it necessary? What is the complexity of rehashing?
  1. Match the descriptions on the left with the names of sorting algorithms on the right

Assumes part of the array is sorted, inserts the next element there. / MergeSort
Splits the array into two, sorts recursively and then merges / Bubble
Based on insertion sort, however the increment step is not static - it is determined by the so called increment sequence / Shell sort
Compares and swaps adjacent elements. Several passes are needed / Insertion
  1. Describe briefly heapsort.
  1. Describe briefly quicksort
  1. Which sorting algorithm are you going to choose if the file to be sorted has very large records and why?
  1. Which sorting algorithm are you going to choose if the file is almost sorted and why?
  1. Which algorithm is usually very fast, however in certain cases its run time may increase to O(N2), and that is why it is usually not used for military and life-supporting applications
  1. Which algorithm requires additional memory comparable in size to the sorted file?
  1. Which algorithm uses a pivot in the sorting process?
  1. Write down the average complexity of each algorithm using Big Oh notation

Bubble sort

Heap sort

Insertion sort

Mergesort

Quick sort

Selection sort

  1. Write the recurrence relation for the worst case complexity of quicksort and solve it.
  1. Write the recurrence relation for the best-case complexity of quicksort and solve it.
  1. Solve the following recurrence relation:

T(N) = 2T(N-1) +1

  1. Consider the following recursive algorithm:

Algorithm Q(n)

//Input: A positive integer n

if n = 1 return 1

else return (Q(n − 1) + 2 ∗ n – 1)

  1. Write down a recurrence relation for the run time of the algorithm and solve it
  2. Write down a recurrence relation for the function Q(n) and solve it
  3. Write down a recurrence relation for the number of multiplications and solve it
  1. Which algorithm is described by the following pseudocode?

1. Initialize D_table s,0 = 0

D_table s,1 = -1

D_table i,j = -1 , i ≠s, j = 0,1

2. Store s in a queue

3. While there are vertices in the queue:

Read a vertex v from the queue

For all adjacent vertices w:

If D_table w,0 = -1 (not computed)

D_table w,0 = D_table v,0 + 1

D_table w,1 = v

Append w to the queue

  1. Which of the following algorithms use priority queue, and which use a queue?

topological sortqueuepriority queue

shortest path algorithm queuepriority queue

unweighted graphs

shortest path algorithm queuepriority queue

weighted graphs

spanning tree in queuepriority queue

unweighted graphs

minimal spanning tree queuepriority queue

weighted graphs

  1. Circle the correct complexity of the following graph algorithms

(|V| - number of nodes, |E| - number of edges.)

topological sort O(|E| + |V|) O(| E |log(| V |))

shortest path algorithm O(|E| + |V|) O(| E |log(| V |))

unweighted graphs

shortest path algorithm O(|E| + |V|) O(| E |log(| V |))

weighted graphs

spanning tree in O(|E| + |V|) O(| E |log(| V |))

unweighted graphs

minimal spanning tree O(|E| + |V|) O(| E |log(| V |))

weighted graphs

  1. The Rubik cube puzzle can be represented by a directed graph, where each vertex corresponds to a state of the cube and each arc corresponds to a move. If there is an edge between two nodes, there is a move that transforms the state of the Rubik cube represented by the first node to a state represented by the second node. Which graph algorithm can be used to find the best solution of the puzzle, the solution with the least number of moves?
  1. You have a business with several offices; you want to lease phone lines to connect them up with each other; and the phone company charges different amounts of money to connect different pairs of cities. You want a set of lines that connects all your offices with a minimum total cost
  1. Consider the following problem:A cable company has to connect four buildings using minimum resources (e.g. length of cable) The distances between the buildings are given below. Which graph algorithm can be used to solve this problem? What is the result – the best way to connect the buildings?

A5B

3 7 8 4

C8D

  1. Describe briefly the greedy approach to problem solving. Give an example of a problem solved by a greedy algorithm and describe the algorithm.
  1. Describe briefly the divide-and-conquer approach to problem solving. Give an example of a problem solved by a divide-and-conquer algorithm and describe the algorithm.
  1. Describe briefly the dynamic programming approach to problem solving. Give an example of a problem solved by a dynamic programming algorithm and describe the algorithm.
  1. Which problems are called P problems? NP- problems? NP-complete problems? NP-hard problems? Give an example for each class of problems.