All CSE1729 Problem Set Solutions PDF

Preview

Summary

Download All CSE1729 Problem Set Solutions PDF

Description

CSE1729 - Introduction to Programming

January 30, 2018 Problem Set 1 Solutions

Honor code. As a student in 1729, you have pledged to uphold the 1729 honor code. Specifically, you have pledged that any work you hand in for this assignment must represent your individual intellectual effort.

1. Re-write the following arithmetic expressions as Scheme expressions. (a) (22 + 42) × (54 × 99). (* (+ 22 42) (* 54 99)) (b) ((22 + 42) × 54) × 99. (* (* (+ 22 42) 54) 99) (c) 64 × 102 + 16 × (44/22). (+ (* 64 102) (* 16 (/ 44 22))) (d) Of course, the first two expressions evaluate to the same number. In what sense are they different? How is this reflected in the Scheme expression? The order of operations is different. Observe how this changes the parenthetical structure of the Scheme expression. (e) In a conventional unparenthesized (infix) arithmetic expression, like 3 + 4 ∗ 5, we rely on a convention to determine which operation we apply first (the convention is typically called the “rules of precedence” or “order of operations”). Are rules of precedence necessary for evaluating arithmetic expressions in Scheme? Explain your answer. No. Any such arithmetic expression determines unambiguously which operator to apply first; the same can be said of all subexpressions! 2. The company HP designed several families of scientific calculators which exploited a nice fact about postfix notation for arithmetic expressions: parentheses are unnecessary to uniquely define the expression. The architecture of these calculators consisted of a simple memory structure called a “stack,” which you may think of as a sequence of numbers which we will denote (n1 , . . . , nk ). Thus (3, 6, 11) and (.001, 0, 100000, 45) are two different stacks; the first contains three numbers; the second contains four numbers. The stack structure is easy to reason about because there are only two different “operations” that are permitted on a stack: push, which adds a new element to the front of the stack, and pop , which removes the first element from the stack. In general, if the push operation is carried out with a number n and a stack (n1 , . . . , nk ), the result is the stack (n, n1 , . . . , nk ). On the other hand, if the pop operation is carried out on the stack (n1 , . . . , nk ), the result is the stack (n2 , . . . , nk ). Note that in order to carry out a push operation, one needs a new element to push onto the stack; note, also, that the pop operation only makes sense if the stack contains at least one number.

1

The HP calculators used this stack architecture to provide the familiar functions of a calculator in the following specific fashion. At all times the calculator maintained a stack of numbers, and there were two ways that the user could interact with the stack: (a) the user could push a new number onto the stack, or (b) the user could apply an arithmetic function (like ∗, /, +, and −) which would pop two elements from the stack, apply the operation to the two elements, and push the result back on to the stack. The calculator typically showed you the first two elements of the stack, so you could read out the result of your computation. For example, a user who wished to compute 17 × (34 + 20) would push the number 17 onto the stack, push the number 34 onto the stack, push the number 20 onto the stack, apply the + operator, and then apply the × operator. A diagram of this computation is shown below, which indicates the contents of the stack at various times (written vertically instead of horizontally, as above): ··· ··· ···

17

17 ··· ···

34

34 17 ···

+

54 17 ···

×

918 ··· ···

20

20 34 17

For convenience, we can denote this sequence of operations on the calculator as [17][34][20]+×. (So a number in brackets indicates that the number is pushed on to the stack.) Note that, in general, the order of the operands for operations such as − and / is important (e.g., 3 − 1 is different from 1 − 3). The convention on the HP calculators is that the first of the two values popped off the stack is the first argument; thus the − operator applied to the stack (1, 2, . . .) will result in the stack (−1, . . .). Give the sequence of operations that would compute the expressions of problem 1 above. Be sure that operations are applied with the same groupings as indicated in the original expressions. (a) Give the sequence of operations to compute the expression (22 + 42) × (54 × 99). [22][42] + [54][99] × ×

(b) Give the sequence of operations to compute the expression ((22 + 42) × 54) × 99. [22][42] + [54] × [99]×

