Algorithms

1. Algorithm   algo

properties ID: 26e0dd8a-352e-4c57-b501-15bdef909d88
CREATED: <2025-02-28 Fri 17:39>
edges

– Algorithm - Wikipedia


1.1. Search

properties ID: 40c56580-d939-4985-be31-ff7499ce7beb
CREATED: <2025-10-26 Sun 20:41>

1.1.1. Binary Search   search

properties ID: c963428d-b5b5-4a9b-9912-ab8b17e3cf46
edges

– wiki


  • A very common algorithm used to find the index of a specific item in a

sorted array.

  • Array must be sorted
  • Executes in logarithmic time
  • Faster than linear search (except for very small arrays)
  • Can be applied easily in many situations
  • There are many variations of binary search such as fractional cascading and exponential search
  • Many data structures provide a better overall design for fast optimal searches, such as Hash Tables
  • Binary Search Tutorials & Notes | Algorithms | HackerEarth

1.1.2. Graph Search

properties ID: 16ca04ab-5406-4460-90a3-4d770babfdf6
CREATED: <2025-12-31 Wed 20:55>
  1. Dijkstra's Algorithm
    properties ID: 3d34c56d-8411-4fcd-9fbc-8594a971da50
    CREATED: <2025-12-31 Wed 20:55>
    edges

    – wiki
    <- Fibonacci Heap


    • shortest path on weighted graph
    • Fredman & Tarjan 1984 proposed a Fibonacci heap priority queue to optimize the running time complexity to O(|E|+|V|log|V|). This is asymptotically the fastest known single-source shortest-path algorithm for arbitrary directed graphs with unbounded non-negative weights. However, specialized cases (such as bounded/integer weights, directed acyclic graphs etc.) can be improved further. If preprocessing is allowed, algorithms such as contraction hierarchies can be up to seven orders of magnitude faster.
    • Dijkstra's algorithm is commonly used on graphs where the edge weights are positive integers or real numbers. It can be generalized to any graph where the edge weights are partially ordered, provided the subsequent labels (a subsequent label is produced when traversing an edge) are monotonically non-decreasing.

1.2. RNG

properties ID: 1e99acf3-3bf4-49e0-ab2c-57c35341a7ad
CREATED: <2025-10-26 Sun 20:42>
AKA: Random Number Generator

1.2.1. PCG

properties ID: 3942e7ba-1e6c-4497-9460-853f433cdae0
CREATED: <2025-10-26 Sun 20:42>
AKA: Permuted Congruential Generator
edges

– wiki


1.3. Sort

properties ID: 0205d00e-3ba5-4016-afcf-03f888f5bd18
CREATED: <2025-02-28 Fri 18:20>
edges

– Sorting algorithm - Wikipedia


1.3.1. Quicksort

properties ID: 3b982e80-df78-423a-ba80-444954468057
CREATED: <2025-10-26 Sun 20:45>
edges

– wiki


1.4. Selection

properties ID: 4e47c5ec-17fc-4bef-b7e4-847957be147f
CREATED: <2025-10-26 Sun 20:45>
edges

– wiki


1.4.1. Quickselect

properties ID: 4e5355b6-8f08-44dc-a3c3-799019a9104b
CREATED: <2025-10-26 Sun 20:45>
edges

– wiki


1.5. Hash

properties ID: 0756b187-0c00-434e-98a5-75e06cb3f01b
CREATED: <2025-02-28 Fri 18:20>
edges

– Hash function - Wikipedia


1.5.1. Hopscotch hashing

properties ID: 2dfa085f-d853-4e13-a6cf-654d0f96b81f
CREATED: <2025-02-24 Mon 21:34>
edges

– Hopscotch hashing - Wikipedia


1.5.2. Perfect Hash

properties ID: 1bf44929-d8bf-40bb-b475-94ca1c631497
CREATED: <2026-01-05 Mon 18:37>
edges

– wiki


1.6. Compression

properties ID: c49d25f8-f2c5-462e-9742-cacc3796da12
CREATED: <2025-10-16 Thu 18:19>
edges

– wiki


1.6.1. Lubachevsky–Stillinger :granular-flow:

properties ID: 7e986f85-e6ca-4f76-b667-bea7fe128b8b

Lubachevsky-Stillinger (compression) algorithm (LS algorithm, LSA, or LS protocol) is a numerical procedure suggested by F. H. Stillinger and B.D. Lubachevsky that simulates or imitates a physical process of compressing an assembly of hard particles. As the LSA may need thousands of arithmetic operations even for a few particles, it is usually carried out on a computer.

An acoustic phenomena of interest: Singing sand

1.6.2. Lossless Compression

properties ID: 299246fd-5153-4fc9-a8b8-0ce0fd097a88
CREATED: <2025-10-16 Thu 18:20>
edges

– wiki


  1. Lempel-Ziv
    properties ID: c2198cb0-16f1-4df5-9671-6fc366116589
    CREATED: <2025-10-16 Thu 18:17>
    AKA: LZ1 LZ2 LZ77 LZ78
    edges

    – wiki
    <- DEFLATE


    Published in papers by Abraham Lempel and Jacob Ziv in 1977 and 1978.

    • form the basis for many variants - LZW LZSS LZMA and more
    • also serve as basis of compression schemes of GIF and DEFLATE
    • uses a sliding window over previous characters
    • LZ1 and LZ2 are both theoretically dictionary coders

1.7. Congestion Control

properties ID: 6c336300-0bf2-4370-86e4-d670c079032a
CREATED: <2025-10-18 Sat 16:57>

1.7.1. Nagle's Algorithm

properties ID: c6dd57ac-90ab-475e-bdff-70698ab5a679
CREATED: <2025-10-18 Sat 16:58>
edges

– wiki


A means of improving efficiency of TCP networks by reducing the number of packets that need to be sent. Defined by John Nagle while working for Ford Aerospace. Published in 1984 as RFC 896.

Especially useful in eliminating overhead in protocols such as telnet.

  • Can be dynamically toggled based on platform support and sockopts. In CL see the nodelay keyword arg to USOCKET:SOCKET-CONNECT.

1.7.2. Round Robin

properties ID: a4b11c78-468b-40d4-ac37-9ddfc804a572
CREATED: <2026-01-05 Mon 18:39>
edges

– wiki


1.8. Cipher

properties ID: 2f14f7d9-a306-44ba-b879-5c211f189f91
CREATED: <2025-10-26 Sun 20:44>

1.8.1. ROT13

properties ID: 364ba4c0-2ad9-4965-ade3-301efb3406d3
CREATED: <2025-10-26 Sun 20:44>
edges

– wiki


A very simple, symmetrical substition cipher that shifts a character by 13 positions. Since the standard alphabet has 26 characters, this operation is its own inverse.

  • The canonical example of weak encryption.

1.9. Multiplication

properties ID: 36fa7337-5b6a-4f5c-8b53-75b075f9803d
CREATED: <2026-04-12 Sun 15:15>

1.9.1. Schonhage-Strassen

properties ID: f3d1f7de-40d8-4db4-b80d-4139ae2ab507
CREATED: <2026-04-12 Sun 15:16>
edges

– Schönhage–Strassen Algorithm: A Quick Overview | Every Algorithm


A classical technique for multiplying large integers.