Discrete Mathematics


Do discrete math books looks boring?  With no real world applications and too abstract. I promise that after reading this post, you will love discrete math



Mathematical Induction This principle is simple. Look at falling dominoes here http://en.wikipedia.org/wiki/Mathematical_induction. The inductive step is important. If some statement holds true for number N implies that it holds true for N+1, it follows that the statement holds true for every number.


Looks simple ? Ready for some advanced exercises ?http://server.math.uoc.gr/~tzanakis/Courses/NumberTheory/MathInduction.pdf

Pigeon Hole Principle
What is the relationship between  Hashtables, Pigeonholes, and Birthdays
Pigeon hole principle looks very simple- If you try to put 6 pigeons in 5 holes, one will inevitably be left out.
But its applications are varied. For example, this birthday problem and also in finding collisions in hashtables
In a typical classroom of 30 students, what are the odds that two of the students will have the same birthday?

Graph Theory



Originated by Euler’s method to determine whether crossing 7 bridges exactly once possible. Has wonderful applications. 

Look here for list of applications of graph theory http://jwilson.coe.uga.edu/emat6680/yamaguchi/emat6690/essay1/gt.html?dhiti=1


See http://eprints.nuim.ie/2702/1/FO_Mathematics.pdf for such beautiful proofs including ones by Gauss

 Mathematics for Computer Science

 Prof.Leighton at MIT (founder of Akamai ) explains the basics of mathematics – Induction, Number theory, Modular arithmetic


The examples are engaging. For e.g, one is from a movie – Bruce is given a 3-gallon jug and a 6-gallon jug and must

measure out exactly 4 gallons.  They also explain how number theory principles are used for securing your data – namely the foundations of RSA cryptography. They give nice and practical examples where graphs are used to model

Data Structures Each vertex represents a data object. There is a directed edge from one
object to another if the first contains a pointer or reference to the second.
Attraction Each vertex represents a person, and each edge represents a romantic attraction.
The graph could be directed to model the unfortunate asymmetries.
Airline Connections Each vertex represents an airport. If there is a direct flight between
two airports, then there is an edge between the corresponding vertices. These
graphs often appear in airline magazines.
TheWeb Each vertex represents a web page. Directed edges between vertices represent


Article – Permutations and Combination



Mathematics for Algorithm analysis

Analysis of algorithms is explained by Peteris


It points to lecture by Erik Demaine. The second half of the lecture is devoted to solving recurrence equations. Three methods are presented:

Substitution method,
Recursion-tree method, and
The Master method.

Mathematics for Programmers

 How much mathematics should a programmer know.  What is the right way to learn math.  Steve Yegge writes here

Knowing even a little of the right kinds of math can enable you do write some pretty interesting programs that would otherwise be too hard. Nobody knows all of math, not even the best mathematicians.


video lectures


Khan’s Academy videos on Probability / Linear Algebra




Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s