question about Design and Analysis of Algorithm?

Design and Analysis of Algorithm CS302 Sunday, 21 February, 2021 Question 1 The Tower of Hanoi is a game in which a stack of disks of varying sizes are moved from one peg to another. The diagram bellow shows the start and goal states. Start State Goal State ALLAH Peg 1 Peg 2 Peg 3 Peg 1 Peg 2 Peg 3 The rules of the game are: only one disk can be moved at a time a disk may only be moved if it is on the top of a stack disk can only be placed on an empty peg or a larger disk . a) Construct a recurrence relation showing required moves to transfer n disks from peg 1 to 3. b) Solve recurrence relation to obtain explicit formula for Tower of Hanoi problem. Question 2 a) Write a program code to multiply two square matrices using programming language of your choice. b) Identify basic operation. c) Compute time complexity of your solution