Day 1: Python

Resources (optional)

• Watch this video on the Ceasar cipher.
• If you’re rusty with your Python, visit this site and:
  • the “Learn the Basics” tutorials are helpful
  • the “List Comprehensions” tutorial is too

Lecture Topics

• notes
• logistics
• course overview
• character representation
• rotation ciphers
• using Replit

Part I: Text, bytes, and data

fahrenheit_to_celcius

This function just implements basic math.

is_ascii_lowercase

For this function, you need return whether a given character is an ASCII lowercase character (i.e., in the range ‘a’ to ‘z’).

You might:

• use the ord function or
• use the string.ascii_lowercase constant.

rotate_character

For this function, you’ll implement “character rotation”. That is, for input characters that are ASCII lowercase, you’ll apply the transformation:

• a -> b
• b -> c
• …
• y -> z
• z -> a

a given number of times.

For characters that are not ASCII lowercase, you should return the original character.

You might implement the above transformation

• with if-statements,
• using a dictionary,
• using the string.ascii_lowercase constant,
• or using the ord and chr functions.

bytes_to_ascii

Given a byte sequence, return a string with one character for every byte. If a byte corresponds to a printable ASCII character (see string.printable), then the byte should be represented by that character. If a byte does not correspond to a printable ASCII character, it should be represented by '?'.

ascii_to_bytes

Given a string of ASCII printable characters, return a byte sequence with one byte per character. That byte should be the ASCII number assigned to that character.

You might use:

• str.encode
• ord

Part II: Python lists

square_odd_numbers_loop

Implement this function using a loop and an if statement. You might use: list.append or the + operator for lists and the ** operator for integers.

square_odd_numbers_comprehension

Implement this function using a list comprehension.

transcription

Implement this function using a technique of your choice. If you use a list comprehension, you’ll probably want to also use a dictionary and the str.join function

Part III: Rotation cipher

rotation_cipher_encrypt/rotation_cipher_decrypt

A rotation cipher uses an integer key from 0 to 25 (inclusive) and just rotates every character in the message by the key. Our rotation cipher will only rotate ASCII lowercase characters. Thus, for key 2, the cipher would implement the following mapping:

You should use rotate_character to implement this function.

rotation_attack_1/rotation_attack_2

For these problems, you are given a rotation ciphertext, without the key. Can you recover the original message?

Part IV: Bonus problems

substitution_attack

In a substitution cipher, there is a single mapping from letters to letters, and the ciphertext is just this mapping applied to the plain-text. That is, there is a table that maps letters in the original message to

For example, using the above table,

hi there!

would encrypt to

qy iqkhk!

A rotation cipher is one kind of substitution cipher: one where the mapping is a character rotation.

Substitution ciphers are very insecure. By thinking about single-letter words, short words, and letter frequencies, one can essentially always decode them.

For this problem, decrypt the substitution ciphertext

pkl cmfdylq gvpk nrdnpvprpvfi avcklmn (ltli afqcylh j afqcylh fil) vn
pkjp pklu aji'p akjiel pkl rislmyuvie wmlxrliau fw ylpplmn vi pkl
yjierjel. pkrn, ji jijyunp aji rnrjyyu mlaftlm pkl qlnnjel. pkvn pjno
vn ltli ljnvlm vw gfms dfrisjmvln jml ifp akjiels. wfm vinpjial, pklml
jml ifp tlmu qjiu nkfmp gfmsn: pkl fiyu fil-ylpplm gfmsn jml v jis j.

and return the message as a string in the substitution_attack function.

collatz_step/collatz_length/max_collatz

Define a function $f$ from positive integers to positive integers that divides even numbers by 2, and for odd numbers multiplies by three and then adds one.

Thus

$$ f(x) = \begin{cases} x/2 &x \text{ is even}\\ 3x+1 &\text{otherwise} \end{cases} $$

So, $f(2) = 1$, $f(3) = 10$ and $f(4) = 2$. The “Collatz conjecture” is that apply $f$ enough times to any number yields 1 eventually. Try it!

For this problem, implement:

• collatz_step: an implementation of $f$
• collatz_length: computes the number of Collatz steps to 1, given a starting point
• max_collatz: the maximum Collatz length for any value in ${1, \ldots, n}$.

For the last function, try to find a faster algorithm than just independently computing collatz_length for each starting value.

us_change

Write a function which, given a number of cents between 0 and 99, computes the minimal set of US coins needed to make that many cents.

hanoi

In the “Towers of Hanoi” puzzle, there are three posts, A, B, and C.

At the beginning there are n (for example, 2) disks on the first post. The disks are stacked in order of size, with the smallest disk on top.

The challenge is to relocate the whole stack from post A to post C

• only moving one disk at a time and
• never placing a bigger disk on a smaller disk.

For example, here is how to solve the puzzle for n = 2:

For this problem, write a function that prints instructions for how to solve the puzzle. The function, hanoi(n, start, end) takes three arguments:

• n: the number of disks
• start: which post ("A", "B", or "C") the disks are initially on
• end: which post ("A", "B", or "C") the disks need to be moved to

Your program should print output like this in the n=2 case, moving from A to C:

Move a disk from A to B Move a disk from A to C Move a disk from B to C

Hint I: use recursion

arbitrary_change

This the same problem as us_coins, but now the function is given a list of coins instead of using the standard US coins ([1, 5, 10, 25]).

Your solution to this problem may not be very efficient: that’s fine!

what_is_is

Notice this weird behavior in the following Python shell session:

>>> x = 2
>>> x == 2
True
>>> x is 2
True
>>> x = 2000
>>> x == 2000
True
>>> x is 2000
False

For which x does is give True? For which x does is give False? What does is do? Why do think this happens? Put your answers in a comment in the what_is_is function?