Computer Science Resources for Autodidacts

8 Replies

Introduction

My post Replicating a BSc in Computer Science through MOOCs is one of the more popular on this blog. A few people were asking me whether I could recommend some books that are particularly suited for autodidacts. In the following, I’m listing resources I found suitable for self-study, including some particularly suitable online courses (MOOCs) to complement your studies.

I do not want anybody to take my word as gospel, though. I’m going to list resources I found helpful. I have not conducted a systematic literature review but merely went through a number of books until I found one I could work with. I recommend the resources below based on my own experience. There may be better resources out there. So, if you’ve found some other books or online courses helpful, then feel free to comment below. Further, there are a lot of rather poor books and courses, which I’m not going to mention, as I found it more constructive to focus on positive examples.

I’m only focussing on key topics in the undergraduate curriculum, i.e. programming, data structures, discrete mathematics, and algorithms. I may post a follow-up on more advanced resources some time in the future, possibly on functional programming and programming language theory. The time spans I mention are based on the assumption that you have a few hours per day available for self-study. Overall, this study program will take you well over a year to finish, and will require serious dedication.

Imperative and Object-Oriented Programmming

I’d recommend learning Python since it’s easy to get started with it. It’s pretty painful to use for anything moderately complex, though. Downey’s book Think Python: How to Think Like a Computer Scientist is concise and contains plenty of exercises. If possible, go through Rice University’s Coursera course An Introduction to Interactive Programming in Python as well. These two resources alone will have you write several thousand lines of Python code. Four months seem like an adequate time span for these two resources.

Java is more of a means to an end if you want to put a skill on your CV recruiters care about. Once more, I’d recommend Downey. Think Java is likewise concise. Since you’ve learnt Python already, Java should be relatively straightforward to pick up. Therefore, schedule one month for this book.

Data Structures

You should have had exposure to data structures in the previously mentioned resources. To gain further practice, go through both the Java and Python sections on CodingBat. You should complete all exercises on your own. If you struggle, then brush up on the basics of Java and Python.

Two months should be plenty of time for all exercises. There are several hundred on there, but if you do a handful to a dozen every day, you’ll progress quickly. You should get to a point where you can solve those exercises straight away, maybe with the exception of a few of the more elaborate ones.

Discrete Mathematics

Schaum’s Outline of Discrete Mathematics is very good. It’s great to have just for the exercises. If the explanations are too sparse for your taste, then Eric Lehman and Tom Leighton’s lecture notes Mathematics for Computer Science, which are freely available online, will serve you well. For instance, I haven’t come across an explanation of generative functions that was clearer and more accessible than theirs.

For my university course in discrete mathematics I bought Rosen’s Discrete Mathematics and Its Applications, as it was the prescribed course literature. I thought it was lacking in some regards. In particular, I wasn’t too fond of the approach of using several, sometimes convoluted, examples without explaining the underlying principles in the abstract. Schaum’s makes a great companion for it, though.

A book some people recommend is Concrete Mathematics by Graham, Knuth, and Patashnik. In the very first line of the preface of said book you can read that it was written for a course at Stanford that was primarily taken by graduate students. I’m tempted to say that just like it is the case with Knuth’s The Art of Computer Programming, people recommend it because they’ve heard the title somewhere and had the impression that it was an authoritative book.

There is no MOOC on discrete mathematics, as far as I know. The Saylor Academy offers course materials, though. Their exam is a bit on the easy side and therefore a good lower bound to aim for. If you don’t have access to a university course, then using the Saylor Academy materials as a guide, and supplementing them with exercises taken from Schaum’s Outline would be a good strategy. You’ll probably need two to three months of part-time study.

Algorithms

Probably the most accessible algorithms textbook is Algorithm Design by Kleinberg and Tardos. I’ve only studied part of this book in the context of taking Stanford’s Coursera course Algorithms: Design and Analysis. Alternatively, Introduction to Algorithms on MIT OCW seems like a good resource, based on the lectures I watched.

If you can, clear your schedule and take the Algorithms course on Coursera, which is a two-part course sequence. It will take you three to four months of study. I haven’t found the time to take part II yet, though. However, I did have a very good impression of part I, and benefited quite a bit from it.

Gödel’s System T in Agda

1 Reply

In Bove and Dybjer’s Agda tutorial “Dependent Types at Work”, section 2.5 briefly introduces Gödel’s System T, which is based on the simply typed lambda calculus with booleans and natural numbers. They give Agda definitions of the primitives of System T, as well as the multiplication and addition operator, using those primitives. As an exercise to the reader, they ask for for further definitions like cut-off subtraction and a few Boolean operations.

