Algorithms Analysis & Design - Lecture 4

Introduction to the Design and Analysis of Algorithms

1. Algorithms
By Mohamed Gamal
© Mohamed Gamal 2024

4. a)
Let ??????(??????) be the number of multiplications made by the algorithm.
Recurrence relation equation: ??????(??????)=??????(??????−1)+1 and ??????0=0
•Using forward substitution:
??????0 = 0
??????1 = ??????0+1 = 1
??????2 = ??????1+1 = 2
??????3 = ??????2+1 = 3
???????????? = ??????
Basic Operation

5. a) Another approach
Let ??????(??????) be the number of multiplications made by the algorithm.
Recurrence relation equation: ??????(??????)=??????(??????−1)+1 and ??????0=0
•Using backward substitution:
????????????=????????????−1 +1
=????????????−2+1+1 = ????????????−2+2
=????????????−3+1+2 = ????????????−3+3
=????????????−4+1+3 = ????????????−4+4
????????????=????????????−?????? + ??????
= ??????0 + ??????
= ??????
??????−??????=0
??????=??????

6. Example: The Tower of Hanoi Puzzle
Problem: move disks from source peg A to destination peg C using an auxiliary (temp) peg B.
Constraints:
–Only one disk can be moved at a time.
– A larger disk cannot be placed on top of a smaller disk.
Source DestinationAuxiliary

7. Try it online!

8. 7 moves in total !

9. ALGORITHM: Hanoi(n, src, dest, temp)
// Input: no. disks, source, destination, temp
// Output: Moves to solve the Tower of Hanoi problem
if n = 1 then
MOVE disk from src to dest directly
else
Hanoi(n-1, src, temp, dest) // Step 1: from src to temp
MOVE disk n from src to dest // Step 2: nth disk from src to dest
Hanoi(n-1, temp, dest, src) // Step 3: from temp to dest

10. Let ??????(??????) be the number of moves made by the algorithm.
Recurrence relation equation: ???????????? = ????????????−1+1+??????(??????−1) and ??????1=1
=2????????????−1+1
•Using forward substitution:
??????(1)=1
??????(2)=2??????(1)+1=3
??????(3)=2??????(2)+1=7
??????(??????)=2
??????
−1
Basic Operation

11. Let ??????(??????) be the number of moves made by the algorithm.
Recurrence relation equation: ????????????=2????????????−1+1 and ??????1=1
•Using backward substitution:
??????(??????)=2????????????−1+1
=22????????????−2+1+1=4??????(??????−2)+3
= 42????????????−3+1+3=8??????(??????−3)+7
??????(??????)=2
??????
??????(??????−??????)+(2
??????
−1)
=2
??????−1
??????(1)+(2
??????−1
−1)
=2
??????
−1
??????−??????=1
??????=??????−1
Basic Operation

13. Determine what this algorithm computes?
??????(1) = 1
??????(2) = ??????(1) + 2∗2−1 = 1 + 3 = 4
??????(3) = ??????(2) + 2∗3−1 = 4 + 5 = 9
??????(4) = ??????(3) + 2∗4−1 = 9 + 7 = 16
??????(??????) = ??????
2
Then this algorithm computes ??????
2
for each positive ??????.
Recurrence relation equation: ??????(??????−1)+2??????−1 for ??????>1
a)

14. b)
Let ??????(??????) be the number of multiplications made by the algorithm.
Recurrence relation equation: ??????(??????)=??????(??????−1)+1 and ??????1=0
•Using backward substitution:
????????????=????????????−1 +1
=????????????−2+1+1 = ????????????−2+2
=????????????−3+1+2 = ????????????−3+3
=????????????−4+1+3 = ????????????−4+4
????????????=????????????−?????? + ??????
= ??????1 +(??????−1)
=(??????−1)
??????−??????=1
??????=??????−1

15. c)
Let ??????(??????) be the number of additions and subtractions made by the algorithm.
Recurrence relation equation: ??????(??????)=??????(??????−1)+2 and ??????1=0
•Using backward substitution:

????????????=????????????−1 +2
=????????????−2+2+2 = ????????????−2+4
=????????????−3+2+4 = ????????????−3+6
=????????????−4+2+6 = ????????????−4+8
??????(??????)=??????(??????−??????)+2∗??????
= ??????1 +2∗??????−1
=2(??????−1)
??????−??????=1
??????=??????−1

17. a)
Let ??????(??????) be the number of multiplications made by the algorithm.
Recurrence relation equation: ??????(??????)=??????(??????−1)+2 and ??????1=0
•Using forward substitution:

