Archive

Hutter Prize -- 500'000€ Prize for Compressing Human Knowledge sponsored by Marcus Hutter

This compression contest is motivated by the fact that being able to compress well is closely related to acting intelligently, thus reducing the slippery concept of intelligence to hard file size numbers. In order to compress data, one has to find regularities in them, which is intrinsically difficult (many researchers live from analyzing data and finding compact models). So compressors beating the current "dumb" compressors need to be smart(er).

References

• Universal Artificial Intelligence book.

Hutter Prize -- 500'000€ Prize for Compressing Human Knowledge sponsored by Marcus Hutter

This compression contest is motivated by the fact that being able to compress well is closely related to acting intelligently, thus reducing the slippery concept of intelligence to hard file size numbers. In order to compress data, one has to find regularities in them, which is intrinsically difficult (many researchers live from analyzing data and finding compact models). So compressors beating the current "dumb" compressors need to be smart(er).

References

• Universal Artificial Intelligence book.

The Missing Semester of Your CS Education -- You should do this self taught course from MIT whether if you have a degree in CS or not. This is my top recommendation for learning the craft of programming/development.

Classes teach you all about advanced topics within CS, from operating systems to machine learning, but there’s one critical subject that’s rarely covered, and is instead left to students to figure out on their own: proficiency with their tools. We’ll teach you how to master the command-line, use a powerful text editor, use fancy features of version control systems, and much more!

Open Source Society University - computer-science: Path to a free self-taught education in Computer Science! -- links to various MOOCs for pretty much all the topics covered in a CS undergraduate curriculum.

A Functional Introduction To Computer Science (Part I) and Part II

CS Primer Courses (This is a paid course) -- The TL;DR is:

• Start wherever looks interesting
• Focus on solving problems
• Use as much or as little of the problem walkthroughs and explainer videos as you need to keep making progress and having fun
• Keep going!

Algorithm Visualizer

Success stories

• 14,000x Speedup - James Hiebert's Blog; Sep 2015; HN
• Applying Textbook Data Structures for Real Life Wins - Heap

Course Pages with Lecture notes

Duke University's CPS130 --Introduction to Design and analysis of Algorithms is an undergraduate course. The lecture notes are good for revising basic concepts.

Jeff Erickson's Algorithm course materials --this is a huge collection of lecture notes, homeworks and exams all in one big document (800+) pages. The tone is conversational, which helps to get a feel of the langauge of the subject. This is a graduate level course.

MIT's Mathematics for Computer Science -- 6.042J, has exhaustive notes on Discrete Mathematics -- 2010

Stanford CS 168: The Modern Algorithmic Toolbox, Spring 2023 by Gregory Valiant; see Tim Roughgarden's Lecture Notes

Cambridge - Algorithms – Course materials

Video Lectures

• Algorithms by Omkar Deshpande on YouTube. Detailed explanation of concepts.
• Abdul Bari - YouTube lectures on Algorithms.
• Pavel Mavrin; "A competitive programming world champion took time to record checks notes ~90 hours of video content in the most accessible way you'll ever see! " -- via Dmitrii Kovanikov

Articles

• Algorithms & Data Structures Series – OmarElGabry’s Blog
• Big O -- A visual story that covers "4 frequently-used categories of big O notation: constant, logarithmic, linear, and quadratic"

Interviews

• 500 Data Structures and Algorithms practice problems and their solutions

Books

Free

• Algorithms by Vazirani et. al
• Lisp, the Universe and Everything: "Programming Algorithms" Book Work in progress (as of Jan 2020). All the algorithms and data structures are explained using Lisp.
• Algorithms and Data Structures - The Basic Toolbox by Kurt Mehlhorn and Peter Sanders. [PDF]
• Algorithms for Modern Hardware - Algorithmica -- Its intended audience is everyone from performance engineers and practical algorithm researchers to undergraduate computer science students who have just finished an advanced algorithms course and want to learn more practical ways to speed up a program than by going from O(nlog⁡n)O(nlogn) to O(nlog⁡log⁡n)O(nloglogn).
• (Tuzhilin and Zhang 2023) PDF This book is result of Sino-Russian collaboration. It collects the lectures which were given to students of mathematics departments of Moscow State University and Peking University about graph theory and its applications. The book’s narrative is sequential: earlier theorems and definitions are used in later material.

Non-Free

• Introduction to Algorithms aka CLRS (affl.) -- the standard textbook for this course in large percentage of undergraduate and graduate classes. The book weighs a ton and looks intimidating, but is quite approachable in practice.

• Grokking Algorithms: An illustrated guide for programmers and other curious people by Aditya Bhargava

Topics

Preliminaries

Probability and Randomness

Dynamic Programming

Divide and conquer algorithms partition the problem into disjoint subproblems, sovle the subproblems recurisvely and then combine their solutions to solve the original problem.

Dynamic programming algorithms apply when the subproblems overlap --ie., when subproblems share subproblems. Dynamic program solves each subproblem just once and saves the answer, thereby avoiding the recomputing the answer.

DP is typically applied to optimisation problems.

Four steps of DP algorithm:

1. Characterise the structure of an optimal solution.
2. Recursively define the value of an optimal solution
3. COmpute the value of the optimal solution, typicall bottom-up.
4. Construct an optimal solution from computed info.

//Characterise the structure. Define the Value. Compute the Value. Construct.

To Read

2013-11-01: Towards a discipline of experimental algorithms by Bernard Moret.

2013-11-01: O-notation considered harmful (use Analytic Combinatorics instead)

References

• Tuzhilin, Zhang (2023). Graphs, Algorithms and Applications.