Duke University’s CPS130 –Introduction to Design and analysis of Algorithms is an undergraduate course. The lecture notes are good for revising basic concepts.
Jeff Erickson’s Algorithm course materials –this is a huge collection of lecture notes, homeworks and exams all in one big document (800+) pages. The tone is conversational, which helps to get a feel of the langauge of the subject. This is a graduate level course.
MIT’s Mathematics for Computer Science – 6.042J, has exhaustive notes on Discrete Mathematics.
Divide and conquer algorithms partition the problem into disjoint subproblems, sovle the subproblems recurisvely and then combine their solutions to solve the original problem.
Dynamic programming algorithms apply when the subproblems overlap –ie., when subproblems share subproblems. Dynamic program solves each subproblem just once and saves the answer, thereby avoiding the recomputing the answer.
DP is typically applied to optimisation problems.
Four steps of DP algorithm:
//Characterise the structure. Define the Value. Compute the Value. Construct.
2013-11-01: Towards a discipline of experimental algorithms by Bernard Moret.
2013-11-01: O-notation considered harmful (use Analytic Combinatorics instead)