# Algorithms

- Page: https://shared.btbytes.com/p/algorithms
- Date: 2020-01-05
- Tags: books, algorithms, computer-science, data-structures

[Algorithm Visualizer](http://algorithm-visualizer.org/)

## Success stories

* [14,000x Speedup - James Hiebert's Blog](http://james.hiebert.name/blog/work/2015/09/14/CS-FTW.html); Sep 2015; [HN
](https://news.ycombinator.com/item?id=24764605)
* [Applying Textbook Data Structures for Real Life Wins - Heap](https://heap.io/blog/engineering/applying-textbook-data-structures-for-real-life-wins)


## Course Pages with Lecture notes

Duke University's [CPS130](http://www.cs.duke.edu/courses/summer02/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](http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/) --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](http://web.archive.org/web/20100125201057/http://courses.csail.mit.edu/6.042/spring10/)

Stanford [CS 168: The Modern Algorithmic Toolbox, Spring 2023](https://web.stanford.edu/class/cs168/index.html) by [Gregory Valiant](http://theory.stanford.edu/~valiant/); see [Tim Roughgarden's Lecture Notes](https://timroughgarden.org/notes.html)

[Cambridge - Algorithms – Course materials](https://www.cl.cam.ac.uk/teaching/2021/Algorithms/materials.html)


## Video Lectures

- [Algorithms](http://www.youtube.com/playlist?list=PL01A89F4E9E5F3ADE&feature=plcp) by Omkar Deshpande on YouTube. Detailed explanation of concepts.
- [Abdul Bari - YouTube](https://www.youtube.com/@abdul_bari/featured) lectures on Algorithms.
- [Pavel Mavrin](https://www.youtube.com/watch?v=oWgLjhM-6XE&list=PLrS21S1jm43igE57Ye_edwds_iL7ZOAG4); "A competitive programming world champion took time to record *checks notes* ~90 hours of video content in the most accessible way you'll ever see! " -- [via Dmitrii Kovanikov](https://x.com/ChShersh/status/1881074346220978642)

## Articles

- [Algorithms & Data Structures Series – OmarElGabry’s Blog](https://medium.com/omarelgabrys-blog/algorithms-data-structures-series-85ec94eb8aff#.jsj1tjni5)
- [Big O](https://samwho.dev/big-o/) -- A **visual** story that covers "4 frequently-used categories of big O notation: **constant**, **logarithmic**, **linear**, and **quadratic**"

## Interviews

- [500 Data Structures and Algorithms practice problems and their solutions](https://medium.com/@kingrayhan/500-data-structures-and-algorithms-practice-problems-and-their-solutions-b45a83d803f0)


## Books

### Free

* [Algorithms](http://www.cs.berkeley.edu/~vazirani/algorithms.html)
    by Vazirani et. al
* [Lisp, the Universe and Everything: "Programming Algorithms" Book](http://lisp-univ-etc.blogspot.com/2019/07/programming-algorithms-book.html) Work in progress (as of Jan 2020). All the algorithms and data structures are explained using Lisp.
* [Algorithms and Data Structures - The Basic Toolbox](https://people.mpi-inf.mpg.de/~mehlhorn/ftp/Mehlhorn-Sanders-Toolbox.pdf) by Kurt Mehlhorn and Peter Sanders. [PDF]
* [Algorithms for Modern Hardware - Algorithmica](https://en.algorithmica.org/hpc/)  -- 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 and Zhang 2023](https://arxiv.org/abs/2312.11543)) [PDF](https://arxiv.org/pdf/2312.11543.pdf) <q>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.</q>

### Non-Free

-   [Introduction to Algorithms aka
    CLRS](http://www.amazon.com/gp/product/0262033844/ref=as_li_ss_tl?ie=UTF8&tag=btbytes-20&linkCode=as2&camp=1789&creative=390957&creativeASIN=0262033844)
    (affl.) -- the standard textbook for this course in large percentage
    of undergraduate and graduate classes. The book weighs a ton and
    looks intimidating, but is quite approachable in practice.
* [Grokking Algorithms: An illustrated guide for programmers and other curious people](https://smile.amazon.com/Grokking-Algorithms-illustrated-programmers-curious/dp/1617292230/) by Aditya Bhargava


Topics
------

### Preliminaries

### Probability and Randomness

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


#### To Read

2013-11-01: Towards a discipline of experimental algorithms by [Bernard
Moret](http://www.cs.unm.edu/~moret/).

2013-11-01: [O-notation considered harmful (use Analytic Combinatorics
instead)](http://jng.imagine27.com/index.php/2013-02-10-121226_analytic-combinatorics-is-better-o-nation-considered-harmful.html)

## References

- Tuzhilin, Zhang (2023). [Graphs, Algorithms and Applications](https://arxiv.org/abs/2312.11543).