## The art of computer programming. 1. Fundamental algorithms

Donald Ervin Knuth

Mentioned 11

I want to learn algorithms using some very basic simple tutorials. Are there any out there? I have heard of recursion and stuff and I would like to get good at it. Any help would be appreciated.

I would start out by taking a look at EternallyConfuzzled which contains great tutorials for basic Data Structures an Algorithms including linked lists and binary search trees, sorting and searching algorithms. If you want to learn more after this I would recommend the following books in order of increasing complexity, completeness, and required math knowledge:

I suggest that you start from sorting algorithms. Read the related wikipedia page, skip the O(n log n) stuff, and focus on the implementations of, say, insertion sort, merge sort, and quick sort. Familiarize with binary searching. Also, learn about some basic data structures, such as vectors, linked lists, stacks, their implementation, and what they are useful for. (More often than not, an algorithm to solve a problem goes together with a suitable data structure.) Once you are confident with different algorithms and data structures, you can dive in a more complete treatise such as the book by Cormen et al.

As for recursion, it is not an algorithm in itself. It is instead a technique that some algorithms employ to solve a problem, when the latter can be naturally split into subproblems. The technique of splitting a problem, solving the subproblems separately and then merging their solutions to obtain a solution for the original problem, is called "divide et impera", or "divide and conquer". (Recursion is also the related feature of most programming languages, where it basically means "functions that call themselves".)

The most cited, the most trivial, and the most useless example of a "recursive algorithm", is the one to compute factorials. Don't mind it. Instead, read about the Tower of Hanoi problem, which admits a simple and elegant recursive solution, and again, study some sorting algorithms, for many of them are indeed recursive.

I was thinking about ways to improve my ability to find algorithmic solutions to a problem.I have thought of solving math problems from various math sectors such as discrete mathematics or linear algebra.After "googling" a bit I have read an article that claimed the need of learning game programming in order to achieve this and it seems logical to me.

Do you have/had the same concerns as me or do you have any ideas on this?I am looking forward to hear them.

P.S.1:I want to say that I already know about programming and how to program(although I am at amateur level:-) ) and I just want to improve at the specific issue, NOT to start learning it

P.S.2:I think that its a useful topic for future reference so I checked the community wiki box.

Read SICP / Structure and Interpretation of Computer Programs and work all the problems; then read The Art of Computer Programming (all volumes), working all the exercises as you go; then work through all the problems at Project Euler.

If you aren't damned good at algorithms after that, there is probably no hope for you. LOL!

P.S. SICP is available freely online, but you have to buy AoCP (get the international, not-for-release-in-north-america edition used for 30 USD). And I haven't done this yet myself (I'm trying when I have free time).

You should check out Mathematics and Plausible Reasoning by G. Polya. It is a rare math book, which actually deals with the thought process involved in making mathematical discoveries. I think it is the same thought process that is involved in coming up with algorithms.

My degree is in Electrical and Computer Engineering but i'm currently employed as a Software Engineer. I took all of the algebra, geometry and calculus classes that one would expect from someone with my degree however I must admit, I think I learned just enough to pass the test but never really saw a use for it and therefore never really retained much of the material.

Now that i've matured some, I see the use for it all of the time. I KNOW that there are lots of places that math knowledge would improve my coding so i'm ready to relearn the old stuff and learn some new stuff.

What are your favorite resources out there? (Resources that can tie math into programming are even better if you have any!) Books? Websites? Blogs?

Or as I like to refer to it: The guy that made me realize I hadn't actually invented or discovered anything that hadn't been known for years.

I really like the book Mastering Technical Mathematics 3rd Edition. It's kind of a bird's-eye view of mathematics with a technical focus. It starts out with such simple concepts as addition and multiplication, but as it explains the concepts it also explains how computers do the calculations. About half-way through you'll find quadratic equations and calculus. Page 442 begins the discussion of "General Time-Space Hypervolume". I didn't see anything about matrix math in there, but for a good "everything about math in a nutshell"-type book it's great.

