Graph Theory Tutorial

Graph Theory Tutorial

This full 6 hour+ course provides a complete introduction to Graph Theory algorithms in computer science.

Code: https://github.com/williamfiset/algorithms
Slides: https://github.com/williamfiset/Algorithms/tree/master/slides/graphtheory

Course created by William Fiset. Check out his YouTube channel: https://www.youtube.com/channel/UCD8yeTczadqdARzQUp29PJw

⭐️ Course Contents ⭐️
⌨️ (0:00:00) Graph Theory Introduction
⌨️ (0:13:53) Problems in Graph Theory
⌨️ (0:23:15) Depth First Search Algorithm
⌨️ (0:33:18) Breadth First Search Algorithm
⌨️ (0:40:27) Breadth First Search grid shortest path
⌨️ (0:56:23) Topological Sort Algorithm
⌨️ (1:09:52) Shortest/Longest path on a Directed Acyclic Graph (DAG)
⌨️ (1:19:34) Dijkstra’s Shortest Path Algorithm
⌨️ (1:43:17) Dijkstra’s Shortest Path Algorithm | Source Code
⌨️ (1:50:47) Bellman Ford Algorithm
⌨️ (2:05:34) Floyd Warshall All Pairs Shortest Path Algorithm
⌨️ (2:20:54) Floyd Warshall All Pairs Shortest Path Algorithm | Source Code
⌨️ (2:29:19) Bridges and Articulation points Algorithm
⌨️ (2:49:01) Bridges and Articulation points source code
⌨️ (2:57:32) Tarjans Strongly Connected Components algorithm
⌨️ (3:13:56) Tarjans Strongly Connected Components algorithm source code
⌨️ (3:20:12) Travelling Salesman Problem | Dynamic Programming
⌨️ (3:39:59) Travelling Salesman Problem source code | Dynamic Programming
⌨️ (3:52:27) Existence of Eulerian Paths and Circuits
⌨️ (4:01:19) Eulerian Path Algorithm
⌨️ (4:15:47) Eulerian Path Algorithm | Source Code
⌨️ (4:23:00) Prim’s Minimum Spanning Tree Algorithm
⌨️ (4:37:05) Eager Prim’s Minimum Spanning Tree Algorithm
⌨️ (4:50:38) Eager Prim’s Minimum Spanning Tree Algorithm | Source Code
⌨️ (4:58:30) Max Flow Ford Fulkerson | Network Flow
⌨️ (5:11:01) Max Flow Ford Fulkerson | Source Code
⌨️ (5:27:25) Unweighted Bipartite Matching | Network Flow
⌨️ (5:38:11) Mice and Owls problem | Network Flow
⌨️ (5:46:11) Elementary Math problem | Network Flow
⌨️ (5:56:19) Edmonds Karp Algorithm | Network Flow
⌨️ (6:05:18) Edmonds Karp Algorithm | Source Code
⌨️ (6:10:08) Capacity Scaling | Network Flow
⌨️ (6:19:34) Capacity Scaling | Network Flow | Source Code
⌨️ (6:25:04) Dinic’s Algorithm | Network Flow
⌨️ (6:36:09) Dinic’s Algorithm | Network Flow | Source Code

Reliable Machine Learning Systems

Reliable Machine Learning Systems

Siraj Raval has a video exploring a paper about genomics and creating reliable machine learning systems.

Deep learning classifiers make the ladies (and gentlemen) swoon, but they often classify novel data that’s not in the training set incorrectly with high confidence. This has serious real world consequences! In Medicine, this could mean misdiagnosing a patient. In autonomous vehicles, this could mean ignoring a stop sign. Machines are increasingly tasked with making life or death decisions like that, so it’s important that we figure out how to correct this problem! I found a new, relatively obscure yet extremely fascinating paper out of Google Research that tackles this problem head on. In this episode, I’ll explain the work of these researchers, we’ll write some code, do some math, do some visualizations, and by the end I’ll freestyle rap about AI and genomics. I had a lot of fun making this, so I hope you enjoy it!

Likelihood Ratios for Out-of-Distribution Detection paper: https://arxiv.org/pdf/1906.02845.pdf 

The researcher’s code: https://github.com/google-research/google-research/tree/master/genomics_ood

Donald Knuth on Algorithms, Complexity, Life, and The Art of Computer Programming

Donald Knuth on Algorithms, Complexity, Life, and The Art of Computer Programming

Donald Knuth is one of the greatest and most impactful computer scientists and mathematicians ever. He is the recipient in 1974 of the Turing Award, considered the Nobel Prize of computing.

He is the author of the multi-volume work, the magnum opus, The Art of Computer Programming. He made several key contributions to the rigorous analysis of the computational complexity of algorithms. He popularized asymptotic notation, that we all affectionately know as the big-O notation.

He also created the TeX typesetting which most computer scientists, physicists, mathematicians, and scientists and engineers use to write technical papers and make them look beautiful.

Lex Fridman interviews him in this video.

EPISODE LINKS:
The Art of Computer Programming (book): https://amzn.to/39kxRwB

OUTLINE:
0:00 – Introduction
3:45 – IBM 650
7:51 – Geeks
12:29 – Alan Turing
14:26 – My life is a convex combination of english and mathematics
24:00 – Japanese arrow puzzle example
25:42 – Neural networks and machine learning
27:59 – The Art of Computer Programming
36:49 – Combinatorics
39:16 – Writing process
42:10 – Are some days harder than others?
48:36 – What’s the “Art” in the Art of Computer Programming
50:21 – Binary (boolean) decision diagram
55:06 – Big-O notation
58:02 – P=NP
1:10:05 – Artificial intelligence
1:13:26 – Ant colonies and human cognition
1:17:11 – God and the Bible
1:24:28 – Reflection on life
1:28:25 – Facing mortality
1:33:40 – TeX and beautiful typography
1:39:23 – How much of the world do we understand?
1:44:17 – Question for God

Machine Learning Algorithms Explained

Machine Learning Algorithms Explained

Here’s a great review of the most common machine learning algorithms by InfoWorld.

Recall that machine learning is a class of methods for automatically creating predictive models from data. Machine learning algorithms are the engines of machine learning, meaning it is the algorithms that turn a data set into a model. Which kind of algorithm works best (supervised, unsupervised, classification, regression, etc.) depends on the kind of problem you’re solving, the computing resources available, and the nature of the data.