Cs502 Collection of Old Papers

www.vujannat.ning.
com
CS502 Fundamentals of Algorithms

Final Term Examination - February 2005
Time Allowed: 150 Minutes
Instructions
Please read the following instructions carefully before attempting any of the
questions:
1. The duration of this examination is 150 Mins.

2. This examination is closed book, closed notes, closed neighbors.
3. Do not ask any questions about the contents of this examination from anyone.
a. If you think that there is something wrong with any of the questions, attempt it
to the best of your understanding.
b. If you believe that some essential piece of information is missing, make an
appropriate assumption and use it to solve the problem.
4. Some of the examination consists of multiple-choice questions. Choose only one
choice as your answer.
a. If you believe that two (or more) of the choices are correct for a particular
question, choose the best one.
b. On the other hand, if you believe that all of the choices provided for a
particular question are wrong then select the one that appears to you as
being the least wrong.
**WARNING: Please note that Virtual University takes serious note of

unfair means. Anyone found involved in cheating will get an `F` grade in
this course.
Total Marks: 80 Total

Questions: 9
Question No. 1 Marks : 10
Answer yes or no and give a brief explanation for your choice.
(a) Kruskals algorithm for minimum weight spanning trees is an example of dynamic
programming algorithm.
(b) An arbitrary graph with G (V, E), with |E| = |V|-1 edges is a tree.
(c) If problem A reduces (is polynomial-time reducible) to problem B and B is NP-
complete then A is NP-complete.
(d) Every problem in NP is NP-complete.
(e) If problem A reduces to problem B and B is in P, then A is in P.
If a problem is not in P, it must be NP-complete.
1 True
2 False
3 Unknown
Consider the following code:

for (j=1; j<n;j++)
for (k=1; k<15;k++)
for(l=5; l<n; l++)
{
Do_something_constant();
}
What order is the execution of this code?
1 O(n)
3
2 O(n )
2
3 O(n log n)
2
4 O(n )
Given a list of N integers, the 3-sum problem is to determine whether there exists 3 integers
in the list (not necessarily distinct) such that x + y + z = 0. Suppose that you are executing the
brute force algorithm below on a computer that executes 1 billion operations (addition,
increment, or comparison) per second.
int brute(int a[], int N)

{
int i, j, k;
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
for (k = 0; k < N; k++)
if (a[i] + a[j] + a[k] == 0) return 1;
return 0; // none found
}
(a) Estimate how many seconds it will take (in the worst case) to solve a problem of size N =
1,000? Full credit if you are within 1% of the exact answer.
(b) Of size N = 10,000?
What is the solution to the recurrence T(n) = T(n/2)+n, T(1) = 1
1 O(logn)
2 O(n)
3 O(nlogn)
2
4 O(n )
5 O(2n)
Consider the following undirected graph
(0-1, 1) (0-4, 4) (0-6, 1) (0-5, 2) (1-2, 1) (1-4, 2)

(1-6, 3) (2-3, 2) (2-5, 3) (3-4, 1) (4-5, 1) (5-6, 3)
Where (i-j, w) means that the edge that connects node i to node j has weight w. give the
parent-link representation of the shortest-paths tree from node 0 that is computed by
Dijkstra's algorithm for the graph using the standard adjacency-lists representation.
Consider the following recurrence equation:

T(1) = 5
T(n) = 2+T(n - 1) for n ≥ 2
T(n) =
Consider the following undirected network with edge weights as show:

(a) List the edges in the MST in the order that Prim's algorithm chooses them. Start Prim's
algorithm from vertex 1.
(b) List the edges in the MST in the order that Kruskal's algorithm selects them.
Kruskals algorithm (choose best non-cycle edge) is better than Prim's (choose best tree
edge) when the graph has relatively few edges.
1 True
2 False
3 Unknown
Page 1 of 2
www.vujannat.ning.com

