Jeff Edmonds
Dept. EE and Computer Science York University Toronto Canada Email: jeff cse.yorku.ca Jeff teaches Theoretical Computer Science at all levels slides, Discord Instructions, GitHub, Schedule, Zoom Class, Recording, Zoom Tutorials, Lab document |
If we run out of material:
More Topics
Building a Computer from Sand
From silicon, to And gates, to circuits, to computers, to self driving cars.
39
Asymptotic Analysis of Time Complexity
We classify algorithms based on whether they are polynomial or
exponential time.
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.
Pointers &
Balanced Trees
One data structure points at another forming linked lists and trees.
They are often a challenge for new programmers in C or Java.
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.)
Probabilities
& Causality
It is important to have a good understanding the basics of probability
theory.
Randomized Algorithms
Calculating probabilities differently to handle causality.
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.
Common Knowledge: Mud on forehead