Why Abstract Thinking Matters Now More Than Ever

One's own subconscious - which generates brilliant insights - needs to be spoken to not in code, but at a higher abstract level. This is needed now more than ever. AI, which now codes better than students ever will, needs to be directed at this same higher abstract level so that it can translate our intent into actions and code. Although top institutions attract top math students, many students struggle with heavy math. Jeff has always prided himself on reaching them by stripping away intimidating jargon and teaching through powerful intuition, games, and meta-algorithm techniques (like loop invariants and recursion broken down "one day at a time").

Jeff teaches many courses in Theoretical Computer Science from the second year undergrad to the graduate level. All of these courses have a large set of power point slides, notes, and questions. Two of them have Jeff's voice recorded along with the slides. He also has a book.

These courses teach how to think about algorithms in an abstract way so that one can talk about them, design new ones, and know that they are correct. Though Jeff will cover various algorithm as examples, the goal really is to teach the students to think abstractly about the key meta-algorithm techniques that everyone should know. These techniques are abstract enough to apply to most any problem that you will face in your job and in your life. Jeff has had many graduated students tell him that his courses were the most useful they had ever taken. (Request: Jeff tends to talk too fast. Please help him go pole pole slowly.)

Courses
Machine Learning
Math1090 Logic for Computer Science
EECS3101 Design and Analysis of Algorithms
EECS6111 Advanced Algorithm Design and Analysis
EECS2011 Fundamentals of Data Structures
EECS2001 Introduction to the Theory of Computation
EECS4111 Computability and Complexity
Some of Jeff's Especially Fun Lectures

Machine Learning Made Easy
description: The basic math needed to understand machine learning

0)	Python/Labs	slides
00)	Building a Computer from Sand	slides
1)	Introduction to Machine Learning	slides	video
2)	Algebra Review	slides	video
3)	Generalizing from Training Data	slides	video	video
4)	Reinforcement Learning Game Tree / Markoff Chains	slides	video
5)	Dimension Reduction & Maximum Likelihood	slides	video
6)	Generative Adversarial Networks	slides
	Some Practical Considerations	slides	video
7)	Ethics	slides	video

Logic for Computer Science
Math 1090 (1st year)
     Before a student can understand or prove anything in mathematics, it is essential to first be able
     to represent it in first order logic. Then they need to be able to deeply understand what it means
     and how to both formally and informally prove such a sentence.

How to Think About Proof Systems
           We will cover lots of intuition for lots of practical examples that are crucial
           for understanding Computer Science.
           We will balance informal intuitive proofs and formal mechanical proofs.
           Jeff's goal is to teach them, not just what to think, but how to think.
Informal Proof System
           The formula is proofed to be valid by giving a winning strategy for the corresponding game.
           For example, formula ∀x ∃y y≥x corresponds to
           "Lets each choose a number and the one with the biggest number wins. You go first."
           Reading left to right, the adversary provides a value for x. Knowing this x, the prover
           provides a y that is bigger.
           The key is that the order in which the players go is crucial to who wins.
Formal Proof System
           For a Hilbert style proof, we need each line standing alone to state something valid.
           The implied meaning of α(x,y_∃(x)) is ∀α∃y_∃∀x α(x,y_∃(x)).
           Then the rules are Modus Pones, adding and removing formals and adding and removing exists.
Propositional Proof System
           We will prove propositional formulas are tautologies
           (i.e. whether a And/Or/Not formula evaluates to be true under every assignment)
           by following obvious rules that mirrors this Davis Putnam computation.
Cover ALL of Computer Science Theory
           We intend to cover the first order logic needed to be able to express all the
           concepts covered in 2001, 3101, 6111,...
           Computable vs Uncomputable, Deterministic vs Probabilistic Algorithms,
           Time Complexity, Compile Time vs Run Time, Big-Oh Notation,
           Compiling a Java program into a TM, Universal TM,
           Computing vs Accepting, Poly vs NP, Reductions, Uncomputable Problems
           Graphs, Finite Fields, Vector Spaces, Information Theory
           You must be saying "too hard"!!! But our goal is much more humble.
           We want first year students to be able to read and understand
           the key first order logic statements that arise from these topics.

Design and Analysis of Algorithms
EECS 3101 (3rd year)
     This course teaches how to think about algorithms in an abstract way
     so that they can talk about them, design new ones, and know that
     they are correct.

First Order Logic (Quantifiers)
           (Before a student can understand or prove anything in mathematics, it
           is essential to first be able to represent it in first order
           logic. Hence, Jeff reviews it in each of his courses.)
Relevant Mathematics
           (We look at asymptotic of running times, solving recurrence relations,
           and summations.)
Loop Invariants for Iterative Algorithms
           (Jeff strongly believes that this is the most important topic in
           Algorithms. Instead of worrying about the entire computation, only
           worry about one step at a time - make progress while maintaining the
           loop invariant.)
Recursive Algorithms
           (Again do not try to understand the entire computation. Trust your
           friends to solve a smaller instances of your problem and use these to
           the solve your own instance.)
Graph Search Algorithms
           (Graphs, ie nodes and edges, are very useful for representing
           data. The first task on them is to search through the nodes.)
Network Flow
           (This is how to best transport goods from factories to stores.)
Linear Programing
           (Extremely useful in industry, eg What ingredients put in your
           hamburger today to minimize its cost.)
Greedy Algorithms Methods
           (These are the simplest possible algorithms. Proving they work,
           however, is hard.)
Dynamic Programming
           (A harder instance is solved by filling out a table of solutions for
           easier sub-instances.)
Reductions
           (Writing an algorithm for one problem from that for another.)