Final Term Examination - August 2004
Instructions
questions:
1. Attempt all questions. Marks of every question are shown adjacent to it.
a. If you think that there is something wrong with any of the questions, attempt
it to the best of your understanding.
**WARNING: Please note that Virtual University takes serious note of unfair
means. Anyone found involved in cheating will get an `F` grade in this course.
Very Important:
Some results you may need:
n n(n + 1) n i x ( n +1) − 1
n
2n3 + 3n 2 + n
∑ i=
i =1 2 ∑ i =
2 ∑ x =
x −1
, i =1 6 , i =1
So please copy this in the word file for later use.
Total Marks: 120 Total Questions: 12
It is impossible to design a sorting algorithm based on comparison of keys worst-case run time is in
O(n).
o True
o False
Consider the following problem: You are given a sequence of n integers that contains log2 n different
integers.For example, n = 8, log(8) = 2: {3,5,3,5,3,5,5,5}; the list of 8 numbers is made up of only two
distinct integers 3 and 5. Design an algorithm to sort this sequence using O(nlog logn) element
comparisons (which is better than O(nlogn)). Prove that your algorithm is indeed O(nlog logn)
[Hint: use variation of heap sort.]
In the following graph, edges are labeled with upper case letters. Edge weights are given
as numbers next to edges.
Recall that Kruskal's algorithm greedily adds edges in a way that avoids cycles. For the graph
shown above, list the edges in the order chosen by Kruskal's algorithm.
Greedy algorithms are called "greedy" because they often take a lot of time.
o True
o False
Kruskal's algorithm (choose best non-cycle edge) is better than Prim's (choose best tree edge) when
the graph has relatively few edges.
o True
o False
Quick sort has a good average run time and a poor worst-case run time.
o True
o False
Page 2 of 2
In the following algorithm, ". . ." stands for some simple calculations that take constant
time, i.e., Θ(1).
procedure(n)
for k from 1 to n do
... /* produces a number j */
if k divides j, then mergesort an n-long list
...
end for
...
end
Note: Think of j as a random integer, so the probability that "k divides j" is "1/k".
(a) Suppose the sorting were free (which it is not). What is the complexity class for the
average running time of this algorithm. You MUST give a reason for your answer. (The class
should be of the form Θ( f (n)) where f (n) is a simple function.)
(b) Suppose that the basic operation is a comparison in merge sort. What is the complexity
class for the average running time of this algorithm. (You may give your answer in the form
Θ(∑ f (k)) where f (k) is a simple function and the sum runs from 1 to n.) You MUST give a
reason for your answer.
(c) Use (a) and (b) to find the complexity class for the average running time of this algorithm.
You MUST give a reason for your answer.
There is a good greedy algorithm for the 0-1 Knapsack Problem.
o True
o False
Consider the following two problems. In P1 we are given as input a set of n squares (specified by
their corner points), and a number k. The problem is to determine whether there is any point in the
plane that is covered by k or more squares.
In P2 we are given as input an n–vertex graph, and a number k; the problem is to determine whether
there is a set of k mutually adjacent vertices. (E.g. for k = 3 we are just looking for a triangle in the
graph.).
Obviously, the problems are both in NP. There exists a simple translation from P1 to P2: just make a
graph vertex for each square, and add an edge between a pair of vertices if the corresponding two
squares overlap.
(a) If P1 is NP-complete, would this translation imply that P2 is NP-complete?

(b) If P2 is NP-complete, would this translation imply that P1 is NP-complete?
(Give your Answer in Yes or NO only)
Dynamic programming uses a top-down approach.
o True
o False
Solve the following recurrence relation with full history:

n-1
T ( n) = ∑ T(i),
i=1
T (1) = 1
Hint: subtract T(n) from T(n+1).
Consider the directed graph G below:
(a) Run DFS on this graph and write down the values of d[v] and f [v] for all vertices v. Assume
that in outer for-loop of the DFS, vertices of G are processed in numeric order of their labels.
For example, DFS will choose v1 initially. Also assume that in DFS-Visit, vertices adjacent to
each vertex u are processed in increasing numeric label. For example, if v10, v5, v8 are
adjacent to some vertex, they will be processed in the order v5, v8, v10.
(b) Identify tree edges, back edges, forward edges and cross edges for the DFS.

Final Term Examination – Spring 2005
Please read the following instructions carefully before

attempting any of the questions:
3. Do not ask any questions about the contents of this examination from
anyone.
a. If you think that there is something wrong with any of the
questions, attempt it to the best of your understanding.
b. If you believe that some essential piece of information is
missing, make an appropriate assumption and use it to solve
the problem.
4. Some of the examination consists of multiple-choice questions.
Choose only one choice as your answer.
a. If you believe that two (or more) of the choices are correct for a
particular question, choose the best one.
b. On the other hand, if you believe that all of the choices provided
for a particular question are wrong then select the one that
appears to you as being the least wrong.
**WARNING: Please note that Virtual University takes serious

action against unfair means. Anyone found involved in
cheating will get an `F` grade in this course.

n n(n + 1) n i x ( n +1) − 1
∑ i=
n
2n3 + 3n 2 + n
i =1 2 ∑ i =
2 ∑ x =
x −1
, i =1 6 , i =1
Best and worst case times of an algorithm may be same.
o True
o False
Can an adjacency matrix for a directed graph ever not be square in shape?
o Yes
o No
If an algorithm has a complexity of 2n2 + 4n + 3 for some model of computation (some

set of assumptions) and some complexity measures (such as number of comparison
operations) we could say that it has complexity
o (a) O(log2 n)
o (b) O(n2)
o (c) O(2 + 4 + 3)
o (d) all of the above
o (e) none of the above
You are given the task of laying down new railway lines which will connect all n cities.
Thus for any pair of cities, you will end up with track connecting them. Note that two
routes may share the same track; track laid between Lahore and Islamabad can be used to
travel in both directions. your goal is to use the minimum amount of track. How would
you achieve the goal now? (Note : consider the scenario carefully and name only the best
suited algorithm)
o 1 Dijkstra's algorithm
o 2 Prims algorithm
o 3 Floyd Warshall algorithm
o 4 Bellman Ford algorithm.

