# Algorithms

Created: by Pradeep GowdaUpdated:Dec 20, 2023

Algorithm Visualizer

## Course Pages with Lecture notes

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 – 2010

## Books

### Free

• Algorithms by Vazirani et. al
• Lisp, the Universe and Everything: “Programming Algorithms” Book Work in progress (as of Jan 2020). All the algorithms and data structures are explained using Lisp.
• Algorithms and Data Structures - The Basic Toolbox by Kurt Mehlhorn and Peter Sanders. [PDF]
• Algorithms for Modern Hardware - Algorithmica – Its intended audience is everyone from performance engineers and practical algorithm researchers to undergraduate computer science students who have just finished an advanced algorithms course and want to learn more practical ways to speed up a program than by going from `O(nlog⁡n)O(nlogn)` to `O(nlog⁡log⁡n)O(nloglogn)`.
• Tuzhilin, Mikhail, and Dong Zhang. “Graphs, algorithms and applications,” 2023. http://arxiv.org/abs/2312.11543. PDF This book is result of Sino-Russian collaboration. It collects the lectures which were given to students of mathematics departments of Moscow State University and Peking University about graph theory and its applications. The book’s narrative is sequential: earlier theorems and definitions are used in later material.

## Topics

### Dynamic Programming

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:

1. Characterise the structure of an optimal solution.
2. Recursively define the value of an optimal solution
3. COmpute the value of the optimal solution, typicall bottom-up.
4. Construct an optimal solution from computed info.

//Characterise the structure. Define the Value. Compute the Value. Construct.