HN Explorer

Ask HN: What skills do I need before tackling The Algorithm Design Manual?

5 points by brewerhimself ↗ HN
I’ve been reading a book called “How To Win At College” by Cal Newport of Study Hacks fame. The book is broken up into a series of tips and tricks that are meant to ultimately lead one to greater success as a university student. One of the tips in the book is “Do something better than anyone you know.” I’ve decided that I want this skill to be the ability to solve algorithmic problems by applying algorithm theory to real-world problems and I’ve decided on The Algorithm Design Manual by Skiena as my introduction to algorithms.

We all agree that computer science is not programming, but I believe a firm grasp on basic CS concepts can make anyone a better developer. This relationship is similar to that of a journalist who studies English. While a journalist can have a great career without studying English, there is certainly an argument that theory (English) is just as important as application (Journalism). For programmers, this is the difference between studying theoretical computer science (algorithms, data structures, AI, etc) and learning programming languages (Python, C, etc).

My goal is to become proficient at engineering optimized algorithms for solving real-world problems. This won’t happen by diving right into a book on algorithms and that is something that I fully understand. My question is this: What do I need to know before I start tackling The Algorithm Design Manual? To be a good algorithm designer one certainly needs to know how to analyze the time complexity of an algorithm. What math skills, specifically, are required to do this well? I’ve heard that going through a book on discrete mathematics would be a good idea. What else would you recommend? Statistics and probability, perhaps?

5 comments

[ 3.1 ms ] story [ 26.5 ms ] thread
mailshanx
Usually, algorithms/data structures are the second course in a CS sequence. If you can code simple programs, you need nothing more than high-school math to be able to work through Skiena's book. Other than that, i would suggest practicing on TopCoder / code chef and the like.
benkant
Statistics and probability don't directly relate to anything in TADM from what I can recall. There's not much to the maths beyond high school stuff. Some discrete maths will help though. Graphs theory, trees and functions especially. Schaum's Outline of Discrete Mathematics is decent.

Obviously Skiena's book is in C- so be somewhat familiar with it. Again no need to go crazy deep into C before you start. You can learn as you go.

I'd recommend just diving in and using other resources as references if you come across anything you don't know, rather than spending too much time working though "pre-requisites".

eshvk
So analyzing the time complexity of an algorithm is the easiest part of designing algorithms. There are two harder parts:

1) Figuring out how to prove whether your algorithm works.

2) Learning how to build new algorithms.

The two parts are intertwined. If you really want to learn how an algorithm works, you must be able to convince yourself how it works: Part of that is to build a mathematical proof that it works, another part is to be able to code it out. So first out figure out the technical language of how to convince yourself mathematically whether an algorithm works: Work on a few proofs, a few chapters from any discrete math books (e.g. Rosen) should help there. Pick a language that lets you focus on algorithm details without having to mess with a lot of infrastructure details. Then practice, go over the book (by which I mean solve as many problems as you can), play with algorithms by googling questions that are related so that you can get a flavor for how different algorithms get used. Eventually as you progress through the book, you will start getting a sense for how to decompose most engineering problems into well known algorithms or combinations of algorithms.