algorithms.md

Algorithms

• See also [solutions]

• MIT Open Courseware Introduction to Algorithms 2020 #MITOpenCourseWare

• Wikipedia: List of algorithms

  • Hundreds of important computer science algorithms
  • Of note
    • [Sorting]
      • bubble sort
      • quick sort
    • [nagles]
    • Clock synchronisation
    • [fourier] transform
    • [Compression]
      • Huffman
    • [Parity] (reconstruction) Hammering?
      • [reed-solomon] [error-correction]
    • Lexical analysis
    • [Hash]
    • geometric
      • Line clipping
      • contour lines
      • [collision-detection]
    • doomsday algorithm Day of the week - conway
    • Dijstra shortest path
    • [dynamic-programming]
    • [levenshtein-distance]
    • substring search
    • Bayes Theorem - graph of probabilitys
    • [polygon] drawing and crossing
    • [line-drawing]
    • [wave-function-collapse]
    • Challenging algorithms and data structures every programmer should try
      • Topological sort - used for spreadsheet cell evaluation order
      • Recursive descent parsing (compilers/interpreters)
      • Myers string diff (algorithm for git diff)
      • Bloom filter (big hash)
      • Piece table (used by text editors to store text as edits)
      • Splay tree (binary tree with most accessed closer to the root)
    • Geometry
      • Geometry Central

        • C++ library of data structures and algorithms for geometry processing, with a particular focus on surface meshes.

    • [graphics]
      • [line-drawing]
      • Filling polygons
    • Streams
      • Estimate distinct entries
        • Computer Scientists Invent an Efficient New Way to Count
    • [markov-chains]

• Nine algorithms that changed the future: the ingenious ideas that drive today's computers MacCormick, John 2011

  • Ingenious ideas that drive today's computers
    • vlebooks
  • Search engine indexing
  • [pagerank]
  • Public Key Cryptography
  • Error-Correcting Codes
  • Pattern Recondition
  • Data Compression
  • Database (Consistency)
  • Digital Signatures

• The Most Important Algorithms

  • A* search algorithm
    • A* Tricks for Videogame Path Finding
    • Introduction to the A* Algorithm
  • Beam Search
  • Binary search
  • Branch and bound
  • Buchberger's algorithm
  • Data compression
  • Diffie-Hellman key exchange
  • Dijkstra's algorithm
  • Discrete differentiation
  • Dynamic programming
  • Euclidean algorithm
  • Expectation-maximization algorithm (EM-Training)
  • Fast [fourier] transform [fft]
  • Gradient descent
  • Hashing
  • ... more

• Algorithms for Modern Processor Architectures

  • [cpu]

• khanacademy.org Unit: Algorithms

  • Lots of interactive sorting algorithms

• GeekForGeeks Algorithms

  • Analysis of Algorithms
  • Searching and Sorting
  • Greedy Algorithms
  • Dynamic Programming
  • Pattern Searching
  • Other String Algorithms
  • Backtracking
  • Divide and Conquer
  • Geometric Algorithms
  • Mathematical Algorithms
  • Bit Algorithms
  • Graph Algorithms
  • Randomized Algorithms
  • Branch and Bound
  • Quizzes on Algorithms
  • Misc

• Awesome Algorithms Education Awesome

  • A curated list to learning and practicing about algorithm.

• Algorithms by Jeff Erickson - June 2019 - Free eBook + lecture notes

• github.com/trekhleb/javascript-algorithms - Algorithms and data structures implemented in JavaScript with explanations and links to further readings

• rosettacode.org

  • Rosetta Code is a programming chrestomathy site. The idea is to present solutions to the same task in as many different languages as possible, to demonstrate how languages are similar and different, and to aid a person with a grounding in one approach to a problem in learning another.

• Grokking Algorithms - An illustrated guide for programmers and other curious people - Aditya Bhargava 2015

• algorithm-visualizer.org

  • LOADS of interesting algorithms animated with step buttons

• VisuAlgo.net - visualising data structures and algorithms through animation

• Visualizing Algorithms - beautiful visual sorts and maze searches

• Prim’s Algorithm III visuisation

• Hacker Earth - Programming Tutorials and Practice Problems

  • Lots of algorithms, visualisations and live coding
  • HackerEarth/Practice/Bubblesort/Visuliser
  • [data-structures]
  • [maths]

dean to binary dean to hex

• Linked lists, pointer tricks and good taste
  • In a 2016 TED interview (14:10) Linus Torvalds speaks about what he considers good taste in coding

AQA A’Level Hand tracing algorithms Video - Craig and Dave

• Path-finding Algorithm-Visualizer

  • https://github.com/Walker-TW/Algorithm-Visualizer

• PGM-index

  • The Piecewise Geometric Model index (PGM-index) is a data structure that enables fast lookup, predecessor, range searches and updates in arrays of billions of items using orders of magnitude less space than traditional indexes while providing the same worst-case query time guarantees
  • Papers + Sourcecode

• vscode: Bracket pair colorization 10,000x faster

  • tree incrementally edited
  • js batches to not block ui thread (on inital load or /* insert)
  • The feature can be enabled by adding the setting "editor.bracketPairColorization.enabled": true

• 14,000x Speedup a.k.a. Computer Science For the Win

Background Blur Features in Google Meet, Powered by Web ML

• [raytracing]
• [demoscene]

Sorting

[sorting]

Sort dances (youtube unplugged activities)

QuickSort MergeSort RadixSort InsertionSort

Kind of realted

• The Skyline algorithm for packing 2D rectangles
  • Packing rectangles efficiently (like tetris)

Search

• Tree
  • Depth first search
  • Breath first search
• Graph
  • Negative-Weight Single-Source Shortest Paths in Near-linear Time

Simple things that are actually hard

• The Problem with Time & Timezones - Computerphile tom scott 10min

• Foldable Words

  • Given a sequence of words - what other words/phrases can be made (not anagrams, these must be in order)
  • itsapleasuretoserveyou ==> I love you

• Gradient-Free-Optimizers

• Maze generation visualization - Maze generation visualization

  • demo

Spelling

• Rebuilding the spellchecker, pt.2: Just look in the dictionary, they said!
  • hunspell - behind most open source spellchecker
  • spylls - Pure Python spell-checker, (almost) full port of Hunspell
• How Unix Spell Ran in 64kB RAM

  • How do you fit a 250kB dictionary in 64kB of RAM and still perform fast lookups? For reference, even with modern compression techniques like gzip -9, you can't compress this file below 85kB.

  • For fast lookups, he initially used a [bloom-filters] perhaps one of its first production uses.

  • When the dictionary grew to 30,000 words, the Bloom filter approach became impractical, leading to innovative hash compression techniques.

  • They computed that 27-bit hash codes would keep collision probability acceptably low, but needed compression.