Homework 7 (due 5/28)
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).

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.