Scribd
Upload
108 views

Capital University of Science and Technology Department of Computer Science CS 3163: Design and Analysis of Algorithms (3) : Fall 2020

The document describes Assignment 5 for an algorithms course, which involves analyzing iterative and recursive algorithms for time and space complexity using techniques like recurrence relations. It provides 7 questions analyzing algorithms for problems like computing factorials and sums of cubes recursively, solving the Tower of Hanoi puzzle, and checking if a graph is complete. Students are asked to set up and solve recurrence relations to determine algorithm efficiencies and compare recursive and iterative solutions.

Uploaded by

Malik Naveed
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
108 views

Capital University of Science and Technology Department of Computer Science CS 3163: Design and Analysis of Algorithms (3) : Fall 2020

The document describes Assignment 5 for an algorithms course, which involves analyzing iterative and recursive algorithms for time and space complexity using techniques like recurrence relations. It provides 7 questions analyzing algorithms for problems like computing factorials and sums of cubes recursively, solving the Tower of Hanoi puzzle, and checking if a graph is complete. Students are asked to set up and solve recurrence relations to determine algorithm efficiencies and compare recursive and iterative solutions.

Uploaded by

Malik Naveed
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

Capital University of Science and Technology

Department of Computer Science

CS 3163: Design and Analysis of Algorithms (3): Fall 2020

Assignment 5: Algorithm Iterative and Recursive Analysis, Efficiency Class


CLO 1 Reproduce algorithms using different algorithms design techniques i.e. Brute Force, Divide & Conquer, Dynamic
Programming, Greedy Algorithms & Backtracking, Branch & Bound. [C2-Comprehension]
CLO 2 Analyze the time and space complexity of different algorithms by using standard analysis techniques. [C4-Analysis]
CLO 3 Implement the algorithms, compare the implementations empirically. [C3-Application]
Maximum Marks: 10 Instructor: Ms. Tayyaba Zaheer
Announcement Date: 20th October 2020 Due Date: 27th October 2020 till 02:00 PM via Microsoft
Teams
Guidelines:
You You are required to submit the hand written assignment file (word or pdf – pictures
attached must be readable and in portrait mode) as courseCode_studentReg#_studenName via
Microsoft Teams (\Assignments\ DAA-CS3163(2)\Assignment 5).
Objectives:
After completion of this Assignment, you will have gained intermediate knowledge of efficiency
class and Iterative and Recursive Analysis of Algorithms.
Related Reading: Class lectures shared on oneDrive and Portal and Chapter 2 (Section 2.4) of
Text Book.
Tools/Software Requirement (Optional):
1. Microsoft Word.
Description:
Fundamentals of Algorithmic Problem Solving and algorithm analysis.
Tasks:
Question 1: Solve the following recurrence relations:

Solution:
Each of these recurrences can be solved by the method of backward substitutions.
Question 2: Set up and solve a recurrence relation for the number of calls made by F(n), the recursive
algorithm for computing n!.
Solution:
The recurrence relation in question is almost identical to the recurrence relation for the number of
multiplications, which is set up and solved in the section 2.4 of the text book.

Page 1 of 4
Question 3: Consider the following recursive algorithm for computing the sum of the first n cubes: S(n) =
13 + 23 + ... + n3.

a. Set up and solve a recurrence relation for the number of times the algorithm’s basic operation
is executed.
b. How does this algorithm compare with the straightforward nonrecursive algorithm for
computing this function?

Solution:

a. The question is similar to that about the efficiency of the recursive algorithm for computing n!.

b. Write a pseudocode for the nonrecursive algorithm and determine its efficiency.

Question 4: Consider the following recursive algorithm.

a. Set up a recurrence relation for this function’s values and solve it to determine what this
algorithm computes.
b. Set up a recurrence relation for the number of multiplications made by this algorithm and
solve it.
c. Set up a recurrence relation for the number of additions/subtractions made by this algorithm
and solve it.

Solution:

a. Note that you are asked here about a recurrence for the function’s values, not about a recurrence for
the number of times its operation is executed. Just follow the pseudocode to set it up. It is easier to
solve this recurrence by forward substitutions (see Appendix B).

b. This question is very similar to one we have already discussed.

c. You may want to include the subtraction needed to decrease n.

Page 2 of 4
Question 5: In the original version of the Tower of Hanoi puzzle, as it was published by Edouard Lucas, a
French mathematician, in the 1890s, the world will end after 64 disks have been moved from a mystical
Tower of Brahma.

a. Estimate the number of years it will take if monks could move one disk per minute. (Assume
that monks do not eat, sleep, or die.)
b. How many moves are made by the ith largest disk (1 ≤ i ≤ n) in this algorithm?
c. Design a nonrecursive algorithm for the Tower of Hanoi puzzle.

Solution:

a. Use the formula for the number of disk moves derived in the section.

b. Solve the problem for 3 disks to investigate the number of moves made by each of the disks. Then
generalize the observations and prove their validity for the general case of n disks.

c. If you fail, do not feel discouraged: though a nonrecursive algorithm for this problems is not
complicated, it is not easy to discover. As a consolation, find a solution on the Web.

Question 6: Consider algorithm for solving the problem by recursively dividing an array into two halves:

a. Set up a recurrence relation for the algorithm’s basic operation and solve it.
b. Can you suggest an algorithm for the problem the given algorithm solve that would be more
efficient?

Solution:

Tracing the algorithm for n = 1 and n = 4 should help.

Question 7: Consider the following recursive algorithm:

Page 3 of 4
a. What does this algorithm compute?
b. Set up a recurrence relation for the algorithm’s basic operation count and solve it.

Solution:

Question 8: Consider the following algorithm to check whether the graph defined by its adjacency
matrix is complete.

What is the algorithm’s Efficiency Class in the Worst Case?

Solution:

Page 4 of 4

You might also like