Math Refresher for Scientists and Engineers (by John R. Fanchi)

Just-In-Time Math for Engineers (by Archibald L. Fripp, Jon B. Fripp and Michael L. Fripp)

I'm interested in learning video game algorithms. (For iPhone particularly, but generally as well. I assume certain concepts are the same.) I am best off (personally) learning from a book but websites are useful too.

What has helped you learn game programming algorithms and concepts?

EDIT:

As per request, I'll clarify the types of algorithms... I was looking for any algorithms really, but I guess I was interested in (top-down view) platformer algorithms, but, now that you mention it, Seth, I do wonder about chess...

EDIT2:

I'm making this a Community Wiki due to the nature of the question.

I am interested in 2D platformer algorithms at the moment. I would like to remake an old video game (a personal favorite, publisher now defunct.)

I don't think there is any one definitive source for game development algorithms, there are so many different ways to approach game development even within a single genre.

The best advice I can give it to learn by playing with existing technology, get a hold of some game frameworks and go through their tutorials. I don't know of many for iPhone but you could look at the Torque Game Engine or Ogre3D for PC based technologies. Microsoft's XNA Framework is also an excellent starting point for console development. Any of those will give you a good idea of the basic structure of a game project and some of the core algorithms like pathfinding, collision detection etc.

If you'd rather read book though, I always recommend the Game Programming Gems series, last I looked they had six or seven volumes but they all contain collections of articles on all aspects fo game development.

Best of Game Programming Gems

These titles are a few years old, but have updated versions at this time. Pay attention specifically to the computational geometry content.

Andre LaMothe - "Tricks of the Windows Game Programming Gurus" http://www.amazon.com/Andre-Lamothe/e/B000ARBG92/ref=ntt_athr_dp_pel_pop_1

and

Corment, Leiserson, et. al. - "Introduction to Algorithms" http://www.amazon.com/Introduction-Algorithms-Thomas-Cormen/dp/0072970545/ref=ntt_at_ep_dpi_2

I'd recommend Realtime Collision Detection by Christer Ericson ( Director of Tools and Technology at Sony Santa Monica Studios - aka God of War ) - despite the title it covers a wider range of approaches than just collison detection including - data structures and algorithms for modern games development.

A lot of computer games coding is also simply good old-fashioned coding i.e data structures + algorithms so don't forget the two classics:
The Art of Computer Programming by Donald Knuth
Programming Pearls by Jon Bentley

There are also some excellent on-line R&D references on games development by many studios such as:
Mike Acton's Blog
Insomniac's R&D Site
Valve's site
DICE's site

Say I have an array of arbitrary size holding single characters. I want to compute all possible combinations of those characters up to an arbitrary length.

So lets say my array is [1, 2, 3]. The user-specified length is 2. Then the possible combinations are [11, 22, 33, 12, 13, 23, 21, 31, 32].

I'm having real trouble finding a suitable algorithm that allows arbitrary lengths and not just permutates the array. Oh and while speed is not absolutely critical, it should be reasonably fast too.