(c) Give the sequence of operations to compute the expression 64 × 102 + 16 × (44/22). [64][102] × [16] × [44][22]/ × + 3. Write Scheme definitions for the functions below. Use the interpreter to try them out on a couple of test cases to check that they work. (a) inc, the function inc(x) = x+1. Once you have defined inc show how to use it to define the function inc2(x) = x + 2. (So, your definition of inc2 should not use the the function + but rather use the function inc.) (define (inc x) (+ x 1)) (define (inc2 x) (inc1 (inc1 x)) (b) square, the function square(x) = x2 . As above, use the function square to define the function fourth(x) = x4 . (define (square x) (* x x)) (define (fourth x) (square (square x))) 2

(c) p, the polynomial function p(x) = (x2 + 1)4 (16x4 + 22)2 . (Hint: Of course it is possible to expand (x2 + 1)4 (16x4 + 22)2 as a polynomial of degree 16 and write a Scheme function to compute this by brute force. You can avoid all this computation by defining p in stages as you did above.) (define (p x) (* (fourth (+ 1 (square x))) (square (+ 22 (* 16 (fourth x)))))) (d) Using the function fourth, write the function sixteenth(x) = x16 . Similarly, using the functions fourth and sixteenth, write the function sixty-fourth(x) = x64 . Recall that 64 = 16 × 4. (You may want to test this on an input relatively close to 1, such as 1.01.) (define (sixteenth x) (fourth (fourth x))) (define (sixty-fourth x) (fourth (sixteenth x))) (e) Reflect on your definition of sixty-fourth above. What would have been the difficulty of defining this merely in terms of ∗? Without abstraction (that is, using a subordinate function), this would have required us to write 64 occurrences of the variable x. Remark Scheme provides built-in support for exponentiation (via the expt function, which is defined so that (expt x y) yields xy ). For the exercises above, however, please construct the functions x 7→ xk using only ∗ and function application. 4. Write Scheme definitions for the functions below. Use the interpreter to try them out on a couple of test cases to check that they work. (a) The normal distribution is the single most important distribution is all of statistics. In general, it has a bell shape, as shown below:

0.3

0.2

0.1

−4

2

−2

4

The normal distribution with standard deviation σ at the point x is given by the function x2 1 e− 2σ2 . N (x, σ) = √ 2 2σ π

Write a Scheme function normal so that (normal x sig) returns N (x, sig). You may use the built-in functions sqrt and exp which compute the square root and ex functions, respectively. For simplicity, you may approximate π by the number 3.142. 3

(define (square x) (* x x)) (define (normal x sig) (* (/ 1 (sqrt (* 2 3.142 (square sig)))) (exp (* -1 (/ (square x) (* 2 (square sig))))))) (b) The Fibonacci spiral, shown below, is a rather remarkable mathematical object which mysteriously appears in a number of places in biology. It is described by the polar equation r(θ) = φθ·(2/π) . Here φ is a constant called the golden ratio which you may approximate by 1.618. Likewise π is the familiar constant which you may approximate by 3.142. In order to carry out the exponentiation, please use the built-in function expt defined so that (expt x y) returns xy . Using these, write a Scheme function fspiral so that (fspiral theta) retuns the value r(theta). (define (fspiral theta) (expt 1.618 (* theta (/ 2 3.142))))

(c) The classical exponential (or “Malthusian”) population growth model predicts the size of a population at a future time based on its current size. Specifically, if the population has size P0 at time 0, the model predicts that the size of the population at time t will be P0 · 2αt , where α is a parameter of the process. Write a scheme function malth so that (malth t p a) returns the value p · 2at . (define (malth t p a) (* p (expt 2 (* t a)))) You can see the rough behavior of the model below. 20

15

10

5

0.5

1 4

1.5

2

2.5

3

(d) A more sophisticated population model can reflect a penalty term that attenuates growth when the population becomes large. (This can occur, for example, if a population has a food source of constrained size: when the population is small, food is relatively plentiful and the population grows; when the population is large, there is intense competition for food and the population does not grow as quickly.) A standard model to capture this is called the single species model and depends on three parameters: the initial population size P0 , a “stable population size” P∞ , and a rate α > 0. Then, as a function of time t, the population has size P∞ · P0 . P (t) = P0 + (P∞ − P0 )e−αt Write a Scheme function singlespecies so that (singlespecies Pi Ps alpha t) returns the value P (t) where P0 = Pi, P∞ = Ps and α = alpha. (define (singlespecies Pi Ps alpha t) (/ (* Pi Ps) (+ Pi (* (- Ps Pi) (exp (* -1 alpha t)))))) To visualize the behavior of such a model, the graph below shows the setting when P0 = 10, P∞ = 1000, and α = 1/25.

800 600 400 200

50

100

5

150

200

250

CSE1729 - Introduction to Programming

February 7, 2018 Problem Set 2 Solutions

Honor code. As a student in 1729, you have pledged to uphold the 1729 honor code. Specifically, you have pledged that any work you hand in for this assignment must represent your individual intellectual effort.

1. Consider the following function

  x − 2π if x > 2π, f (x) = sin(x) if 0 ≤ x ≤ 2π,   x if x < 0.

Define a function piecewise so that (piecewise x) returns f (x). In your code, please simply approximate π with the decimal 3.142. Use the built-in function (sin x) which returns sin(x). To visualize the function, the plot below shows the values in a region around zero.

1

2

−2

4

6

8

−1

−2 (define (piecewise x) (cond ((¡ x 0) x) ((¡ x (* 2 3.142)) (sin x)) (else (- x (* 2 3.142))))) 2. Recall from class the definition of number-sum, which computes the sum of the first n numbers: (define (number-sum n) (if (= n 0) 0 (+ n (number-sum (- n 1))))) (a) Adapt the function so that it computes the sum of the first n positive squares. Call your new function square-sum. When evaluated at 4, your function should return the sum of the first 4 positive perfect squares: 1 + 4 + 9 + 16 = 30. An immediate adaptation yields: 1

(define (square-sum n) (if (= n 0) 0 (+ (* n n) (square-sum (- n 1))))) (b) Adapt the function so that it computes the sum of the first n even numbers. Call your function even-number-sum. When evaluated at 4, your function should return the sum of the first 4 even numbers: 2 + 4 + 6 + 8 = 20. (Incidentally, evaluate your function at 1, 2, 3, 4, 5, 6, and 7. Does this sequence of numbers look familiar? Responding to this is optional, but you will learn something interesting if you figure out the answer.) The kth even number is (2k). Thus we have: (define (even-number-sum n) (if (= n 0) 0 (+ (* 2 n) (even-number-sum (- n 1))))) You will notice that the sum of the first n even numbers is exactly n(n + 1). 3. Write a recursive function that, given a positive integer k, returns the product      1 1 1 . ··· 1 − 1− 1− k 3 2 | {z } k−1

Call your function h-product.

(Experiment with the results for some various values of k; this might suggest a simple non-recursive way to formulate this function. Please hand-in the natural recursive version, though.) (define (h-product n) (if (= n 1) 1 (* (- 1 (/ 1 n)) (h-product (- n 1))))) With a little experimentation, you’ll discover that this product is always equal to 1/n. 4. Consider the problem of determining how many divisors a positive integer has. For example: • The number 4 has three divisors: 1, 2, and 4; • The number 5 has two divisors: 1 and 5; • The number 10 has four divisors: 1, 2, 5, and 10. In this problem you will write a Scheme function (divisors n) that computes the number of divisors of a given number n. The first tool you will need is a way to figure out if a given whole number ℓ divides another whole number n evenly. We provide the code for this, which you can just use as-is in your solution (it involves a function that we haven’t talked about in class yet): (define (divides a b) (= 0 (modulo b a))) Once you have defined this function, (divides a b) will be #t if a divides b evenly, and #f if not. For example:

2

> (divides 2 4) #t > (divides 3 5) #f > (divides 6 3) #f At first glance, the problem of defining (divisors n) appears a little challenging, because it’s not at all obvious how to express (divisors n) in terms of, for example, (divisors (- n 1)); in particular, it’s not really clear how to express this function recursively. To solve the problem, you need to introduce some new structure! Here’s the idea. Focus, instead, on the function (divisors-upto n k) which computes the number of divisors n has between 1 and k (so it computes the number of divisors of n upto the value k). Now you will find that there is a straightforward way to compute (divisors-upto n k) in terms of (divisors-upto n (- k 1)). Specifically, notice that   0 if k = 0;     0 if n = 0;  (divisors-upto n k) = 1 if k = 1;    1 + (divisors-upto n (- k 1)) if k divides n;   (divisors-upto n (- k 1)) if k does not divide n.

Write the Scheme code for the function divisors-upto; notice then that you can define (define (divisors n) (divisors-upto n n))

In this case, we call divisors-upto a “helper” function. What did it do? It let us “re-structure” the problem we wish to solve in such a way that we can recursively decompose it. (define (divides a b) (= 0 (modulo b a))) (define (divisors-upto n k) (cond ((= k 1) 1) ((divides k n) (+ 1 (divisors-upto n (- k 1)))) (else (divisors-upto n (- k 1))))) (define (divisors n) (divisors-upto n n)) 5. Write a function—called pseries—which, given a positive integer k, returns the sum of the first k terms of the infinite series: 4 4 4 4 4 − + − + − ··· . 7 9 5 1 3 (Thus, when called with the number 1 your function should return 4.) Use your function to sum the first 100 terms of this series. Observe that signs alternate in this series; one easy way to implement an alternating sign is to use the function (−1)ℓ , which is 1 when ℓ is even, and −1 when ℓ is odd. You may wish to use the built-in Scheme function (expt x t), which returns xk (and so provides a straightforward way to compute (−1)ℓ ). Depending on how you wrote your code, Scheme may have produced exact output of the form a/b. To coerce Scheme to give you an approximation in decimal form, change the constant “4” in your code to “4.0”. Now compute the sum of the first 100,000 terms. Does this number look (roughly) familiar?

3

(define (pseries k) (if (= k 0) 0.0 (+ (* -1 (expt -1 k) (/ 4 (- (* 2 k) 1))) (pseries (- k 1))))) This series converges (rather slowly) to π . 6. Recall from high-school trigonometry the sin function: If T is a right triangle whose hypotenuese has length 1 and interior angles x and π/2 − x, sin(x) denotes the length of the edge opposite to the angle x (here x is measured in radians). You won’t need any fancy trigonometry to solve this problem.

1

sin x

cos x

angle x

Figure 1: A right triangle.

It is a remarkable fact that for all real x, sin x = x −

x3 x5 x7 + ··· + − 7! 3! 5!

Write a Scheme function new-sin so that (new-sin x n) returns the sum of the first (n + 1) terms of this power series evaluated at x. Specifically, (new-sin x 3), should return x−

x3 x5 x7 + − 7! 3! 5!

and, in general, (new-sin x n) should return n X

(−1)k

k=0

x2k+1 . (2k + 1)!

You may use the built-in function (expt x k), which returns xk . It might make sense, also, to define factorial as a separate function for use inside your new-sin function. (Aesthetic hint: Note that the value 2k is used several times in the definition of the kth term of this sum. Perhaps you can use a let statement to avoid computing this quantity more than once?) One solution is the following: (define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1))))) (define (new-sin x k) (if (= k 0) x (let ((p (+ (* 2 k) 1))) 4

(+ (* (expt -1 k) (expt x p) (/ 1 (factorial p))) (new-sin x (- k 1)))))) 7. (cf. SICP problem 1.4) Suppose we designed a new if function as follows: (define (new-if predicate then-clause else-clause) (if predicate then-clause else-clause)) Check that new-if works as you might expect by evaluating: > (new-if (= 0 0) 4 5) 4 > (new-if (= 0 1) 4 5) 5 Recall now the factorial function that we defined and discussed in class: (define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1))) ) ) How does factorial behave if you replace the usage of if with new-if? Explain. We discussed this at length in class: usage of new-if will result in a factorial function that never terminates.

