# CSci 1901: Bonus Questions

#### Bonus Question (RSA Encryption) from Lab 2 -- 1 point

Next week you will write some procedures for preforming RSA encryption, a very common encryption and decryption method. It will not be necessary to understand that mathematics behind RSA encryption, but understanding the math will make the lab more interesting. For this bonus question read through the following description of RSA encryption and answer the following questions:
• RSA encryption involves 4 numbers, namely P,Q,D, and E. P and Q must be prime. E must be odd and must satisfy two additional conditions, what are these conditions?
• What is the one condition that the number D must satisfy?
• Use this dictionary, that associates words with a numeric value, to find the encoding for the word "abstract". This is the number T described in the above link.
• Use the value for T that you just found to find the encrypted cipher text (called C) for "abstract". Use the following RSA values - P = 61, Q = 53, E = 17, and D= 2753. You will need to make use of the function `(expmod a b c)` from the book which efficiently computes the value `a^b mod c`
```(define (square x) (* x x))

(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (square (expmod base (/ exp 2) m))
m))
(else
(remainder (* base (expmod base (- exp 1) m))
m))))
```
• Use `expmod` to verify that the cipher text you found above decrypts properly back to the numeric encoding for abstract.

#### Bonus Question from Lab 3 (RSA Encryption) -- 1 point

Complete the following exercises from the text:
1. Exercise 1.12. This requires writing a procedure that computes the binomial coefficient (nk) using a recursive process on the Pascal triangle. The binomial coefficent is usually computed as ``` (nk) = n!/k!*(n-k)! ``` This exercise requires to use the recursive process described in the exercise instead of using the factorial function.
2. Exercise 1.16. This requires rewriting the procedure fast-expt so that it generates a linear iterative process.
3. Exercise 1.17. This requires writing a fast multiplication procedure using additions. You can write the procedure to generate a linear recursive process or a linear iterative process, whatever you prefer.

#### Challenge Question from Lab 3 (RSA Encryption) -- 3 points

Answer Exercise 1.28. This requires that you understand the math described in the exercise, you write the corresponding Scheme code, and include test case to show that your procedure work as expected.

#### Bonus Question from Lab 4 (More RSA Encryption) -- 1 point

Complete the following exercises from the text:
1. Exercise 1.29, which is on using the Simpson rule to compute the integral of a n function f between a and b. The Simpons rule is as follows
where h = (b - a)/n, for some even integer n, and yk = f(a + kh). (Increasing n increases the accuracy of the approximation.)
Define a procedure that takes as arguments f, a, b, and n and returns the value of the integral, computed using Simpson's Rule. Use your procedure to integrate cube between 0 and 1 (with n = 100 and n = 1000).
2. Exercise 1.39 which is approximating the tangent function using the continued fraction representation
where x is in radians. Define a procedure (tan-cf x k) that computes an approximation to the tangent function based on Lambert's formula. K specifies the number of terms to compute.
How large must you make k in order to get an approximation that is accurate to 4 decimal places?

#### Bonus Questions from Lab 6 (Trees)

1. Bonus Question 1 -- 1 point
[This is exercise 2.28 from the textbook]. Write your procedure in two dfferent ways, one without using any higher-order procedures and one using map and recursion.
Write a procedure fringe that takes as argument a tree and returns a list whose elements are all the leaves of the tree arranged in left-to-right order. For example,
```(define x (list (list 1 2) (list 3 4)))
STk> (fringe x)
(1 2 3 4)
STk> (fringe (list x x))
(1 2 3 4 1 2 3 4)
```
2. Bonus Question 2 -- 2 points
A string is a collection of characters surrounded by double quotes. An example of a string is "hello". For this problem you should write the procedure `string-to-frequency-list`. This procedure should take in a string, and return a list of symbol-frequency pairs. An example of symbol-frequency pair is the list ```(#\h 2)```. `#\h` is the symbol (remember `#\h` is a character, not an actual scheme symbol), and 1 is the frequency, or the number of times `#\h` appeared in some string we wanted to encode. `str2frequency-list` must return a list of these frequency pairs, one pair for each unique character in the string passed to string-to-frequency-list.

`(string-to-frequency-list "hello")` should return the list: `((#\h 1) (#\e 1) (#\l 2) (#\o 1))`, or a similar list with a different ordering of the symbol-frequency pairs.

The procedure `string->list` is built into STk, and may be useful to you. It takes in a string and returns the list containing each of the characters in the string in the order they appear in the string. So for instance `(string->list "hello")` would return the list `(#\h #\e #\l #\l #\o)`.

`string-to-frequency-list` is more complicated than procedures in prior labs. Plan how to decompose the problem into simpler problems before you start writing your procedure.

You can come up with your own solution, or follow the steps outlined here:

1. Write a procedure `(unique L)` which will examine a list and return a sublist with all duplicates removed. For example `(unique (list 3 1 3 4 1))` would return a list like `(3 1 4)` which has the duplicate elements removed.
Tip: You can use `(member x lst)` to check if `x` is list `lst`.
2. Write a procedure `(count-occurrences obj L)` which will count the number of times `obj` appears in the list `L`.
Tip: To test if two numbers are the same you have seen the `=` operator, but this only works for numbers. To test if `x` and `y` are the same for more general kinds of data you can use `(eqv? x y)`.
3. Go over the list of unique characters (generated with the `unique` and `string->list` functions.) Ideally you you will use the `map` function to recurse over this list. Use `count-occurences` to generate the frequencies for each unique character during your recursive or iterative process.

Useful procedures for the bonus question:

• `(member obj lst)` returns a nonfalse value if `obj` is found in list `lst` or `#f` otherwise. More precisely, if `obj` is in the list `lst` it will return the list starting at `obj`.
• `(eqv? obj1 obj2)` returns `#t` if `obj1` and `obj2` are the same. It works for numbers, characters, and symbols, but not for lists. To compare characters you can also use `(char=? char1 char2)`
• `(string->list str)` returns a list of characters contained in string `str`.

#### Bonus Question from Lab 7 (Ordered Lists and Binary Trees) -- 1 point

What are the runtime complexities of your solutions to the following steps from the lab?
• Step 3: Convert a Set to a Binary Tree
• Step 4: Union of Sets (Binary Tree)
• Step 5: Intersection of Sets (Binary Tree)

#### Bonus Questions from Lab 9 (Local State and Hilbert Space Filling Curves)

• Bonus Question 1 -- 1 Point
If you want to write the various Hilbert curves you have created in Step 5, so that instead of each using only a part of the canvas the curves are drawn on top of each other, how do you need to change the calls to the procedure hilbert that you used in Step 5?
• Bonus Question 2 -- 1 Point
Use the set-color! procedure described above to assign a color to the lines drawn by the hilbert procedure. Choose the colors from the following: red white green blue black yellow cyan magenta orange purple brown pink. You'll need something like `(set-color! (draw-line 0 0 20 0) 'green)` to set the color of the line to green.
• Bonus Question 3 -- 2 Points
Write a procedure that given the list of colors above, allows one to select a random color from that list. Use your procedure to draw hilbert functions with different colors. Tip: The procedure `(random n)` returns a random number in the interval 0 to n.

#### Bonus Questions from Lab 11 (Tables)

[This is from Exercise 3.27 from the textbook] Memoization (also called tabulation) is a technique that enables a procedure to record, in a local table, values that have previously been computed. This technique can make a vast difference in the performance of a program. A memoized procedure maintains a table in which values of previous calls are stored using as keys the arguments that produced the values. When the memoized procedure is asked to compute a value, it first checks the table to see if the value is already there and, if so, just returns that value. Otherwise, it computes the new value in the ordinary way and stores this in the table. As an example of memoization, recall from section 1.2.2 the exponential process for computing Fibonacci numbers:
```(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1)) (fib (- n 2))))))
```
We define the memoizer as
```(define (memoize f)
(let ((table (make-table)))
(lambda (x)
(let ((previously-computed-result (lookup x table)))
(or previously-computed-result
(let ((result (f x)))
(insert! x result table)
result))))))
```
The memoized version of the fibonacci procedure is
```(define memo-fib
(memoize (lambda (n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (memo-fib (- n 1))
(memo-fib (- n 2))))))))
```
1. Bonus Questions 1 -- 1 Point
Using the code above compute `(fib 30)` and `(memo-fib 30)`. Did you notice a difference in the time to compute them?
2. Bonus Questions 2 -- 1 Point
Now compute `fib` for increasingly larger numbers. Stop when the computation takes approximatively more than 1 minute. Write down the largest number for which you computed `fib`.
3. Bonus Questions 3 -- 1 Point
Repeat the same process as in the previous step but this time using `memo-fib`. What is the largest number for which you can compute `memo-fib`? Is this much larger than what you found for `fib`?
4. Bonus Questions 4 -- 1 Point
Explain why `memo-fib` computes the nth Fibonacci number in a number of steps proportional to n instead of being exponential in n as for `fib`.
5. Bonus Questions 5 -- 1 Point
Would `memo-fib` still work if we had simply defined `memo-fib` to be `(memoize fib)`? Why or why not? explain your reasoning.

#### Bonus Questions from Pop 9 -- 1 point

Write a procedure in Scheme to count the number of actions in an agenda data structure, i.e. that counts the number of thunks in all the queues in the agenda data structure. [Hint: write a procedure to return the length of a queue and then use the selectors for the agenda]