algorithms
#define algorithms: \
I----------------------------------------------------------------------------------------------------\
I----------------------------------------------------------------------------------------------------\
I----------------------------------------------------------------------------------------------------\
I /$$$$$$ /$$ /$$ /$$ /$$ \
I /$$__ $$| $$ |__/ | $$ | $$ \
I | $$ \ $$| $$ /$$$$$$ /$$$$$$ /$$$$$$ /$$ /$$$$$$ | $$$$$$$ /$$$$$$/$$$$ /$$$$$$$ \
I | $$$$$$$$| $$ /$$__ $$ /$$__ $$ /$$__ $$| $$|_ $$_/ | $$__ $$| $$_ $$_ $$ /$$_____/ \
I | $$__ $$| $$| $$ \ $$| $$ \ $$| $$ \__/| $$ | $$ | $$ \ $$| $$ \ $$ \ $$| $$$$$$ \
I | $$ | $$| $$| $$ | $$| $$ | $$| $$ | $$ | $$ /$$| $$ | $$| $$ | $$ | $$ \____ $$ \
I | $$ | $$| $$| $$$$$$$| $$$$$$/| $$ | $$ | $$$$/| $$ | $$| $$ | $$ | $$ /$$$$$$$/ \
I |__/ |__/|__/ \____ $$ \______/ |__/ |__/ \___/ |__/ |__/|__/ |__/ |__/|_______/ \
I /$$ \ $$ \
I | $$$$$$/ \
I \______/ \
I----------------------------------------------------------------------------------------------------\
I----------------------------------------------------------------------------------------------------\
I----------------------------------------------------------------------------------------------------I
"Gamedev"
Pseudo_code:
• pseudo-code is a rough approximation of a imperative language grammar
• used for describing algorithms without bias towards any concrete language
• the closest concrete language that resembles pseudo-code is COBOL 60,
this fact might be important for properly highlighting pseudo-code in documents
• all keywords are written in all CAPS, making it easier to read without syntax highlighting
• since it cannot be compiled, the writer can focus on the meat of the algorithm,
instead of defining all required subcomponents
• irrelevant functions or complex conditions explained elsewhere
could be abstracted as natural language
• due to its nature, there are numerous dialects
— common dialectic changes:
• assignment using "=" or ":="
• ALGOL/C/C++/shell style comments
• reversed block end keyword order ("END FUNCTION" <-> "FUNCTION END")
• reversed end keywords ("END IF" <-> "FI")
• often translated to the mother tongue of the audience
• its also not uncommon that the keywords are kept intact
COMMENT conventional English pseudo-code
FUNCTION example (my_parameter : integer)
IF my_parameter = 1 THEN
RETURN TRUE
END IF
RETURN FALSE
END FUNCTION
i : integer
i := 2
CALL example i
COMMENT other keywords:
PROCEDURE
LOOP
WHILE
FOR IN
INPUT
OUTPUT
MEGJEGYZÉS Magyar pseudo-code megfelelője a fenti blokknak
FÜGGVÉNY példa (paraméter : egész)
HA paraméter = 1 AKKOR
VISSZATÉR IGAZ
VÉGE HA
VISSZATÉR HAMIS
VÉGE FÜGGVÉNY
i : egész
i := 2
HÍVÁS példa i
MEGJEGYZÉS további kulcs szavak
PRECEDÚRA
CIKLUS
AMÍG
BEOLVAS
KIÍR
—
• pseudo-code has the flaw that it cannot be experimented on by beginners
— all code below is written in C23:
• inclusion of <iso646> is always presumed
>all code examples BELOW are written in valid Nim |see AT "/Nim"
— how nim differs from pseudo code:
• pass-ing an array of arbitrary size is done with "varargs";
just mentally replace it with "array"
Flow_charts: Flow_charts:
• diagrammatic representation of an algorithm
• very useful for visualizing control
○ struct
[start][arrow]([step][arrow]*)[end]
○ components
flowline : connects any (with a few exceptions) 2 blocks; one directional;
symbolizes control flow;
some form of an arrow;
multiple flowlines directed to the same block shall intersect
○ blocks
start : where execution starts; no flowlines lead into it
end : where execution terminates; no flowlines lead out of it
process : changes some internal state {variable assignment}; a normal instruction
logic : conditional decision; most commonly binary
input/output : entering data or displaying data
function : jump to predefined process (the start of another flowchart)
○ symbols
ANSI_and_ISO:
start:
,,,,,,,,,
.' '.
| START |
'. .'
^^^^^^^^^
end:
,,,,,,,,,
.' '.
| END |
'. .'
^^^^^^^^^
process:
+-------------+
| [...] |
+-------------+
input_or_output:
--------------
/ [...] /
--------------
logic:
A
/ \
/ \
/ \
| [...] |
\ /
\ /
\ /
V
function:
+-------------+
| | [...] | |
+-------------+
Computability: Computability:
• a bool property of all problems
• if a problem could not be decided by any possible algorithm,
its said to be incomputable
• its formally accepted that such, incomputable program does exist,
proven by the Halting problem
• its the decision problem applied to programming
Halting_problem:
• assume bool function HALT('x') can compute whether 'x' is computable or not
x ┌──────────┐ Y/N
-> │ HALT │ ->
└──────────┘
• we can construct a machine which depending on the output of HALT:
if true : while(true){}
if false : false ┌───┐
x ┌──────────┐ Y/N ┌───────┘ ∞ │ N
-> │ HALT │ -> -> │ LOL │ ->
└──────────┘ └───────────┘
• call this DIAGONAL
┏━━━━━━━━━━━━┓
┃ DIAGONAL ┃
x ┃┌───┐ ┌───┐┃ Y/N
-> ┃│ H │->│ L │┃ ->
┃└───┘ └───┘┃
┗━━━━━━━━━━━━┛
• lets feed it itself
┏━━━━━━━━━━━━┓
┃ DIAGONAL ┃
DIAGONAL ┃┌───┐ ┌───┐┃ ?
-> ┃│ H │->│ L │┃ ->
┃└───┘ └───┘┃
┗━━━━━━━━━━━━┛
if HALT concludes that DIAGONAL will halt
— > HALT returns true
— > L enters an infinite loop
— > DIAGONAL never halts
if HALT concludes that DIAGONAL will not halt
— > HALT returns false
— > L returns false
— > DIAGONAL did halt
• in both possibilities HALT is wrong
• therefor no such HALT can be built that is always correct
• therefor HALT is impossible
• therefor there is at least 1 problem that cannot be computed
Complexity: Complexity:
Computational:
• describes how the number of computational steps increase
depending on the size of the input
• doesnt actually tell one "how fast" an algorithm is
{linear and sentinel search both have the same complexity}
Oh_notation:
• "O notation"
• classifies worst case computational complexity
(maximum steps taken) with constants ignored
— Big-Oh:
if f(n) <= c * g(n); then
f(n) := O(g(n))
— Little-Oh:
if f(n) < c * g(n); then
f(n) := o(g(n))
Classes:
• set of machines of languages using some model grouped together
by their common limit on a specific resource while performing computation
• set builder notation
○
P ⊆ NP ⊆ PSPACE ⊆ EXP ⊆ NEXP ⊆ DTIME ⊆ NTIME
DTIME:
DTIME(f(n)) := { P : P will be solved under O(f(n)) on a deterministic Turing Machine }
• "Deterministic TIME"
• its a function, return-ing sets of languages which can be solved on a Turing machine
under the argument function applied to the Big-Oh notation
• practically the Big-Oh notation interpreted as a set in the context of Turing Machines
• such f(n) exists, that the result entails all deterministic problems
• the main use of DTIME() is to define (other) complex-ity class-es with
P:
P := Uₖ DTIME(n^k)
• "Polinominal time"
• its easiest to tell whether an algorithm is P, by confirming that each of its atomic steps are P
• "reasonably" solvable problems all belong here; ie. there is an actual strategy
{ path finding
matrix multiplication
}
NTIME:
NTIME(f(n)) := { P : P will be solved under O(f(n)) on a non-deterministic Turing Machine }
• "Non-deterministic TIME"
NP:
NP := Uₖ NTIME(n^k)
• "Nondeterministic Polinominal time"
• no solving strategy is know; each possible solution must be tried
• verifying a solution can be done in polynomial time
• can be solved polinominally on a non-deterministic Turing Machine
• many algorithms belonging to NP are unsolved problems; there is no formal proof that there is no P solution
• there is no formal proof that NP is not equal to P
{
hamiltonian path
independent set
traveling salesman
sodoku
}
NP_complete:
• every language that is an element of NP, to which every other element of NP is polynominal time Karp reducible
• a solution in P could only exist if P == NP
NP_hard:
• a problem at least as hard has the hardest problem in NP (an NP-complete one)
• if any NP hard problems were to be solved, it would prove that P == NP
• is not necessary an element of NP
coNP: _
coNP := {L : L ∈ P}
• not equal to complementer NP
• could be equal to NP
if P == NP; then
coNP == NP == P
if NP != coNP; then
P != NP
{ tautology
}
EXP:
EXP := Uₖ DTIME(2^n^k)
• "EXPonential time"
NEXP:
NEXP := Uₖ NTIME(2^n^k)
• "Non-deterministic EXPonential time"
P_VS_NP_problem:
• "is coming up with a solution inherently harder than checking it?"
• famous mathematical problem
• unsolved
• one of the Millennium Prize Problems (there is 1'000'000 USD)
• for example, is composing "Das Wohltemperierte Klavier Book 1" inherently harder,
than appreciating it?
— if P turns out to equal NP:
• all encryption must be thrown out, never to be replaced
• we get the answer to the Ultimate Question of Life,
The Universe, and Everything
DSPACE:
DSPACE(f(n)) := {P : P always halts on all inputs of length n, using a maximum of f(n) cells on a deterministic Turing Machine}
DTIME(t(n)) ⊆ DSPACE(t(n))
• "Deterministic SPACE"
NSPACE:
NSPACE(f(n)) := {P : P always halts on all inputs of length n, using a maximum of f(n) cells on a non-deterministic Turing Machine}
NSPACE(f(n)) ⊆ DSPACE(f(n)²)
• "Non-deterministic SPACE"
• the maximum of any path, not the maximum of all paths added
Swap: Swap:
• to swap the values of 2 variables another one of is required as a buffer
• the swap variable holds the value of one variable while its value gets overwritten by the others
| NAME | VALUE |
//------------------------ Initial state
[ VARIABLE 1 ] = 5 ;
[ VARIABLE 2 ] = 12 ;
[ SWAP ] = N/A ;
//------------------------ End state and steps
[ VARIABLE 1 ] = 5 ; <--.--.
\ \
II. | \
/ |
[ VARIABLE 2 ] = 12 ; <--. | I.
\ |
III. | /
/ /
[ SWAP ] = 5 ; <-----'
//-- Steps Broken Down --
//------------------------ Storing the first value for later use
[ VARIABLE 1 ] = 5 ; ---.
\
\
|
[ VARIABLE 2 ] = 12 ; |
|
/
/
[ SWAP ] = 5 ; <--'
//------------------------ Over writing VARIABLE 1 with VARIABLE 2; now '5' can only be retrieved from SWAP
[ VARIABLE 1 ] = 12 ; <--.
\
|
/
[ VARIABLE 2 ] = 12 ; ---'
[ SWAP ] = 5 ;
//------------------------ Over writing VARIABLE 2 with SWAP; the swap is completed; SWAP can be discarded or repurposed
[ VARIABLE 1 ] = 12 ;
[ VARIABLE 2 ] = 12 ; <--.
\
|
/
[ SWAP ] = 5 ; ---'
// function
template<typename T> void swap(T& t1, T& t2){
T swp = t1;
t1 = t2;
t2 = swp;
}
// called as
swap([a], [b])
— arithmetic:
• spares us from using a swap
• known interview question
— basically only works on ints
• floats could loose precision;
• variadic strings may resize
• the Lord may save us from attempting this on C strings
void swap(int &a, int &b) {
a = a + b;
b = a - b;
a = a - b;
}
DATA_STRUCTURE_BASED: DATA_STRUCTURE_BASED:
○ Example data used in this section
{
var myArray = @[34, 23, 78, 41, 7, 87, 52, 36, 29, 42]
var myArray2 = @[34, 12, 31, 76, 41, 43, 71, 23, 36, 91, 92, 42]
var sortedArray = @[1, 2, 3, 6, 8, 10, 13, 14, 17, 20]
}
{
int myArray[] = {34, 23, 78, 41, 7, 87, 52, 36, 29, 42};
int myArray2[] = {34, 12, 31, 76, 41, 43, 71, 23, 36, 91, 92, 42};
int sortedArray[] = {1, 2, 3, 6, 8, 10, 13, 14, 17, 20};
}
Summary: Summary:
• "How much?"
○ given
• an array containing <typename> elements
• <typename> has
○ algorithm
{
int summary(int* a, int n){
int sum = 0;
int i = 0;
while(i < n){
sum = sum + a[i];
++i;
}
return sum;
}
summary(myArray, len(myArray))
429
}
Selection: Selection:
• "Which are?"
• one wants to get (ie. copy) all the elements from an array which has some property
○ given
• 2 arrays containing <typename> elements
• <typename> has
○ algorithm
{ proc k(a, b : varargs<int>; n : int) : int =
}
Counting: Counting:
• "Megszámlálás"^HU
• "How many?"
• one wants to know how many elements are in an array which has some property
○ given
• an arrays containing <typename> elements
• <typename> has
○ algorithm
{ proc k(a : varargs<int>; n : int) : int =
}
Minmax_selection: Minmax_selection:
• "Minimum, maxiumum kiválasztás"^HU
• "Which is?"
• one wants to know what is the largest/smallest element of an array
○ given
• an arrays containing <typename> elements
• <typename> has
○ algorithm
1. initialize a variable
○ type: same as <typename>
○ purpose: to hold the desired value
○ default value: one that will return false when tested against any element of the array
{if one is looking for the max value, choose a number which will be smaller
than any possible value in array;
for example:
if you know array contains only positive numbers then -1 will do
if you know array contains a wide range of values then the smallest possible
represntable in <typename> is your best bet
if NaN is a possible value of <typename> and NaN > [value] is always false
then its always gonna be safe
}
Descision: Descision:
• "eldöntés"^HU
• "Is there?"
• "any"
• checking a data structure for an arbitrary condition
// for simplicity, the condition is an element being equal to a target value
bool any(int * array, int target, int n) {
for (int i = 0; i < n; i++) {
if (array[i] == target) {
// NOTE: if this weren't a function and we were setting
// a result variable directly,
// it would be crucial to `break` to avoid redundant checks
return true;
}
}
return false;
}
Intersection: Intersection:
• "Metszet"^HU
• creation of a set from the common elements of 2 sets
{
proc intersection(a : varargs<int>; b : varargs<int>; an : int; bn : int) : seq<int> =
var c = newseq<int>()
var i = 0
while i < an:
var h = 0
while h < bn:
if a[i] == b[h]:
c.add(a[i])
h = h + 1
i = i + 1
return c
intersection(myArray, myArray2, len(myArray), len(myArray2))
@[34, 23, 41, 36, 42]
}
Union: Union:
pass
Merge: Merge:
• "Összefutattás"^HU
pass
SEARCH: SEARCH:
• return-ed values are always 0 indexed
• algorithms which try to find the index of a value inside an array
• if the value is not found a value outside of the bounds of the array is return-ed;
conventionally this dummy value is -1 in most implementations across languages
Linear: Linear:
• one checks every element until the desired element is found
• if the desired element is not found a value outside of the bounds of the searched array is return-ed
{
proc linearSearch(a : varargs<int>; n : int; q : int) : int =
var i = 0
while a[i] != q and i < n:
i = i + 1
return i
proc linearSearch(a : varargs<int>; n : int; q : int) : int =
for i in countup(0, n):
if a[i] == q:
return i
return -1
linSrc(myArray, len(myArray), 41)
3
}
Sentinel: Sentinel:
• "strázsás"^HU
• builds on linear search
• one adds the desired element to the end of the array; this way the element will always be found before over running the indexes,
therefor the bound checking part of the while-s condition can be eliminated
• for every iteration uses one less comparison
• adding one element to an array could be very costly so not always better than linear search
{
proc sentinelSearch(a : var seq<int>, n : int, q : int) : int =
a.add(q)
var i = 0
while a[i] != q:
i = i + 1
return i
sentinelSearch(a, len(a), 7)
4
}
Jump: Jump:
• alias "block search"
• sorted only
• one jumps blocks of square route of the length of the array;
at each position its checked whether that value is larger than the desired one;
if so one jumps back (with the same interval) and linear searches until the position from which he jumped back from;
if the value is found in the process its return-ed else we know value is not present in the array
{
import std/math
proc jumpSearch(a : varargs<int>; n : int; q : int) : int =
var j = (int)sqrt((float)n)
var i = j - 1
while i < n and a[i] < q:
i = i + j
i = i - j
for h in countup(i, i + b):
if a[h] == q:
return h
return -1
jumpSearch(sortedArray, len(sortedArray), 10)
5
}
Binary: Binary:
• sorted only
• one tests at the middle of the array, this tells him whether the desired value is to the left or the right
relative to this halving point (or it is it); one readjusts the searched array to the derived area
• we create two indexes pointing to the two ends of the array at the start, call them ${left} and ${right};
we got another one which always calculated to halve the distance of the first two, call it ${middle}
(when this would leave us with a fraction the result is rounded consistently to one way);
if the value locate at ${middle} is smaller than our desired value -as the array is ordered-
one can be certain that every value bellow it is also smaller therefor only the top half must be further searched,
so we readjust ${left} to where ${middle} was + 1 and we recalculate ${middle};
in the opposite case .ie ${middle} is larger by the same logic ${right} gets moved to ${middle} - 1 which is recalculated afterwards;
this process is continue-d until either ${left} or ${right} doesnt hit the desired value or the two overlap,
proving the desired value is not present
{
proc binarySrc(a : var seq<int>, n : int, q : int) : int =
var l = 0
var r = n - 1
while l <= r:
let i = (int)( (l + r) / 2 )
if a[i] < q:
l = i + 1
elif a[i] > q:
r = i - 1
else:
return i
return -1
binarySearch(sortedArray, len(sortedArray), 6)
3
}
○ Comparison tables
+------------+------------+
| Algorithm | Complexity |
+------------+------------+
| Linear | O(n) |
| Sentinel | O(n) |
| Jump | O(√n) |
| Binary | O(log(n)) |
+------------+------------+
GRAPH: GRAPH:
https://github.com/agvxov/Sliperint
___ ___ ___ ___
/ \ / \ / \ / \
| 1 | | 10 | | 4 |----| 6 |
,\___/, \___/ ,\___/ \___/
,ˇ ˇ, ,ˇ
___ ,ˇ ˇ, ___ ,ˇ ___
/ \ˇ ˇ/ \ˇ / \
| 0 | | 3 | | 7 |
\___/, ,\___/, ,\___/
ˇ, ,ˇ ˇ, ,ˇ
ˇ, ___ ,ˇ ˇ, ___ ,ˇ
˘/ \ˇ ˘/ \ˇ
| 2 | | 5 |
\___/ ,\___/,
,ˇ ˇ,
___ ,ˇ ˇ, ___
/ \ˇ ˘/ \
| 9 | | 8 |
\___/ \___/
• a cost might be associated with each edge
○ common search problems on graphs
• find a path between ${A} and ${B}
• find the shortest path between ${A} and ${B}
• find the lowest cost path between ${A} and ${B}
• find node clusters (based on connectivity)
Random: Random:
• the name does not lie
• we randomly go from vertex to vertex
• does it sound like a good idea to you?
DFS: DFS:
• "Dept First Search"
I.| II.|III.| IV.
O
/ \ │
/ \ │
/ \ │
O O │
/ \ / \ │
/ \ / \ V
O O O O
• the graph is traversed vertically
• a list of previously seen states is kept
{
0 1 3 4 5
6 7
8
9
2
}
BFS: BFS:
• "Breath Frist Search"
O I. <───
/ \
/ \ -----
O O II. <───
/ \ / \ -----
O O O O III. <───
• the graph is traversed vertically horizontally
• a list of previously seen states is kept
{
0 1
2
3 4
5
6
7
8
9
}
○ Comparison tables
+------------+------------+
| Algorithm | Complexity |
+------------+------------+
| DPS | O(V+E) |
+------------+------------+
SORTING: SORTING:
○ Comparison perspectives
— complexity
— memory
— stability
— all explanations will use the following array as an example:
int myArray[] = {5, 3, 7, 2, 8, 4, 1, 6};
Memory before the array Memory after the array
| |
V V
+---+---+---+---+---+---+---+---+---+---+
|###| 5 | 3 | 7 | 2 | 8 | 4 | 1 | 6 |###|
+---+---+---+---+---+---+---+---+---+---+
Bubble: Bubble:
• by repeatedly comparing neighbouring element pairs we shift shift the larger values to one side
• every <int>th run will place the <int>th largest to its correct position, therefor comparisons
with that element can be omitted from further runs
{
void bubbleSort(int a[], const int &n){
bool swapped;
do{
swapped = false;
int i = 0;
while(i < n - 2){
if(a[i] > a[i + 1]){
swap(a[i], a[i + 1])
swapped = true;
}
i = i + 1;
}
}while(swapped);
}
void bubbleSort(int a[], const int &n){
bool swapped;
do{
swapped = false;
int i = 0;
int h = n - 2
while(i < h){
if(a[i] > a[i + 1]){
swap(a[i], a[i + 1])
swapped = true;
}
i = i + 1;
}
h = h - 1;
}while(swapped);
}
}
Cocktail: Cocktail:
• bidirectional bubble sort
• iterates over which side it goes from
• performs better if elements are close to their final position
{
void cocktailSort(int a[], const int &n){
bool swapped;
do{
swapped = false;
int i = 0;
while(i < n - 2){
if(a[i] > a[i + 1]){
swap(a[i], a[i + 1])
swapped = true;
}
i = i + 1;
}
if(not swapped){ break; }
i = n - 1;
while(i > 0){
if(a[i] < a[i - 1]){
swap(a[i], a[i - 1])
swapped = true;
}
i = i - 1;
}
}while(swapped);
}
cocktailSort(myArray1, lenMyArray1)
}
Insertion: Insertion:
• we start from the start of the array and approach to the end
• for every position we check every
{
void insertionSort(int a[], const int &n){
int i = 1;
int j;
while(i < n){
j = i - 1;
while(j > 0 and a[j - 1] > a[j]){
swap(a[j], a[j - 1])
j = j - 1;
}
i = i + 1;
}
}
void improvedInsertionSort(int a[], const int &n){
int i = 1;
while(i < n){
int swap = a[i];
int j = i - 1;
while(j >= 0 and a[j] > swap){
a[j + 1] = a[j];
j = j - 1;
}
a[j + 1] = swap;
i = i + 1;
}
}
insertionSort(myArray1, lenMyArray1)
}
○ in practice:
i,j
|
V
+---+---+---+---+---+---+---+---+---+
|###| 5 | 3 | 7 | 2 | 8 | 4 | 1 | 6 |
+---+---+---+---+---+---+---+---+---+
j > 0 ? No.
j-1 i,j
| |
V V
+---+---+---+---+---+---+---+---+---+
|###| 5 | 3 | 7 | 2 | 8 | 4 | 1 | 6 |
+---+---+---+---+---+---+---+---+---+
j > 0 ? Yes.
myArray[j] > 0 ? Yes.
Selection: Selection:
{
void selectoinSort(int a[], const int &n){
int i = 0;
while(i < n){
int min = i;
int j = i + 1;
while(j < n){
if(a[j] < a[min]){
min = j;
}
j = j + 1;
}
if(min != i){
swap(a[i], a[min])
}
i = i + 1;
}
}
selectionSort(myArray1, lenMyArray1)
}
Quick: Quick:
{
void quickSort(int a[], const int &low, const int &high){
if(low < high){
int swap;
int i = low - 1;
int j = low;
while(j < high){
if(a[j] < a[high]){
i = i + 1;
swap(a[i], a[j])
}
j = j + 1;
}
i = i + 1;
swap(a[i], a[high])
quickSort(a, low, i - 1);
quickSort(a, i + 1, high);
}
}
quickSort(myArray1, 0, lenMyArray1);
}
Merge: Merge:
{
void mergeSort1(int a[], int b[], const int &low, const int &high){
if(high - low == 1){ return; }
const int mid = (low + high) / 2;
mergeSort1(b, a, low, mid);
mergeSort1(b, a, mid, high);
int i = low;
int j = mid;
int k = low;
while(i < mid and j < high){
if(a[i] < a[j]){
b[k] = a[i];
i = i + 1;
}else{
b[k] = a[j];
j = j + 1;
}
k++;
}
while(i < mid){
b[k] = a[i];
i = i + 1;
k = k + 1;
}
while(j < high){
b[k] = a[j];
j = j + 1;
k = k + 1;
}
}
void mergeSort2(int a[], int b[], const int &low, const int &high){
if(high - low <= 1){ return; }
const int mid = (low + high) / 2;
mergeSort2(b, a, low, mid);
mergeSort2(b, a, mid, high);
int i = low;
int j = mid;
int k = low;
while(k < high){
if(i < mid and (j >= high or a[i] <= a[j])){
b[k] = a[i];
i = i + 1;
}else{
b[k] = a[j];
j = j + 1;
}
k = k + 1;
}
return;
}
int arrayToSortTo[] = (int*)malloc(lenMyArray1 * sizeof(int));
int i = 0; while(i < lenMyArray1){ arrayToSortTo[i] = myArray1[i]; i = i + 1; }
mergeSort(myArray1, arrayToSortTo, 0, lenMyArray1)
}
Shell: Shell:
{
void shellSort(int a[], const int &n){
int i = 0;
int g;
while((g = n / pow(2, i + 1) , g > 0)){
int h = 0;
while(h < g){
int j = h;
while(j < n){
int swap = a[j];
int k = j;
while(k >= g and b[k - g] > swap){
a[k] = a[k - g];
k = k - g;
}
a[k] = swap;
j = j + g;
}
h = h + 1;
}
i = i + 1;
}
}
shellSort(myArray1, lenMyArray1)
}
Sleep: Sleep:
• peak autism
• the elements are concurrently passed to a function which waits for the specified amount before yield-ing it back some way
{
#!/bin/bash
function f() {
sleep "$1"
echo "$1"
}
while [ -n "$1" ]
do
f "$1" & shift
done
wait
./sleep_sort.sh 5 3 6 3 6 3 1 4 7
}
Combinatoric: Combinatoric:
Permutation: Permutation:
{
def f(v, s):
if len(v) == 1:
print(s + v[0])
return
for h in range(len(v)):
s2 = s + v[h]
v2 = v.copy()
del v2[h]
f(v2, s2)
}
COMPRESSION: COMPRESSION:
Lossless: Lossless:
• the act of rehousing data into less memory, in such a way that no information is lost
• compression is generally lossless with the notable
exception of media {images; videos; sounds}
• zip-s, rar-s, tar-s and such are all lossless
Huffman_algorithm: Huffman_algorithm:
• for every symbol in the original data, a new variable length symbol is assigned
• the more more likely is the usage of an original symbol (ie. the more it is present
in the original data) the short-er the assigned symbol will be
○ process
1. a list of all array with a corresponding weight is made (where the weight
is equal to the probability it will be used or the times it is used)
2. the two lowest weight are get assigned a bit each, then a new weight is
created with from the sum of them
3. repeat step 2 until there's a single weight is left
4. a uniquely identifiable new symbol can be read for every symbol from
the highest weight towards the original symbol interpreting the bits
assigned
• assigning 0/1 corresponding to the lower/higher weight consistently
is good practice
{ "dreamers and the dead"
'd': III
'r': II
'e': IIII
'a': III
'm': I
' ': III
'n': I
'd': I
't': I
'h': I
'e': 4
'd': 3
'a': 3
' ': 3
'r': 2
'm': 1
'n': 1
'd': 1
't': 1
'h': 1
'e': 4
'd': 3
'a': 3
' ': 3
'r': 2
'm': 1
'n': 1
'd': 1
't': 1 -----.
\
}-----
/
'h': 1 -----^
'e': 4
'd': 3
'a': 3
' ': 3
'r': 2
'm': 1
'n': 1
'd': 1
1
't': 1 -----.
\
}-----
0 /
'h': 1 -----^
'e': 4
'd': 3
'a': 3
' ': 3
'r': 2
'm': 1
'n': 1
'd': 1
1
't': 1 -----.
\
}----- 2
0 /
'h': 1 -----^
1
'e': 4 -----.
\ 1
}----- 7 ------------------------------------------------------------------------.
0 / \
'd': 3 -----^ \
\
}----- 20
1 /
'a': 3 -----. /
\ 1 /
}----- 6 -------------------------------------------------. /
0 / \ /
' ': 3 -----^ \ /
\ 0 /
}----- 13 -----^
1 /
'r': 2 -----. /
\ 1 /
}----- 3 ---------------------------. /
0 / \ /
'm': 1 -----^ \ /
\ 0 /
}----- 7 -----^
1 /
'n': 1 -----. /
\ 1 /
}----- 2 -----. /
0 / \ /
'd': 1 -----^ \ /
\ 0 /
}----- 4 -----^
1 /
't': 1 -----. /
\ 0 /
}----- 2 -----^
0 /
'h': 1 -----^
'e': 11
'd': 10
'a': 011
' ': 010
'r': 0011
'm': 0010
'n': 00011
'd': 00010
't': 00001
'h': 00000
}
Entropy: Entropy:
• a measurement of uncertainty
• you should be embracing entropy
{
where p is a set of weighted properties;
n is the number of elements in p
n
Σ pˇi == 1
i=1
n
— ( Σ pˇi * log₂(pˇi) )
i=1
}
{
— ( 1/6 * log₂(1/6) + 5/6 * log₂(5/6) ) ~= 0.65
}
RASTER: RASTER:
https://github.com/agvxov/demoPaint.git
Line: Line:
DDA: DDA:
• suffers from float errors
• on small scales it still looks more orderly than alternatives
• a step is determined, and used throughout
// @BAKE g++ $@ -o $*.out -ggdb $(pkg-config --cflags --libs ncurses)
#include <sys/param.h> // MAX()
#include <math.h>
#include <ncurses.h>
typedef struct {
int y;
int x;
} spatial;
void dda(const char c, const spatial from, const spatial to) {
const int steps = MAX(abs(to.y - from.y), abs(to.x - from.x));
struct {
double y;
double x;
} d = {
.y = (double)from.y,
.x = (double)from.x,
};
for (int i = 0; i < steps+1; i++) {
mvaddch(round(d.y), round(d.x), c);
d.y += (double)(to.y - from.y) / (double)steps;
d.x += (double)(to.x - from.x) / (double)steps;
}
return;
}
signed main() {
initscr();
noecho();
curs_set(0);
spatial from = {6, 0};
spatial to = {0, 20};
dda('-', from, to);
refresh();
while(1) { ; }
endwin();
return 0;
}
MidPoint: MidPoint:
• unlike DDA, it does not use floats
• closest pixel is determined on a per point basis
// @BAKE g++ $@ -o $*.out -ggdb $(pkg-config --cflags --libs ncurses)
#include <sys/param.h> // MAX()
#include <math.h>
#include <ncurses.h>
typedef struct {
int y;
int x;
} spatial;
void midpoint(const char c, spatial from, const spatial to) {
spatial d = {
.y = abs(to.y - from.y),
.x = abs(to.x - from.x),
};
spatial s = {
.y = (from.y < to.y) ? 1 : -1,
.x = (from.x < to.x) ? 1 : -1,
};
int direction = (d.x > d.y ? d.x : -d.y) / 2;
while (true) {
mvaddch(from.y, from.x, c);
if (from.x == to.x
&& from.y == to.y) {
break;
}
int buffer = direction;
if (buffer > -d.x) {
direction += -d.y;
from.x += s.x;
}
if (buffer < d.y) {
direction += d.x;
from.y += s.y;
}
}
}
signed main() {
initscr();
noecho();
curs_set(0);
spatial from = {6, 0};
spatial to = {0, 20};
midpoint('-', from, to);
refresh();
while(1) { ; }
endwin();
return 0;
}
Circle: Circle:
// @BAKE g++ $@ -o $*.out -Wall -Wpedantic $(pkg-config --cflags --libs sdl2)
#include <math.h>
#include <SDL.h>
SDL_Window* window;
SDL_Renderer* renderer;
void draw_circle_2w(const SDL_Point &p, const int &r){
const int r2 = r * r;
for (int y, x = -r; x <= r; x++) {
y = (int)(round(sqrt(r2 - x*x)));
SDL_RenderDrawPoint(renderer, p.x + x, p.y + y);
SDL_RenderDrawPoint(renderer, p.x + x, p.y - y);
}
}
void draw_circle_4w(const SDL_Point &p, const int &r){
const int r2 = r * r;
SDL_RenderDrawPoint(renderer, p.x, p.y + r);
SDL_RenderDrawPoint(renderer, p.x, p.y - r);
for (int y, x = 1; x <= r; x++) {
y = (int)(round(sqrt(r2 - x*x)));
SDL_RenderDrawPoint(renderer, p.x + x, p.y + y);
SDL_RenderDrawPoint(renderer, p.x + x, p.y - y);
SDL_RenderDrawPoint(renderer, p.x - x, p.y + y);
SDL_RenderDrawPoint(renderer, p.x - x, p.y - y);
}
}
void draw_circle_8w(const SDL_Point &p, const int &r){
const int r2 = r * r;
SDL_RenderDrawPoint(renderer, p.x , p.y + r);
SDL_RenderDrawPoint(renderer, p.x , p.y - r);
SDL_RenderDrawPoint(renderer, p.x + r, p.y );
SDL_RenderDrawPoint(renderer, p.x - r, p.y );
for (int x = 1, y = (int)(round(sqrt(r2 - x*x)));
x <= y;
++x, y = (int)(round(sqrt(r2 - x*x)))) {
SDL_RenderDrawPoint(renderer, p.x + x, p.y + y);
SDL_RenderDrawPoint(renderer, p.x + x, p.y - y);
SDL_RenderDrawPoint(renderer, p.x - x, p.y + y);
SDL_RenderDrawPoint(renderer, p.x - x, p.y - y);
SDL_RenderDrawPoint(renderer, p.x + y, p.y + x);
SDL_RenderDrawPoint(renderer, p.x + y, p.y - x);
SDL_RenderDrawPoint(renderer, p.x - y, p.y + x);
SDL_RenderDrawPoint(renderer, p.x - y, p.y - x);
}
}
void fill_circle_nested(const SDL_Point &p, const int &r){
for (int i = 0; i < r; i++) {
draw_circle_8w((SDL_Point){p.x, p.y}, i);
}
}
void fill_circle_2w(const SDL_Point &p, const int &r){
const int r2 = r * r;
for (int y, x = -r; x <= r; x++) {
y = (int)(round(sqrt(r2 - x*x)));
SDL_RenderDrawLine(renderer, p.x + x, p.y + y, p.x + x, p.y - y);
}
}
signed main(int argc, char* argv[]) {
SDL_Init(SDL_INIT_VIDEO);
window = SDL_CreateWindow("Circle", 0, 0, 800, 800, SDL_WINDOW_SHOWN);
renderer = SDL_CreateRenderer(window, -1, SDL_RENDERER_ACCELERATED);
SDL_SetRenderDrawColor(renderer, 0, 0, 0, 255);
SDL_RenderClear(renderer);
SDL_SetRenderDrawColor(renderer, 255, 0, 0, 255);
draw_circle_2w( (SDL_Point){400 , 400 - 210}, 100);
draw_circle_4w( (SDL_Point){400 , 400 }, 100);
draw_circle_8w( (SDL_Point){400 , 400 + 210}, 100);
fill_circle_nested((SDL_Point){400 + 210, 400 }, 100);
fill_circle_2w( (SDL_Point){400 - 210, 400 }, 100);
SDL_RenderPresent(renderer);
while (1) { ; }
return 0;
}
Curve:
• we would like to both express and display smooth surfaces with a set of control points
• the number of control points are also commonly referred to as "degrees"
Brézier:
{ vector fonts }
• generally only the starting and ending control point lies on the curve
• recursive linear interpolation until only one point remains
• control point changes are global, they change the trajectory of the whole curve
— a linear brézier curve has 2 control points:
• just a line
— a quadratic brézier curve has 3 control points:
pass
— a qubic brézier curve has 4 control points:
• the most common brézier curve in practice
— a more than 4 degree brézier curve is rarely used:
• globality adds up, making it very hard to draw anything useful with it
• computational requirements explode using de casteljaus,
which used to be a significant problem up until 1986
algorithms:
https://drna.padovauniversitypress.it/system/files/papers/DRNA-2024-3-09.pdf
— de casteljau's:
• old as the highway
let d := dimensions
let n := len(control_points)
O(dn²)
— Volk-Schumaker:
• "VS"
• has no geometric interpretation
let n := len(control_points)
O(n)
— Woźny-Chudy:
• has a geometric interpretation
let n := len(control_points)
O(n)
Hermite:
• a velocity is given for each control point
Cardinal:
• velocities are calculated from the neighbouring control points
• the curve will travel over every control point
• the starting and ending control points cannot have such vectors,
as they dont have 2 neighbours and therefor cannot be displayed
as part of the curve;
in practice this is solved by adding 2 hidden control points,
which have the position of the visible end control points
neighbours mirrored
• looks jumpy, so vectors are usually down adjusted with a constant
— catmull-rom:
• special case of a cardinal hermite spline where the vector
scale is exactly 0.5
• looks clean
• commonly used in vidya
Spline:
• a series of curves joined together
— have multiple properties of continuity with practical significance for designers:
• do reflections on its surface look terrible in 3D? { car design }
• is it suitable for expressing continuous motion?
(will the speed of the object look all messed up?) { animations }
• is it suitable for tracing with a camera?
(are there any sharp turns at the joints?)
Filling:
Scanline:
• start a line iterating over our polygon
• start filling on odd lines encountered,
stop filling on even lines encountered
— special case:
• concave edges
__
| \ /|
| \/ |
| |
````````
=> exclude line intersection points
• egde part of concave formation
__
| \ /|
| './ |
| |
`````````
=> only exclude edges whose points are minimum of its neighbours
Flood:
• "bucket-fill"
• choose an arbitrary point inside the polygon
• fill neighbouring points given that they are not a boundary line
and are not filled already
• BFS and DFS variants
X
X#X
X
XXX
X#X
XXX
Eight_queens:
https://github.com/agvxov/8_queens
• placing 8 queens on a chessboard in such a way
that they could not take each other in 1
• the task can be completed (using the same algorithm),
on an ${N} by ${N} board with ${N} queens
• famous problem given to beginner developers
Levenshtein: Levenshtein:
• string distance metric
• "the number of edits to produce one text from another"
• commonly misspelled as "Levenstein"
— associated with fuzzy searching, but not great for it:
• computationally expensive especially for substrings,
so it scales badly in interactive systems {user browser history}
• cannot recognize missing or swapped keywords,
because that's not simply what it does
• does not account for common typos {'e' -> 'i'} or fat-fingering
• for the ABOVE reasons its best as a quick spell checker
○ "edit"
• insertion
• deletion
• substitution
Damerau_levenshtein:
○ "edit"
• insertion
• deletion
• substitution
• adjacent char swapping