Here are some exercises to help you practice for the final exam.
In the base 2 number system there are only two possible digits: 0 and 1. These are often called bits. Each bit counts for twice as much as the bit to the right, so the binary number 101 is 1 * 4 + 0 * 2 + 1 * 1 = 5.
Here is a table of the first 8 non-negative numbers in both binary and decimal.
| Binary | Decimal |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 10 | 2 |
| 11 | 3 |
| 100 | 4 |
| 101 | 5 |
| 110 | 6 |
| 111 | 7 |
| 1000 | 8 |
Write a recursive function convert_to_binary that takes a
non-negative integer as a parameter and returns the binary
representation of that number (as a string of 0's and 1's).
Hint 1: you can figure out the least significant binary digit by
using the remainder operator: number % 2. You can also
use integer division to get rid of the last digit, halving the number.
For example, 19 % 2 is 1, and 19 / 2 is 9.
Hint 2: If you can determine the binary representation, b, of an integer divided by 2, you can determine the binary representation of the original integer by appending a 0 or a 1 to b.
Write a recursive function that takes two positive integers and returns their greatest common divisor (GCD). The GCD of two integers is the biggest number that goes into each number evenly. For example, the GCD of integers 9 and 6 is 3; the GCD of integers 12 and 4 is 4.
Hint: assume m is greater than or equal to n. It is true that gcd(m, n) = gcd(m- n, n).
Write a recursive function that takes a list and returns a list consisting of every second element of the original list. For example, for the list [2, 4, 6, 8, 10, 12], your function should return [4, 8, 12]. Do not modify the original list.
Consider the following problem (adapted from Cormen et al., Introduction to Algorithms, 2001). You are given an n by n checkerboard, where each of its squares is associated with a positive amount of money. Starting somewhere on the bottom row, the game involves moving a checker to somewhere on the top row. At each step, there are a maximum of three allowable moves. First, you may move the checker up to the square above. Second, you may move the checker to the square above and to the left, but only when the checker is not already positioned on the first column. Third, you may move the checker to the square above and to the right, but only when the checker is not positioned on the last column. For each square the checker occupies during the game, you receive that square's money value. Maximize the amount of money you receive.
Write a recursive function to solve this problem. Your recursive solution will be very inefficient; the efficient way to solve this problem requires dynamic programming, a topic that we unfortunately won't be able to cover this semester.
Consider a merge sort that makes three recursive calls: one to sort the first third of the list, one to sort the middle third, and one to sort the last third. Assume that you have a function to merge the three resulting sorted sublists into one big sorted list. What is the running time of the algorithm now?