NP-Completeness
           (Most search problems that industry cares about are believed to not
           have poly-time algorithms.)

First Order Logic (Quantifiers)
           (Before a student can understand or prove anything in mathematics, it
           is essential to first be able to represent it in first order
           logic. Hence, Jeff reviews it in each of his courses.)
Loop Invariants
           (Jeff strongly believes that this is the most important topic in
           Algorithms. Instead of worrying about the entire computation, only
           worry about one step at a time - make progress while maintaining the
           loop invariant.)
Recursion
           (Again do not try to understand the entire computation. Trust your
           friends to solve a smaller instances of your problem and use these to
           the solve your own instance.)
Network Flow
           (This is how to best transport goods from factories to stores.)
Linear Programming
           (Extremely useful in industry, eg What ingredients put in your
           hamburger today to minimize its cost.)
Randomized Algorithms
           (Surprisingly when computing, it sometimes helps to flipping coins.)
Calculating probabilities differently to handle causality.
Linear Algebra and Finite Fields
           (A quick introduction)
More Recursion - Fast Fourier Transformations
           (Used for processing signals, compressing images, and quickly
           multiplying integers.)
Distributed Systems mud on forehead & common knowledge
           (Fun information theory. I know that my mom knows that my father loves me.)
Greedy Algorithms
           (These are the simplest possible algorithms. Proving they work,
           however, is hard.)
Dynamic Programming
           (A harder instance is solved by filling out a table of solutions for
           easier sub-instances.)
Approximation Algorithms
           (The problems that do not have quick algorithms can sometimes be
           solved approximately.)
NP-completeness
           (Most search problems that industry cares about are believed to not
           have poly-time algorithms.)
Computability
           (Some computational problems are solved by NO algorithms.)

Java & Object Oriented Programming
           (An object has both actions and data)
Abstract Data Types
           (What the user of the data structure needs to know about how it is
           used, without needing to know how it is implemented.)
Positions and Pointers
           (One data structure points at another forming linked lists and trees.
           They are often a challenge for new programmers in C or Java.)
Contracts
           (Big systems need clear specifications about how its parts communicate.)
Assertions and Invariants
           (Big systems, data structures, and algorithms alike need to have clear
           specifications that never change.)
Asymptotic Analysis of Time Complexity
           (We classify algorithms based on whether they are polynomial or
           exponential time.)
Recursion
Balanced Trees
           (A great data structure storing objects is a binary tree. If it is
           balanced than its depth is only log(n) with n nodes. Hence, operations
           are quick.)
Maps Hash Tables and Dictionaries
           (Items are "randomly" placed in at table.)
Graph Search Algorithms
           (Graphs, ie nodes and edges, are very useful for representing
           data. The first task on them is to search through the nodes. )
Programming Methods
           (There are a few programming meta-algorithms that most algorithms fit
           into. These should be understood.)
Other

Math Preliminaries
First Order Logic
           (Before a student can understand or prove anything in mathematics, it
           is essential to first be able to represent it in first order
           logic. Hence, Jeff reviews it in each of his courses.)
Turing Machines and Models of Computability
           (Historic and mathematical ways of modeling machines for computing.)
Deterministic Finite Automata - Machine
           (Useful for modeling simple machines eg coke machine.)
Deterministic Finite Automata and Regular Languages Classes
           (We classify computational problems based on the amount of resources
           used to compute them.)
Context Free Grammars
           (Useful for modeling and parsing languages.)
Countable and Uncountable Infinite
           (There are more real numbers than fractions and the same number of
           fractions as integers.)
Halting Problem is Uncomputable
           (Some computational problems are solved by NO algorithms.)
Reductions For Uncomputability
           (Knowing that some computational problems are hard, we prove that
           others are.)
No Proof System for Number Theory
           (Godel proved that there is no mechanical way of proving everything in
           mathematics.)
NP-completeness
           (Reductions involve writing an algorithm for one problem from that for
           another. NP-Completeness give strong evidence that most search
           problems that industry cares about are believed to not have poly-time
           algorithms.)

First Order Logic
           (Before a student can understand or prove anything in mathematics, it
           is essential to first be able to represent it in first order
           logic. Hence, Jeff reviews it in each of his courses.)
Turing Machines
           (Historic and mathematical ways of modeling machines for computing.)
Other Models of Computability
           (More Historic ways of modeling machines for computing.)
Complexity Classes
           (We classify computational problems based on the amount of resources
           used to compute them.)
Diagonalization & Uncomputability
           (There are more real numbers than fractions and the same number of
           fractions as integers.)
           (Some computational problems are solved by NO algorithms.)
Reductions For Uncomputability
           (Knowing that some computational problems are hard, we prove that
           others are.)
No Proof System for Number Theory
           (Godel proved that there is no mechanical way of proving everything in
           mathematics.)
NP-completeness
           (Reductions involve writing an algorithm for one problem from that for
           another. NP-Completeness give strong evidence that most search
           problems that industry cares about are believed to not have poly-time
           algorithms.)

Machine Learning Made Easy
Orbit of Earth is Ellipse
Building a Computer from Sand
Calculating probabilities differently to handle causality
Spiral Graph Equations
Jeff and his son wrote a working JAVA compiler in three days for a grade 10 project.
Swimming in Lake with Monster on Shore
Probabilities
Calculus Using Infinitesimals
Faster Merge Sort
Stacking Blocks with Shift
Ackermann's Function
Common Knowledge: Mud on forehead
Recursive Picture Java Program (Needs to be more user friendly)
Newtonian analysis of orbital motion
Goodstein Theorem: a fun sequence of numbers
Not English: 1 2