University of Guadalajara Create a Program Code Programming Task

Homework 2Include display statements and function calls as necessary to completely demonstrate that your code works
for each of the following problems.
Email your racket file to me when done (normally a .rkt extension).
Define the procedures below.
Write a procedure reverse-digits (n) which returns a number with the digits of n in reverse order.
For example, (reverse-digits 397164) → 461793.
Define a predicate same-digits? (a b) which returns #t if the integers a and b contain the same digits.
If a digit occurs n times in a, it must also occur n times in b. For example,
(same-digits? 133042 420313) → #t, but (same-digits? 133042 42013) → #f.
To solve the problem, one technique would be to add some extra procedures for manipulating digits inside a number.
Here are some hints:
To find the number of digits in a number, count how many times you need to divide it by 10 until you reach 0.
To extract the second digit of 5784: floor( 5784/102 ) mod 10=7. Note that mod in racket is modulo or remainder
To assemble the digits 3, 4, and 5 into a number: 3×102+4×101+5×100 = 345
The standard Scheme procedures modulo and floor may prove useful. The solution only needs to consider non-negative integers.
Or….. you could “cheat” and convert each number to a list, sort, and check for equality.
Around 1946 John von Neumann came up with possibly the first suggestion for generating pseudorandom numbers using ordinary arithmetic: take the square of the previous random number and extract the middle digits. If we are working with four-digit numbers, the square will be 8 digits, and the middle 4 digits are returned as the result. If we are working with ten-digit numbers, the square will be 20 digits and the middle 10 will be returned. As an example, for 10 digits, if the previous value is 5,772,156,649, squaring it gives 33,317,792,380,594,909,201, producing 7,923,805,949 as the next number in the sequence.
Implement von Neumann’s middle-square random number generator. The procedure should take two parameters: the previous number, and the number of digits in the result. You can use the expt function to square numbers, or implement a square function yourself, or just multiply the number by itself.
Test out the algorithm. Can you spot any problems with it?
If both n and 2n −1 are primes, then n is said to be a Mersenne prime. The first few Mersenne primes are 2, 3, 5, 7, 13, 17, 19, 31, and 61. Use the primality routines in SICP 1.2.6 to write a procedure for finding such primes (or use the built in prime?). It should take two parameters the starting n and a predicate to test for primality, and return the next Mersenne prime. (If you find a ten million digit prime number, you can pick up a $100,000 prize and forget all about Lisp; see http://www. mersenne.org/.) An example of calling this function might look like this:
(next-mersenne 20 prime?)
which should return 31.
Testing
Unit testing is possible with racket, although you are not required to do this for testing your code. Simply for illustration purposes, here is some test code written by Adam S. for problems 1b and 2.Functional Programming
with Scheme
Procedural Abstraction (2)
Procedures and Processes
Process
– a sequence of operations (events) that evolve in time
(on a computer, for example)
Procedure
– a description (a specification) of how a process should evolve
from one stage to another
slide 2
Procedures and Processes (contd)
Both procedures and processes may be
– recursive
– iterative
An iterative process
– described by a fixed number of state variables
– state variables are updated on each iteration until some stop
condition is met
A recursive process
– keeps track of previous, unfinished steps (deferred operations) to be
completed later after the stop condition is met
slide 3
Procedures and Processes (contd)
An iterative procedure may describe
– a recursive process – e.g., by explicitly using a stack of deferred
operations as a state variable (questionable)
– an iterative process (most common in imperative PL; loop
constructs such as while, for, repeat etc.)
A recursive procedure may describe
– a recursive process (most common in FP)
– an iterative process (tail‐recursion, possible also in imperative PL
with optimizing compilers)
In this course we use exclusively recursive procedures
(no looping constructs, though Scheme allows some)
slide 4
Recursion
General recursion scheme – to solve a problem:
– test the problem for the stop condition(s)
– if any stop condition is met, produce a solution
– if not, reduce the problem and use (combine) the result(s) of
solving the subproblem(s) to solve the current problem
Linear recursion – generate one smaller problem (reduce)
Tree‐recursion – generate several smaller problems (divide‐
and‐conquer)
Recursion is guaranteed to terminate only with correct stop
conditions and problem reductions; otherwise it may
specify an infinite process
slide 5
Recursive Signature Campaign
Goal: send a mail with n signatures
Method:
1. Prepare an empty mail with n lines
2. If there are any free lines
–
reserve a line for yourself and
forward the mail to the next person
–
when the mail comes back, sign in
your line before that person
–
return to the previous person, or (if
first) send the mail
3. If there are no free lines, simply
return the mail
slide 6
Iterative Signature Campaign
Goal: send a mail with n signatures
Method:
1. Prepare an empty mail with n
lines
2. If there are any blank lines
–
sign after the previous person
(or as first)
–
forward to the next person
3. If there are no blank lines,
send the mail (the goal is
achieved)
slide 7
Recursive Processes
Maintain a variable number of deferred operations
Consume space proportional to the size of the input
(dependent on the number of recursive calls)
(define (factorial n)
(if (< n 2) ;; compute 3! (factorial 3) 1 (* 3 (factorial 2)) (* n (factorial (- n 1))))) (* 3 (* 2 (factorial 1))) (* 3 (* 2 1)) (* 3 2) 6 slide 8 Iterative Processes Maintain a fixed number of state variables Consume constant space (independent on the number of iterations) (define (factorial n) (define (iter product counter) (if (> counter n)
;; compute 3!
(factorial 3)
(iter 1 2)
product
(iter 2 3)
(iter (* counter product)
(iter 6 4)
(+ counter 1))))
6
(iter 1 2))
slide 9
Tail Recursion
If, at a particular step sk, there are no further operations to
be performed on the result* r of a recursive call sk+1 other
than simply returning r, r can be passed directly to the
caller’s (sk) caller (sk‐1)
As soon as sk+1 is called, sk may be removed from the
runtime stack (optimization in tail‐recursion)
6
factorial(3)
6
factorial(3)
2
6
factorial(2)
iter(1,1)
1
6
factorial(1)
iter(1,2)
* In general, if there are no deferred operations to be done later – see next slide
6
iter(2,3)
6
iter(6,4)
slide 10
Tail Recursion (contd)
Compare the following procedures
– both are recursive
– none of them needs the result of the recursive call
– one generates a recursive process, the other an iterative process
(which is which?*)
(define (count* n)
(cond ((= n 0) n)
(else (- n n)
(count* (- n 1)))))
(define (count** n)
(cond ((= n 0) 0)
(else (count** (- n 1))
(- n n))))
– replace (- n n) with (display n) (a side‐effect procedure)
to see the difference
* Hint: the else construct is a part of the special syntactic form of cond , not a regular procedure
slide 11
Tree Recursion
Intuitively appealing
– splits a large problem into a number of similar but smaller
subproblems
– easy to invent, easy to implement
Possibly ineffective in practice
– smaller subproblems may be (partially) overlapping; if one
subproblem is identical to or contains another subproblem, there
will be redundant computation
– in pure FP, an intelligent compiler might detect such situations; in
presence of side effects this may not be possible (and reasonable)
– no longer linear – causes a deferrence‐explosion
(O(kn) complexity for k subproblems and n recursion steps)
slide 12
Tree Recursion (contd)
Fibonacci numbers
– the sequence 0, 1, 1, 2, 3, 5, 8, 13, …
(define (fib n)
(if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))) – the fib(n – 1) subproblem ’contains’ the fib(n – 2) subproblem, the computation is (highly) redundant – in fact, the whole tree is fractal‐like (self‐similar) slide 13 Tree Recursion (contd) Fibonacci numbers – revised (define (fib n) (define (iter a b c) (if (= c n) b (iter (+ a b) b (+ c 1)))) (iter 1 0 0)) – compute the numbers bottom‐up – reuse results of already computed smaller subproblems – compare both fibs with a timing macro; what is the dependence of elapsed time on the input number? slide 14 Tree Recursion (contd) It is not always straightforward (or possible) to reduce redundant computation by replacing a tree‐recursive process with an iterative one – a recursive process is (usually) much more intuitive if the algorithm is recursive – branches in the tree may be only partially overlapping – the tree represents an exhaustive search in a search space where some of the states may not contribute to the solution, or there are alternative solutions (nondeterminism) – to write an iterative version we would have to know the (a) solution path a priori (e.g., Towers of Hanoi) slide 15 Towers of Hanoi The rules of the puzzle – – – – three pegs disks of various sizes placed on top of each other only smaller disks on larger disks only move one disk at a time The goal – move all disks from one peg to another The solution – a (recursive) procedure (a tree‐recursive process) that takes the number of disks on the first peg and produces a sequence of moves appropriate to move all disks to the second peg, using the third peg as necessary slide 16 Towers of Hanoi (contd) Employ wishful thinking – decide how to make the problem simpler – pretend you know how to solve the simpler problem – decide how to use this solution to solve the original problem Solution (outline) – to move all disks from the initial peg pi • move all but the last disk dl to the additional peg pa (wishful thinking) • move dl to the target peg pt • move all from pa to pt (wishful thinking again) – if there are no disks on pi, simply do nothing slide 17 Orders of Growth Each process has some space (S) and time (T) requirements Recursive and iterative solutions of the same problem may have different complexity (order of growth) in S and T in terms of the input size n Complexity Space Time (#steps) Θ(1) – constant all iterative processes Θ(n) – linear linear recursive processes linear iterative, linear recursive processes Θ(bn) – exponential Θ(log n) – logarithmic – e.g. recursive fib e.g. fast-exp e.g. gcd, fast-exp Θ(nm) – power law slide 18 Exponentiation Possible to implement as a recursive procedure that generates a recursive or an iterative process – most obvious recursive version (linear S and T) – iterative (constant S and linear T) – successive squaring recursive (logarithmic S and T) – successive squaring iterative (constant S and logarithmic T) Exercise: Implement a procedure ^ that exponentiates an arbitrary base b with an arbitrary exponent e (i.e., b and e do not have to be integers) Exercise: Implement a procedure ^^ that computes the n‐th power tower of a number b slide 19 Greatest Common Divisor The greatest common divisor (GCD) of two numbers a and b is the largest number that divides both a and b with no remainder The Euclid’s Algorithm – the oldest known nontrivial algorithm – employs an iterative process with GCD runtime in terms of a and b logarithmic time requirement – if r is the remainder of the division of a by b, then GCD(a,b) equals GCD(b,r) (reduction – can use wishful thinking; assume a > b)
– if r is 0, then GCD(a,b) equals b (base case)
– iterative process, recursive procedure
slide 20
Prime Factorization
A number n is said to be prime if its only divisor* is n
To check if n is prime, test if any number m, m2 < n, divides n (if m2 = n, n is obviously not prime) Alternatively, test if any prime number p, p2 < n, divides n – iterative process, recursive procedure – constant S and power‐law T (Θ(n1/2)) Every number n that is not prime can be expressed as the, product of prime numbers p1, p2, ..., pk, where pi < n for each i, and the primes are not necessarily all unique * The number 1 is usually not considered as a prime number and, in this context, as a divisor slide 21 Prime Factorization (contd) Factorization of a number n is the problem of finding a sequence of numbers (factors) whose product equals n Prime factorization is a factorization in which all factors are prime numbers To find all prime factors of a number n, find the first prime p that divides n and then prime‐factorize the number n/p – iterative process, recursive procedure – constant S and power‐law T (Θ(n1/2)) slide 22