15-113
Spring 2023

Home

Syllabus

Schedule

Piazza

CMU 15-113: Special Topics in Applied Python Programming
Schedule
Spring 2023

Week Dates Event / Topics
Week
#1
Mon 16-Jan
to
Fri 20-Jan
  • Mon 16-Jan: MLK Day (No Classes)
  • Code:
  • Data Representation + Encoding Card Tricks
    • Parity Card Trick, 110 Card Trick, Fitch-Cheney Card Trick, "OK" Card Trick
  • Sorting Algorithms
    • Mergesort, Quicksort, Heapsort, Radixsort
  • Heaps
    • Heap properties, percolation, heappush, heappop
  • Plotting with matplotlib
    • plt.plot(), show(), legend(), xlabel(), ylabel(), title()
  • Additional Topics
    • bitwise operators: masks, &, ~, <<, two's complement (~x+1)
    • Pigeonhole Principle, timeit.timeit(fn, number=n), globals(), try/except, truthy/falsey (eg [] is falsey), 10's complement, lattice multiplication, better-than-FOIL grid multiplication
Week
#2
Mon 23-Jan
to
Fri 27-Jan
  • Code:
  • Huffman Encoding
    • Variable-length encoding (different # of bits per symbol)
    • No symbol's code can be a prefix of another symbol's code (this allows easy decoding)
    • Add (symbol,frequency) to a min-heap, pop two at a time, combine these into a joint symbol of the summed frequency with the two nodes as children, push this back onto the heap.
    • This produces a tree. Walk the tree to form the code (left is 1, right is 0).
    • Can use (square root of inverse of) Scrabble tile scores to effectively compress text! Amazing!
  • Webscraping
    • Easiest (in many cases): copy text from web page, paste into Python, end edit from there.
    • Medium: requests.get(url).text
    • Hardest (but most powerful): beautifulSoup (bs4)
  • Additional Topics
    • OOP comparables using __lt__, quick binary to decimal, dir(module) to see module functions, decorators, globals using g.xyz, nonlocals, closures, stackframes, memoizing, @cache, *args, Von Neumann Architecture, Von Neumann Coin Toss (fair toss with unfair coin!).
Week
#3
Mon 30-Jan
to
Fri 3-Feb
  • Code:
  • Card Tricks Redux
    • Ting and Brad won the Fitch-Cheney Contest! Woohoo!
  • Make Truth Table (for arbitrary Boolean function)
    • Get source with inspect.getsource(f)
    • Get parameter names with inspect.signature(f).parameters
    • Get all 2N boolean assignments:
      1. Counting from 0 to (2N-1)
      2. Using recursion
      3. Using list(product([0, 1], repeat=N))
  • Power Sum Polynomials
    • See here
    • Goal: given a power p, find the coefficients of this polynomial: fp(n) = 1p + ... + np
    • First use handwavy calculus to argue that fp(n) is a polynomial of degree (p+1)
    • Next use linear algebra to solve for this polynomial
    • Represent matrices as regular 2d Python lists
    • Invert a matrix with numpy.linalg.inv(A)
    • Multiply two matrices with numpy.matmul(A, B)
    • Convert floats to nice fraction strings with str(Fraction(f).limit_denominator(10**3))
Week
#4
Mon 6-Feb
to
Fri 10-Feb
  • Code:
  • Selenium
  • Is with Immutables
    • Python reuses some, but not all, immutable objects.
    • For example, integers <= 256 are generally reused (aliases).
    • However, only if this can be resolved at compile-time, not runtime.
    • Thus: it is hard to know when (A is B) is true for immutables.
    • Thus: do not use "is" with immutables.
  • Tail Recursion Elimination
    • Tail recursion is when the very last thing a function does is return a recursive call to itself.
    • Some languages optimize away tail recursion, so it does not grow the call stack. Python does not do that.
    • We can manually do this in several ways, from hacky to extremely hacky. We discussed some options in class.
Week
#5-6
Mon 13-Feb
to
Fri 24-Feb
  • Code:
  • Solving Combinatoric Puzzles
    • Solves:
      • Three-Card Poker
      • Krypto (24)
      • Cryptarithm (SEND+MORE=MONEY)
  • Backtracking
    • Solve Cryptarithms much faster than naive combinatoric approach.
    • Assign letters right-to-left (ones digits first).
    • Key point: check constraints as we go so we prune most of the search space.
  • Additional Topics
    • itertools: product, combinations, permutations
    • inner functions (using nonlocal variables)
Week
#7
Mon 27-Feb
to
Fri 3-Mar
  • Mon 27-Feb: Semester Course Drop Deadline
  • Code:
  • One-Player AI
    • Depth-First Search (DFS) with a Stack
    • Breadth-First Search (BFS) with a Queue
    • A* (A-Star) with a Heap
      • Cost = (moves to state) + (heuristic guess of moves to solution)
      • Heuristic must be "admissible" (can be too low, but cannot be too high)
  • Additional Topics
Mon 6-Mar
to
Fri 10-Mar
  • Spring Break (No Classes)
Week
#8
Mon 13-Mar
to
Fri 17-Mar
  • Code:
  • Minimax
    • Two-player game search (minimax)
    • Heuristic functions
    • Horizon, depth, quiescence,...
    • Challenge: remove deepcopy + run faster (search deeper)
Week
#9
Mon 20-Mar
to
Fri 24-Mar
  • Web Programming and Flask, by Leon
  • Code:
  • Notes:
  • Web development topics
    • HTTP
      • What's in a request
      • Status code
      • GET vs. POST
      • Response body: HTML or json?
    • Backend vs. frontend
      • Backend
        What the server is doing. Contains server logic, database, etc.
      • Frontend
        How the app is presented to the user. Could be a browser app, desktop app, mobile app, etc.
      • Fullstack
        Frontend and backend together
    • Web server with Flask
      • Routing
      • Returning rendered template
      • Returning dictionary as json
      • Matching URL pattern
      • Getting URL parameter
    • Database
      • querying, inserting, deleting, updating, etc.
    • Misc
      • Type annotation in Python
      • Sending request using the curl command
Week
#10
Mon 27-Mar
to
Fri 31-Mar

Machine Learning and PyTorch, by Helen and Leon

Files

Tuesday:

  1. Machine Learning Motivation
    • Handwritten 7, L, 1 classifier
    • Writing solution by hand vs making computer learn solution
  2. High-level Math and Ideas
    • assume basic knowledge of linear algebra and derivatives (such as matrix multiplication, linear combinations, basic derivatives calculation, product rule, and chain rule)
    • conceptual understanding of how neural networks work
      • forward propagation
      • backward propagation
        • gradient descents
      • batching
      • learning rate
      • activation function
  3. Cat Classifier (NumPy implementation)
    • Implementation with math explanations
    • Binary classification: either True of False

Thursday:

  1. Introduction to PyTorch
    • basic matrix operations
    • auto gradient calculation
    • implementing linear regression
      • Mean squared error
  2. Cat Classifier Example Revisited (PyTorch Version)
    • Defining model class
    • Train a model
  3. Intro to Lab: MNIST Digit Classifier with PyTorch
    • Training loop
      • batch sizes
      • epochs
    • multi-layer fully connected layers
  4. Lab: Code out the model for MNIST and training functions
Week
#11
Mon 3-Apr
to
Fri 7-Apr
  • Mon 3-Apr: Semester Course Withdraw + Pass/Fail Deadline
  • Code:
  • Word lists:
  • 13 student-feedback poll results
  • Article on writing code with ChatGPT
    • ChatGPT writes good code except when it doesn't
    • Can ask ChatGPT to "make it faster" and it does!
    • But ChatGPT makes mistakes too often
    • Bottom line: useful tool but not a replacement (not yet, at least)
  • Median in O(N)
    • Based on partition function from quicksort
  • Minimax redux
    • Discussed solving Isola with minimax
    • Heuristic: difference in number of legal moves (computer - human)
    • Minimax outperformed all the non-search strategies we used
  • Boggle
    • How to play
    • Solving boggle with tries (prefix trees) and backtracking
      • Actually, we used a set of all prefixes instead of a trie
      • Optional hw: rewrite using tries (see huffman coding)
  • Discussion
    • "Nothing matters more than the people."
  • Thu 6-Apr: Optional:
    • Logic Programming, by Arnav
    • Code:
    • Notes:
    • Logic Programming Topics
      • Definitions
        • variables: any value; V/s. constants
        • goals: functions from substitutions to goals
        • substitutions: assignment of values to variables
        • stream: list of streams (or suspensions)
        • boolean connectives: transformers to goals
      • Implementation of goals
        • Equalization
          eq_eq(term_1, term_2) goal: succeeds if term_1, term_2 unify
        • Unification I
          a reduction of term_1 and term_2 to their root/base. If both constants, and equal, term_1 and term_2 unify. If not, then the given substitution leads to a contradiction, and eq_eq(term_1, term_2) fails.
        • Unification II
          If either is a variable, given that variables can take on any value, the substitution is “extended” with term_1: term_2, allowing them to "unify"
      • Conjunction (And)
        • Returns a stream whose solutions meet the constraints of every goal conjuncted.
      • Disjunction (Or)
        • Returns a stream where each solution satisfies the constraints of at least one of the disjuncted goals.
      • Negation (Not)
        • a simple not_eq(term_1, term_2) goal, generating an infinite stream of assignments to term_1 such that term_1 != term_2.
        • Infinite streams: a stream whose second element is a function that generates a stream. We replace the generator function with a new one that satisfies the constraints of the new goal in the resultant stream.
Week
#12
Mon 10-Apr
to
Fri 14-Apr
  • Tue 11-Apr: No class today
  • Thu 13-Apr to Sat 15-Apr: Spring Carnival (No Classes)
Week
#13
Mon 17-Apr
to
Fri 21-Apr
  • Tue 18-Apr: Writing a Custom Interpreter (nanolisp)
    • Code:
    • Tokens + Tokenizing (Lexing)
    • Parse Trees + ASTs + Parsing
    • Environments + Evaluating
    • REPLs (Read-Evaluate-Print loops, "shells")
  • Thu 20-Apr: Optional:
    • Video and OpenCV, by Gleb
    • Code:
    • Basics
      • What is computer vision and its applications?
      • Classical and ML-based computer vision: different applications
      • What is OpenCV?
        • Primary framework for CV in C++ and Python
        • Relies on numpy
    • Color spaces and thresholding
      • Loading and showing a sample image with oranges
      • Trying to find oranges on the image
      • Idea: filter in RGB color space
      • Problem: not very specific, the result includes unwanted pixels
      • Solution: use HSV (Hue, Saturation, Value) color space to decouple colors from saturation and intensity
    • Contour detection and Hough transform
      • Convolutions
        • Blurring by convolving an image with a Gaussian kernel
        • Canny edge detection algorithm
      • Line detection with a Hough transform, concept of Hough space
    • Hands on task — detecting a pencil in the web camera image
      • Possible approach:
        • Filter for the color of the pencil in HSV
        • Run Canny contour detection on the resulting mask
        • Detect lines by performing a Hough transform on the contour image
Week
#14
Mon 24-Apr
to
Fri 28-Apr
  • Tue 25-Apr: Optional:
    • Movie Editing with moviepy, by Sheng
  • Code:
  • Summary:
    • Moviepy basic intro + methods
      • Videofileclip() & .subclip
      • .fl (used to modify the frame of a clip)
      • .mirror & .resize
      • .array
    • Transition Library:
      • line/circle wipes
        Takes in a duration and clip and uses a line/circle to wipe to blank
      • line/circle transitions
        Takes in a duration and two clips and uses a line/circle to transition between two clips
      • transition function
        Allows us to control the timing of our wipe over a period of time
  • Tue 25-Apr: Optional:
    • Audio Manipulation and pydub, by Sandra
  • Code:
  • Documents:
  • How sound is quantified
    • Sine waves are sound
    • Amplitude is volume
    • Frequency is pitch
  • Audio manipulation in PyDub
    • Lots of built in functions!
    • Pitching audio up or down
      • Calculate the change in frequency
      • Stretch/compress the audio file using frame rate adjustment
  • Thu 27-Apr: Wrapping up