You land at Heathrow airport for a vacation in London. Your hotel located in Essex, a
suburb of London. You will need to take the train to get to your hotel. You have a map
that shows the train lines and the fares between various points in London. You would like
to minimize the fare you need to pay to travel from the airport to your hotel. To make
matters complicated, the airline you traveled on gave you a discount coupon that can be
used on one train journey. The coupon can be used only once. The coupon will get you
50% discount on the train fare. The coupon also lists which train lines the coupon can be
used on to get the 50% discount. Solve the problem on the following sample train lines
map (node A is the airport, node B is Essex where the hotel is). The notation 40,y means
the fare is 40 and discount is available. If the coupon is used on this line, the fare would
be 20. Describe the algorithm you have used to determine the train route that minimizes
the total fare. [25 pts]
Solve the following recurrence using iteration method ( show intermediate steps )[10 pts]
T(n) = n + 2T(n/2)
T(1) = 1

Recall that a dynamic programming solution to the 0-1 knapsack problem can be derived
from the following recurrence formula for c[i,w], the value of the solution for items 1, . .
. , i and maximum weight w.
>:
The algorithm based on this recurrence takes as inputs the maximum weight W, the
number of items n, and the two sequences v = hv1,v2, . . . ,vni and w = hw1,w2, . . . ,wni.
It stores the c[i, j] values in a table c[0..n,0..W]. At the end of the computation, c[n,W]
contains the maximum value the thief can take.
In the following example the inputs are n = 6,W = 8, with values vi and weights wi:
From these inputs the following c table is computed by the algorithm:
The last part of the algorithm uses this table to determine which items the thief should
take to achieve the maximum value, 22.
(a) Describe this last part of the algorithm: how, in general, it determines the items to be
taken.(Note : in maximum three lines.)
(b) For the above example, list the items to take (i.e., list their indices).
[25 pts]
Run DFS sweep and topological sort on the directed graph defined by the following
adjacency matrix.
[15 pts]
Connecting VU Students
CS502-Fundamentals of Algorithms
Final Term Examination – spring 2006
Compute all-pairs shortest paths using Floyd-Warshall algorithm on the following graph
Use Prim’s Algorithm starting with vertex “V1”to find the minimal spanning tree for the graph
Consider the following digraph

(a) Find the adjacency matrix of this graph
(b)List the strongly connected components of this digraph
If a graph has v vertices and e edges. Then to obtain a spanning tree we have to delete
• v edges
• v – e + 5 edges
• v + e edges
• None of these
Which of the following is not true about Dijkstra’s algorithm?

I. The length of the shortest path to the start vertex is always zero
II.It takes time polynomial to the number of vertices
III. It will work on any weighted graph with positive weights
IV. It can be implemented to run in O(V ) time
• Only II
• Only IV
• Both II and IV
• None of these
If a problem is not in P, it must be NP-complete
• Yes
• No
• Unknown
You are managing 300 million dollars. From this money you can sponsor 4 projects P1, P2, P3,
and P4 with total cost no more than 300 million dollars. The project P1 has cost 60 million and
generates a profit 20 millions ,the, project P2 has cost 240 million and generates a profit 500
millions, the project P3 has cost 180 million and generates a profit 300 millions ,the project P4
has cost 120 million and generates a profit 210 millions
Find out which projects to sponsor so that you get the largest profit.
Hint: This is the classic 0-1 knapsack problem
Consider the following adjacency list:
Which of the following graph(s) describe(s) the above adjacency list?
1.
2.
3.
4.
5.
Which statement is true

(I) The running time of Bellman-Ford algorithm is Θ(VE)
(II) Both Dijkstra’s algorithm and Bellman-Ford are based on performing repeated relaxations
(III) The 0-1 knapsack problem is hard to solve
• Only I
• Only III
• Both I and III
• All of these
The recurrence relation of Tower of Hanoi is given below

⎧1 if n =1
T ( n) = ⎨
⎩ 2T (n − 1) + 1 if n >1
In order to move a tower of 4 rings from one peg to another, how many ring moves are required
• 15
• 7
• 12
• None of these
Which sequence is not a valid topological order of the directed graph shown below?
• ABDCEF
• ADBCEF
• ABCDFE
• ADBCFE
• ABDFEC
Suppose we have two problems A and B .Problem A is polynomial-time reducible and problem
B is NP-complete. If we reduce problem A into B then problem A becomes NP-complete
• Yes
• No
The total degrees of the following graph G
are
• 4
• 5
• 7
• 8
Which of the following arrays represent descending (max) heaps?

I. [10,7,7,2,4,6]
II. [10,7,6,2,4,7]
III. [10,6,7,2,4,6]
IV. [6,6,7,2,4,10]
• Only II
• Only IV
• Both II and IV
• Both I and III
Which of the following statement(s) is/are correct?

(a) O(n log n + n2) = O(n2).
(b) O(n log n + n2) = O(n2 log 2n)
(c) O(c n2) = O(n2) where c is a constant.
(d) O(c n2) = O(c) where c is a constant.
(e) O(c) = O(1) where c is a constant.
• Only (a)
• Only (c)
• Both (a) and (e)
• Both (c) and (e)
• (a) ,(c),(e)
The adjacency matrix say A= [aij] is defined as
⎧1 if {vi , v j }is an edge of G

aij = ⎨
⎩0 otherwise
•
aij = ⎨
⎩1 otherwise
•
⎧−1 if {vi ,v j }is an edge of G
aij = ⎨
⎩0 otherwise
•
aij = ⎨
⎩−1 otherwise
•
Consider the following Huffman Tree
The binary code for the string “TEA” is
• 10 00 010
• 011 00 010
• 10 00 110
• None of these
Which of the shortest path algorithms would be most appropriate for finding paths in the graph
with negative edge weights and cycles?
I.Dijkstra’s Algorithm
II. Bellman-Ford Algorithm
III. Floyd Warshall Algorithm
• Only II
• Only III
• Both II and III
Which of the following orders is not a possible order in which Depth First Search can visit
the vertices of the directed graph shown below?
• ABCEFD
• ACEBFD
• ADFEBC
• ADFBCE
• ABFECD
WWW.vujannat.ning.com
http://vujannat.ning.com
Largest Online Community of VU Students
FINALTERM EXAMINATION
SPRING 2007 Marks: 50
CS502 - FUNDAMENTALS OF ALGORITHMS (Session Time: 150min
-5)
StudentID/LoginID: ______________________________
Student Name: ______________________________
Center Name/Code: ______________________________
Exam Date: Thursday, July 05, 2007
INSTRUCTIONS
Please read the following instructions carefully before attempting
any of the questions:
1. Attempt all questions. Marks are written adjacent to each question
2. Paste the bitmap image for the tables, diagrams etc while solving your
questions
a. If you think that there is something wrong with any of the questions,
attempt it to the best of your understanding.
6. Write all steps, missing steps may lead to deduction of marks
7. Use of cell phone during the examination is strictly prohibited, otherwise strict
disciplinary action will be taken as per university rules

action against unfair means. Anyone found involved in
cheating will get an `F` grade in this course.
For Teacher's use only

Question 1 2 3 4 5 6 7 8 9 10 Total
Marks
Question No: 1 ( Marks: 1 ) - Please choose one

The recurrence relation of Tower of Hanoi is given below
⎧1 if n =1
T ( n) = ⎨
⎩ 2T (n − 1) + 1 if n >1
In order to move a tower of 6 rings from one peg to another, how many moves are
required?
► 15
► 7
► 63
► 32
Edge (u, v) is a forward edge if
► u is a proper descendant of v in the tree
► v is a proper descendant of u in the tree
► None of these
⎛ ⎞
Is 22n = O⎜2 n ⎟ ?
⎝ ⎠
► Yes it is possible
► No it is not possible
► None of these
If, in a DFS forest of digraph G = (V, E), f[u] ≤ f[v] for an edge (u, v) Є E then the edge is called
► Back edge
► Forward edge
► Cross Edge
► Tree Edge
► None of these

How can the number of strongly connected components of a graph change if a new edge is added?
► The number of strongly connected components can be increased.
► The number of strongly connected components can be reduced.
► No change will occur.
► None of these.
Question No: 6 ( Marks: 10 )
Complete the following instance of the optimal matrix multiplication ordering problem.
Also give the optimal multiplication order.
p[0]=5 p[1]=4 p[2]=3 p[3]=4 p[4]=5

p[5]=6
1 K 2 K 3 K 4 K 5 k
1 0 0 60 1 120 2 195 2 ? ?
2 0 0 48 2 120 2 222 2
3 0 0 60 3 150 4
4 0 0 120 4
5 0 0
For the following given comparison, what are the tradeoffs between adjacency lists and
adjacency matrices?
Comparison Winner
Faster to test if (x, y) exists. ?
Faster to find vertex degree? ?
Less memory on small graphs? ?
Less memory on big graphs? ?
Edge insertion or deletion? ?
Faster to traverse the graph? ?
Better for most problems? ?

Run Dijkstra's algorithm on the following graph, starting at node A. Show all the
intermediate values.
Apply Bellman-Ford Algorithm on the following graph. Show values after each iteration
in a tabular form. S is the starting node.
Show the linear ordering of vertices produced by TOPOLOGICAL-SORT when it is run

on the following DAG
WWW.vujannat.ning.COM
FINALTERM EXAMINATION
Total Marks: 75
SEMESTER FALL 2004
CS502-FUNDAMENTALS OF ALGORITHM-3 Duration: 120min
StudentID/LoginID
Name
PVC Name/Code
Date
Maximum Time Allowed: (2 Hour)
questions:
1. Attempt all questions. All Questions carry Equal Marks.
**WARNING: Please note that Virtual University takes serious note of unfair
means. Anyone found involved in cheating will get an `F` grade in this course.
For Teacher’s use only

