1.

Operation of HEAPSORT on the array A = <5,13,2,25,7,17,20,8,4>

From file exam_heap

A d-ary heap is like a binary heap, but (with one possible exception) non-leaf nodes have d children instead of 2 children.

  1. How would you represent a d-ary heap in an array?
  2. What is the height of a d-ary heap of n elements in terms of n and d?
  3. Give an efficient implementation of EXTRACT-MAX- in a
    d-ary max-heap. Analyze its running time in terms of
    d and n.

Solution

  1. A d-ray heap can be implemented using a dimensional array as follows. The root is kept in A[1], its d children are kept in order in A[2] through [d+1] and so on.
    The procedures to map a node with index i to its parent and its jth child are given by:

D-ARY-PARENT(i)return (i-2)/d+1

D-ARY-CHILD(i,j)return d(i-1)+j+1

  1. Since each node has d children, the height of the tree is

Θ(lgd n).

2. Counting sorton <6,0,2,0,1,3,4,6,1,3,2>

3. Represent the following graph using adjacency matrix, incident matrix and adjacency list

The adjacency matrix:

a / b / c / d / e / f / g
a / 0 / 0 / 1 / 1 / 0 / 1 / 0
b / 0 / 0 / 0 / 1 / 1 / 0 / 0
c / 1 / 0 / 0 / 0 / 0 / 1 / 0
d / 1 / 1 / 0 / 0 / 1 / 1 / 0
e / 0 / 1 / 0 / 1 / 0 / 0 / 0
f / 1 / 0 / 1 / 1 / 0 / 0 / 0
g / 0 / 0 / 0 / 0 / 0 / 0 / 0

The incident matrix:

ac / ad / af / bd / be / cf / de / df
a / 1 / 1 / 1 / 0 / 0 / 0 / 0 / 0
b / 0 / 0 / 0 / 1 / 1 / 0 / 0 / 0
c / 1 / 0 / 0 / 0 / 0 / 1 / 0 / 0
d / 0 / 1 / 0 / 1 / 0 / 0 / 1 / 1
e / 0 / 0 / 0 / 0 / 1 / 0 / 1 / 0
f / 0 / 0 / 1 / 0 / 0 / 1 / 0 / 1
g / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0

Adjacency list.

4 prove that. = Ω(n2n)
We need to prove that there exist c, n0 > 0 such that
22n ≥ cn2n for every n ≥ n0.
22n ≥ cn2n ⇒
log(22n) ≥ log(cn2n) ⇒
2n ≥ logc + logn + log2n ⇒
2n ≥ logc + logn + n
True for all n ≥ n0 = 1 and c = 1

5. Consider a state space where the start state is number 1 and the successor function for state n returns two states, numbers 2n and 2n+1.

  1. Draw the portion of the state space for states 1 to 15.
  2. Suppose the goal state is 11. List order of visiting nodes for BFS, DLS

Answer , a)

b) BFS: 1234567891011

DFS: 1248951011

6. For the following two functions, what is the largest integer X such that B is asymptotically faster than A?

functionA(intn)
fori:=1to7do
A(n/2);
fori:=1ton^2do
c:=c+1; / functionB(intn)
fori:=1toXdo
B(n/4);
fori:=1ton^2do
c:=c+1;
Answer
By the master theorem,
the worst-case asymptotic complexity of A is Θ( n lg 7) ≈ Θ( n 2.807),
the worst-case asymptotic complexity of B is Θ( n log4 x),
x > 16
log 4 x < lg 7 = log 4 49
largest integer X such that B is asymptotically faster than A is 48

7. Show the difference between algorithms and heuristics in guessing a secret dictionary word constituted from the following letters:

y i o o l B g

answer

Secret word: Biology

Algorithms / Heuristics
Algorithms exhaust all possibilities before arriving at a solution. but guarantee solutions.
O(n !) = O(7!) =5040 / Heuristics make it easy for us to use simple principles to arrive at solutions to problems. Does not guarantee solution.
Putting Capital B at the beginning,
And (ology) at the end, O(1)
+O(n) for scanning  O(n) =O(7)

8. Write down an algorithm and draw a flowchart to find and print the largest of N (N can be any number) numbers. Read numbers one by one. Verify your result by a trace table. (Assume N to be 5 and the following set to be the numbers {1 4 2 6 8 })

9. Discuss one heuristic of your choice

Answer : here

10. Young Trevor McKinney, is caught up by an assignment: think of something to change the world and put it into action. Trevor conjures the notion of paying a favor not back, but forward--repaying good deeds not with payback, but with new good deeds done to three new people.

Assume that a community of size n person, and that each one pays forward to three people 1 male and 2 female.

Draw a recursion tree specifying the width and the height.

Solution !