Building abstractions by using this rather limited set of primitives turned out to be a pleasant diversion, so I went on and implemented further operations. But to start, here are the primitives of System T in Agda, as they were given by the authors. The six primitives of System T are true, false, zero, succ, if_then_else_, and natrec, i.e. recursion on natural numbers.

module SystemT where

data Bool : Set where
  true  : Bool
  false : Bool

data ℕ : Set where
  zero : ℕ
  succ : ℕ → ℕ

if_then_else_ : {C : Set} → Bool → C → C → C
if true  then x else y = x
if false then x else y = y

natrec : {C : Set} → C → (ℕ → C → C) → ℕ → C
natrec p h  zero    = p
natrec p h (succ n) = h n (natrec p h n)

Further, Bove and Dybjer give definitions for addition and multiplication:

_+_ : ℕ → ℕ → ℕ
_+_ n m = natrec m (λ x y → succ y) n

_*_ : ℕ → ℕ → ℕ
_*_ n m = natrec zero (λ x y → y + m) n

The subtraction operation requires the predecessor function. Note that the predecessor of zero is zero. Further note that since we are restricting ourselves to natural numbers, subtraction is defined as so-called cut-off subtraction. This means that computations that yield negative numbers when performed on integers yield zero instead. Concretely, 1 – 2 = 0 instead of -1 because we restrict ourselves to nonnegative integers.

pred : ℕ → ℕ
pred n = natrec n (λ x y → x) n

_-_ : ℕ → ℕ → ℕ
_-_ n m = natrec n (λ x y → (pred y)) m

This might look a bit hairy, so it’s probably helpful to walk through this function. First, subtract one from zero:

zero - (succ zero)
= natrec zero (λ x y → pred y) (succ zero)
= (λ x y → pred y) zero (natrec zero (λ x y → pred y) zero)
= (λ x y → pred y) zero  zero
= pred zero
= zero

Second, two minus one:

(succ (succ zero)) - (succ zero)
= natrec (succ (succ zero)) (λ x y → pred y) (succ zero)
= (λ x y → pred y) zero (natrec (succ (succ zero)) (λ x y → pred y) zero)
= (λ x y → pred y) zero (succ (succ zero))
= pred (succ (succ zero))
= succ zero

To do a bit more in System T, Boolean operators would be nice to have. Using “if_then_else_” the operators for not, and, or, and xor are straightforward to define:

¬ : Bool → Bool
¬ b = if b then false else true

_∧_ : Bool → Bool → Bool
a ∧ b = if a then b else false

_∨_ : Bool → Bool → Bool
a ∨ b = if a then true else b

_⊕_ : Bool → Bool → Bool
a ⊕ b = if a then (¬ b) else b

An equality check for boolean values follows naturally:

equalityBool : Bool → Bool → Bool
equalityBool a b = if a then (a ∧ b) else (¬ (a ∧ b))

On the other hand, I found the definition of equality for natural numbers tricky. The function ‘zero?’ is therefore not defined using the perviously mentioned primitives of System T. I’ll have to look further into lambda calculus. As it is, ‘zero?’ is a small blemish of this implementation of System T.

zero? : ℕ → Bool
zero? zero = true
zero? _    = false

positive? : ℕ → Bool
positive? n = ¬ (zero? n)  -- there are no negative numbers

equalityNat : ℕ → ℕ → Bool
equalityNat a b = (zero? (a - b)) ∧ (zero? (b - a))

Lastly, here are comparison operators for natural numbers:

_>_ : ℕ → ℕ → Bool
a > b = positive? (a - b)

_<_ : ℕ → ℕ → Bool
a < b = positive? (b - a)

_≥_ : ℕ → ℕ → Bool
a ≥ b = (a > b) ∨ (equalityNat a b)

_≤_ : ℕ → ℕ → Bool
a ≤ b = (a < b) ∨ (equalityNat a b)

All of this looks pretty clean. I let Agda evaluate a few expressions, which all worked fine.

The higher-order function ‘fold’

Leave a reply

When students encounter higher-order functions in functional programming, they are normally exposed to the following three first: map, filter, and fold. The higher-order functions map and filter are intuitively accessible. With the former you apply a function to each element of a list, while the latter retains only elements for which a given predicate is true. One might want to implement those functions in Haskell as follows:

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