Question Q1 Q2 Q3 Q4 Q5 Q6 Q7 Total
Marks
n n(n + 1) n
2n 3 + 3n 2 + n n i x ( n +1) − 1
∑ i=
2
, ∑ i 2
=
6
, ∑ x =
x −1
i =1 i =1 i =1
Question No: 1 Marks: 20
Indicate whether true or false. Beware of guessing: correct answer +5pts, no answer 0pts
(a) In Prim’s algorithm, the additional information maintained by the algorithm is the length of
the shortest edge from vertex v to points already in the tree.
A) TRUE
B) FALSE
C) UNKNOWN
(b) Although it requires more complicated data structures, Prim's algorithm for a
minimum spanning tree is better than Kruskal's when the graph has a large number of
vertices.
A) TRUE.
B) FALSE
C: UNKNOWN
(c) If a problem is NP-complete, it must also be in NP.

A) TRUE.
B) FALSE
C) UNKNOWN
(d) What is the worst-case runtime complexity of the following C function
int function(int n){

int i, j, k;
k = n;
for(i=-100; i<10*log(n);i++){
k = k/2;
}
for(j=i; j> n; j--){
k=j/2;
}
return k;
}
What order is the execution of this code

a) O(log n)
b) O(n)
c) O(n log n)
d) O(n2)
e) O(n2 log n)
What is the solution to the recurrence T(n) = 2T(n/2)+1, T(1) = 1
T(n) =

The first diagram shown below is a tree which is a heap. The items in the heap are now to be sorted using
heapsort. The following diagram shows the tree after all items have been sorted. Show the contents of the tree
as it would appear after each of the first six passes of heapsort.

Suppose Prim’s algorithm is applied to the weighted graph shown here starting at vertex a to find a minimum cost
spanning tree. State the edges that would be added to the tree in the order that they are added. Name an edge
using its endpoints, in alphabetical order. For example, the edge joining vertices p and q should be called {p, q},
not {q, p}. Given a choice of edges at any point, choose the one that would be first alphabetically. For example,
given the possibility of choosing either {x, z} or {w, y}, you should choose {w, y} (because w proceeds x).

Consider the digraph on five nodes, labeled 0 through 4, with six directed edges
0→1, 1→4, 4→0, 0→2, 2→3, 3→2
List the strongly connected components of this digraph.

Consider the following 21 character message that consists of 3 a’s, 7 c’s, 6 t’s, and 5 g’s:
a a c c c c a c t t g g g t t t t c c g g
Are the following 43 bits a possible Huffman encoding of the message above?
0000001111000101010010010010101010111001001
Justify your answer as concisely and rigorously as possible.
In the following graph, edges are labeled with upper case letters. Edge weights are given as numbers next
to edges.
Recall that Dijkstra’s algorithm finds the shortest path from v1 to all other vertices by adding edges that
make shortest paths. For the graph shown above, each edge is bidirectional; that is, you can travel on
either direction on it for the same cost. List the edges in the order chosen by Dijkstra’s algorithm.

Mid Term Examination - November 2004
Instructions
questions:

a. If you believe that two (or more) of the choices are correct for a particular
b. On the other hand, if you believe that all of the choices provided for a
particular question are wrong then select the one that appears to you as
being the least wrong.
**WARNING: Please note that Virtual University takes serious note of

unfair means. Anyone found involved in cheating will get an `F` grade in
this course.
Total Marks: 70 Total

Questions: 7
9
A PC like computer can perform 10 operations per second. Consider that we have five
different algorithms for a specific problem. For each algorithm i, we know the number of
operations Ti(n) it will perform on a problem of size n:
T1(n) = 6000000 ·n
T2(n) = 60000 ·nlogn
2
T3(n) = 0.003 ·n
−6 3
T4(n) = 10 ·n
−18 n
T5(n) = 10 ·2
For each algorithm compute the size nmax of the largest problem the respective algorithm
can solve within 1 second, 1 minute and 1 hour. Enter the maximal problem sizes into the
following
6
Describe an efficient algorithm to find the median of a set of 10 integers; it is known that
there are fewer than 100 distinct integers in the set.
Recall the counting sort algorithm, where

1 n is the number of elements to be sorted
2 each element is an integer in the range 1 to k
3 A is the input array, of size n
4 B is the final sorted output array
5 C is the intermediate array of size k
1: for i = 1 to k
2: C[i] = 0
3: for i = 1 to n
4: C[A[i]] = C[A[i]] + 1
5: for i = 2 to k
6: C[i] = C[i] + C[i-1]
7: for i = n downto 1
8: B[C[A[i]]] = A[i]
9: C[A[i]] = C[A[i]] - 1
(a) For the input array [6,3,7,5,4,3,3,2,8,9,1,6], and k = 9, specify the contents of
the arrays B and C
• (4 points) after the second for-loop (line 3); C =
• (2 points) after the third for-loop (line 5); C =
• After each of the first three iterations of the fourth loop (line 7);
1. (3 points)
B=
C=
2. (3 points)
B=
C=
3. (3 points)
B=
C=
(b) (5 points) Suppose that the for-loop on line 7 above, is modified as follows:
7: for i = 1 to n
Will the algorithm still sort the input? If no, explain why not. If yes, what is the effect of this
Modification to the algorithm and the output?
When using merge sort to sort an array, do the recursive calls to merge sort depend on the
number of elements in the array, the values of the elements or both? Briefly explain.
Insertion sort can be expressed as a recursive procedure as follows: In order to sort array
A[1..n], we recursively sort array A[1..n-1] and then insert A[n] into the sorted array A[1..n-1].
Give an equation that describes the overall running time of this algorithm on an input array of
size n, in terms of the running time on smaller input.
T(n) =
Compute the edit distance and edit scripts for the strings "HEAP" and "CHEAT". Recall that
the edit distance recurrence is
⎛ E (i − 1, j ) + 1 ⎞
⎜ ⎟
⎜ E (i, j − 1) + 1 ⎟
E(i, j) = min
⎜ E (i − 1, j − 1) + 1 ifA[i ] ≠ B[ j ] ⎟
⎜ ⎟
⎝ E (i − 1, j − 1) ifA[i ] = B[ j ] ⎠
Using big-oh notation, give the running time of the following piece of code. Briefly
justify your answer.
for (i = 1; i <= n; i++)