5

CSE1729 - Introduction to Programming

February 13, 2018 Problem Set 3 Solutions

Remark 1. The Racket interpreter can maintain two different representations of numeric quantities: fractions and decimal representations. While fractions always represent exact numeric quantities, decimal expansions maintain a finite number of digits to the right of the decimal point. The Racket interpreter will attempt to infer, when dealing with numbers, whether to maintain them as fractions or as decimal expansions. For example

> (/ 1 2) 1/2 > (/ 1 2.0) 0.5 > (+ (/ 1 2) (/ 1 3) (/ 1 6)) 1 > (+ (/ 1 2) (/ 1 3.0)) 0.8333333333333333 > In general, the interpreter will maintain exact expressions for numeric quantities “as long as possible,” expressing them as fractions. You can instruct the interpreter that a number is to be treated as a decimal by including a decimal point: thus 1 is treated as an exact numeric quantity, whereas 1.0 is treated as a decimal expansion. The interpreter knows how to convert fractions to decimals (you can configure the number of digits of accuracy you wish), but will never convert decimals back to fractions (or integers). (So you know, this process is called type-casting.) Arithmetic expressions like (+ 1 1.0) pose a problem because the two arguments are of different “types.” In this case, the interpreter will transform the exact argument ( 1) into a decimal value, and then proceed as though all arguments were decimals (returning a decimal result). Other arithmetic operations are treated similarly. 1 1 1 1. Define H n = 1 + 2 + . . . + n ; these are referred to as the harmonic numbers. A remarkable fact about these numbers is that as n increases, they turn out to be very close toln n. (ln n is the natural logarithm of n.) In particular, as n increases the difference |H n − ln n| converges to a constant (Euler’s constant).

(a) Give a SCHEME function, called harmonic so that (harmonic n) returns H n . (b) Using your function from the previous part, give an estimate of Euler’s constant. Specifically, write a SCHEME function Eulerest so that (Eulerest n) returns the absolute value of the difference between H n and ln n. (You may wish t...