NYU CS-UY 1134 Lab 6

1. For each of the following code snippets:

   a. Given the following inputs, trace the execution of each code snippet.Write down all outputs in order and what the functions return.

   b. Analyze the running time of each. For each snippet:

   ​ i. Draw the recursion tree that represents the execution process of the function, and the cost of each call

   ​ ii. Conclude the total (asymptotic) run-time of the function.

a.

def func1(n):  # Draw out func1(16)
    if (n <= 1):
        return 0
    else:
        return 10 + func1(n-2)

b.

def func2(n):  # Draw out func2(16)
    if (n <= 1):
        return 1
    else:
        return 1 + func2(n//2)

c.

def func3(lst): # Draw out func3([1, 2, 3, 4, 5, 6, 7, 8])
    if (len(lst) == 1):
        return lst[0]
    else:
        return lst[0] + func3(lst[1:])

In this section, it is strongly recommended that you solve the problem on paper before writing code.

1. Write a recursive function that returns the sum of all numbers from 0 to n. (5 minutes)

def sum_to(n):
    """
    : n type: int
    : return type: int 
    """

2. Write a recursive function that returns the product of all the even numbers from 1 to n (assume n is passed in as an even number). (5 minutes)

ex) if n=8→2 * 4 * 6 * 8 = 384,so the function returns 384.

def product_evens(n):
    """
    : n type: int
	: return type: int 
	"""

3. Write a recursive function to find the maximum element in a non-empty, non-sorted list of numbers.

ex) if the input list is [13, 9, 16, 3, 4, 2], the function will return 16.

a. Determine the runtime of the following implementation. (7 minutes)

def find_max(lst):
    if len(lst) == 1:
        return lst[0] # base case
    prev = find_max(lst[1:])
    if prev > lst[0]:
        return prev
    return lst[0]

b. Update the function parameters to include low and high. Low and high are int values that are used to determine the range of indices to consider.Implementation run-time must be linear. (10 minutes)

def find_max(lst, low, high):
    """
    : lst type: list[int] 
    : low, high type: int 
    : return type: int 
    """

4. Valid Palindrome – Leetcode 125

A palindrome is a phrase where all characters are the same backward and forward.

Given a string str and its range of indices to consider, return True if it is a palindrome,or False otherwise. Assume all characters are lowercase. Must run in O(n) time.

ex) is_palindrome("racecar", 0, 6) returns True # racecar

is_palindrome("racecar", 1, 5) returns True # aceca

is_palindrome("race car", 0, 6) returns False # empty space counts as a

character

is_palindrome("racecar", 1, 3) returns False # ace

def is_palindrome(str, low, high):
    """
    : str type: str
    : low, high type: int : return type: bool 
    """

5. Binary Search – Leetcode 704

Given an array of integers nums which is sorted in ascending order, low and high indices, and an integer target, write a function to search for target in nums. If target exists between low and high, then return its index. Otherwise, return None.

You must write an algorithm with $O(log n)$ runtime complexity.

def binary_search(lst, low, high, val):
    """
    : lst type: list[int]
    : val type: int
    : low type, high type: int
    : return type: int (found), None 
    """

6. Vowel and Consonant Count

Given a string of letters representing a word(s), write a recursive function that returns a tuple of 2 integers: the number of vowels, and the number of consonants in the word.

Remember that tuples are not mutable so you’ll have to create a new one to return each time when you’re updating the counts. Since we are always creating a tuple of 2 integers each time, the cost is constant. Implementation run-time must be linear. (25 minutes)

ex) word = “NYUTandonEngineering”

vc_count(word, 0, len(word)-1) → (8, 12) # 8 vowels, 12 consonants

def vc_count(word, low, high):
    """
    : word type: str
    : low, high type: int
    : return type: tuple (int, int) 
    """

7. OPTIONAL

Given a list of integers, write a function to print the sum triangle of the array. Each row in the sum triangle is defined as the sum of each number and the one exactly after it.

Note that if there is no number after it, this number is removed. That is, there will always be one fewer number after each row.

Example,if lst = [1, 2, 3, 4, 5],the sum triangle will be printed as followed:

[48]                ← #[20+28]
[20, 28]            ← #[8+12,12+16]
[8, 12, 16]         ← #[3+5,5+7,7+9]
[3, 5, 7, 9]        ← #[1+2,2+3,3+4,4+5]
[1, 2, 3, 4, 5]     ← startinglist

def list_sum_triangle(lst):
    """
    : lst type: list
    : output type: None 
    """

公众号：AI悦创【二维码】