Q1: Thane of Cadr

Define the procedures cadr and caddr, which return the second and third elements of a list, respectively. If you would like a quick refresher on scheme syntax consider looking at Lab 10 Scheme Refresher.

We need to implement the function c???r. To have a better understanding of this notation, you should look from back to the front in ???. For example, the cadr function will call cdr then call car on the input.

OOP

Q1: Vending Machine

In this question you’ll create a vending machine that only outputs a single product and provides change when needed.

Create a class called VendingMachine that represents a vending machine for some product. A Vending Machineobject returns strings describing its interactions. Remember to match exactly the strings in the doctests – including punctuation and spacing!

Fill in the VendingMachine class, adding attributes and methods as appropriate, such that its behavior matches the following doctests:

Coding Questions

Q2: Over or Under

Define a procedure over-or-under which takes in a number num1 and a number num2 and returns the following:

• -1 if num1 is less than num2
• 0 if num1 is equal to num2
• 1 if num1 is greater than num2

Challenge: Implement this in 2 different ways using if and cond!

text

Read more...

 Exercise Solution

Recursion and Tree Recursion

Q1: Subsequences

A subsequence of a sequence S is a subset of elements from S, in the same order they appear in S. Consider the list [1, 2, 3]. Here are a few of it’s subsequences [], [1, 3], [2], and [1, 2, 3].

Write a function that takes in a list and returns all possible subsequences of that list. The subsequences should be returned as a list of lists, where each nested list is a subsequence of the original input.

Q2: Convert Link

Write a function convert_link that takes in a linked list and returns the sequence as a Python list. You may assume that the input list is shallow; that is none of the elements is another linked list.

Try to find both an iterative and recursive solution for this problem!

It is easy to solve this problem iteratively. All we have to do is to make a list to store these nodes we have visited while we iterating this linklist.

Accounts

Q2: Retirement

Add a time_to_retire method to the Account class. This method takes in an amount and returns how many years the holder would need to wait in order for the current balance to grow to at least amount, assuming that the bank adds balance times the interest rate to the total balance at the end of every year.

The description tells us that: We will add our balance every year, so when may we retire? Both the math and code are simple.

Q1: Generate Permutations

Given a sequence of unique elements, a permutation of the sequence is a list containing the elements of the sequence in some arbitrary order. For example, [2, 1, 3], [1, 3, 2], and [3, 2, 1] are some of the permutations of the sequence [1, 2, 3].

Implement gen_perms, a generator function that takes in a sequence seq and returns a generator that yields all permutations of seq. For this question, assume that seq will not be empty.

Mutability

Write a function which takes in a list lst, an argument entry, and another argument elem. This function will check through each item in lst to see if it is equal to entry. Upon finding an item equal to entry, the function should modify the list by placing elem into lst right after the item. At the end of the function, the modified list should be returned.

See the doctests for examples on how this function is utilized.

Mobiles

Q2: Weights

Implement the planet data abstraction by completing the planet constructor and the size selector so that a planet is represented using a two-element list where the first element is the string 'planet' and the second element is its size.

From the description, we can know what is planet. It is a ['planet', size]. Then we can take a look at the mobile function, the solution is quite similar.

Lists

Q1: Factors List

Write factors_list, which takes a number n and returns a list of its factors in ascending order.

We can know such a basic mathematical fact: the factor of a number can only be up to half of it (when the number is even). So we use for i in range(1, n // 2 + 1)

Intro

I find it really interesting to solve recursive problems. I like this way of solving problems, the code is concise and intuitive, which is why I wrote this blog.

📒 How to solve a recursive problem ?

1. What is the base case ?
2. How to break down the current problem into simpler ones ?

Later, I will follow this idea to solve the recursion problem in this lab.

Recursion

Q2: Summation

Write a recursive implementation of summation, which takes a positive integer n and a function term. It applies term to every number from 1 to n including n and returns the sum.

hw03. Recursion, Tree Recursion

Q1: Num eights

Write a recursive function num_eights that takes a positive integer pos and returns the number of times the digit 8 appears in pos.

Important: Use recursion; the tests will fail if you use any assignment statements. (You can however use function definitions if you so wish.)

It is easy to think of the answer to this question, for we have seen a similar one in lecture. We can split the pos into all_bust_last and last. When we arrive at the base case, we just need to check if it is equals to 8. Because we can not use = in this problem, we need to use function instead.