
Jeff's Courses
Thinking Abstractly About Algorithms
Jeff's Lecture Material
List of Topics.ppt
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
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.)
Advanced Algorithm Design and Analysis
CSE 6111 (grad)
This reviews the previous course for our grad students and tries to
teach them the missing math and algorithms that they should
practically know.
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.)
Fundamentals of Data Structures
EECS 2011 (2nd year)
This is your basic data structures course with a focus on systems
invariants and understanding.
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
Introduction to the Theory of
Computation
EECS 2001 (2nd year)
This course is useful for a graduate student interested in the
theoretical aspects of computer science.
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.)
Computability and Complexity
CSE 4111/5111 (4th year)
This is more of the CSE 2001 course.
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.)
Some of Jeff's Especially Fun Lectures
(Fun)