Question 1 Consider the triangleArea function from the textbook shown below: def

Question

Question 1

Consider the triangleArea function from the textbook shown below:

def triangleArea(sideLength) :

if sideLength <= 0 :

return 0

if sideLength == 1 :

return 1

smallerSideLength = sideLength - 1

smallerArea = triangleArea(smallerSideLength)

area = smallerArea + sideLength

return area

What will happen if line #6 is changed to: smallerSideLength = sideLength

Question options:

Infinite recursion will occur when sideLength is equal to 0.

Infinite recursion will occur when sideLength is equal to 1.

Infinite recursion will occur when sideLength is greater than or equal to 2.

Infinite recursion will occur for any value of sideLength.

Question 2

How many squares are drawn by the following code segment?

def tSquare(width, x, y, canvas) : canvas.drawRect(x, y, width, width) if width >= 4 :

tSquare(width / 2, x, y, canvas)tSquare(width / 2, x + width / 2, canvas)tSquare(width / 2, x, y + width / 2, canvas) tSquare(width / 2, x + width / 2, y + width / 2, canvas)

# Code to setup the canvas has been omitted tSquare(0, 0, 8, canvas)

Question options:

1

4

5

8

Question 3

Complete the code for the myFactorial recursive function shown below, which is intended to compute the factorial of the value passed to the function:

1. 2. 3. 4. 5.

def myFactorial(n) :if _____________________________ :

      return 1

   else :

return n * myFactorial(n - 1)

Question options:

n == 1

(n - 1) == 1

n * (n - 1) == 1

myFactorial(n) == 1

Question 4

Recall the permutations function from Section 11.5 in the textbook.

def permutations(word) : result = []

if len(word) == 0 : result.append(word) return result

else:for i in range(len(word)) :

shorter = word[ : i] + word[i + 1 : ] shorterPermutations = permutations(shorter) for string in shorterPermutations :

result.append(word[i] + string) return result

What is the base case for this function? Question options:

The empty list

Any list containing exactly one character

The empty string

Any string containing exactly one character

Question 5

particular algorithm visits n3 + nlog(n) + n! elements in order to perform its task on a list of n elements. Which big-Oh expression best describes the growth rate of this algorithm?

Question options:

O(n)

O(n3)

O(n!)

O(nlog(n)

Explanation / Answer

Question 1

Answer:

Infinite recursion will occur when sideLength is greater than or equal to 2.

Explanation

def triangleArea(sideLength) :

if sideLength <= 0 :

return 0

if sideLength == 1 :

return 1

smallerSideLength = sideLength - 1

smallerArea = triangleArea(smallerSideLength)

area = smallerArea + sideLength

return area

If smallerSideLength = sideLength is written in line 6, Then value of sideLength is not reduced so causes infinite recursion.

If sideLength=0 then it returns 0 . No recursion

If sideLength=1 then it returns 1 . No recursion

If sideLength=2 or more, then it recursively call triangleArea(sideLength) with same value of sideLength. So Infinite recursion will occur

-----------------------

Question 2

Answer:

1

Explanation

def tSquare(width, x, y, canvas) :

canvas.drawRect(x, y, width, width)

if width >= 4 :

tSquare(width / 2, x, y, canvas)

tSquare(width / 2, x + width / 2, canvas)

tSquare(width / 2, x, y + width / 2, canvas)

tSquare(width / 2, x + width / 2, y + width / 2, canvas)

If we call ,   tSquare(0, 0, 8, canvas)

Then width=0, x=0,y=8. Line 1 is canvas.drawRect(x, y, width, width) . draws a square

Then condition width>4 is false. So recursive call is not possible.

So it draws the square once.

------------------------------------------------------------------------------------------------------------------

Question 3

Answer:

n==1

Explanation

As we factorial(0)=1 and also factorial(1)=1. As the input is intended for the 1 ,2 ,3    (not 0).

So the base condition is if(n==1) then return 1;

--------------------------------------------------------------------------------

Question 4

Answer: The empty string

Explanation

The base is clearly known that

if len(word) == 0 :

result.append(word)

return result

len(word) == 0 means the word which is a string (not a list ) contains no character means it is empty

---------------------------------------------------------------------------

Question 5

Answer:    O(n!)

Explanation

n3 + nlog(n) + n!

let        f1(n)= O(n^3)

            f2(n)=O(nlog(n))

            f3(3)=O(n!)

and we know that f1(n)+ f2(n)+ f3(n)= O(MAX(   n^3 , nlog(n) , n!)

which is O(n!)

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.