filter :: (a -> Bool) -> [a] -> [a]
filter _ [] = []
filter p (x:xs)
  | p x       = x : filter p xs
  | otherwise = filter p xs

On the other hand, fold is somewhat more confusing. As I’ve found, the treatment of this topic on the Haskell wiki is not overly accessible to novices, while the explanation given in Learn You A Haskell is, like pretty much everything in it, too cute for its own good.

There are two cases of fold, namely foldr and foldl, with ‘r’l and ‘l’ describing right-associativity and left-associativity, respectively. One possible definition of foldr is:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _ z []     = z
foldr f z (x:xs) = f x (foldr f z xs)

‘z’ is the last element of the list you’re applying the function to. I sometimes hear people refer to this as the “identity element”, but this is not necessarily correct. ‘z’ can be the identity element. For instance, if you want to multiply all values in a list of integers, you would chose the integer 1 to take the place of ‘z’. However, nothing is keeping you from picking any other integer.

To illustrate foldr with an example, let’s evaluate the following function call:

foldr (*) 1 [1,2,3]
(*) 1 (foldr (*) 1 [2,3])
(*) 1 ((*) 2  (foldr (*) 1 [3]))
(*) 1 ((*) 2  ((*) 3 (foldr (*) 1 [])))
(*) 1 ((*) 2  ((*) 3 1))
(*) 1 ((*) 2  3)
(*) 1 6
6

To make this evaluation more digestible from the fourth line onwards, it could also be written as:

1 * (2 * (3 * 1))
1 * (2 * 3)
1 * 6
6

This example shows the application of the function to each element in the list. Maybe this reminds you of how lists are constructed using the cons operator, i.e. (1 : (2 : (3 : []))) is represented, after adding syntactic sugar, as [1, 2, 3].

In fact, a list can be constructed using a fold. So, if you were in a silly mood, you could create a function that takes a list, runs it through fold, and returns the same list:

listId :: [a] -> [a]
listId xs = foldr (:) [] xs

Of course, ‘xs’ can be omitted on both sides of this equation. If you now call this function with the argument [1, 2, 3], you’ll get (1 : (2 : (3 : []))) in return, which is [1, 2, 3].

Let’s now look at foldl, which is fold with left-associativity. One possible definition is as follows.

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl _ z []     = z
foldl f z (x:xs) = foldl f (f z x) xs

Evaluating the same expression as given above, with foldr, results in:

foldl (*) 1 [1,2,3]
foldl (*) ((*) 1 1) [2, 3]
foldl (*) ((*) ((*) 1 1) 2) [3]
foldl (*) ((*) ((*) ((*) 1 1) 2) 3) []
((*) ((*) ((*) 1 1) 2) 3)
((*) ((*) 1 2) 3)
((*) 2 3)
6

You can probably see why defining a ‘listId’ function with foldl results in an error.

Also note that foldl and foldr only give the same result if the binary operator f is associative. Just consider what happens when you’re using an operator that isn’t, for instance:

> foldr (/) 1 [1,2,3]
> 1.5
>
> foldl (/) 1 [1,2,3]
> 0.16666666666666666

The first function call evaluates to (1 / (2 / (3 / 1))), and the second to (((1 / 2) / 3) / 1).

Review: Introduction to Functional Programming (edX)

Leave a reply

I just finished the last problem set in Erik Meijer’s online course Introduction to Functional Programming. This seems like a good opportunity to briefly reflect on it. There aren’t a lot of functional programming MOOCs available. I’m only aware of two Coursera courses, one on FP in Scala, and another on FRP in Akka. While Erik Meijer repeatedly made the point that his course was not on Haskell but on FP in general, there most certainly was a strong focus on exploring functional programming with Haskell.

The recommended course literature was Graham Hutton’s Programming in Haskell, which is incidentally the same book I used when I took a similar course at university. As far as programming-related textbooks go, Hutton’s book is among the best, as he explains topics concisely, and poses carefully selected exercises to the reader. It’s the exact opposite of your typical Java or Python textbook, or the, in my opinion, highly overrated “Learn you a (Haskell|Erlang) for Great Good” books, but that may be a topic for another article.

If you just used the textbook, you’d be well-prepared for the homework exercises and labs already. Still, I enjoyed Erik Meijer’s presentation, and his sometimes quirky remarks, such as that he wants his students to “think like a fundamentalist and code like a hacker”. In special “jam sessions” he demonstrated functional programming concepts in other languages, such as Scala, Dart, Hack, and Kotlin. What I also liked was that some of the labs were offered in several programming languages. The very first lab was offered in Haskell, Groovy, F#, Frege (!), and Ruby, for instance, which led me to playing around with some new languages.

