CS PrimerProgramming: Beyond the Basics
Programming is an unnatural act Alan Perlis There are countless ways to write any given program. This course is designed to ensure that you have all the tools at your disposal to fully express yourself with code, including functional composition and recursion, object oriented programming, and a basic understanding of concurrency.
If you are already familiar with the concepts covered below, you may prefer to cherry pick any interesting problems or skip ahead to Computer Systems
I will also use this course as an opportunity to share some of my philosophy of programming, as well as some of preferences for how I like to approach the practice of programming. I won't pretend to have the final word on these topics: there is no one correct way. But others have found these thoughts helpful in the past, and you might too.
At the core of this course however are the sequences of problems for each topic. You should aim to solve each problem, using the worked solutions and supplementary explainers as needed. For more suggestions on how to approach CS Primer, see the how-to guide.
As a supplementary text, I recommend Composing Programs by John DeNero, or the classic SICP upon which it is based, either in the original Scheme or newer JavaScript version. For a more playful, problem-oriented approach, I also highly recommend The Little Schemer, particularly on the topics of higher order functions and recursion.
I will mostly use Python as the language of choice below, but you're welcome to work in another language if you prefer. Those that don't support higher order functions and/or classes may find some problems more challenging to adapt.
NOTE: I am currently recording this course and will release problems progressively
Introduction
We'll solve a few short problems together as a warmup, and to start exploring some of the concepts we'll cover in the course.
Problems
| Luhn algorithm | Write a simple program to validate credit card numbers (1:13:11) |
| Tic-tac-toe | Implement a command line tic tac toe (58:29) |
Explainers
Higher order functions and recursion
In most languages, it's possible to treat functions not just as a set of instructions, but as their own thing that can be bound to variables and passed around. This can often enable better program factoring, readability and code reuse.
Recursion is a power tool will often allow us to write code in a way that closely fits how a problem is expressed. Many structures in computing are nested, so we will often traverse or otherwise process them recursively. It's also a technique where deliberate practice is particularly helpful.
As a supplementary resource, consider Chapter 1.6 and Chapter 1.7 of Composing Programs as well as the Little Schemer book.
Problems
| Reduce everything | show how flexible and powerful the "reduce" function is (39:53) |
| Memoize | write a "decorator" function to create caching versions of others (27:44) |
| Basic recursion | solve a series of short problems to practice recursive thinking (49:04) |
| Pretty print | print a nested structure with readable indentation (22:40) |
| Trampoline | implement your own tail call optimization (35:34) |
Objects and classes
"Objects" can be a useful way to organize programs with complex state, and have become popular in many languages, along with systems for defining how different types of objects related to one another, like "classes". Unfortunately, these tools can also be misused, so in this module we focus on understanding what problem exactly is solved by having objects and classes, so that we can use them wisely.
Problems
| Refactor life | refactor a convoluted object-oriented Game of Life implementation (1:23:50) |
| Vector class | write a class to perform vector operations (55:57) |
| DIY objects | implement your own objects (26:26) |
| DIY basic inheritance | add basic inheritance to your object system (24:59) |
Explainers
Miscellanea
Here we cover those things that don't neatly fit into other topics.
Problems
| Bytecode interpreter | mimic the fetch/decode/execute cycle in software, like an interpreter (45:31) |