-
Notifications
You must be signed in to change notification settings - Fork 13
Expand file tree
/
Copy pathonline-algorithms.html
More file actions
119 lines (108 loc) · 45.5 KB
/
online-algorithms.html
File metadata and controls
119 lines (108 loc) · 45.5 KB
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
<!DOCTYPE html>
<html lang="en-US">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width,initial-scale=1">
<title>Algorithm - Online algorithms</title>
<meta name="generator" content="VuePress 1.8.2">
<link rel="icon" type="image/png" sizes="32x32" href="/favicon-32x32.png">
<link rel="icon" type="image/png" sizes="16x16" href="/favicon-16x16.png">
<link rel="manifest" href="/site.webmanifest">
<link rel="apple-touch-icon" sizes="180x180" href="/apple-touch-icon.png">
<link rel="mask-icon" href="/safari-pinned-tab.svg" color="#5bbad5">
<meta name="description" content="Paging (Online Caching)">
<meta property="og:site_name" content="DevTut">
<meta property="og:title" content="Algorithm - Online algorithms">
<meta property="og:description" content="Paging (Online Caching)">
<meta property="og:type" content="article">
<meta property="og:url" content="/algorithm/online-algorithms.html">
<meta property="og:image" content="/logo.png">
<meta name="twitter:title" content="Algorithm - Online algorithms">
<meta name="twitter:description" content="Paging (Online Caching)">
<meta name="twitter:url" content="/algorithm/online-algorithms.html">
<meta name="twitter:card" content="summary_large_image">
<meta name="twitter:image" content="/logo.png">
<meta name="theme-color" content="#ffffff">
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="black">
<meta name="msapplication-TileImage" content="/mstile-150x150.png">
<meta name="msapplication-TileColor" content="#da532c">
<meta name="google-site-verification" content="76_rKXgwMVIjd-axJC_1zPV9OS4mEjvtgjYOWVkAdnQ">
<link rel="preload" href="/assets/css/0.styles.60619e34.css" as="style"><link rel="preload" href="/assets/js/app.1779e102.js" as="script"><link rel="preload" href="/assets/js/3.2cfa8016.js" as="script"><link rel="preload" href="/assets/js/59.6dfdd9ba.js" as="script">
<link rel="stylesheet" href="/assets/css/0.styles.60619e34.css">
</head>
<body>
<div id="app" data-server-rendered="true"><div class="theme-container"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><!----> <span class="site-name">DevTut</span></a> <div class="links"><form id="search-form" role="search" class="algolia-search-wrapper search-box"><input id="algolia-search-input" class="search-query"></form> <nav class="nav-links can-hide"> <a href="https://github.com/devtut/generate" target="_blank" rel="noopener noreferrer" class="repo-link">
GitHub
<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav></div></header> <div class="sidebar-mask"></div> <aside class="sidebar"><nav class="nav-links"> <a href="https://github.com/devtut/generate" target="_blank" rel="noopener noreferrer" class="repo-link">
GitHub
<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav> <ul class="sidebar-links"><li><section class="sidebar-group depth-0"><p class="sidebar-heading open"><span>Algorithm</span> <!----></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/algorithm/" aria-current="page" class="sidebar-link">Disclaimer</a></li><li><a href="/algorithm/getting-started-with-algorithm.html" class="sidebar-link">Getting started with algorithm</a></li><li><a href="/algorithm/algorithm-complexity.html" class="sidebar-link">Algorithm Complexity</a></li><li><a href="/algorithm/big-o-notation.html" class="sidebar-link">Big-O Notation</a></li><li><a href="/algorithm/trees.html" class="sidebar-link">Trees</a></li><li><a href="/algorithm/binary-search-trees.html" class="sidebar-link">Binary Search Trees</a></li><li><a href="/algorithm/check-if-a-tree-is-bst-or-not.html" class="sidebar-link">Check if a tree is BST or not</a></li><li><a href="/algorithm/binary-tree-traversals.html" class="sidebar-link">Binary Tree traversals</a></li><li><a href="/algorithm/lowest-common-ancestor-of-a-binary-tree.html" class="sidebar-link">Lowest common ancestor of a Binary Tree</a></li><li><a href="/algorithm/graph.html" class="sidebar-link">Graph</a></li><li><a href="/algorithm/graph-traversals.html" class="sidebar-link">Graph Traversals</a></li><li><a href="/algorithm/dijkstras-algorithm.html" class="sidebar-link">Dijkstra’s Algorithm</a></li><li><a href="/algorithm/a-pathfinding.html" class="sidebar-link">A* Pathfinding</a></li><li><a href="/algorithm/a-pathfinding-algorithm.html" class="sidebar-link">A* Pathfinding Algorithm</a></li><li><a href="/algorithm/dynamic-programming.html" class="sidebar-link">Dynamic Programming</a></li><li><a href="/algorithm/applications-of-dynamic-programming.html" class="sidebar-link">Applications of Dynamic Programming</a></li><li><a href="/algorithm/kruskal-s-algorithm.html" class="sidebar-link">Kruskal's Algorithm</a></li><li><a href="/algorithm/greedy-algorithms.html" class="sidebar-link">Greedy Algorithms</a></li><li><a href="/algorithm/applications-of-greedy-technique.html" class="sidebar-link">Applications of Greedy technique</a></li><li><a href="/algorithm/prim-s-algorithm.html" class="sidebar-link">Prim's Algorithm</a></li><li><a href="/algorithm/bellman-ford-algorithm.html" class="sidebar-link">Bellman–Ford Algorithm</a></li><li><a href="/algorithm/line-algorithm.html" class="sidebar-link">Line Algorithm</a></li><li><a href="/algorithm/floyd-warshall-algorithm.html" class="sidebar-link">Floyd-Warshall Algorithm</a></li><li><a href="/algorithm/catalan-number-algorithm.html" class="sidebar-link">Catalan Number Algorithm</a></li><li><a href="/algorithm/multithreaded-algorithms.html" class="sidebar-link">Multithreaded Algorithms</a></li><li><a href="/algorithm/knuth-morris-pratt-kmp-algorithm.html" class="sidebar-link">Knuth Morris Pratt (KMP) Algorithm</a></li><li><a href="/algorithm/edit-distance-dynamic-algorithm.html" class="sidebar-link">Edit Distance Dynamic Algorithm</a></li><li><a href="/algorithm/online-algorithms.html" aria-current="page" class="active sidebar-link">Online algorithms</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/algorithm/online-algorithms.html#paging-online-caching" class="sidebar-link">Paging (Online Caching)</a></li></ul></li><li><a href="/algorithm/integer-partition-algorithm.html" class="sidebar-link">Integer Partition Algorithm</a></li><li><a href="/algorithm/maximum-path-sum-algorithm.html" class="sidebar-link">Maximum Path Sum Algorithm</a></li><li><a href="/algorithm/maximum-subarray-algorithm.html" class="sidebar-link">Maximum Subarray Algorithm</a></li><li><a href="/algorithm/sliding-window-algorithm.html" class="sidebar-link">Sliding Window Algorithm</a></li><li><a href="/algorithm/sorting.html" class="sidebar-link">Sorting</a></li><li><a href="/algorithm/bubble-sort.html" class="sidebar-link">Bubble Sort</a></li><li><a href="/algorithm/merge-sort.html" class="sidebar-link">Merge Sort</a></li><li><a href="/algorithm/insertion-sort.html" class="sidebar-link">Insertion Sort</a></li><li><a href="/algorithm/bucket-sort.html" class="sidebar-link">Bucket Sort</a></li><li><a href="/algorithm/quicksort.html" class="sidebar-link">Quicksort</a></li><li><a href="/algorithm/counting-sort.html" class="sidebar-link">Counting Sort</a></li><li><a href="/algorithm/heap-sort.html" class="sidebar-link">Heap Sort</a></li><li><a href="/algorithm/cycle-sort.html" class="sidebar-link">Cycle Sort</a></li><li><a href="/algorithm/odd-even-sort.html" class="sidebar-link">Odd-Even Sort</a></li><li><a href="/algorithm/selection-sort.html" class="sidebar-link">Selection Sort</a></li><li><a href="/algorithm/pigeonhole-sort.html" class="sidebar-link">Pigeonhole Sort</a></li><li><a href="/algorithm/radix-sort.html" class="sidebar-link">Radix Sort</a></li><li><a href="/algorithm/shell-sort.html" class="sidebar-link">Shell Sort</a></li><li><a href="/algorithm/pancake-sort.html" class="sidebar-link">Pancake Sort</a></li><li><a href="/algorithm/searching.html" class="sidebar-link">Searching</a></li><li><a href="/algorithm/substring-search.html" class="sidebar-link">Substring Search</a></li><li><a href="/algorithm/breadth-first-search.html" class="sidebar-link">Breadth-First Search</a></li><li><a href="/algorithm/depth-first-search.html" class="sidebar-link">Depth First Search</a></li><li><a href="/algorithm/hash-functions.html" class="sidebar-link">Hash Functions</a></li><li><a href="/algorithm/travelling-salesman.html" class="sidebar-link">Travelling Salesman</a></li><li><a href="/algorithm/shortest-common-supersequence-problem.html" class="sidebar-link">Shortest Common Supersequence Problem</a></li><li><a href="/algorithm/knapsack-problem.html" class="sidebar-link">Knapsack Problem</a></li><li><a href="/algorithm/equation-solving.html" class="sidebar-link">Equation Solving</a></li><li><a href="/algorithm/longest-common-subsequence.html" class="sidebar-link">Longest Common Subsequence</a></li><li><a href="/algorithm/longest-increasing-subsequence.html" class="sidebar-link">Longest Increasing Subsequence</a></li><li><a href="/algorithm/check-two-strings-are-anagrams.html" class="sidebar-link">Check two strings are anagrams</a></li><li><a href="/algorithm/pascal-s-triangle.html" class="sidebar-link">Pascal's Triangle</a></li><li><a href="/algorithm/algo-print-a-m-n-matrix-in-square-wise.html" class="sidebar-link">Algo:- Print a m*n matrix in square wise</a></li><li><a href="/algorithm/matrix-exponentiation.html" class="sidebar-link">Matrix Exponentiation</a></li><li><a href="/algorithm/polynomial-time-bounded-algorithm-for-minimum-vertex-cover.html" class="sidebar-link">polynomial-time bounded algorithm for Minimum Vertex Cover</a></li><li><a href="/algorithm/dynamic-time-warping.html" class="sidebar-link">Dynamic Time Warping</a></li><li><a href="/algorithm/fast-fourier-transform.html" class="sidebar-link">Fast Fourier Transform</a></li><li><a href="/algorithm/pseudocode.html" class="sidebar-link">Pseudocode</a></li><li><a href="/algorithm/contributors.html" class="sidebar-link">The Contributors</a></li></ul></section></li></ul> </aside> <main class="page"> <div class="theme-default-content content__default"><h1 id="online-algorithms"><a href="#online-algorithms" class="header-anchor">#</a> Online algorithms</h1> <h2 id="paging-online-caching"><a href="#paging-online-caching" class="header-anchor">#</a> Paging (Online Caching)</h2> <h3 id="preface"><a href="#preface" class="header-anchor">#</a> Preface</h3> <p>Instead of starting with a formal definition, the goal is to approach these topic via a row of examples, introducing definitions along the way. The remark section <strong>Theory</strong> will consist of all definitions, theorems and propositions to give you all informations to faster look up specific aspects.</p> <p>The remark section sources consists of the basis material used for this topic and additional information for further reading. In addition you will find the full source codes for the examples there. Please pay attention that to make the source code for the examples more readable and shorter it refrains from things like error handling etc. It also passes on some specific language features which would obscure the clarity of the example like extensive use of advanced libraries etc.</p> <h3 id="paging"><a href="#paging" class="header-anchor">#</a> Paging</h3> <p>The paging problem arises from the limitation of finite space. Let's assume our cache <code>C</code> has <code>k</code> pages. Now we want to process a sequence of <code>m</code> page requests which must have been placed in the cache before they are processed. Of course if <code>m<=k</code> then we just put all elements in the cache and it will work, but usually is <code>m>>k</code>.</p> <p>We say a request is a <strong>cache hit</strong>, when the page is already in cache, otherwise, its called a <strong>cache miss</strong>. In that case, we must bring the requested page into the cache and evict another, assuming the cache is full. The Goal is an eviction schedule that <strong>minimizes the number of evictions</strong>.</p> <p>There are numerous strategies for this problem, let's look at some:</p> <ol><li><strong>First in, first out (FIFO)</strong>: The oldest page gets evicted</li> <li><strong>Last in, first out (LIFO)</strong>: The newest page gets evicted</li> <li><strong>Least recently used (LRU)</strong>: Evict page whose most recent access was earliest</li> <li><strong>Least frequently used (LFU)</strong>: Evict page that was least frequently requested</li> <li><strong>Longest forward distance (LFD)</strong>: Evict page in the cache that is not requested until farthest in the future.</li> <li><strong>Flush when full (FWF)</strong>: clear the cache complete as soon as a cache miss happened</li></ol> <p>There are two ways to approach this problem:</p> <ol><li><strong>offline</strong>: the sequence of page requests is known ahead of time</li> <li><strong>online</strong>: the sequence of page requests is not known ahead of time</li></ol> <h3 id="offline-approach"><a href="#offline-approach" class="header-anchor">#</a> Offline Approach</h3> <p>For the first approach look at the topic <a href="http://stackoverflow.com/documentation/algorithm/7993/applications-of-greedy-technique#t=201611270008467964173" target="_blank" rel="noopener noreferrer">Applications of Greedy technique<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a>. It's third Example <strong>Offline Caching</strong> considers the first five strategies from above and gives you a good entry point for the following.</p> <p>The example program was extended with the <strong>FWF</strong> strategy:</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token keyword">class</span> <span class="token class-name">FWF</span> <span class="token operator">:</span> <span class="token base-clause"><span class="token keyword">public</span> <span class="token class-name">Strategy</span></span> <span class="token punctuation">{</span>
<span class="token keyword">public</span><span class="token operator">:</span>
<span class="token function">FWF</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">:</span> <span class="token function">Strategy</span><span class="token punctuation">(</span><span class="token string">"FWF"</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token punctuation">}</span>
<span class="token keyword">int</span> <span class="token function">apply</span><span class="token punctuation">(</span><span class="token keyword">int</span> requestIndex<span class="token punctuation">)</span> <span class="token keyword">override</span>
<span class="token punctuation">{</span>
<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator"><</span>cacheSize<span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">if</span><span class="token punctuation">(</span>cache<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> request<span class="token punctuation">[</span>requestIndex<span class="token punctuation">]</span><span class="token punctuation">)</span>
<span class="token keyword">return</span> i<span class="token punctuation">;</span>
<span class="token comment">// after first empty page all others have to be empty</span>
<span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span>cache<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> emptyPage<span class="token punctuation">)</span>
<span class="token keyword">return</span> i<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token comment">// no free pages</span>
<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">void</span> <span class="token function">update</span><span class="token punctuation">(</span><span class="token keyword">int</span> cachePos<span class="token punctuation">,</span> <span class="token keyword">int</span> requestIndex<span class="token punctuation">,</span> <span class="token keyword">bool</span> cacheMiss<span class="token punctuation">)</span> <span class="token keyword">override</span>
<span class="token punctuation">{</span>
<span class="token comment">// no pages free -> miss -> clear cache</span>
<span class="token keyword">if</span><span class="token punctuation">(</span>cacheMiss <span class="token operator">&&</span> cachePos <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator"><</span> cacheSize<span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span>
cache<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> emptyPage<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre></div><p>The full sourcecode is available <a href="http://pastebin.com/AF7EC2xJ" target="_blank" rel="noopener noreferrer">here<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a>. If we reuse the example from the topic, we get the following output:</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code>Strategy<span class="token operator">:</span> FWF
Cache initial<span class="token operator">:</span> <span class="token punctuation">(</span>a<span class="token punctuation">,</span>b<span class="token punctuation">,</span>c<span class="token punctuation">)</span>
Request cache <span class="token number">0</span> cache <span class="token number">1</span> cache <span class="token number">2</span> cache miss
a a b c
a a b c
d d X X x
e d e X
b d e b
b d e b
a a X X x
c a c X
f a c f
d d X X x
e d e X
a d e a
f f X X x
b f b X
e f b e
c c X X x
Total cache misses<span class="token operator">:</span> <span class="token number">5</span>
</code></pre></div><p>Even though <strong>LFD</strong> is optimal, <strong>FWF</strong> has fewer cache misses. But the main goal was to minimize the number of evictions and for <strong>FWF</strong> five misses mean 15 evictions, which makes it the poorest choice for this example.</p> <h3 id="online-approach"><a href="#online-approach" class="header-anchor">#</a> Online Approach</h3> <p>Now we want to approach the online problem of paging. But first we need an understanding how to do it. Obviously an online algorithm cannot be better than the optimal offline algorithm. But how much worse it is? We need formal definitions to answer that question:</p> <p><strong>Definition 1.1:</strong> An <strong>optimization problem</strong> Π consists of a set of <strong>instances</strong> Σ<sub>Π</sub>. For every instance σ∈Σ<sub>Π</sub> there is a set Ζ<sub>σ</sub> of <strong>solutions</strong> and a <strong>objective function</strong> f<sub>σ</sub> : Ζ<sub>σ</sub> → ℜ<sub>≥0</sub> which assigns apositive real value to every solution.<br> We say OPT(σ) is the value of an optimal solution, A(σ) is the solution of an Algorithm A for the problem Π and w<sub>A</sub>(σ)=f<sub>σ</sub>(A(σ)) its value.</p> <p><strong>Definition 1.2:</strong> An online algorithm A for a minimization problem Π has a <strong>competetive ratio</strong> of r ≥ 1 if there is a constant τ∈ℜ with</p> <blockquote></blockquote> <p>w<sub>A</sub>(σ) = f<sub>σ</sub>(A(σ)) ≤ r ⋅ OPT(σ) + τ</p> <p>for all instances σ∈Σ<sub>Π</sub>. A is called a <strong>r-competitive</strong> online algorithm. Is even</p> <blockquote></blockquote> <p>w<sub>A</sub>(σ) ≤ r ⋅ OPT(σ)</p> <p>for all instances σ∈Σ<sub>Π</sub> then A is called a <strong>strictly r-competitive</strong> online algorithm.</p> <p>So the question is how <strong>competitive</strong> is our online algorithm compared to an optimal offline algorithm. In their famous <a href="http://www.cs.technion.ac.il/%7Erani/book.html" target="_blank" rel="noopener noreferrer">book<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a> Allan Borodin and Ran El-Yaniv used another scenario to describe the online paging situation:</p> <p>There is an <strong>evil adversary</strong> who knows your algorithm and the optimal offline algorithm. In every step, he tries to request a page which is worst for you and simultaneously best for the offline algorithm. the <strong>competitive factor</strong> of your algorithm is the factor on how badly your algorithm did against the adversary's optimal offline algorithm. If you want to try to be the adversary, you can try the <a href="https://pastebin.com/u/kgoedde/1/Wak9refA" target="_blank" rel="noopener noreferrer">Adversary Game<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a> (try to beat the paging strategies).</p> <h3 id="marking-algorithms"><a href="#marking-algorithms" class="header-anchor">#</a> Marking Algorithms</h3> <p>Instead of analysing every algorithm separately, let's look at a special online algorithm family for the paging problem called <strong>marking algorithms</strong>.</p> <p>Let σ=(σ<sub>1</sub>,...,σ<sub>p</sub>) an instance for our problem and k our cache size, than σ can be divided into phases:</p> <ul><li>Phase 1 is the maximal subsequence of σ from the start till maximal k different pages are requested</li> <li>Phase i ≥ 2 is the maximal subsequence of σ from the end of pase i-1 till maximal k different pages are requested</li></ul> <p>For example with k = 3:</p> <blockquote></blockquote> <p><a href="https://i.stack.imgur.com/u4VjA.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/u4VjA.png" alt="enter image description here"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>A marking algorithm (implicitly or explicitly) maintains whether a page is marked or not. At the beginning of each phase are all pages unmarked. Is a page requested during a phase it gets marked. An algorithm is a marking algorithm <strong>iff</strong> it never evicts a marked page from cache. That means pages which are used during a phase will not be evicted.</p> <p><strong>Proposition 1.3:</strong> <strong>LRU</strong> and <strong>FWF</strong> are marking algorithm.</p> <p><strong>Proof:</strong> At the beginning of each phase (except for the first one) <strong>FWF</strong> has a cache miss and cleared the cache. that means we have k empty pages. In every phase are maximal k different pages requested, so there will be now eviction during the phase. So <strong>FWF</strong> is a marking algorithm. <br>
Let's assume <strong>LRU</strong> is not a marking algorithm. Then there is an instance σ where <strong>LRU</strong> a marked page x in phase i evicted. Let σ<sub>t</sub> the request in phase i where x is evicted. Since x is marked there has to be a earlier request σ<sub>t*</sub> for x in the same phase, so t* < t. After t* x is the caches newest page, so to got evicted at t the sequence σ<sub>t*+1</sub>,...,σ<sub>t</sub> has to request at least k from x different pages. That implies the phase i has requested at least k+1 different pages which is a contradictory to the phase definition. So <strong>LRU</strong> has to be a marking algorithm.</p> <p><strong>Proposition 1.4:</strong> Every marking algorithm <strong>is strictly k-competitive</strong>.</p> <p><strong>Proof:</strong> Let σ be an instance for the paging problem and l the number of phases for σ. Is l = 1 then is every marking algorithm optimal and the optimal offline algorithm cannot be better. <br>
We assume l ≥ 2. the cost of every marking algorithm, for instance, σ is bounded from above with l ⋅ k because in every phase a marking algorithm cannot evict more than k pages without evicting one marked page. <br>
Now we try to show that the optimal offline algorithm evicts at least k+l-2 pages for σ, k in the first phase and at least one for every following phase except for the last one. For proof lets define l-2 disjunct subsequences of σ. Subsequence i ∈ {1,...,l-2} starts at the second position of phase i+1 and end with the first position of phase i+2.<br>
Let x be the first page of phase i+1. At the beginning of subsequence i there is page x and at most k-1 different pages in the optimal offline algorithms cache. In subsequence i are k page request different from x, so the optimal offline algorithm has to evict at least one page for every subsequence. Since at phase 1 beginning the cache is still empty, the optimal offline algorithm causes k evictions during the first phase. That shows that</p> <blockquote></blockquote> <p>w<sub>A</sub>(σ) ≤ l⋅k ≤ (k+l-2)k ≤ OPT(σ) ⋅ k</p> <p><strong>Corollary 1.5:</strong> <strong>LRU</strong> and <strong>FWF</strong> are <strong>strictly k-competitive</strong>.</p> <p><strong>Excercise:</strong> Show that <strong>FIFO</strong> is no marking algorithm, but <strong>strictly k-competitive</strong>.</p> <p>Is there no constant r for which an online algorithm A is r-competitive, we call A <strong>not competitive</strong></p> <p><strong>Proposition 1.6:</strong> <strong>LFU</strong> and <strong>LIFO</strong> are <strong>not competitive</strong>.</p> <p><strong>Proof:</strong> Let l ≥ 2 a constant, k ≥ 2 the cache size. The different cache pages are nubered 1,...,k+1. We look at the following sequence:</p> <blockquote></blockquote> <p><a href="https://i.stack.imgur.com/zS05d.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/zS05d.png" alt="enter image description here"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>The first page 1 is requested l times than page 2 and so one. At the end, there are (l-1) alternating requests for page k and k+1. <br> <strong>LFU</strong> and <strong>LIFO</strong> fill their cache with pages 1-k. When page k+1 is requested page k is evicted and vice versa. That means every request of subsequence (k,k+1)<sup>l-1</sup> evicts one page. In addition, their are k-1 cache misses for the first time use of pages 1-(k-1). So <strong>LFU</strong> and <strong>LIFO</strong> evict exact k-1+2(l-1) pages.<br>
Now we must show that for every constant τ∈ℜ and every constant r ≤ 1 there exists an l so that</p> <blockquote></blockquote> <p><a href="https://i.stack.imgur.com/lUOxY.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/lUOxY.png" alt="enter image description here"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>which is equal to</p> <blockquote></blockquote> <p><a href="https://i.stack.imgur.com/arDFI.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/arDFI.png" alt="enter image description here"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>To satisfy this inequality you just have to choose l sufficient big. So <strong>LFU</strong> and <strong>LIFO</strong> are not competitive.</p> <p><strong>Proposition 1.7:</strong> There is <strong>no r-competetive</strong> deterministic online algorithm for paging with <strong>r < k</strong>.</p> <p>The proof for this last proposition is rather long and based of the statement that <strong>LFD</strong> is an optimal offline algorithm. The interested reader can look it up in the book of Borodin and El-Yaniv (see sources below).</p> <p>The Question is whether we could do better. For that, we have to leave the deterministic approach behind us and start to randomize our algorithm. Clearly, its much harder for the adversary to punish your algorithm if it's randomized.</p> <p><strong>Randomized paging will be discussed in one of next examples...</strong></p> <h4 id="remarks"><a href="#remarks" class="header-anchor">#</a> Remarks</h4> <h3 id="theory"><a href="#theory" class="header-anchor">#</a> Theory</h3> <p><strong>Definition 1:</strong> An <strong>optimization problem</strong> Π consists of a set of <strong>instances</strong> Σ<sub>Π</sub>. For every instance σ∈Σ<sub>Π</sub> there is a set Ζ<sub>σ</sub> of <strong>solutions</strong> and a <strong>objective function</strong> f<sub>σ</sub> : Ζ<sub>σ</sub> → ℜ<sub>≥0</sub> which assigns apositive real value to every solution.<br> We say OPT(σ) is the value of an optimal solution, A(σ) is the solution of an Algorithm A for the problem Π and w<sub>A</sub>(σ)=f<sub>σ</sub>(A(σ)) its value.</p> <p><strong>Definition 2:</strong> An online algorithm A for a minimization problem Π has a <strong>competetive ratio</strong> of r ≥ 1 if there is a constant τ∈ℜ with</p> <blockquote></blockquote> <p>w<sub>A</sub>(σ) = f<sub>σ</sub>(A(σ)) ≤ r ⋅ OPT(&sigma) + τ</p> <p>for all instances σ∈Σ<sub>Π</sub>. A is called a <strong>r-competitive</strong> online algorithm. Is even</p> <blockquote></blockquote> <p>w<sub>A</sub>(σ) ≤ r ⋅ OPT(&sigma)</p> <p>for all instances σ∈Σ<sub>Π</sub> then A is called a <strong>strictly r-competitive</strong> online algorithm.</p> <p><strong>Proposition 1.3:</strong> <strong>LRU</strong> and <strong>FWF</strong> are marking algorithm.</p> <p><strong>Proof:</strong> At the beginning of each phase (except for the first one) <strong>FWF</strong> has a cache miss and cleared the cache. that means we have k empty pages. In every phase are maximal k different pages requested, so there will be now eviction during the phase. So <strong>FWF</strong> is a marking algorithm. <br>
Lets assume <strong>LRU</strong> is not a marking algorithm. Then there is an instance σ where <strong>LRU</strong> a marked page x in phase i evicted. Let σ<sub>t</sub> the request in phase i where x is evicted. Since x is marked there has to be a earlier request σ<sub>t*</sub> for x in the same phase, so t* < t. After t* x is the caches newest page, so to got evicted at t the sequence σ<sub>t*+1</sub>,...,σ<sub>t</sub> has to request at least k from x different pages. That implies the phase i has requested at least k+1 different pages which is a contradictory to the phase definition. So <strong>LRU</strong> has to be a marking algorithm.</p> <p><strong>Proposition 1.4:</strong> Every marking algorithm <strong>is strictly k-competitive</strong>.</p> <p><strong>Proof:</strong> Let σ be an instance for the paging problem and l the number of phases for σ. Is l = 1 then is every marking algorithm optimal and the optimal offline algorithm cannot be better. <br>
We assume l ≥ 2. the cost of every marking algorithm for instance σ is bounded from above with l ⋅ k because in every phase a marking algorithm cannot evict more than k pages without evicting one marked page. <br>
Now we try to show that the optimal offline algorithm evicts at least k+l-2 pages for σ, k in the first phase and at least one for every following phase except for the last one. For proof lets define l-2 disjunct subsequences of σ. Subsequence i ∈ {1,...,l-2} starts at the second position of phase i+1 and end with the first position of phase i+2.<br>
Let x be the first page of phase i+1. At the beginning of subsequence i there is page x and at most k-1 different pages in the optimal offline algorithms cache. In subsequence i are k page request different from x, so the optimal offline algorithm has to evict at least one page for every subsequence. Since at phase 1 beginning the cache is still empty, the optimal offline algorithm causes k evictions during the first phase. That shows that</p> <blockquote></blockquote> <p>w<sub>A</sub>(σ) ≤ l⋅k ≤ (k+l-2)k ≤ OPT(σ) ⋅ k</p> <p><strong>Corollary 1.5:</strong> <strong>LRU</strong> and <strong>FWF</strong> are <strong>strictly k-competitive</strong>.</p> <p>Is there no constant r for which an online algorithm A is r-competitive, we call A <strong>not competitive</strong>.</p> <p><strong>Proposition 1.6:</strong> <strong>LFU</strong> and <strong>LIFO</strong> are <strong>not competitive</strong>.</p> <p><strong>Proof:</strong> Let l ≥ 2 a constant, k ≥ 2 the cache size. The different cache pages are nubered 1,...,k+1. We look at the following sequence:</p> <blockquote></blockquote> <p><a href="https://i.stack.imgur.com/zS05d.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/zS05d.png" alt="enter image description here"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>First page 1 is requested l times than page 2 and so one. At the end there are (l-1) alternating requests for page k and k+1. <br> <strong>LFU</strong> and <strong>LIFO</strong> fill their cache with pages 1-k. When page k+1 is requested page k is evicted and vice versa. That means every request of subsequence (k,k+1)<sup>l-1</sup> evicts one page. In addition their are k-1 cache misses for the first time use of pages 1-(k-1). So <strong>LFU</strong> and <strong>LIFO</strong> evict exact k-1+2(l-1) pages.<br>
Now we must show that for every constant τ∈ℜ and every constan r ≤ 1 there exists an l so that</p> <blockquote></blockquote> <p><a href="https://i.stack.imgur.com/lUOxY.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/lUOxY.png" alt="enter image description here"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>which is equal to</p> <blockquote></blockquote> <p><a href="https://i.stack.imgur.com/arDFI.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/arDFI.png" alt="enter image description here"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>To satisfy this inequality you just have to choose l sufficient big. So <strong>LFU</strong> and <strong>LIFO</strong> are not competetive.</p> <p><strong>Proposition 1.7:</strong> There is <strong>no r-competetive</strong> deterministic online algorithm for paging with <strong>r < k</strong>.</p> <h3 id="sources"><a href="#sources" class="header-anchor">#</a> Sources</h3> <h3 id="basic-material"><a href="#basic-material" class="header-anchor">#</a> Basic Material</h3> <ol><li>Script Online Algorithms (german), Heiko Roeglin, University Bonn</li> <li><a href="https://en.wikipedia.org/wiki/Page_replacement_algorithm" target="_blank" rel="noopener noreferrer">Page replacement algorithm<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></li></ol> <h3 id="further-reading"><a href="#further-reading" class="header-anchor">#</a> Further Reading</h3> <ol><li><a href="http://www.cs.technion.ac.il/%7Erani/book.html" target="_blank" rel="noopener noreferrer">Online Computation and Competetive Analysis<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a> by Allan Borodin and Ran El-Yaniv</li></ol> <h3 id="source-code"><a href="#source-code" class="header-anchor">#</a> Source Code</h3> <ol><li>Source code for <a href="http://pastebin.com/AF7EC2xJ" target="_blank" rel="noopener noreferrer">offline caching<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></li> <li>Source code for <a href="https://pastebin.com/u/kgoedde/1/Wak9refA" target="_blank" rel="noopener noreferrer">adversary game<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></li></ol></div> <footer class="page-edit"><div class="edit-link"><a href="https://github.com/devtut/generate/edit/master/docs/algorithm/online-algorithms.md" target="_blank" rel="noopener noreferrer">Edit this page on GitHub</a> <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></div> <!----></footer> <div class="page-nav"><p class="inner"><span class="prev">
←
<a href="/algorithm/edit-distance-dynamic-algorithm.html" class="prev">
Edit Distance Dynamic Algorithm
</a></span> <span class="next"><a href="/algorithm/integer-partition-algorithm.html">
Integer Partition Algorithm
</a>
→
</span></p></div> </main></div><div class="global-ui"><!----></div></div>
<script src="/assets/js/app.1779e102.js" defer></script><script src="/assets/js/3.2cfa8016.js" defer></script><script src="/assets/js/59.6dfdd9ba.js" defer></script>
</body>
</html>