solutions 14/12/2023

A1.
1) Worst case:
f1: n^2 --> E
f2: n^2 --> E
f3: n   --> C
f4: n log n --> D
2) Best case:
f1: n^2 --> E
f2: n --> C
f3: n --> C
f4: 1 --> A
A2.
3) 
0 1 2 3 4 5 6
C A B G D E F
4) no
5) yes
6) no
A3. 
7) 10 5 1 / 3 2 / / 4 / / 9 7 6 / / 8 / / / 15 11 / 13 12 / / 14 / / / 
8) 2 4 3 1 6 8 7 9 5 12 14 13 11 15 10
9) 10 5 1 / 3 2 / / 4 / / 9 7 6 / / 8 / / / 15 13 12 / / 14 / / / 
10) 9 5 1 / 3 2 / / 4 / / 7 6 / / 8 / / 10 / 15 11 / 13 12 / / 14 / / /
A4.
11) It is not possible to have a topological sort of all the nodes in the directed graph as there are several cycles. Suppose such a sort would have existed. Consider the cycle G C I. No matter wich node among G, C and I appears first in the sort, there will always be an edge from a later node pointing back to this node, hence violating the topological sort. 
12) A B F D H C I E G
13) A B C D E F H I G
Part B:
B1.
1) no
2) no 
3) yes 
4) yes 
5) no 
6) yes 

B2.
7) Let n be the number of calls to add so far. Let #copies be the number of 
assignments "fresh_elements[i] = m_elements[i]" required to copy elements of 
previous arrays to fresh ones at the last call to add. Let size' and m_capacity' 
be the new values of the variables size and m_capacity, respectively.

n	size	m_capacity	size	m_capacity	#copies
1	0		0			1		1			0
2	1		1			2		2			1
3	2		2			3		4			2
4	3		4			4		4			0
5	4		4			5		8			4
6	5		8			6		8			0
7	6		8			7		8			0
8	7		8			8		8			0
9	8		8			9		16			8
...

The capacity is doubled each time we are about to add an element when n equals 
the current capacity.
So:

n		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	...
#copies 0	1	2	0	4	0	0	0	8	0	0	0	0	0	0	0	16	0	...

Given n, the number of copies is Sum from p = 0 to floor(log_2 n) of 2^p.

This is a geometric sum resulting in (2^(1+floor(log_2 n)) - 1). 

Observe n/2 <= 2^(floor(log_2 n)) <= n. Hence the average number of copies is 1/2 <= #copies / n <= 1.

So the average number of copies is in O(1).



B3.
8)
a-> b
a-> c
b-> c
a-> b
c-> a
c-> b
a-> b


Printing content of stacks when starting and after each move:

a 1 2 3 
b
c

a-> b

a 2 3 
b 1
c

a-> c

a 3 
b 1
c 2

b-> c

a 3 
b 
c 1 2

a-> b

a  
b 3
c 1 2

c-> a

a 1
b 3
c 2

c-> b

a 1 
b 2 3
c

a-> b

a  
b 1 2 3
c


9) 

solve_steps(m) is the number of top, push and pop instructions 
when solve(m,src,dst,via) is called.

if m=0 then solve_steps(m) is 0.
if m > 0, then a call to solve(m, src, dst, via) results in two calls 
to solve(m-1, ...) and in a constant amount of work (a top, push and pop). 

Hence, solve_steps(m) = 2 solve_steps(m-1)+ C ( C can be chosen to be 1, 3 or left as a constant).


10)

m          :	0	1	2	3	4	5	6	
solve_steps:	0	C	3C	7C	15C	31C	63C

Let g(m) = 2^m. It is enough to show that solve_steps(m) = C *(g(m)-1) for any m >= 0
to establish that solve_steps(m) is in Theta(2^m).

We show solve_steps(m) = C * (g(m) - 1) by induction on m:

initially: m=0, g(0)=1 and solve_steps(m) = 0.

Suppose solve_steps(m)=C * (g(m)-1). Show solve_steps(m+1)=C * (g(m+1)-1).

solve_steps(m+1)= 2 solve_steps(m)+C =(by induction hypothesis) = 2 (C * (g(m) - 1)) + C = C * (2 g(m) - 1) = (definition of g) = C * (g(m+1) - 1) 

Hence, solve_steps(m)=C * (g(m)-1) and solve_steps(m) is Theta(2^m).