-
Notifications
You must be signed in to change notification settings - Fork 16
/
algorithms.theory.txt
137 lines (114 loc) · 9.79 KB
/
algorithms.theory.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
ALGORITHMS
QUALITIES ==> #Qualities of an algorithm:
# - "optimality": best solution is found
# - "completeness": all solutions are found
# - "accuracy": results are close to solutions
# - "precision": results are close to each other
# - "complexity"/"efficiency" (see performance doc):
# - "parallelism" (see its doc)
# - "locality of reference" (see performance doc)
# - "persistence" (see state doc)
HEURISTIC ==> #Achieving high efficiency by trading off other qualities
/=+===============================+=\
/ : : \
)==: SUBPROBLEMS :==(
\ :_______________________________: /
\=+===============================+=/
SUBPROBLEM ==> #Subset of input
OPTIMAL SUBSTRUCTURE ==> #When each subproblem's solution is the optimal solution
OVERLAPPING SUBPROBLEM ==> #When some subproblems are the same.
#I.e. memoization can be used
GREEDINESS ==> #Way to divide an algorithm into subproblems.
#Each subproblem is iterately computed then merged:
# - each iteration picks candidate ("local optimum")
# that gets closer to solution ("global optimum")
# - if no candidate, stops
# - each iteration does not keep previous individual results
#Pros:
# - can be used even with no optimal substructure
# - but in that case, is heuristic, i.e. does not achieve optimality
# - sometimes better time complexity
# - better memory complexity
#Cons:
# - cannot use overlapping subproblems nor parallelism
RECURSION ==> #Way to divide an algorithm into subproblems.
#All subproblems are computed, then are all merged together.
#Also called "dynamic programming|optimization"
#Pros:
# - can re-use overlapping subproblems
# - can use parallelism
#Cons:
# - only possible if optimal substructure
# - worst memory complexity (e.g. stack size)
#Can be:
# - "divide and conquer"/"bottom-up":
# - start with subset of input, merged into bigger input
# - example: distribution sorts
# - "decrease and conquer"/"top-down":
# - start with whole input, divided into subsets
# - example: binary search
# - "prune and search": when doing it with constant factor
#"Recursive|inductive data structure":
# - when subsets of data structures have same properties as superset
# - allows efficient recursive algorithms, e.g. merging
# - example: array, simply linked list, binary search tree
# - couter-example: hash table, doubly linked list, cartesian tree
RANDOMIZED ==> #When algorithm uses randomness as part of its logic
#I.e. output differs between runs.
#The output can either be:
# - always correct
# - not always correct: "probabilistic"
GENETIC ALGORITHM ==> #Heuristic algorithm using solutions ("individuals") with series ("chromosomes") of parameters ("genes"):
# - initially random
# - often represented as array of bits|characters
#Then the following is repeated:
# - best ones ("fitness score") are kept ("selection")
# - new ones are created by mixing multiple solutions ("crossover")
# - some of their parameters are randomly changed ("mutation")
HYBRID ==> #When mixing together the logic of multiple algorithms solving the same problem.
#Goal: getting pros of each.
#Either:
# - switch a single algorithm based on input
# - switch from one algorithm to another during computation, after a specific event
/=+===============================+=\
/ : : \
)==: DYNAMISM :==(
\ :_______________________________: /
\=+===============================+=/
DYNAMIC ALGORITHM ==> #When input is changing.
#Can be:
# - "fully dynamic": adding and removing elements
# - "incremental algorithm|optimization": only adding elements
# - "online algorithm|optimization":
# - each new input must compute new solution
# - "streaming algorithm":
# - new input can defer new solution ("buffering")
# - memory is limited (i.e. usually greedy algorithms are used)
# - opposite is "offline algorithm"
# - "decremental algorithm": only removing elements
#Opposite is "static algorithm"
#The word "dynamic" in that sense can also be applied to:
# - "dynamic problem"
# - "dynamic data structure"
# - "dynamization": transforming static data structure into dynamic data structure
#Note that "dynamic programming" is not the same as "dynamic algorithm"
#Each new input can be thought as a subproblem:
# - i.e. dynamic problems can be solved using greedy or recursive algorithms
# - when using a greedy algorithm, might not reach optimality:
COMPETITIVE ANALYSIS ==> #Calculating complexity cost of online algorithm
#"Competitive ratio":
# - online algorithm complexity divided by related offline algorithm's
#Uses online algorithm's worst time complexity:
# - i.e. each new input is always the worst that could be
# - if the algorithm computation is randomized, can calculate random seeds:
# - "strong|adaptive offline advisary": all at beginning
# - "medium|adaptive online advisary": one input at a time
# - "oblivious|weak advisary": not at all
ADAPTIVE ALGORITHM ==> #When algorithm behavior or qualities changes according to input
#Example: adaptive sorts
GENERAL-PURPOSE ALGORITHM ==> #When algorithm works for many types of input
#Pro: qualities do no change with different inputs
# - including when input changes over time
#Con: qualities are not optimized for each specific input