Jeff's Courses
Thinking Abstractly About Algorithms
Jeff's Lecture Material
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.)
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 res present 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 res present 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.)
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 res present 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 res present 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)