Assume ID:999

1) Sequence from attached list of sequences:

20,18,13,8,5,16,9,12,1,14,15,19,17,7,2,4

Pb1:

1) Sequential tree representation:
20 18 13 8 5 1 / 2 / 4 / / 7 / / 9 / 12 / / 16 14 / 15 / / 17 / / 19 / / /

2) In order traversal:
1 2 4 5 7 8 9 12 13 14 15 16 17 18 19 20

3) Pot order traversal:
4 2 1 7 5 12 9 8 15 14 17 16 13 19 18 20

4) delete root:
18 13 8 5 1 / 2 / 4 / / 7 / / 9 / 12 / / 16 14 / 15 / / 17 / / 19 / /

5) Insertion sequence of 15 nodes resulting in BST of height 14:

1 2 5 7 8 9 12 13 14 15 16 17 18 19 20

6) Insertion sequence of 15 nodes resulting in BST of height 3:

13 7 27 2 9 15 19 1 5 8 12 14 16 18 20

Pb2:

7) Starting from A=[20,18,13,8]
20 18 13 8
18 20 13 8
18 13 20 8
13 18 20 8
13 18 8 20
13 8 18 20
8 13 18 20

8) The minimal number of swaps, here 0, is obtained when starting from
an ordered array, here [8,13,18,20]

9) Worst-case insertion sort complexity is Theta(n^2). This complexity
is obtained with a decreasing sequence, for instance [8,13,18,20]. In
this case, the outer loop will perfrom n-1 iterations. At each such
iteration i:1<= i < n, the inner loop will perform i comparisons /
swaps (oc constant cost c). This will result in: c*(1+2+3+...+(n-1))
steps, i.e., c*(n-1)*n/2 which is in Theta(n^2).

10) The 8 elements sequence is:

L=20,18,13,8,5,16,9,12

The result of the recursive call on the first half is:
L1= 8 13 18 20

The result of the recursive call on the second half is:
L2= 5 9 12 16 

The merge step repeats (as long as both L1 and L2 are non-empty)
comparing the first element of L1 with the one of L2. It moves the
smaller one to the destination list.  It also copies to the
destination list the elements of L1 (respectively L2) if L2 in the
order they appear if (respectively L1) is empty.

This results in a sorted destination list because L1 and L2 were
sorted. It is linear in n=|L1|+|L2| because there will be at most n
constant-time comparisons and copies take place (since only the first
elements of the list are compared, and after each comparison one
element is moved to the destination).

11. DFS:

s1(20) s16(4) s15(2) s14(7) s13(17) s12(19) s11(15) s10(14) s9(1) s8(12) s7(9) s6(16) s5(5) s4(8) s3(13) s2(18) s2(18)

12. BFS:

"Pure BFS":
s1(20) s16(4) s2(18) s15(2) s3(13) s14(7) s4(8) s13(17) s5(5) s12(19) s6(16) s11(15) s7(9) s10(14) s8(12)  s9(1)

Also accepted: s1(20) s16(4) s2(18) s15(2) s3(13) s14(7) s4(8) s5(5) s13(17) s6(16) s12(19) s7(9) s11(15) s8(12) s10(14) s9(1)



13. Dijkstra's sequence of "traversed" edges:

A D - D F - A C - B F - D G - B H - A E - C I

Part B:
Pb 1:
20,18,13,8,5,16,9,12,1,14,15,19,17,7,2,4

1. AVL tree of height 2 using 4 first elements: 8,13,18,20
T2:  18 13 8 / / / 20 / /

2. AVL tree of height 3 using 7 first elements: 5,8,9,13,16,18,20
T3: 16 9 8 5 / / / 13 / / 18 / 20 / / 

3. AVL tree of height 4 using 12 first elements:
1,2,4,5,7,8,9,12,13,14,15,16
T4:

12 7 4 2 1 / / / 5 / / 8 / 9 / / 15 14 13 / / / 16 / /

4. AVL tree of height 5 using 16 elements:

You can reason about the minimal number of nodes n(h) to build an AVL
tree for some height h. You can see that n(1)=2 and n(2)=4. An AVL
tree of height h will have a child of height h-1 (by definition of
height) and another of height h-1 or h-2 (by the AVL property). Both
children should be AVL trees (by the AVL property). By minimality, the
second child should have heigt h-2. This results in n(h) = n(h-1) +
n(h-2) + 1 (i.e. nodes contributed by the choildren plus one for the
root). The minimal number for height 5 would be:
n(5)=n(4)+n(3)+1=2*n(3)+n(2)+2=3*n(2)+2*n(1)+4=20.

The minimal number of nodes for height 5 is then 20.

Pb 2:

a=[20,-2,-5,-5,-3,11,-7,3]


1. result: low=0, high=0, sum=20.

2. bar_steps(n) boils down to a constant amount of work (5 assignments
and an addition) together with two loops. The first loop iterates from
mid to low while the scond from mid+1 to high. Each iteration involves
a constant amount of work ( (between an assignement, an addition and a
comparison, and 3 assignments, an addition and a comparison). Given
that the number of iterations is mid-low+1 + high - (mid+1) +
1=high-low+1=n, we get that bar_steps(n) is in Theta(n).

3. If high==low (i.e., n=1), foo_steps(1) involves 3 assignments.
Otherwise, high-low+1 = n with n is a power of 2. foo involves two
recursive calls to foo and a call to bar. because n is a power of 2
and the calls to foo involve mid-low+1 and high-(mid+1)-1 elements
with mid=(low+high)/2, then each of the two calls involve n/2
elements. The call to bar involves all n elements (i.e. high-low+1).
Therefore, for n > 1, foo_steps(n) = 2 foo_steps(n/2)+bar_steps(n)+C
where the constant C accounts for an addition, a division, 4
assignments and 4 comparisons (in the worst case).

4. Using 2,3, we have:
2*foo_Steps(n/2) + g'(n) <= foo_steps(n) <= 2*foo_Steps(n/2) + g(n) with g, g' linear

-> Using the Master theorem, and since g(n) is in Theta(n^(log_2 2)),
we get foo_steps(n) in Theta (n^(log_2 2) log_2 n) = Theta(n log n). 

-> expand, there are c, b such that g(n) = c.n + b (similar for lower bound):
foo(n) <= 2 foo(n/2) + c n + b
       	  = 2^2 foo(n/4) + 2 c n/2 + b + c n + b
	  
          = 2^i foo(n/(2^i)) + c i n + (1+2+ ... 2^i) b
(i = log n)
     	  = n foo(1) + c n log n + (n-1) b
	  in O(n log n)

there are c' b' such that c' n + b' = g'(n). In a similar way:
foo(n) in Omega(n log n)

hence foo in Theta(n log n)