for (j = 1; j <= n/2; j++)
for (k = 1; k <= j; k++)
cout << "hello world\n";
WWW.vujannat.ning.COM
CS502-ALGORITHMS
MID –FALL2007
Q#1Total time for heapify is:

Ο (log2 n)
Ο (n log n)
Ο (n2 log n)
Ο (log n)
Q#2
Solve the recurrence using iteration method and also find time complexity (Θ notation)
T (n) = C + O (1) + T (n-1)

T (1) =1 and C is a constant.
Q#3
Suggest the criteria for measuring algorithms. Also discuss the issues need to be
discussed in the algorithm design.
Q#4
If an algorithm has a complexity of log 2 n + nlog 2 n + n. we could say that it has
complexity
O(n)
O( n log2 n)
O(3)
O( log2 ( log2 n ))
O ( log2 n)
Q#5
Let the set P = {(1, 13), (2, 9), (3, 15), (4, 12), (5, 14), (6, 6), (7, 3), (8, 10), (9, 2), (10, 8),
(11, 9), (13, 6), (15, 3), (18, 5)}. You are required to give the final state of stack after the
execution of sweep line algorithm for 2d-maxima. No intermediate steps or graphics to be
shown.
Q#6
Suppose we have hardware capable of executing 106 instructions per second. How long
would it take to execute an algorithm whose complexity function is T (n) = 2n2 on an
input of size n = 108?
Q#7
In RAM model instructions are executed
One after another
Parallel
Concurrent
Random
Q#8
In selection algorithm, because we eliminate a constant fraction of the array with each
phase, we get the
Convergent geometric series

Divergent geometric series
None of these
Q#9
Due to left-complete nature of binary tree, heaps can be stored in
Link list
Structure
Array
None of above
Page 1 of 3

Mid Term Examination – Spring 2005
Instructions
questions:

2. This examination is closed book, closed notes, closed neighbors; any one found cheating will
get no grade.
a. If you think that there is something wrong with any of the questions, attempt it to the
best of your understanding.
4. Some of the examination consists of multiple-choice questions. Choose only one choice as
your answer.
a. If you believe that two (or more) of the choices are the correct ones for a particular
b. On the other hand, if you believe that all of the choices provided for a particular
question are the wrong ones, select the one that appears to you as being the least
wrong.
Very Important Note:

Please do copy the expressions written down, in your word document, these will be used in the
solution of your paper

n n(n + 1) n i x ( n +1) − 1
∑ i=
n
2n 3 + 3n 2 + n ∑ x =
i =1 2 ∑i =1
i2 =
6 i =1 x −1
Develop an O(nlogn)-time algorithm that solves the following problem: Given an unsorted
array of n real numbers and a real number x, decide whether there are two numbers y and
z in this array such that x = y+z. The output of your algorithm should be "No" if no such
numbers y and z exist; otherwise, it should report y and z. (Note that there may be more
than one such pair of numbers. It is sufficient to report one of them.) Argue briefly why
your algorithm takes O(nlogn) time.
The worst-case search time for a sorted singly-linked list of n items is

o O(1)
Page 2 of 3
o O(logn)
o O(n)
o O(nlogn)
o O(n2)
Compute the edit distance and edit scripts for the strings "THROUGH" and
"PLOUGH". Recall that the edit distance recurrence is
E(i-1, j)+1
E(i, j-1)+1
E(i, j) = min E(i-1, j-1)+1 if A[i] ≠ B[ j]
E(i-1, j-1) if A[i] = B[ j]
Solve the recurrence using Iteration method and also find time complexity (Theta
notation)
T(n) = 1+2T(n-1), T(1) = 1

Note: show all necessary steps to get maximum marks.
Consider the following code:

for(j =1; j < n; j++)
for(k = 1; k < 15; k++ )
for(l = 5; l < n; l++ )
{
Page 3 of 3
do_something_constant(); // takes O(1) time
}
What order is the execution time of this code?
o O(n)
o O(n3)
o O(n2 logn)
o O(n2)
o O(nlogn)

Mid Term Examination – Spring 2006 (session I)

