When dokumenting the solutions to the exercises use a word processor and do not write by hand. Using a word processor saves time both for you and certainly for me, that have to check your solutions.
Exercise set seven: due in written using metoo by November 29.
The task is to design a simple system for maintaining a library of books. Implement and validate the following:
There are two primary objects in the system - Library and Book. The book (we do not consider multiple copies) can be described by recording the following details about it:
Title = String Authors = set(Author) Author = String Publisher = String Copyright = Int let this be just the publishing yearThese details can be held in a record:
Book = record(title: Title, authors: Authors, publisher: Publisher,
copyright: Copyright)
The library will be defined as: Library = set(Books) and the primary operations are
emptylibrary : -> Library
addbook : Library x Book -> Library
rembook : Library x Title -> Library remove book from library
inlibrary : Library x Title -> Bool
In order to make the system more useful one still want to be able to produce an entity containing all authors and also to be able to represent the library indexed by authors
allauthors : Library -> set(Author) indexbyauthors : Library -> map(Author, set(Book))
Exercise set six (SML): due in written by November 8.
1. Using SML implement the procedure reverse that reverses the first level elements of a list. Define also the procedure deep-reverse that reverses to any level.
Exercise set five (5.1 - 7.1): due in written by October 18.
1. In the problem Towers of Hanoi one needs a procedure that given a list of three lists, identified as 1, 2 and 3: ((list 1) (list 2) (list 3)), gives as result the list obtained when the first item in list m is moved to be the first item in list n. Write the needed procedure (move m n lis).
2. Write a special form that makes it possible to write an if construct in the following way:
(if-then-else predicate
(then expression1)
(if-else expression2))
3. Define a procedure that works on an argument list of numbers and produces a list consisting of elements that are the sum of consecutive elements in the argument list (1+2 3+4...). If the argument list consists of an odd number of elements the last element is discarded. (add-pairs 1 2 3 4 5) should give as result (3 7). (Use the unrestricted lambda)
4. In Section 3.2 we defined (sum-odd-squares m n) using streams implemented as ordinary lists. Make necessary changes so that delayed lists are used instead. (Will not be required in full, do what you can.)
Exercise set four (4.1 - 4.5): due in written by October 11.
1. Write a class that can produce and handle stacks. It should have the attributes: make-stack, empty?, top, print-stack, push, pop.
2. For vectors there exist among others the following procedures: vector?, (make-vector length fill), (vector-length vec), (vector-ref vec k), (vector-set! vec k obj) with their obvious meanings and parameters. The elements of a vector can be any object, and are referenced with k above ranging from 0 to length-1. Define procedures for (vector-add v1 v2), (vector-sub v1 v2) working for vectors v1,v2 having the same length and numerical elements.
3. In many applications, for instance for finding large primes one needs to be able to evaluate a**k (modulo n). Define an efficient procedure that computes a**k (modulo n). Try this for large values of a,k,n. For a stright forward solution you will soon have big problems. How could you improve your solution in order to be able to tackle larger problems? There exist a very efficient solution based on the binary representation of k. Can you find this?
1) Direct : 2**10 (modulo 13) = 1024 (modulo 13) = 10
2) Successive: 2**10 (modulo 13) = (((2**2)**2)**2)*2**2 (modulo 13)
= (3**2)*4 (modulo 13) = 36 (modulo 13) = 10,
because ((2**2)**2) (modulo 13) = 3
3) Very efficient ...
Exercise set three (3.1 - 3.2): due in written by October 4.
1. The procedure reverse reverses the first level elements of a list. Define the procedure deep-reverse that reverses to any level.
2. Define a procedure (permutations ls) that gives all permutations of the elements in the list ls. For instance (permutations '(1 2 3)) should result in (( 1 2 3) ( 1 3 2) (2 1 3) ( 2 3 1) (3 1 2) (3 2 1)) or any permutation of this list. (This may be a little tricky!)
3. Write a procedure that forms the product of numbers in a list. The procedure should exit directly when an element that is not a number is found (because then no numerical result can be produced) or when zero is found (because then the result will be zero if the rest are numbers). (Use call-with-current-continuation.)
Exercise set two (2.5 - 2.9): due in written by September 27.
1. The oldest known nontrivial algorithm is Euclid's Algorithm for computing the greatest common divisor (gcd) of any two positive integers (300 B.C.). The idea of the algorithm is based om the observation that, gcd(a,b)=gcd(b,remainder(a,b)), and that gcd(x,0)=x.
2. Define a function div that divides m by n and displays the result with k decimals. Use the two standard functions quotient and remainder, m/n = (quotient m n) + (remainder m n)/n. (Hint. Display the integral part, the decimal point, and the decimals one by one by recursively displaying the quotient of 10*remainder and counting the decimals displayed.)
In addition to your own testing, try your algorithm for
(div 10 81 10)
(div 60499999499 490050000000 200)
3. Define a function that computes the radical-inverse of a number n in the number system with base b. If the representation of the number n in the number system with base b is (... a2 a1 a0) then phi(b,n) is the number in the same number system who's representation is 0.a0 a1 a2 ... We have: phi(2,0)=0, phi(2,1)=0.5, phi(2,2)=0.25, phi(2,3)=0.75, phi(2,4)=0.125,... Such sequences are called the van der Corput sequences and have the characteristic that phi(b,0),...,phi(b,n) samples the interval (0,1) rather uniformly for any n.
4. Define the general curried function for f(g(x)). Use this to define the sin2(x) function.
Exercise set one (1.1 - 2.4): due in written by September 20. In addition to presenting the requested functions also show the result of testing them by executing with appropriate parameter values.
1. Write a procedure that computes the volume of a cylinder with the height h and the base an circle with radius r. (The volume is always a positive entity.)
2. The roots of a second degree polynomial in one variable ax**2+bx+c, are (-b+ r)/2a and (-b- r)/2a, where r=sqrt(b**2-4ac). Define a procedure that displays the roots based on this definition. What is the value of the procedure?
3. In some cases the function defined in 2. above does not give the correct answer (eg. a=0, r=0, b**2-4ac<0). Write a new procedure that corrects that by giving suitable output in all cases.
4. Complement the procedure power so that it gives the correct result in all cases.
Solution points: