Fantastic Learning Resources Aug 6, 2023

On Mentorship

Having a great mentor is fantastic, but mentors are not always available. Luckily, programming can be mastered without a mentor, if you got past the initial learning step. When you code, you get a lot of feedback, and, through trial and error, you can process the feedback to improve your skills. In fact, the hardest bit is actually finding the problems to solve (and this article suggests many). But if you have the problem, you can self-improve noticing the following:

• How you verify that the solution works.
• Common bugs and techniques to avoid them in the future.
• Length of the solution: can you solve the problem using shorter, simpler code?
• Techniques — can you apply anything you’ve read about this week? How would the problem be solved in Haskell? Could you apply pattern from language X in language Y?

In this context it is important to solve the same problem repeatedly. E.g., you could try solving the same model problem in all languages you know, with a month or two break between attempts. Repeatedly doing the same thing and noticing differences and similarities between tries is the essence of self-learning.

On Programming Languages

Learning your first programming language is a nightmare, because you are learning your editing environment (PyScripter, IntelliJ IDEA, VS Code) first, simple algorithms second, and the language itself third. It gets much easier afterwards!

Learning different programming languages is one of the best way to improve your programming skills. By seeing what’s similar, and what’s different, you deeper learn how the things work under the hood. Different languages put different idioms to the forefront, and learning several expands your vocabulary considerably. As a bonus, after learning N languages, learning N+1st becomes a question of skimming through the official docs.

In general, you want to cover big families of languages: Python, Java, Haskell, C, Rust, Clojure would be a good baseline. Erlang, Forth, and Prolog would be good additions afterwards.

On Algorithms

There are three levels of learning algorithms

Level 1

You are not actually learning algorithms, you are learning programming. At this stage, it doesn’t matter how long your code is, how pretty it is, or how efficient it is. The only thing that matters is that it solves the problem. Generally, this level ends when you are fairly comfortable with recursion. Few first problems from Project Euler are a great resource here.

Level 2

Here you learn algorithms proper. The goal here is mostly encyclopedic knowledge of common techniques. There are quite a few, but not too many of those. At this stage, the most useful thing is understanding the math behind the algorithms — being able to explain algorithm using pencil&paper, prove its correctness, and analyze Big-O runtime. Generally, you want to learn the name of algorithm or technique, read and grok the full explanation, and then implement it.

I recommend doing an abstract implementation first (i.e., not “HashMap to solve problem X”, but “just HashMap”). Include tests in your implementation. Use randomized testing (e.g., when testing sorting algorithms, don’t use a finite set of example, generate a million random ones).

It’s OK and even desirable to implement the same algorithm multiple times. When solving problems, like CSES, you could abstract your solutions and re-use them, but it’s better to code everything from scratch every time, until you’ve fully internalized the algorithm.

Level 3

One day, long after I’ve finished my university, I was a TA for an algorithms course. The lecturer for the course was the person who originally taught me to program, through a similar algorithms course. And, during one coffee break, he said something like

We don’t teach algorithms so that students can code Dijkstra with their eyes closed on the job. They probably won’t have to code any fancy algorithms themselves.

We teach algorithms so that students learn to think about invariants and properties when writing code. Real-life code is usually simple enough that it mostly works if you just throw spaghetti onto the wall. But it doesn’t always work. To write correct, robust code at work, you need to think about invariants.

The trick with algorithms is that coding them is hard. The only way to avoid bugs is to force yourself to think in terms of invariants.

I was thunderstruck! I didn’t realize that’s the reason why I am learning (well, teaching at that point) algorithms! Before, I always muddled through my algorithms by randomly tweaking generally correct stuff until it works. E.g., with a binary search, just add +1 somewhere until it doesn’t loop on random arrays. After hearing this advice, I went home and wrote my millionth binary search, but this time I actually added comments with loop invariants, and it worked from the first try! I applied similar techniques for the rest of the course, and since then my subjective perception of bug rate (for normal work code) went down dramatically.

So this is the third level of algorithms — you hone your coding skills to program without bugs. If you are already fairly comfortable with algorithms, try doing CSES again. But this time, spend however much you need double-checking the code before submission, but try to get everything correct on the first try.

On Algorithm Names

Here’s the list of things you might want to be able to do, algorithmically. You don’t need to be able to code everything on the spot. I think it would help if you know what each word is about, and have implemented the thing at least once in the past.

Linear search, binary search, quadratic sorting, quick sort, merge sort, heap sort, binary heap, growable array (aka ArrayList, vector), doubly-linked list, binary search tree, avl tree, red-black tree, B-tree, splay tree, hash table (chaining and open addressing), depth first search, breadth first search, topological sort, strongly connected components, minimal spanning tree (Prim & Kruskal), shortest paths (bfs, Dijkstra, Floyd–Warshall, Bellman–Ford), substring search (quadratic, Rabin-Karp, Boyer-Moore, Knuth-Morris-Pratt), trie, Aho-Corasick, dynamic programming (longest common subsequence, edit distance).

On Larger Programs

A very powerful exercise is coding a medium-sized project from scratch. Something that takes more than a day, but less than a week, and has a meaningful architecture which can be just right, or messed up. Here are some great projects to do:

Ray Tracer

Given an analytical description of a 3D scene, convert it to a colored 2D image, by simulating a path of a ray of light as it bounces off objects.

Software Rasterizer

Given a description of a 3D scene as a set of triangles, convert it to a colored 2D image by projecting triangles onto the viewing plane and drawing the projections in the correct order.

Dynamically Typed Programming Language

An interpreter which reads source code as text, parses it into an AST, and directly executes the AST (or maybe converts AST to the byte code for some speed up)

Statically Typed Programming Language

A compiler which reads source code as text, and spits out a binary (WASM would be a terrific target).

Relational Database

Several components:

• Storage engine, which stores data durably on disk and implements on-disk ordered data structures (B-tree or LSM)
• Relational data model which is implemented on top of primitive ordered data structures.
• Relational language to express schema and queries.
• Either a TCP server to accept transactions as a database server, or an API for embedding for an in-processes “embedded” database.

Chat Server

An exercise in networking and asynchronous programming. Multiple client programs connect to a server program. A client can send a message either to a specific different client, or to all other clients (broadcast). There are many variations on how to implement this: blocking read/write calls, epoll, io_uring, threads, callbacks, futures, manually-coded state machines.

Again, it’s more valuable to do the same exercise six times with variations, than to blast through everything once.