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:

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:

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?

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

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]
Copyright: © 2007 by the Regents of the University of Minnesota
Department of Computer Science and Engineering. All rights reserved.
Comments to: Maria Gini
Changes and corrections are in red.