2. Paste the bitmap image for the tables, diagrams etc while solving your questions
3. The duration of this examination is 90 Minutes.
a. If you think that there is something wrong with any of the questions,
attempt it to the
b. If you believe that some essential piece of information is missing,
make an appropriate
assumption and use it to solve the problem.

action against unfair means. Anyone found involved in cheating
will get an `F` grade in this course.
The following function calculate kn , for integer k and n. Determine closed expression T(n) for
running time. Assuming that arithmetic operations take unit time.
function exp1(k, n)
{
power := 1;
for i = 1 to n do{
newpower := 0;
for j := 1 to k do{
newpower := newpower + power;
}
power := newpower
}
return(power)
}
T(n) = ?
Consider the following pairs of functions

I . f(x) = x2 + 3x+7 g(x) = x2 + 10
2
II f(x) = x log(x) g(x) = x3
III f(x) = x + log(3x +7) g(x) = (x2 +17x +3)2
4 8
Which of the pairs of functions f and g are asymptotic?
Only I
Only II
Both I and III
None of the above
Execution of the following code fragment
int Idx;
for (Idx = 0; Idx < N; Idx++)
{
cout << A[Idx] << endl;
}
is best described as being
O(N)
O(N2)
O(log N)
O(N log N)
If algorithm A has running time 7n2 + 2n + 3 and algorithm B has running time 2n2, then
Both have same asymptotic time complexity

A is asymptotically greater
B is asymptotically greater
None of others
Which of the following sorting algorithms is stable?

(i) Merge sort,
(ii) Quick sort,
(iii) Heap sort,
(iv) Counting Sort.
Only i
Only ii
Both i and ii
Both iii and iv
Determine the complexity of an algorithm that measures the number of print statements in an
algorithm that takes a positive integer n and prints 1 one time, 2 two times, 3 three times , ... ,
n n times.
That is
2 2
3 3 3
……………
……………
n n n n ……..n (n times)
Note:There is no need to write Algorithm(Pseudo code)
Solve the following recurrence

⎧1 if n =1
T ( n) = ⎨
⎩ 2T (n − 2)+n if n >1
Compute the edit distance and edit scripts for the strings “PROPERTY” and “POCKET”.
Consider the following recurrence relation

⎧2 if n = 0
T ( n) = ⎨
⎩6T (n − 1) otherwise
Then T(2) is
36
72
12
None of the above
The appropriate big θ classification of the given function. f(n) = 4n2 + 97n + 1000 is
θ(n)
θ(2n)
θ(n2)
θ(n2 log n)
The following subroutine computes 22 for a given number N.

compute(N)
{
If (N==1)
return 2
else
return compute(N - 1) * compute(N - 1)
}
What category of algorithmic solutions best characterizes the approach taken in this
subroutine (algorithm)?
Search and traversal

Divide-and-conquer
Greedy algorithm
Dynamic Programming
Assume that a given algorithm has a runtime C that depends on the size N of its input
according to the following two formulas:
⎧0 if N = 1
C(N ) = ⎨
⎩C ( N − 1) + 2 if N > 2
Which of the following functions C(N) describes the runtime of the algorithm?
C(N) = N – 1
C(N) = (N - 1)2
C(N) = log2 N
C(N) = 2(N - 1)
Let us say we have an algorithm that carries out N2 operations for an input of size N. Let us
say that a computer takes 1 microsecond (1/1000000 second) to carry out one operation.
How long does the algorithm run for an input of size 3000?
90 seconds
9 seconds
0.9 seconds
0.09 seconds
Consider the following polynomial

aknk+ak-1nk-1+………….a0 .
What is the Big –O representation of the above polynomial?
O(kn)
O(nk)
O(nk+1)
None of the above

Mid Term Examination – Spring 2006 (session II)

2. Paste the bitmap image for the tables, diagrams etc while solving your
questions
3. The duration of this examination is 60 Minutes.
5. Do not ask any questions about the contents of this examination from
anyone.
a. If you think that there is something wrong with any of the
questions, attempt it to the
b. If you believe that some essential piece of information is
missing, make an appropriate
assumption and use it to solve the problem.
6. Some of the examination consists of multiple-choice questions. Choose only
one choice as your answer.

I . f(x) = x2 + 3x+7 g(x) = x2 + 10
II f(x) = (x3 + x2 + x + 1)4 g(x) = (x4 +x3 + x2 + x + 1)3
III f(x) = x4 + log(3x8 +7) g(x) = (x2 +17x +3)2
IV f(x) = x2log(x) g(x) = x3
2
V f(x) = log(x + 1) g(x) = log( x)
I and IV
II and V
I , II and III
None of above
Consider the C++ program segment given below:
for ( i=0 ; i < n; i++) {

for (j = 1,sum=a[0]; j < = i; j++)
Sum+=a[j];
Cout<< “The sum for sub-array is<< sum;

}
The running time of the above algorithm is
n.
n log n .
log n .
n2.
Ackerman’s function is defined recursively on nonnegative integer’s m and n as follows
⎧n +1 if m= 0
⎪
a (m, n) = ⎨a (m-1, 1) if m ≠ 0, n= 0
⎪a (m-1, a(m, n-1)) if m ≠ 0, n ≠ 0
⎩
Write a single recursive function in C++ that computes Ackerman’s function. Do not use
other functions or loops. Assume parameters m and n passed are always greater or equal to
zero

