One Paragraph Definitions

Simple and clear definitions to technical concepts. The aim is understanding. Definitions for Stats, Applied Math, and CS Algorithms

[oneparagraphdefinitions-blog]

What is Graph Coloring?

What is Graph Coloring?

In graph theory, given a set of vertices and edges connecting them, the Graph Coloring Problem involves assigning ‘colors’ (labels, numbers) to vertices. These colors have to follow one important rule. No two vertices connected by an edge can be of the same color. (This is the Vertex Coloring problem. Similarly there is an edge coloring problem.)

Why the interest in Graph Coloring problems?

It turns out that quite a number of problems in life (from classroom to sports team scheduling, time-tabling, to Sudoku) can be mapped to be Graph Coloring problems. And therefore, modeling a problem as a Graph Coloring problem and learning to solve them become very valuable skills.

For more details

Wikipedia page on Graph Coloring

http://en.wikipedia.org/wiki/Graph_coloring

Michael Trick’s GC and clique document

http://mat.gsia.cmu.edu/COLOR/color.html

Graph Coloring Resources Page – Joseph Culberson

http://webdocs.cs.ualberta.ca/~joe/Coloring/

[oneparagraphdefinitions-blog]

What is tail recursion?

First, let’s understand “tail calls” in a function, where you call another function at the tail end. A tail recursion is where you do as many calculations first as you can, then call the same function again (recursion). So what’s the big deal? The advantage is that in tail recursion, the “stack” from past calls doesn’t have to be remembered.  We are passing the results up to this point, to the next call.

For more details:

This StackOverflow question has great responses and explanation.

http://stackoverflow.com/questions/33923/what-is-tail-recursion