??????(1)=0
??????(2)=??????(1)+2=2
??????(3)=??????(2)+2=4
??????(4)=??????(3)+2=6
??????(5)=??????(4)+2=8

????????????=2??????−1
Basic Operation

18. a) Another approach
Let ??????(??????) be the number of multiplications made by the algorithm.
Recurrence relation equation: ??????(??????)=??????(??????−1)+2 and ??????1=0
•Using backward substitution:

??????(??????) =??????(??????−1) +2
= [ ??????(??????−2) +2 ] +2 =??????(??????−2) +4
= [ ??????(??????−3) +2 ] +4 =??????(??????−3) +6
= [ ??????(??????−4) +2 ] +6 =??????(??????−4) +8
??????(??????) =????????????−?????? +2??????
= ??????1 +2(??????−1)
= 2?????? −1
Basic Operation
??????−??????=1
??????=??????−1

19. ALGORITHM: S(n)
// Input: A positive integer n
// Output: The sum of the first n cubes
S ← 1
for i ← 2 to n do
S ← S + i * i * i
return S
The number of multiplications made by this algorithm will be
෍
??????=2
??????
2=
??????−2+1
2
×(2+2) = 2(??????−1)
This is exactly the same number as in the recursive version, but the no recursive version
doesn't carry the time and space overhead associated with the recursion's stack.
b) Comparing with the non-recursive algorithm

20. Question 1:
Assignments

21. Question 2:

22. Thank You!

24. Question 1

25. Answers

26. b)
Let ??????(??????) be the number of additions made by the algorithm.
Recurrence relation equation: ????????????=????????????−1+??????(??????−1)+1 and ??????0=0
=2????????????−1+1
•Using forward substitution:

??????(0)=0
??????(1)=2??????(0)+1=1
??????(2)=2??????(1)+1=3
??????(3)=2??????(2)+1=7
??????(4)=2??????(3)+1=15

????????????=2
??????
−1
Basic Operation

27. b) Another approach
Let ??????(??????) be the number of additions made by the algorithm.
Recurrence relation equation: ??????(??????)=2??????(??????−1)+1 and ??????0=0
•Using backward substitution:

??????(??????) =2??????(??????−1) +1
=2[ 2??????(??????−2) +1 ] +1 =4??????(??????−2) +3
=4[ 2??????(??????−3) +1 ] +3 =8??????(??????−3) +7
=8[ 2??????(??????−4) +1 ] +7 =16??????(??????−4) +15
????????????=2
??????
????????????−?????? +(2
??????
−1)
= 2
??????
??????0 +(2
??????
−1)
=2
??????
−1
Basic Operation
??????−??????=0
??????=??????

28. d.It’s a very bad algorithm because it is vastly inferior to the algorithm that simply
multiplies an accumulator by 2 ?????? times. O(2
??????
)

29. Question 2

30. a) The algorithm computes the value of the smallest element in a given array.
Let A = [9, 5, 8, 2]
▪n = 4 ≠ 1
▪Call Riddle([9, 5, 8]) (subarray A[0..2]):
▪For Riddle([9, 5, 8]):
▪n = 3 ≠ 1
▪Call Riddle([9, 5]) (subarray A[0..1]):
▪For Riddle([9, 5]):
▪n = 2 ≠ 1
▪Call Riddle([9]) (subarray A[0..0]):
▪n = 1, so it returns 9.
▪Compare temp = 9 with A[1] = 5:
▪9 > 5, so return 5.
▪Riddle([9, 5]) returns 5.
▪Compare temp = 5 with A[2] = 8:
▪5 <= 8, so return 5.
▪Riddle([9, 5, 8]) returns 5.
▪Compare temp = 5 with A[3] = 2:
▪5 > 2, so return 2.

31. b)
Let ??????(??????) be the number of the number of key comparisons made by the algorithm.
Recurrence relation equation: ??????(??????)=??????(??????−1)+1 and ??????1=0
•Using backward substitution:

???????????? = ??????(??????−1) +1
=[ ??????(??????−2) +1 ] +1 =??????(??????−2) +2
=[ ??????(??????−3) +1 ] +2 =??????(??????−3) +3
=[ ??????(??????−4) +1 ] +3 =??????(??????−4) +4
????????????=????????????−?????? + ??????
= ??????1 +(??????−1)
=??????−1
Basic Operation
??????−??????=1
??????=??????−1