This chapter is about infinite sets and some challenges in proving things about them. There has been a truly astonishing outcome of studying infinite sets. Their study led to the discovery of fundamental, logical limits on what computers can possibly do. For example, in a later section, they use reasoning …

Topics: Recursion: iteration vs. recursion, inductive reasoning Recursion is review for me. I like the example she gave with the student asking professor, TA, and LA to regrade. Big idea: “Earlier” function calls are waiting on results before completing. Went over some more examples of recursion. When to use recursion …

Recursive data - define something in terms of simpler version of the same thing. Recursive data types play a central role in programming, and induction is really all about them. Recursive data types are specified by recursive definitions, which say how to construct new data elements from previous ones. Along with …

Finished the problem set in about an hour. It was a good exercise. Here is my solution along with test case results: My solution: # Purpose: Check for similarity between two texts by comparing different kinds of word statistics. import string import math ### DO NOT MODIFY THIS FUNCTION def load_file(filename …

Generative Recursion Module Generative recursion is in many ways similar to structural recursion: a function calls itself recursively (or several functions call themselves in mutual recursion). For the recursion to terminate, each recursive call must receive an argument that is in some way "closer to the base case". That is …

Topics: Dictionaries: keys, values, mutability, iteration over a dict, examples This is review for me, I am familiar with dictionaries. I guess one new thing I learned is that dictionary keys must be immutable or technically hash-able objects. Although in practice this is obvious.

Topics: Exceptions, assertions Introduced to the try/except code blocks, with some examples. Also introduced to assertions, as a way to program defensively. I sort of forgot about assertions so this is good review. I will look to use them in my future code. They are good for enforcing invariants …

State machines are a simple, abstract model of step-by-step processes. One of the most important uses of induction in computer science involves proving one or more desirable properties continues to hold at every step in a process. A property that is preserved through a series of operations or steps is …

Topics: More Functions as Objects, Keyword Arguments, Default Arguments, Debugging: glass box/black box testing, examples List comprehensions are review for me. Default parameters are also review. Functions can return another function. Why bother returning functions? Code can be rewritten without returning function objects Good software design Embracing ideas of …

Topics: Aliasing and cloning Going over some operations on lists, including .clear(), .pop(), del() and .remove(). Iterating over a list as you are mutating the list can lead to unpredictable behavior. Takeaway here is to be careful when mutating a list while iterating over it. Consider using a copy. = sign …