0368.1105 Extended Introduction to Computer Science

0368.1105 Extended Introduction to Computer Science

TEL AVIV UNIVERSITY

Department of computer science

0368.1105 – Extended Introduction To computer Science

Spring semester, 2000-2001

Homework 3

This homework is due by 2.4.2001, 18:00, in the hand-in boxes near room 005 in Schreiber building. Write your name, ID number and group number clearly, and keep a copy of the assignment. Remember to include a meaningful sample execution of your code for each question that requires coding (a printout).

1 a. Write a program that checks whether a given input n is a Carmichael number.

b. Write a program that finds all Carmichael numbers up to a given input m.

c. Analyze the running time of the algorithms you gave in a and b.

d. Check the running time on a sample of 10 numbers chosen at random between

1 and 1000000. (Use the primitive procedure (runtime)). Does it match your

prediction?

2. Solve the following recursive equations:

a. T(n)=T(n/2)+O(1), T(1)=O(1).

b. T(n)=2T(n/2)+O(1), T(1)=O(1).

c. T(n)=2T(n/2)+O(n), T(1)=O(1).

d. T(n)=4T(n/2)+O(n), T(1)=O(1).

3. a. In class we saw a recursive solution to factorial. Write an iterative solution to

factorial, call it fact.

Now suppose

(define (fact-mod n b)

(remainder (fact n) b)))

Also write a procedure fact-mod-2 that pushes the mod operation into the

procedure fact.

b. Compare the running time of fact-mod and fact-mod-2 on large n and b.

c. Compute (fact-mod (- n 1) n) on a large random sample of numbers. Can you

guess what is this value?

4. The procedure sum defined here, generates a recursive process.

(define (sum term a next b)

(if (> a b)

0

(+ (term a)

(sum term (next a) next b))))

  1. Define a new version of sum that generates an iterative process.
  2. Define a procedure product, analogous to sum, which computes the product of a given function at points over a given range.

5.

Part I

Define a procedure apply­to­5 that takes a procedure of one argument and applies it to 5. For example,

==> (apply­to­5 square)

25

Use substitution to evaluate the following expressions:

  1. (apply-to-5 1+)
    value:
  2. (apply-to-5 (lambda(x) (+ 5 x))
    value:
  3. (apply-to-5 apply-to-5)
    value:

part II

Write a procedure apply­to that, given a number n, returns the procedure analogous to apply­to­5

(for n = 5). That is, you should be able to write

(define apply­to­5 (apply­to 5))

Given the following definitions:

(define apply­to­5 (apply­to 5))

(define (3* x) (* 3 x))

Use substitution to evaluate the following expression:

(apply-to-5 3*)

value:

6. Write a procedure shift which, given a function F and a value a produces the function G such that G(x) = F (x – a). That is, you should have

((shift square 3) 8) ==> 25

7. The square procedure computes the square of a number, and the sqrt procedure computes the square root of a number. Mathematically, these are inverse functions; that is, x = sqrt (square (x)) = square (sqrt (x)) for all nonnegative x. But on the computer, which cannot represent numbers with infinite precision, square and sqrt will not be perfect inverses. In this exercise, we will write procedures to help investigate the behavior of inverse procedures.

  1. Write a procedure test-sqrt-of-square that takes a number as argument and tests whether the square root of the square of the number is equal to the original number (this procedure should return true or false). Try it on a few numbers.
  2. Write a procedure test-square-of-sqrt that takes a number as argument and tests whether the square of the square root of the number is equal to the original number. Try it on a few numbers.
  3. We might want to test other pairs of inverse procedures, not just sqrt and square. Abstract the idea of testing a pair of inverse procedures by writing a procedure make-inverse-tester that takes two procedures as arguments and returns an inverse-testing procedure. For example, we can define test-sqrt-of-square and test-square-of-sqrt as follows:

(define test-square-of-sqrt

(make-inverse-test square sqrt))

(define test-sqrt-of-square

(make-inverse-test sqrt square))

8 a. Write a procedure compose such that (compose F G) evaluated at x returns F

applied to (G x). For example:

((compose square 1+) 7) ==> 64

((compose 1+ square) 7) ==> 50

b. Use compose to define repeated-application, where (repeated-application fn n) is

a procedure that applies fn to its argument n times:

(define 5+ (repeated-application 1+ 5))

(5+ 100) ==> 105

c. Define repeated­application without using compose.

9. For each of the cases bellow, give an expression involving foo, whoses evaluation will return the value 2.

a. (define foo

(lambda (x) (* 2 x)))

b. (define foo

(lambda (x) (x 3)))

c. (define foo

(lambda (y) (lambda ( x) (- y x))))

d. (define (foo x)

( x (lambda (x) (* 2 x))))

10. Suppose mad is defined as follows:

(define (mad fn)

(lambda (x) (fn (fn (fn x)))))

What are?

  1. ((mad 1+) 0)
  2. ((mad (mad 1+)) 0)
  3. (((mad mad) 1+) 0)
Top View