Homework 2 (Due 4/11/2024 at 11:59pm)

Name:

ID:

Submission instruction:

• Download the file as .ipynb (see top right corner on the webpage).

• Write your name and ID in the field above.

• Answer the questions in the .ipynb file in either markdown or code cells.

• Before submission, make sure to rerun all cells by clicking Kernel -> Restart & Run All and check all the outputs.

• Upload the .ipynb file to Gradescope.

Q1 Fibonacci sequence

(1). Create a markdown cell below, write down the recurrence relation for the Fibonacci sequence

\(F_0 = 0\), \(F_1 = 1\), \(F_n = F_{n-1} + F_{n-2}\) for \(n >= 2\)

(2) Write a function, myfibo(n), using a loop, that returns the n-th Fibonacci number. Show your solution is correct by output the first 10 Fibonacci numbers.

# code here

def myfibo(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    else:
        a = 0
        b = 1
        for i in range(1, n):
            c = a + b
            a = b
            b = c
        return c

fibo_nums = [myfibo(i) for i in range(10)]
print(fibo_nums)

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

(3) Write a function, myfibo_rec(n), using recursion, that returns the n-th Fibonacci number.

# code here
def myfibo_rec(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return myfibo_rec(n-1) + myfibo_rec(n-2)

fibo_nums = [myfibo_rec(i) for i in range(10)]
print(fibo_nums)

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

(4) [Extra, not graded] Compare the time it takes to run myfibo(20) and myfibo_rec(20). Which one is faster? Why?

%%timeit
# run the following code to check the time, %%timeit will run the code multiple times and give you the average time it took to run the code 
myfibo(20)

363 ns ± 5.37 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

%%timeit 
myfibo_rec(20)

669 μs ± 10.7 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

Answer: myfibo is faster. myfibo_rec is slower because it makes many redundant calculations: for example, myfibo_rec(5) = myfibo_rec(4) + myfibo_rec(3), but myfibo_rec(4) = myfibo_rec(3) + myfibo_rec(2), notice that myfibo_rec(3) is calculated twice.

Q2 Working with list

(1) Define a function my_cumulative_sum(x), which take a list of numbers x, and modify x, so that the modified list is the list of cumulative sum of the original list:

If the original list is [\(x_0\), \(x_1\), \(x_2\), …], then the modified list is [\(x_0\), \(x_0+x_1\), \(x_0+x_1+x_2\), …].

Your function should only use a single for-loop.

For example

x = [1,1,1]

my_cumulative_sum(x)

print(x)

produce [1,2,3]

Test your function with input [1,2,3,4]

# code here
def my_cumulative_sum(x):
    for i in range(1, len(x)):
        x[i] = x[i] + x[i-1]

x = [1,2,3,4]
my_cumulative_sum(x)
print(x)

[1, 3, 6, 10]

(2)

Generate a list of numbers between 1 and 100 that exclude (1) multiples of 7 and (2) numbers that ends with 7

For example, 7, 14, 17, 21, 27, 28, .. are excluded.

Do not use “outer for-loop”. you can use list comprehension.

Hint: you might need to convert between integer and string.

Hint: you can define a helper function.

# code here

def should_exclude(n):
    if n % 7 == 0:
        return True
    str_n = str(n)
    if str_n[-1] == '7':
        return True

    return False

x = [i for i in range(1, 101) if not should_exclude(i)]
print(x)

[1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 15, 16, 18, 19, 20, 22, 23, 24, 25, 26, 29, 30, 31, 32, 33, 34, 36, 38, 39, 40, 41, 43, 44, 45, 46, 48, 50, 51, 52, 53, 54, 55, 58, 59, 60, 61, 62, 64, 65, 66, 68, 69, 71, 72, 73, 74, 75, 76, 78, 79, 80, 81, 82, 83, 85, 86, 88, 89, 90, 92, 93, 94, 95, 96, 99, 100]

(3)

Given the previous list, write a one-liner that sorts the list in increasing order based on the value of sin(x) for each element x. In other words, for any two elements x and y, x should come before y if sin(x) < sin(y). You can assume that ties can be kept in their original order.

Hint: Use list comprehension along with the built-in function sorted (or the list method sort) and a lambda function.

# Code here
from math import sin
sorted(x, key=lambda x: sin(x))

[11,
 55,
 99,
 80,
 36,
 30,
 74,
 61,
 5,
 93,
 86,
 24,
 68,
 23,
 43,
 92,
 48,
 4,
 18,
 62,
 73,
 29,
 81,
 54,
 10,
 12,
 100,
 79,
 31,
 75,
 60,
 16,
 6,
 50,
 94,
 85,
 41,
 25,
 69,
 66,
 22,
 44,
 88,
 3,
 19,
 72,
 38,
 82,
 53,
 9,
 13,
 78,
 34,
 32,
 76,
 59,
 15,
 51,
 95,
 40,
 26,
 65,
 1,
 45,
 89,
 90,
 46,
 2,
 20,
 64,
 71,
 39,
 83,
 96,
 52,
 8,
 58,
 33]

Q3 Implement a Rectangle class with the following attributes and methods:

• Attributes: width, height

• Methods:

  • __init__(self, width, height): initialize the width and height of the rectangle

  • area(self): return the area of the rectangle

  • smaller_than(self, rec): return True if the area of the rectangle is smaller than the area of another rectange object rec, False otherwise

  • resize(self, c): resize the rectangle, where c is a scaling factor. For example, if c=2, the width and height of the rectangle will be doubled. If c=0.5, the width and height of the rectangle will be halved.

  • If rec is a Rectangle object, print(rec) should print the (width,height) of the rectangle.

  • (Challenge, not graded) overload the ‘<’ operator so that rec1 < rec2 returns True if the area of rec1 is less than the area of rec2, False otherwise.

(1) Define your class here

# code here

class Rectangle:
    def __init__(self, width, height):
        self.width = width
        self.height = height
    
    def area(self):
        return self.width * self.height
    
    def smaller_than(self, other):
        return self.area() < other.area()   
    
    def __repr__(self):
        return f"({self.width}, {self.height})"

    def resize(self, c):
        self.width = self.width * c
        self.height = self.height * c
    
    def __lt__(self, other):
        return self.area() < other.area()

(2) Use examples to demonstrate that the methods in your class work as expected.

# code here

r1 = Rectangle(1, 2)
r2 = Rectangle(2, 3)

# should print 2
print(r1.area())

# should print (1, 2)
print(r1)

# should print True
print(r1.smaller_than(r2))

r1.resize(2)
print(r1.area()) # should print 8

# should print False
print(r1.smaller_than(r2))

# should print True
print(r2 < r1)

2
(1, 2)
True
8
False
True

Q4 Two sum problem

The problem is from Leetcode, which is a website for practicing coding problems.

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9

Output: [0,1]

Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6

Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6

Output: [0,1]

def twoSumList(num, target):
    # solve the problem using list,
    # this is slow
    for i in range(len(num)):
        for j in range(i+1, len(num)):
            # check if the two numbers add up to target
            if num[i] + num[j] == target:
                return [i, j]



def twoSumDict(nums,target):
    # solve the problem using dictionary,
    # this is faster than twoSumList
    dict_num_idx = {} # dictionary {num : index}
    for i in range(len(nums)):
        # nums[i] is my current num
        # we want the index of the complement
        complement = target - nums[i]
        
        # check if complement is already in my dictionary
        if complement in dict_num_idx:
            # already there, then get the index
            other_idx = dict_num_idx[complement]
            return [i, other_idx]
        else:
            # if not there, we keep in our dictionary
            # might use it in the future
            dict_num_idx[nums[i]] = i
    

# test
# should return [0, 1] or [1, 0]

print(twoSumDict([2,7,11,15], 9))

print(twoSumList([2,7,11,15], 9))

[1, 0]
[0, 1]