Assignment 1, due Aug 29

Solutions

Part of the homework for CS:2630, Fall 2019
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

A test of your understanding of the prerequisites: Consider this recursive integer function. All operators here are integer operations. This is an informal expression of the function, that is, pseudocode; it is not coded in a real programming language:
```
function f( i, j )
   if i = 0
      return 0
   else
      return f( j, i-1 ) + j
```
a) What is the value of f(1,1)? (0.2 point)

f(1,1) = f(1,0)+1 = f(0,0)+0+1 = 0+0+1 = 1

b) What is the value of f(2,3)? (0.2 point)

f(2,3) = f(3,1)+3 = f(1,2)+1+3 = f(2,0)+2+1+3 = f(0,1)+0+2+1+3 = 0+0+2+1+3 = 6

c) What is the value of f(4,5)? (0.2 point)

f(4,5) = f(5,3)+5 = f(3,4)+3+5 = f(4,2)+4+3+5 = f(2,3)+2+4+3+5
phiew, but fortunately, we solved f(2,3) above, so
f(4,5) = 6+2+4+3+5 = 20

d) What is the value of f(6,7)? (0.2 point)

f(6,7) = f(7,5)+7 = f(5,6)+5+7 = f(6,4)+6+5+7 = f(4,5)+4+6+5+7
again fortunately, we already solved f(4,5) above, so
f(4,5) = 20+4+6+5+7 = 42

e) Give a short (20 words suffice) intuitive description of what this function does, not how it does it. (Hint: Ignore the code, look at your answers to parts a to e.) (0.2 point)

f(i,j) returns the product of i times j for all non-negative integers i and j.
A test of your understanding of the prerequisites: Here is another pseudocode fragment:
```
operation o(x) -- x may not be null
    if (x.next ≠ null) x.next.back = x.back
    if (x.back ≠ null) x.back.next = x.next
```
A Question: This code performs an elementary operation on a common data structure. Name that operaton and name the data structure. (A 5 to 10 word answer will suffice.) (0.5 points)

Deletion from a doubly-linked list. (where null pointers mark the ends of the list.)
A problem based on Chapter 2: Give the 7-bit ASCII representation of the text "Aug. 29, 19" Don't include the quotation marks. Give your result as a column of binary numbers, one per character. (0.5 points)
```
1000001  A
1110101  u
1100111  g
0101110  .
0100000
0110010  2
0111001  9
0101100  ,
0100000
0110001  1
0111001  9
```
Background: Take the due date, 08/19/19, take out the slashes and interpret it as the decimal number 81919.
a) Convert this to binary using the pen and paper method shown in Chapter 2. Show your work! (0.3 points)
```
81919
40959 1
20479 1
10239 1
 5119 1
 2559 1
 1279 1
  639 1
  319 1
  159 1
   79 1
   39 1
   19 1
    9 1
    4 1
    2 0
    1 0
    0 1 10011111111111111
```
b) Convert your answer from part A to hexadecimal. (0.3 points)
```
13FFF
```
You can check your work in the above conversion problems by using any binary-hex-decimal conversion calculator (there are lots of them on the web), but you will be expected to be able to do such conversions by hand.
Background: Follow the instructions in the Getting Started handout for running the 2630 install script. Help will be provided in discussion section for those who have not succeeded in this by then. Write down what the script outputs for you. (0.4 points)

You will get something resembling this:
```
Thu 29 Aug 2019 10:17:33 AM CDT: HawkID added CS:2630 commands
```
Except that your HawkID will be substituted for the literal text HawkID and the time and date will be when you did it.