Algorithms

1. Algorithm   algo

properties


ID: 26e0dd8a-352e-4c57-b501-15bdef909d88
CREATED:


edges

– Algorithm - Wikipedia


1.1. Search

properties


ID: 40c56580-d939-4985-be31-ff7499ce7beb
CREATED:


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:


  1. Dijkstra's Algorithm
    properties


    ID: 3d34c56d-8411-4fcd-9fbc-8594a971da50
    CREATED:


    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:
AKA: Random Number Generator


1.2.1. PCG

properties


ID: 3942e7ba-1e6c-4497-9460-853f433cdae0
CREATED:
AKA: Permuted Congruential Generator


edges

– wiki


1.3. Sort

properties


ID: 0205d00e-3ba5-4016-afcf-03f888f5bd18
CREATED:


edges

– Sorting algorithm - Wikipedia


1.3.1. Quicksort

properties


ID: 3b982e80-df78-423a-ba80-444954468057
CREATED:


edges

– wiki


1.4. Selection

properties


ID: 4e47c5ec-17fc-4bef-b7e4-847957be147f
CREATED:


edges

– wiki


1.4.1. Quickselect

properties


ID: 4e5355b6-8f08-44dc-a3c3-799019a9104b
CREATED:


edges

– wiki


1.5. Hash

properties


ID: 0756b187-0c00-434e-98a5-75e06cb3f01b
CREATED:


edges

– Hash function - Wikipedia


1.5.1. Hopscotch hashing

properties


ID: 2dfa085f-d853-4e13-a6cf-654d0f96b81f
CREATED:


edges

– Hopscotch hashing - Wikipedia


1.5.2. Perfect Hash

properties


ID: 1bf44929-d8bf-40bb-b475-94ca1c631497
CREATED:


edges

– wiki


1.6. Compression

properties


ID: c49d25f8-f2c5-462e-9742-cacc3796da12
CREATED:


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:


edges

– wiki


  1. Lempel-Ziv
    properties


    ID: c2198cb0-16f1-4df5-9671-6fc366116589
    CREATED:
    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:


1.7.1. Nagle's Algorithm

properties


ID: c6dd57ac-90ab-475e-bdff-70698ab5a679
CREATED:


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:


edges

– wiki


1.8. Cipher

properties


ID: 2f14f7d9-a306-44ba-b879-5c211f189f91
CREATED:


1.8.1. ROT13

properties


ID: 364ba4c0-2ad9-4965-ade3-301efb3406d3
CREATED:


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:


1.9.1. Schonhage-Strassen

properties


ID: f3d1f7de-40d8-4db4-b80d-4139ae2ab507
CREATED:


edges

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


A classical technique for multiplying large integers.