Exercise 4.1, problem 5a for i := 1 to 123 do for j := 1 to i do print i * j
a) How many times is the print statement of the third line executed?

Since we have to count iterations starting from one until 123, the first count would be 1 then 3 then 6 and so forth. The segment can be translated to (n)(n+1)/2 where 123 would be (n). (123)(123 + 1)/2
The statement is executed 7626 times.

Exercise 4.2, problem 18a
a) How many permutations of 1, 2, 3 have k ascents, for k = 0, 1, 2?
Ascent can be determined by simply looking at its numbers. In the case of 123, 3 > 2 and 2 >1 so there are 2 ascents.
123 = 2 321 = 0 231 = 1 213 = 1 132 = 1 312 = 1 k = 0 1 k = 1 4 k = 2 1

Exercise 4.3, problem 22a
Solve each problem (if possible), and then convert the results to base 10 to check your answers. Watch for any overflow errors. 8 4 2 1 0101 5
+ 0001 1 0110 6

Exercise 4.4, problem 1a
1. For each of the following pairs a, b ∈ Z+, determine gcd (a, b) and express it as a linear combination of a, b.
a) 231, 1820 1820 = 7 (231) + 203 0 < 203 < 231 231 = 1 (203) + 28 0 < 203 < 28 203 = 7 (28) + 7 0 < 28 < 7 28 = 4 (7) + 0 7 gcd(1820, 231) = 7

7 = 203 – 7 (28) 203 – 7 (231 – 203) 8 (203) – 7 (231) 8 (1820 – 7 (231)) – 7(231) 8 (1820) – 63 (231) Exercise 5.1, problem 4 For which sets A, B is it true that A X B = B X A? Sets A, B will not be equal to one another if numbers within the sets are different. An example is
Set A = 5, 3, 2 Set B = 4, 5 ,7
In this case A ≠ B.
Sets A, B will be equal if both have the same numbers, order in which they are presented is not important.
Set A = 5, 2, 4 Set B = 2, 5 , 4
This will make equal sets A = B
Also if there is a 0 in any of the sets.
Set A = 0 , 4 Set B = 5, 4
(0) X (20) = 0 A = B, A or B = 0

Exercise 5.2, problem 4
4. If there are 2187 functions f : A→B and |B| = 3, what is |A|?
3|A|=2187 = 3|7|= 2187
A = 7

Exercise 5.3, problem 1a
1. Give an example of finite sets A and B with |A|, |B| ≥ 4 and a function f : A→B such that (a) f is neither one-to-one nor onto; (b) f is one-to-one but not onto; (c) f is onto but not one-to-one; (d) f is onto and one-to-one.
Consider A = {1,2,3,4,} B = {a,b,c,d,e} f = {(1, a), (2,a), (3,b), (4, c)}

Exercise 5.4, problem 13a
The list has 5 elements. Thus it has a degree of 5.

Exercise 5.7, problem 1a
Question A is a linear equation, so the answer must be O(n).

Exercise 5.8, problem 5a
8 − 10x + 7x2 − 2x3 + 3x4 + 12x5
The following 5th degree polynomial has five additions.
The pseudocode given has 2 multiplications for the entire loop execution, thus the amount of multiplications can be translated to 2n where additions were simply n.
Thus there are 10 multiplications.