This course is certainly, for the most part, comparable to a university-level course in functional programming. I do have some gripes with the form of the assessment, though. For instance, a common type of question asked you to indicate which of a given number of alternative function definitions were valid. Sometimes the code was obfuscated, and since you couldn’t just copy and paste it, it could easily happen that a GHCi error message was due to a mistake you made while copying the program. This might not have been a problem if those questions had been rare, but because there were so many of them, the tedium was palpable. In later weeks I skipped those questions since I saw very little educational value in them.

Further, the labs were a bit too straight-forward for my taste, but that may be a limitation of the MOOC format. The advice “follow the types” was repeated like a mantra. It is of course a good idea to use type signatures as a guide. However, being given a template that contains correct type signatures and that only requires one to write a few lines of code — if I’m not mistaken, in some weeks the labs required just about a dozen lines of Haskell in total — seems partly misguided. Obviously, it is much more difficult to design a program yourself, and define the correct type signatures. Merely filling in function definitions, on the other hand, is somewhat akin to painting by numbers. It might therefore be a good idea to add a peer-reviewed project to this course in its next iteration. My experience with peer-review on MOOCs is mixed, but it’s better than nothing. After all, the theory behind FP is sufficiently covered. It’s just that the course doesn’t require writing a lot of code, which could only be excused on the labs that focus on type classes and monads.

Overall, Introduction to Functional Programming is a very good course. However, if you’re taking it as a novice, you might want to do the exercises in Hutton’s book in order to get more practice with programming in Haskell.

How Coursera pesters “learners” who are not interested in paying for a PDF certificate

10 Replies

I haven’t had much time for MOOCs recently, but when I find an interesting one, I try to fit it into my schedule. Thankfully, this task gets easier all the time. While about a year ago one could pick among a plethora of free courses from Udactiy, Coursera, and EdX, nowadays the landscape is a lot less interesting. Udacity discontinued free certificates some months ago, and switched to a subscription-based model. Coursera has been phasing out their free certificates, “because employers and others found the two different kinds of credentials confusing”, as was stated in the course forum for Advertising and Society. Further, they’ve divided courses into much smaller units. What used to be one large course may now be delivered as four or five separate courses, for which you’d have to pay individually. EdX flirted with the idea of discontinuing their free ‘honours’ certificates, and silently dropped them some time ago. However, they were (silently) reintroduced some months later.

Coursera used to be my favourite MOOC provider, but I can’t stand what they have become. The absolutely worst aspect is that they constantly shove advertising for their “verified certificate” in your face. It used to be the case that if you got a decent result on a quiz, they served an ad for the verified certificate. Those ads you could close. Currently, though, Coursera displays ad you cannot close. After you’ve taken the quiz, the screen is overlaid with an ad for a verified statement of accomplishment.

This is their ad.

This is their ad.

In the example below I scored 100%, so there wasn’t much of a need for reviewing my answers to the questions. However, even if I wanted to, I couldn’t have reviewed my answers, because the ad is permanently displayed even when I navigate back to the quiz section. First you get to see this:

Let's review the answers to that quiz!

Let’s review the answers to that quiz!

But guess what happens if you click on “Review”! Well, I couldn’t believe it either, but Coursera keeps serving you this ad, presumably until you pony up the cash for a verified certificate:

Sorry, but you've got to pay if you want to review your answers.

Sorry, but you’ve got to pay if you want to review your answers.

This is utterly inexcusable. I’d expect behaviour like that from a website selling some kind of scam product, but not on a website that purports to be a reputable business. Well, profit-driven higher-education arguably qualifies as a scam, so this move by Coursera may be fitting.

Fortunately I live in a country where I have access to high-quality higher education for free, so paying for an automatically generated PDF is simply out of the question. To me, those certificates are a neat motivation to finish a course, but they are essentially worthless. Without the certificates, I see no advantage of a Coursera MOOC over MIT OCW, at least in the areas I’m interested in. That Coursera chose to dramatically worsen the user experience for those who refuse to pay for a verified certificate by showing ads you cannot remove seems absurd to me. Coursera’s numbers arguably demonstrate that this move increases revenues in the short term. Sadly, their numbers don’t capture that this incredibly short-sighted move might alienate a significant part of their user base, which they nowadays call “learners”.