Knuth covers combinations and permutations in some depth in The Art of Computer Programming, vol 1. Here is an implementation of one of his algorithms I wrote some years ago (don't hate on the style, its ancient code):

``````#include <algorithm>
#include <vector>
#include <functional>
#include <iostream>
using namespace std;

template<class BidirectionalIterator, class Function, class Size>
Function _permute(BidirectionalIterator first, BidirectionalIterator last, Size k, Function f, Size n, Size level)
{
// This algorithm is adapted from Donald Knuth,
//      "The Art of Computer Programming, vol. 1, p. 45, Method 1"
// Thanks, Donald.
for( Size x = 0; x < (n-level); ++x )   // rotate every possible value in to this level's slot
{
if( (level+1) < k )
// if not at max level, recurse down to twirl higher levels first
f = _permute(first,last,k,f,n,level+1);
else
{
// we are at highest level, this is a unique permutation
BidirectionalIterator permEnd = first;
f(first,permEnd);
}
// rotate next element in to this level's position & continue
BidirectionalIterator rotbegin(first);
BidirectionalIterator rotmid(rotbegin);
rotmid++;
rotate(rotbegin,rotmid,last);
}
return f;
}

template<class BidirectionalIterator, class Function, class Size>
Function for_each_permutation(BidirectionalIterator first, BidirectionalIterator last, Size k, Function fn)
{
return _permute<BidirectionalIterator,Function,Size>(first, last, k, fn, distance(first,last), 0);
}

template<class Elem>
struct DumpPermutation : public std::binary_function<bool, Elem* , Elem*>
{
bool operator()(Elem* begin, Elem* end) const
{
cout << "[";
copy(begin, end, ostream_iterator<Elem>(cout, " "));
cout << "]" << endl;
return true;
}
};

int main()
{

int ary[] = {1, 2, 3};
const size_t arySize = sizeof(ary)/sizeof(ary[0]);

for_each_permutation(&ary[0], &ary[arySize], 2, DumpPermutation<int>());

return 0;
}
``````

Output of this program is:

``````[1 2 ]
[1 3 ]
[2 3 ]
[2 1 ]
[3 1 ]
[3 2 ]
``````

If you want your combinations to include repeated elements like [11] [22] and [33], you can generate your list of combinations using the algorithm above, and then append to the generated list new elements, by doing something like this:

``````for( size_t i = 0; i < arySize; ++i )
{
cout << "[";
for( int j = 0; j < k; ++j )
cout << ary[i] << " ";
cout << "]" << endl;
}
``````

...and the program output now becomes:

``````[1 2 ]
[1 3 ]
[2 3 ]
[2 1 ]
[3 1 ]
[3 2 ]
[1 1 ]
[2 2 ]
[3 3 ]
``````

Introduction

I know I'm going to lose a lot of reputation for this question and I also know it will be flagged as inappropriate but I'm really curious about that so I'm not giving up if there's any chance I'm getting at least an answer.

Question

Today I woke up thinking:

Hei, how could random functions be really random if they are created by an algorithm?

Think about it. How could you create a function that simulates randomness without the concept of random already built in? I began to think:

Hei, I'd take an array of int, then I'd do [thing], then [thing], than [thing] again, then I'd choose only odd numbers... ecc

But it seems more likely a function that make it more confusing to predict what the choose will be rather than real randomness.

Is it possible to create randomness? How are functions that returns random ints (such as `rand()` in PHP) created? How can they simulate randomness?

Read volume 2, chapter 3 of this seminal work if you want the maths behind it. You can buy it to look impressive on your bookshelf. (Just keep in mind that most people who buy it wind up never actually reading it -- for a good reason. It's VERY dense and VERY difficult reading.) The short answer that doesn't involve massive tomes of difficult text is that "random" numbers generated purely algorithmically are pseudorandom, which is to say that they are "random enough".

Where can I find e-books on Data Structures and Algorithms? I am currently reading "Computer Algorithms: Introduction to design and Analysis" by Sara Baase and Allen Van Gelder. I would like to have additional information to supplement what's in this book. Also some references on worst-case analysis would be great.

Introduction to Algorithms

The Art of Computer Programming - by Donald Knuth (hard read, but well worth it, not recommended for a first algorithms book)

Concrete Mathemetics - By Donald Knuth (understanding the math behind algorithms)

I don't know if e-book versions are available for these, but if they are...these books will definitely give you the theory behind worst-case, and asymptotic analysis of algorithms.

I am a newbie in the software development field. I am hungry for more avenues through which I can develop, nurture, and mature in my development, scripting, and programming skills, more so outside of work time. I'd like to know what type of set-up (hardware and/or software) would be extremely beneficial or that others have found necessary for this endeavor.

I want to be able to equip my home 'office' with tools that will enable me to progress and grow as a developer.

Write Code:

In this article Jeff Atwood talks about how to become better at designing and writing software by designing and writing a lot of software. His is stated more elegantly, but it is a valid point. The more you do something, the better you will get at it.

Hardware:

Any modern PC/Mac hardware should suffice. If you plan to run Windows or Linux I would use a PC over Mac. There is a lot of clamor over which is better, but use the one you like the best.

It should be a moot point in this day and age, but make sure you have some sort of reliable internet connectivity (cable, dsl, whatever...). Then you will have access to Google and stackoverflow; both good resources for programmers.

Make sure you have a keyboard and mouse which are comfortable to you. This includes setting up your desk and chair to accommodate your height and hand position. You will be at the computer for long stretches of time, and you want to be comfortable.

Editor/IDE:

Choose an editor: Vim, EMACS, KATE, Eclipse, whatever. It doesn't really matter which one, but whichever one you do pick learn it well. The editor is your main tool and you want to be comfortable and knowledgeable when using it. The better you know your editor the faster you can create/edit code.

It helps to have an editor that runs on all platforms you may be developing on, but it is not necessary.

Build Tools:

At some point you will find your self face to face with having to create or fix a build stystem. Make is pretty standard for *nix and C/C++, but for your own personal projects find the one that suits you best. There are a lot to choose from: Scons, Ant, Make, Jam, ...

I personally use SCons, since it is python based, and I like python.

Books:

When learning a new topic I would recommend getting a good book on it. This will generally give you a good overview of what you are getting into, and give you a good foundation to learn from. Google and Stackoverflow are good for specific questions, but a general overview of a topic is harder to get.

This of course assumes you have the luxury of time and money. For the monetarily constrained you can often find free versions of electronic books online.

Languages:

I used to have strong feelings about which languages to learn, but now I realize you should write in the language you enjoy most. However don't be afraid to try new languages. I personally like C++, python, and C# in no particular order.

Since you are just starting out pick the languages which you can get for free, which I actually think is most languages these days.

In the business world the language of choice tends to fluctuate on about a 5-7 year cycle. However you can find a job (at least currently) in all the "big" languages (C++, JAVA, C# VB.net, python, ruby, perl, ...). If you learn one of the modern languages well, it is typically not a problem to transition to another language quickly. The libraries tend to take longer to learn than the language itself. So pick a language you like learning in and learn it.

Miscellaneous Thoughts:

As Marc Charbonneau said set up source control. There are plenty of free source control offerings, so pick the one you like best. Personally I use Perforce, which is free for two or less people. I ahve heard good things about Subversion and git as well. The specific one is not as important, but choose one of them.

If you want to get a deeper knowledge of computing I would recommend Sipser's Book and Knuth.

Whichever language you choose I would spend time learning the debugger for it as well.

If you are doing web development, then make sure you know how to minimally setup and run Apachie (or IIS).

Avoid holy wars if you can. They are a waste of time, and you don't learn anything from it except that people are stubborn. Some Holy war topics (bracket style, editors, endianess, "best" language, "best" OS, ...).

My personal setup:

Standard PC (Windows XP Pro)

• Visual Studio 2007 (a little behind).
• VIM
• Python
• C/C++
• C#
• Scons

Standard PC (FreeBSD runs headless: no GUI)

• gnu tool chain (Make, C/C++ etc)
• VIM
• python
• Scons

I was wondering how the Random functions in every programming language works so I want to generate a number by myself i.e. I don't want to use any inbuilt classes or functions.

If you are curious how it works you can start with Wikipedia: Random number generation and List of random number generators. The second link will give you list of few popular algorithms (like Mersenne Twister) that you can implement by yourself.

You can also decompile System.Random with .Net Reflector and compare given algorithms with what is implemented natively in .Net

Also, Art of Computer Programming by D. Knuth has a chapter on random numbers and their generation.

I know the formula for the recurrence relation is T(n)=aT(n/b)+f(n). And given that equation I know how to solve for the BigO. My homework question asked me to write a recursive function to count the number of nodes in a list, which I did but then asked me to write a recurrence relation. Here's my code:

``````int count(ListNode *l)
{
if(!l) return 0;
if(!l->next) return 1;

return 1 + count(l->getNext());
}
``````

But I am totally lost on how to create/formulate my own recurrence relation formula...how do I find a or b....I don't know where to begin. How do I write the recurrence relation for this function? Thank you.

Your first recurrence relation is normally used to describe running time of divide-and-conquer algorithms. `a` here shows how many parts you are dividing your data to, `1/b` shows what piece of original data is used in each part, and `f(n)` shows how much time you need on each "level". For example, in QuickSort algorithm you divide your data (array or list) into 2 parts, each of which is exactly half (1/2) of original data, and on each "level" of dividing you need to go through all `n` elements 1 time. So recurrence relation is

``````T(n) = 2T(n/2) + n
``````

(which evaluates to O(n * lg(n))) And in binary search you divide data into 2 parts, but take only 1 of them, and time on each "level" is constant, so relation is:

``````T(n) = T(n/2) + 1
``````

However, your function in C doesn't follow divide-and-conquer strategy. Instead it demonstrates mathematical induction. You define start conditions: if `l` equals `NULL`, then length is 0, and if it `l->next` equals `NULL` (you also define condition for 1 element in list). Then you define a kind of inductive step - you define how to compute function for nth element, if you know function value for (n - 1)th element. So, knowing value of a function for 1st element you can apply this rule and get value for 2nd element, then for 3rd and so on.

So you can see that induction method is recurrence algorithm by the nature. Here we have 2 times to consider. First is a time to compute value at the start point (or end point - it depends on the order you are looking at the list). In your function you just return this value, so it is constant (`C1`). Second is a time to make 1 step. In your function it is also constant (`C2`). Intuitively you should see that execution time of this algorithm will be:

``````T(n) = C1, when n = 1
T(n) = T(n - 1) + C2, when n > 1
``````

Thus, unless `n = 1`, you define time to execute algorithm on `n` element through time to execute it on `n - 1` elements. In BigO notation any constant is defined as `1` and case of 1 element is not considered, so your final recurrence relation is:

``````T(n) = T(n - 1) + 1
``````

(which evaluates to `T(n) = T(n - 1) + 1 = T(n - 2) + 2 = ... = 1 + n`, or `O(n)`)

We are all talking about the efficiency of the algorithms and it depends on input size -basically.

How about the system specifications of current computer that runs the algorithm? does it make any difference to run a different sorting algorithm in a Core 2 Duo 2.6 GHZ, 4 GB RAM-computer or in a P-2, 256 MB RAM-computer?

I am sure that there must be a performance difference. But, I want to know what is the real relationship between algorithms and system specifications...

Yes, it does depend on system specification. One system might be 10 times faster than another, so it will run bubblesort and quicksort on a set of data 10 times faster than the other.

But when you do analysis of algorithms, you often ignore constant factors like that, which is one thing that big-O notation does. So bubblesort is O(n^2) and quicksort is O(nlogn) (in the average case), and that holds no matter how fast your hardware is.

The interesting thing is when you start comparing apples and oranges. If you're running bubblesort on your fast hardware, you may find it's faster than quicksort on the slow hardware -- but only up to a point. Eventually, with a large enough input set, the quicksort on the slow hardware is going to be faster than bubblesort on the fast hardware.

If you want to start making comparisons like that, you need to do two things together: determine algorithmic complexity including the constant factors, and develop a speed model (e.g. how many iterations of a particular loop it can perform per second) for the actual hardware you're running on. One of the interesting things about Knuth's Art of Computer Programming, compared with other books on algorithms, is that he does both, so that for each algorithm he examines, he calculates how many units of execution time it will take for a given size of input on his (mythical) MIX computer. You could then adjust the calculation for faster or slower hardware -- something that big-O notation doesn't help with.