I . f(x) = (x3 + x2 + x + 1)4 g(x) = (x4 +x3 + x2 + x + 1)3
x 2
II f(x) = 22 g(x) = 2x
III f(x) = 2x + 3 g(x) = 2x + 7
IV f(x) = log(x2 + 1) g(x) = log( x)
Which of the pairs of functions f and g are asymptotic?
Only I
Only III
Both I and II
Both III and IV
Dynamic programming uses a top-down approach.
True
False
The edit distance between FOOD and MONEY is
At most four
At least four
Exact four

⎧4 if n = 1
T ( n) = ⎨
⎩T (n / 5) + 3n if n is divisible by 5
2
Then T(5) is
25
75
79
None of the above

Compute the edit distance and edit scripts for the strings “CRICKET” and “HOCKEY”.
Calculate the θ complexity of the following sort procedure
sort( A[1..n] )
{
for i = 2 to n do
for j = n downto i do
if( A[j-1] > A[j] )
swap(A[j-1], A[j])
}
Execution of the following code fragment

int i = N;
while (i > 0)
{
int Sum = 0;
int j;
for (j = 0; j < N; j++)
Sum++;
cout << Sum << end;
i--;
}
is best described as being
O(N)
O(N2)
O(log N)
O(N log N)
It is impossible to design a sorting algorithm based on comparison of keys whose worst-case

run time is in O(n).
True
False

⎧5 if n = 1
T ( n) = ⎨
⎩2T (n / 2) + 3 if n is even
Then T(8) is
61
29
13
None of the above
The merge sort algorithm involves the following steps.

(i) Recursively sort the 1st and 2nd halves separately
(ii) Merge the two-sorted halves into a sorted group.
(iii) If the number of items to sort is 0 or 1, return.
Which is the correct order of instructions in merge sort algorithm?
(i),(ii),(iii)
(ii),(iii),(i)
(iii),(ii),(i)
(iii),(i),(ii)
Let X[1..n] and Y[1..n] be two arrays, each containing n numbers already in sorted order.
Give an O(logn)-time algorithm to find the median of all 2n elements in arrays X and Y.

Cs502 Collection of Old Papers

Uploaded by

Copyright:

Available Formats

Cs502 Collection of Old Papers

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Cs502 Collection of Old Papers

Uploaded by

Copyright:

Available Formats

What are the instructions provided in the examination?

What are the instructions provided in the examination?

What is the time complexity of the brute force 3-sum algorithm described?

What is the time complexity of the brute force 3-sum algorithm described?

www.vujannat.ning.

CS502 Fundamentals of Algorithms

1. The duration of this examination is 150 Mins.

**WARNING: Please note that Virtual University takes serious note of

Total Marks: 80 Total

Question No. 1 Marks : 10

Answer yes or no and give a brief explanation for your choice.

(d) Every problem in NP is NP-complete.

(e) If problem A reduces to problem B and B is in P, then A is in P.

Question No. 2 Marks : 5

If a problem is not in P, it must be NP-complete.

Question No. 3 Marks : 5

Consider the following code:

Question No. 4 Marks : 5

int brute(int a[], int N)

Question No. 5 Marks : 5

What is the solution to the recurrence T(n) = T(n/2)+n, T(1) = 1

Question No. 6 Marks : 10

Consider the following undirected graph

(0-1, 1) (0-4, 4) (0-6, 1) (0-5, 2) (1-2, 1) (1-4, 2)

Question No. 7 Marks : 5

Consider the following recurrence equation:

Question No. 8 Marks : 20

Consider the following undirected network with edge weights as show:

Question No. 9 Marks : 5

CS502 Fundamentals of Algorithms

So please copy this in the word file for later use.

Total Marks: 120 Total Questions: 12

Question No. 1 Marks : 5

Question No. 2 Marks : 15

Question No. 3 Marks : 20

Question No. 4 Marks : 5

Question No. 5 Marks : 5

Question No. 6 Marks : 5

Question No. 8 Marks : 5

There is a good greedy algorithm for the 0-1 Knapsack Problem.

Question No. 9 Marks : 10

(a) If P1 is NP-complete, would this translation imply that P2 is NP-complete?

(Give your Answer in Yes or NO only)

Question No. 10 Marks : 5

Dynamic programming uses a top-down approach.

Question No. 11 Marks : 10

Solve the following recurrence relation with full history:

Question No. 12 Marks : 20

Consider the directed graph G below:

CS502 Fundamentals of Algorithms

Please read the following instructions carefully before

**WARNING: Please note that Virtual University takes serious

Some results you may need:

Question No. 1 Marks : 05

Best and worst case times of an algorithm may be same.

If an algorithm has a complexity of 2n2 + 4n + 3 for some model of computation (some

Question No. 4 Marks : 05

Question No. 5 Marks : 25

Question No. 6 Marks : 10