# 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.

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

http://world.mathigon.org/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

http://www.cs.princeton.edu/courses/archive/spr10/cos433/mathcs.pdf

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

http://betterexplained.com/articles/easy-permutations-and-combinations/

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

http://csvls.blogspot.com/2010/04/video-lectures-of-discrete-mathematics.html

Khan’s Academy videos on Probability / Linear Algebra