CSC 241

We finished talking about loop patterns (5.3), started on the while loop (5.4, 5.5). Next week, we will complete while loops (5.6) and talk about dictionaries (6.1), tuples, and sets (6.2) and character encodings (6.3).

- 5/27 is memorial day, so there is no class meeting
- there will be a lab on 5/28.

**Submission**: The homework is due by midnight (I will not accept late homeworks).
You can submit your homework through d2l
into the drop-box for this homework.
Please prepare your homework as a *single file* containing all answers
(e.g. doc, docx, or pdf,
not a zip file).

When submitting programs, include the programs, together with screenshots of test-runs of your program (make sure screenshots are sized so the text is legible; resize and/or crop the images).

1. (Reading Assignment) Read Sections 5.3-5.5 of the textbook.

2. (Pseudo-Sudoku, 15pt) We are interested in a generalized version of Sudoku which is placed on an nxn board. There is only one rule: in each row and each column every number from 1 to n occurs exactly once. E.g. below is a 3x3 and a 4x4 square (but n could be any number even larger than 9).

1 | 3 | 2 |

2 | 1 | 3 |

3 | 2 | 1 |

1 | 3 | 2 | 4 |

3 | 2 | 4 | 1 |

4 | 1 | 3 | 2 |

2 | 4 | 1 | 3 |

a) [5pt] Write a function good(lst) which as inputs takes a 1-dimensional
list and which returns True if lst contains all the digits from 1 to
len(lst) inclusive. *Note:* you are not allowed to use set() or
similar tricks. A simple loop will do.

b) [10pt] Write a function ps(lst) which as input takes a 2-dimensional list representing an nxn pseudo-sudoku square, and which verifies that each row and each column contains each number between 1 and n exactly once. You can assume that the list lst is 2-dimensional and each row has the same number of entries as there are rows.

*Hint 1*: if you cannot get part a) to work correctly, you can use
the following implementation of good for use in part b).

*Hint 2*: start with the magic square example we saw in class. First check the
rows. *Hint 3*: When checking the columns, remember that you have the good()
function, so build each column as a list for checking.

3. (While Loop, 5pt) Write a function **acronym(s)**
that returns a string consisting of all the upper-case letters in s. You are
not allowed to use a for loop (we've done that), use a while loop instead.

4. (While Loop, 5pt) You know that floating point values in
Python (differently from integers) have limited precision. You are wondering
how small they can get before they become (effectively) zero. Write a
program **infinitesimal()** which evaluates 2**(-n) for
increasing values of n, until it finds one for which 2**(-n) equals zero (in
Python; mathematically, that's nonsense, of course, unless you believe in
infinitesimals). Return that n. The following screenshot shows you what that
n is on my (and probably your) Python installation. You cannot assume that
you know that number, you need to write a program to find it that keeps
working, even if the precision settings change.

*Hint*: you may be inclined to calculate 2**(-n) step
by step by starting with 1 and dividing by 2 in each step until you hit 0.
While that's computationally better than calculating 2**(-n) in each step as
n increases, it leads to a slightly different result. Try 1/(2**1075) versus
(1/2)**1075; mathematically they are the same, but in floating point
arithmetic they are not. There is a slim chance that your final n will
differ because your installation used different settings for floating point
precision, but that really shouldn't happen.

5. (While Loop, 10pt) Implement a function **bid()**
that allows users to bid on an item. Users can enter a number. If that
number is at least 2 more than the previous number, the new bid is accepted,
and becomes the current bid. Otherwise, the current bid remains the same.
Initially, the bid is 0. Just hitting return (resulting in the empty
string), leaves the bidding simulation. *Note*: this is simplified in
that we do not keep track of secret bids. Typically, when the current bid is
$10 and there is a $2 increment, then bidding $15 would increase the bid to
$12 with a secret bid of $15. You do **not** have to implement
this version.

Marcus Schaefer

Last updated: May 22nd, 2019.