Lecture calendar

Virtual lecture room on Zoom. Passcode: 101877

Notes will sometimes be posted in advance, but all notes are subject to change.

                  LecturesReading and Materials
Week 1

Lecture 1: Intro slides, Why ESC180 is the Most Important Course You'll Take, Python expressions and variables, a very simple Python program, Conditionals: printing an absolute number, printing different messages depending on the number. Youtube videos on tracing: Part 1, Part 2, Part 3.

Lecture 2: Intro slides, part 2, the secret number magic trick + comments, more on writing conditional: the Jack Sparrow example (the YouTube clip), intro to the quadratic equation solver. Zoom Recording.

Suggested readings for the next couple of lectures: Downey chapters 1-2 and/or Gries chapters 1-2. Note: you're only responsible for the material in lecture. However, some people learn best by reading, which is why I'm listing readings.

Week 2

Lecture 1: a note on printing multiple values, string literals in Python, ints and floats, more on finite precision, in the context of the quadratic equation solver. Zoom Recording

Lecture 2: Functions; global and local variables. Multiple assignments and swapping variables. Zoom recording

Lecture 3: Summary: passing data to and from functions. Swapping variables. Variable naming conventions. Zoom recording.

Optional aside for people who like irrational numbers: you cannot store most irrational numbers in computers: there is just not enough space to store an infinite number of digits. So what can you do? You can store a string like "pi", and hope that's interpreted in a sensible way. Of course, most irrational numbers aren't named! You can also store Python code that generates the irrational number in question to arbitrary precision (coming up in a few weeks: code to compute numbers like sqrt(2) and π). But note that there are uncountably many irrational numbers, but only countably many Python programs. That means that you still can't hope to represent almost any irrational numbers.

The distinction between "parameters" and "arguments" is perhaps too thin, but here's an explanation. A lot of the time, the terms are used interchangeably.

Suggested readings for the next couple of lectures: Gries ch. 3 and 5, Downey ch. 3-4, Downey 5.1-5.7, Downey 11.6 for global variables.

See these lecture notes on Booleans and if-statements and these lecture notes on locals/globals. Also see this tutorial.

Just for fun: PEP 8, the official Python style guide,

Just for fun: George Boole is the person after whom Boolean Algebra is named.

CodingBat exercises: Warmup-1

Week 3

Lecture 1: Boolean functions and Boolean algebra. has_roots(). Converting Booleans. Flow control with return statements. Zoom recording

Lecture 2: For-loops and computing powers, while-loops and computing log10, Primality testing with for-loops. Integer division. Zoom recording.

Lecture 3: More assignment operators. More on range. More on primality testing. Swapping variable values without temporary storage. Factorials and trailing zeros. Converting for loops into while loops. Zoom recording.

Videos: Computing log10 using while-loops, primality testing, tracing is_prime, Converting for-loops into while-loops

For completeness: Python operator precedence.

Just for fun, about computing exponents: how to compute b^x when x is not an integer? This is generally done by computing power series rather than repeatdly multiplying b by itself. See Lab#3 for an example of a computation of a sum of a power series.

Interview question: compute the number of trailing zeros in n! efficiently for large n.

CodingBat exercises: Logic-1, Logic-2,

Week 4

Lecture 1: Testing and the main block: login.py, test_login.py (Zoom recording). Lists I, Lists II, Lists III. Zoom recordings: Part 1, Part 2, Part 3, Part 4.

Lecture 2: Lists and range, slicing lists, slicing with for and while, extend, sort. Zoom recording.

Lecture 3: extend, sort (cont'd). Computing pi with loops and random(). Zoom recording

Reading: Downey Ch. 7, Gries Ch. 9

CodingBat exercises: List-1, List-2

Week 5 Lecture 1: infinite loops, break and continue. The Missing K problem. Nested loops. Zoom recording

Lecture 2: Nested loops and nested lists; odds and ends; Zoom recording

Lecture 3: intro to the Python memory model. Zoom recording.

Interview question: solve the missing K problem efficiently

Reading: continue reading Downey Ch. 7, Gries Ch. 9

Codingbat exercises: String-1, String-2

All of the Python string methods

Week 6

Lecture 1: intro to the Python memory model, continued. Recording

Lecture

Memory model exercises (solutions, Exercise C video)

Week 7

Lecture 1: Recording (code)

Lecture 2: Recording (reverse_str, is_anagram, return a data packet uniformly at random

Lecture 3: Recording (detecting a sequence of n "a"s + b

Week 8

Lecture 1: Recording (intro to dictionaries, deleting elements of lists while iterating over them, tuples, tuples as keys, inverting dictionaries)

Lecture 2: Recording (sparse matrices, files)

Lecture 3: Recording (binary search)

Week 9

Lecture 1: Recording (longest run, timing functions, intro to plotting runtime

Lecture 2: Recording (selection sort, bucket sort/counting sort first try)

Lecture 3: Recording (counting sort, bozosort, complexity isn't straightforward, complexity of arithmetic operations on integers)

Week 10

Lecture 1: Recording (factorial using recursion, is_even using recursion, intro to Race to 21)

Lecture 2: Recording (Race to 21, sum_list, sum_list2)

Lecture 3: Recording (complexity of sum_list2, fact_while, fact_iter, fact_rec, computing powers with recursion)

Notes: sum_list, complexity of factorial, complexity of exponentiation, fast exponentiation, converting iterative functions to recursive

Week 11

Lecture 1: Recording (various flavours of fib()). Complexity of fib(), deep copy

Lecture 2: Recording. Intro to word embeddings. Quick notes on sets and dictionaries.

Lecture 3: Recording. MergeSort, why we can't do better with comparison-based sorts.

Notes:

Week 12

Lecture 1: Recording. Generating all combinations, Nov30.py

Lecture 2: Recording. call trees summary, 2015 exam Q9.

Lecture 3: Recording. NumPy and Monte Carlo integration

Week 13

Lecture: Recording (Turing and Goedel)

Notes: More on Turing and Goedel from Scott Aaaronson's Quantum Computing Since Democritus