-
Notifications
You must be signed in to change notification settings - Fork 16
/
Copy pathalgorithms.theory.txt
127 lines (110 loc) · 8.64 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
┏━━━━━━━━━━━━━━━━┓
┃ 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