tag:blogger.com,1999:blog-61948392024-03-08T04:58:23.859+05:30Balbir's BlogI describe all the programming and non-programming stuff I doBalbirhttp://www.blogger.com/profile/17752733091129859385noreply@blogger.comBlogger443125tag:blogger.com,1999:blog-6194839.post-61214005437975851792023-12-27T12:31:00.003+05:302023-12-29T07:10:40.202+05:30Ranking and Unranking permutations<p>I've been a big fan of Skiena's <a href="https://www.algorist.com/" target="_blank">Algorithm Design Manual</a>, I recently found my first edition of the book (although I own the third edition), I felt guilty for not using and started with the much more compact first edition. I do run into errata, but being able to discover it on my own and see it fixed in the new editions, provides a lot of satisfaction :)</p><p>One of the commonly used algorithms for combinatorics is ranking and unranking of permutations. The algorithm provided in the book is derived from the Combinatorica package. The book provides an example or two, which is quite terse, so I decided to implement things myself. There is a slightly better explanation in <a href="https://www.cambridge.org/core/books/computational-discrete-mathematics/8DC544DE0083D555A110BEBCB8A277D5">Computational Discrete Mathematics</a>, also written by the same author.</p><p>Here is my python implementation of the rank/unrank algorithm(s)
<!-- HTML generated using hilite.me --><div style="background: #ffffff; overflow:auto;width:auto;border:solid gray;border-width:.1em .1em .1em .8em;padding:.2em .6em;"><table><tr><td><pre style="margin: 0; line-height: 125%"> 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</pre></td><td><pre style="margin: 0; line-height: 125%"><span style="color: #008800; font-weight: bold">import</span> <span style="color: #0e84b5; font-weight: bold">functools</span>
<span style="color: #555555; font-weight: bold">@functools.lru_cache</span>(maxsize<span style="color: #333333">=</span><span style="color: #007020">None</span>)
<span style="color: #008800; font-weight: bold">def</span> <span style="color: #0066BB; font-weight: bold">fact</span>(n):
<span style="color: #008800; font-weight: bold">if</span> n <span style="color: #333333">==</span> <span style="color: #0000DD; font-weight: bold">1</span> <span style="color: #000000; font-weight: bold">or</span> n <span style="color: #333333">==</span> <span style="color: #0000DD; font-weight: bold">0</span>:
<span style="color: #008800; font-weight: bold">return</span> <span style="color: #0000DD; font-weight: bold">1</span>
<span style="color: #008800; font-weight: bold">else</span>:
<span style="color: #008800; font-weight: bold">return</span> n<span style="color: #333333">*</span>fact(n<span style="color: #333333">-</span><span style="color: #0000DD; font-weight: bold">1</span>)
<span style="color: #008800; font-weight: bold">assert</span> fact(<span style="color: #0000DD; font-weight: bold">5</span>) <span style="color: #333333">==</span> <span style="color: #0000DD; font-weight: bold">120</span>
<span style="color: #008800; font-weight: bold">assert</span> fact(<span style="color: #0000DD; font-weight: bold">0</span>) <span style="color: #333333">==</span> <span style="color: #0000DD; font-weight: bold">1</span>
<span style="color: #888888">#@param perm - given a permutation as an array, calculate it's rank</span>
<span style="color: #008800; font-weight: bold">def</span> <span style="color: #0066BB; font-weight: bold">rank</span>(perm):
<span style="color: #008800; font-weight: bold">if</span> <span style="color: #000000; font-weight: bold">not</span> <span style="color: #007020">isinstance</span>(perm, <span style="color: #007020">list</span>):
<span style="color: #008800; font-weight: bold">raise</span> <span style="background-color: #fff0f0">"Invalid input"</span>
<span style="color: #008800; font-weight: bold">else</span>:
n <span style="color: #333333">=</span> <span style="color: #007020">len</span>(perm)
<span style="color: #008800; font-weight: bold">if</span> n <span style="color: #333333">==</span> <span style="color: #0000DD; font-weight: bold">0</span> <span style="color: #000000; font-weight: bold">or</span> (n <span style="color: #333333">==</span> <span style="color: #0000DD; font-weight: bold">1</span> <span style="color: #000000; font-weight: bold">and</span> perm[<span style="color: #0000DD; font-weight: bold">0</span>] <span style="color: #333333">==</span> <span style="color: #0000DD; font-weight: bold">1</span>):
<span style="color: #008800; font-weight: bold">return</span> <span style="color: #0000DD; font-weight: bold">0</span>
rest <span style="color: #333333">=</span> <span style="color: #007020">list</span>(<span style="color: #007020">map</span>(<span style="color: #008800; font-weight: bold">lambda</span> x: x <span style="color: #333333">-</span> <span style="color: #0000DD; font-weight: bold">1</span> <span style="color: #008800; font-weight: bold">if</span> x <span style="color: #333333">></span> perm[<span style="color: #0000DD; font-weight: bold">0</span>] <span style="color: #008800; font-weight: bold">else</span> x, perm[<span style="color: #0000DD; font-weight: bold">1</span>:]))
<span style="color: #008800; font-weight: bold">return</span> (perm[<span style="color: #0000DD; font-weight: bold">0</span>]<span style="color: #333333">-</span><span style="color: #0000DD; font-weight: bold">1</span>) <span style="color: #333333">*</span> fact(n<span style="color: #333333">-</span><span style="color: #0000DD; font-weight: bold">1</span>) <span style="color: #333333">+</span> rank(rest)
<span style="color: #888888">#@param n, k - given rank k of an n element permutation, print it</span>
<span style="color: #008800; font-weight: bold">def</span> <span style="color: #0066BB; font-weight: bold">unrank</span>(k, n, perm):
q, r <span style="color: #333333">=</span> <span style="color: #007020">divmod</span>(k, fact(n <span style="color: #333333">-</span> <span style="color: #0000DD; font-weight: bold">1</span>))
perm[<span style="color: #0000DD; font-weight: bold">0</span>] <span style="color: #333333">=</span> q <span style="color: #333333">+</span> <span style="color: #0000DD; font-weight: bold">1</span>
<span style="color: #008800; font-weight: bold">if</span> n <span style="color: #333333">==</span> <span style="color: #0000DD; font-weight: bold">1</span>:
<span style="color: #008800; font-weight: bold">return</span> [perm[<span style="color: #0000DD; font-weight: bold">0</span>]]
rest <span style="color: #333333">=</span> perm[<span style="color: #0000DD; font-weight: bold">1</span>:]
newperm <span style="color: #333333">=</span> unrank(r, n <span style="color: #333333">-</span> <span style="color: #0000DD; font-weight: bold">1</span>, rest)
rest <span style="color: #333333">=</span> <span style="color: #007020">list</span>(<span style="color: #007020">map</span>(<span style="color: #008800; font-weight: bold">lambda</span> x: x<span style="color: #333333">+</span><span style="color: #0000DD; font-weight: bold">1</span> <span style="color: #008800; font-weight: bold">if</span> x <span style="color: #333333">>=</span> perm[<span style="color: #0000DD; font-weight: bold">0</span>] <span style="color: #008800; font-weight: bold">else</span> x, newperm))
<span style="color: #008800; font-weight: bold">return</span> [perm[<span style="color: #0000DD; font-weight: bold">0</span>]] <span style="color: #333333">+</span> rest
</pre></td></tr></table></div>
<p>Here are some simple tests and their output</p><div style="text-align: left;"><span style="font-family: courier; font-size: x-small;">for i in range(24):<br /></span><span style="font-family: courier; font-size: x-small;"> perm=[0 for i in range(4)]<br /></span><span style="font-family: courier; font-size: x-small;"> perm=unrank(i, 4, perm)<br /></span><span style="font-family: courier; font-size: x-small;"> print(perm, "->", rank(perm))</span></div><div style="text-align: left;"><span style="font-family: courier; font-size: x-small;"><br /></span></div><div><div class="lm-Widget lm-Panel jp-OutputArea-child" style="background-color: white; box-sizing: border-box; color: rgba(0, 0, 0, 0.87); display: flex; flex-direction: row; overflow: hidden; position: relative; width: 1182px;"><div class="lm-Widget jp-RenderedText jp-mod-trusted jp-OutputArea-output" data-mime-type="application/vnd.jupyter.stdout" style="box-sizing: border-box; flex-grow: 1; flex-shrink: 1; height: auto; line-height: var(--jp-code-line-height); overflow: auto; padding-left: 1ch; position: relative; user-select: text; width: 1118px;"><pre style="border: none; color: var(--jp-content-font-color1); line-height: var(--jp-code-line-height); margin-bottom: 0px; margin-top: 0px; overflow-wrap: break-word; overflow: auto; padding: 0px; text-wrap: wrap; word-break: break-all;"><span style="font-family: courier; font-size: x-small;">[1, 2, 3, 4] -> 0
[1, 2, 4, 3] -> 1
[1, 3, 2, 4] -> 2
[1, 3, 4, 2] -> 3
[1, 4, 2, 3] -> 4
[1, 4, 3, 2] -> 5
[2, 1, 3, 4] -> 6
[2, 1, 4, 3] -> 7
[2, 3, 1, 4] -> 8
[2, 3, 4, 1] -> 9
[2, 4, 1, 3] -> 10
[2, 4, 3, 1] -> 11
[3, 1, 2, 4] -> 12
[3, 1, 4, 2] -> 13
[3, 2, 1, 4] -> 14
[3, 2, 4, 1] -> 15
[3, 4, 1, 2] -> 16
[3, 4, 2, 1] -> 17
[4, 1, 2, 3] -> 18
[4, 1, 3, 2] -> 19
[4, 2, 1, 3] -> 20
[4, 2, 3, 1] -> 21
[4, 3, 1, 2] -> 22
[4, 3, 2, 1] -> 23
</span></pre><div><br /></div></div></div></div><p>Eyeballing them, they look right to me</p><p><b>Next steps:</b></p><p><a href="https://rosettacode.org/wiki/Permutations/Rank_of_a_permutation" target="_blank">Rosetta Code Ranking of Permutations</a> has a comprehensive implementation of ranking/unranking algorithms, including iterative implementations. I would recommend moving to these set as they can be much more performant<br /></p><p><br /></p>Balbirhttp://www.blogger.com/profile/17752733091129859385noreply@blogger.com0tag:blogger.com,1999:blog-6194839.post-32246049318875859042022-03-27T14:19:00.002+05:302023-05-28T17:08:12.779+05:30Introduction to Algorithms Fourth Edition (almost out, so is the code)<div class="separator" style="clear: both; text-align: center;"><br /></div><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://mit-press-us.imgix.net/covers/9780262046305.jpg?auto=format&w=298&dpr=2&q=20" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="679" data-original-width="596" height="679" src="https://mit-press-us.imgix.net/covers/9780262046305.jpg?auto=format&w=298&dpr=2&q=20" width="596" /></a></div><br /><p><br /></p><p> The book is almost out <a href="https://mitpress.mit.edu/books/introduction-algorithms-fourth-edition">there</a>. There is <a href="http://mitp-content-server.mit.edu:18180/books/content/sectbyfn?collid=books_pres_0&id=11599&fn=clrsPython.zip">code</a> and <a href="https://mitp-content-server.mit.edu/books/content/sectbyfn?collid=books_pres_0&id=11599&fn=selected-solutions.pdf">selected solutions</a> as well. The book is supposed to be in full colour from what I heard. What do you think of the code? There is an interesting <a href="https://www.youtube.com/watch?v=9lTGHkvGL8Q&feature=emb_rel_pause">interview</a> as well.</p>Balbirhttp://www.blogger.com/profile/17752733091129859385noreply@blogger.com0tag:blogger.com,1999:blog-6194839.post-24077810421008671182022-03-27T14:14:00.002+05:302022-03-27T14:14:28.979+05:30Defer style programming in C<p> It's a well known trick, but I loved the ability to defer functions in golang. In C, gcc provides an attribute for cleanup. I posted a pull request for the <a href="https://github.com/libcgroup/libcgroup/pull/117">libcgroup</a>. Turns out systemd has something similar, but I do like that the attributes have implicit functions and the overall design seems cleaner. I do not like dereferencing a double void star pointer though.</p><p>More details can be found in the pull request</p>Balbirhttp://www.blogger.com/profile/17752733091129859385noreply@blogger.com0tag:blogger.com,1999:blog-6194839.post-79257776767235655762021-11-28T12:44:00.008+05:302021-11-29T06:54:39.109+05:30Test Driven Development<p><span style="font-family: inherit;">I've been learning <a href="https://www.rust-lang.org/" target="_blank">rust</a> programming language. The addition of the ability to write tests in-built is quite a welcome change to most programming languages. I found that I spent a lot of time debugging corner cases (bounds) in my algorithms, so I decided to do a test driven approach (not a chaos/random approach), but more targetted towards my weakness with boundary conditions. My favourite small/short/complex algorithm is quicksort.<a></a></span></p><p>Here is the code I wrote</p><div style="line-height: 19px;"><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"><span style="color: blue;">use</span> std::cmp::PartialOrd;</div><span style="background-color: #fffffe; font-family: Consolas, Liberation Mono, Courier, monospace, Droid Sans Mono, monospace, monospace, Droid Sans Fallback; font-size: 14px; white-space: pre;"><br /></span><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"><span style="color: green;">/// Quicksort</span></div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"><span style="color: green;">/// Simple sort algorithm that is type aware and is unique in that it's test driven</span></div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"><span style="color: green;">/// </span></div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"><span style="color: blue;">fn</span> partition<T: PartialOrd>(elements: &<span style="color: blue;">mut</span> [T], low: usize, high: usize) -> usize {</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: green;">// Explictly set the pivot to the lowest element</span></div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">let</span> <span style="color: blue;">mut</span> i : usize;</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">let</span> <span style="color: blue;">mut</span> j : usize;</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> </div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">if</span> high <= low {</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">return</span> low;</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> }</div><span style="background-color: #fffffe; font-family: Consolas, Liberation Mono, Courier, monospace, Droid Sans Mono, monospace, monospace, Droid Sans Fallback; font-size: 14px; white-space: pre;"><br /></span><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> i = low; j = high -<span style="color: #098658;">1</span>; <span style="color: green;">// Bounds 1, check</span></div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> </div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">while</span> i < j {</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">while</span> elements[i] <= elements[low] && i < (high-<span style="color: #098658;">1</span>) { i = i + <span style="color: #098658;">1</span>; } <span style="color: green;">// Bounds 2</span></div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">while</span> elements[j] >= elements[low] && j > low { j = j - <span style="color: #098658;">1</span>; } <span style="color: green;">// Bounds 3</span></div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> </div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">if</span> i >= j {<span style="color: blue;">break</span>; } <span style="color: green;">// Bounds 4</span></div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> </div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> elements.swap(i, j); <span style="color: green;">// Check 5</span></div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> }</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> elements.swap(low, j); <span style="color: green;">// Check 6</span></div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> j</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;">}</div><span style="background-color: #fffffe; font-family: Consolas, Liberation Mono, Courier, monospace, Droid Sans Mono, monospace, monospace, Droid Sans Fallback; font-size: 14px; white-space: pre;"><br /></span><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"><span style="color: blue;">fn</span> __quicksort<T: PartialOrd + std::fmt::Debug>(elements: &<span style="color: blue;">mut</span> [T], low: usize, high: usize)</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;">{</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">let</span> p = partition(elements, low, high);</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">if</span> p > low {</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> __quicksort(elements, low, p);</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> }</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">if</span> p < high {</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> __quicksort(elements, p+<span style="color: #098658;">1</span>, high);</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> }</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;">}</div><span style="background-color: #fffffe; font-family: Consolas, Liberation Mono, Courier, monospace, Droid Sans Mono, monospace, monospace, Droid Sans Fallback; font-size: 14px; white-space: pre;"><br /></span><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"><span style="color: blue;">fn</span> quicksort<T: PartialOrd + std::fmt::Debug>(elements: &<span style="color: blue;">mut</span> [T])</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;">{</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">let</span> len = elements.len();</div><span style="background-color: #fffffe; font-family: Consolas, Liberation Mono, Courier, monospace, Droid Sans Mono, monospace, monospace, Droid Sans Fallback; font-size: 14px; white-space: pre;"><br /></span><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> __quicksort(elements, <span style="color: #098658;">0</span>, len);</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;">}</div><span style="background-color: #fffffe; font-family: Consolas, Liberation Mono, Courier, monospace, Droid Sans Mono, monospace, monospace, Droid Sans Fallback; font-size: 14px; white-space: pre;"><br /></span><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;">#[test]</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"><span style="color: blue;">fn</span> partition_bounds_test_single()</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;">{</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">let</span> <span style="color: blue;">mut</span> elements = vec![<span style="color: #098658;">1</span>];</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> assert_eq!(<span style="color: #098658;">0</span>, partition(&<span style="color: blue;">mut</span> elements, <span style="color: #098658;">0</span>, <span style="color: #098658;">1</span>));</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;">}</div><span style="background-color: #fffffe; font-family: Consolas, Liberation Mono, Courier, monospace, Droid Sans Mono, monospace, monospace, Droid Sans Fallback; font-size: 14px; white-space: pre;"><br /></span><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;">#[test]</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"><span style="color: blue;">fn</span> partition_bounds_test_mostly_sorted()</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;">{</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">let</span> <span style="color: blue;">mut</span> elements = vec![<span style="color: #098658;">10</span>, <span style="color: #098658;">2</span>, <span style="color: #098658;">4</span>, <span style="color: #098658;">5</span>, <span style="color: #098658;">6</span>];</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">let</span> expected = vec![<span style="color: #098658;">6</span>, <span style="color: #098658;">2</span>, <span style="color: #098658;">4</span>, <span style="color: #098658;">5</span>, <span style="color: #098658;">10</span>];</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">let</span> len = elements.len();</div><span style="background-color: #fffffe; font-family: Consolas, Liberation Mono, Courier, monospace, Droid Sans Mono, monospace, monospace, Droid Sans Fallback; font-size: 14px; white-space: pre;"><br /></span><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> assert_eq!(<span style="color: #098658;">4</span>, partition(&<span style="color: blue;">mut</span> elements, <span style="color: #098658;">0</span>, len));</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> assert_eq!(expected, elements);</div><span style="background-color: #fffffe; font-family: Consolas, Liberation Mono, Courier, monospace, Droid Sans Mono, monospace, monospace, Droid Sans Fallback; font-size: 14px; white-space: pre;"><br /></span><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">let</span> <span style="color: blue;">mut</span> elements = vec![<span style="color: #098658;">2</span>, <span style="color: #098658;">4</span>, <span style="color: #098658;">5</span>, <span style="color: #098658;">6</span>, <span style="color: #098658;">10</span>];</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">let</span> expected = vec![<span style="color: #098658;">2</span>, <span style="color: #098658;">4</span>, <span style="color: #098658;">5</span>, <span style="color: #098658;">6</span>, <span style="color: #098658;">10</span>];</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">let</span> len = elements.len();</div><span style="background-color: #fffffe; font-family: Consolas, Liberation Mono, Courier, monospace, Droid Sans Mono, monospace, monospace, Droid Sans Fallback; font-size: 14px; white-space: pre;"><br /></span><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> </div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> assert_eq!(<span style="color: #098658;">0</span>, partition(&<span style="color: blue;">mut</span> elements, <span style="color: #098658;">0</span>, len));</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> assert_eq!(expected, elements);</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;">}</div><span style="background-color: #fffffe; font-family: Consolas, Liberation Mono, Courier, monospace, Droid Sans Mono, monospace, monospace, Droid Sans Fallback; font-size: 14px; white-space: pre;"><br /></span><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;">#[test]</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"><span style="color: blue;">fn</span> partition_bounds_test_2_elements_sorted()</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;">{</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">let</span> <span style="color: blue;">mut</span> elements = vec![<span style="color: #098658;">15</span>, <span style="color: #098658;">10</span>];</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">let</span> expected = vec![<span style="color: #098658;">10</span>, <span style="color: #098658;">15</span>];</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">let</span> len = elements.len();</div><span style="background-color: #fffffe; font-family: Consolas, Liberation Mono, Courier, monospace, Droid Sans Mono, monospace, monospace, Droid Sans Fallback; font-size: 14px; white-space: pre;"><br /></span><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> assert_eq!(<span style="color: #098658;">1</span>, partition(&<span style="color: blue;">mut</span> elements, <span style="color: #098658;">0</span>, len));</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> assert_eq!(expected, elements);</div><span style="background-color: #fffffe; font-family: Consolas, Liberation Mono, Courier, monospace, Droid Sans Mono, monospace, monospace, Droid Sans Fallback; font-size: 14px; white-space: pre;"><br /></span><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">let</span> <span style="color: blue;">mut</span> elements = vec![<span style="color: #098658;">10</span>, <span style="color: #098658;">15</span>];</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">let</span> expected = vec![<span style="color: #098658;">10</span>, <span style="color: #098658;">15</span>];</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">let</span> len = elements.len();</div><span style="background-color: #fffffe; font-family: Consolas, Liberation Mono, Courier, monospace, Droid Sans Mono, monospace, monospace, Droid Sans Fallback; font-size: 14px; white-space: pre;"><br /></span><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> assert_eq!(<span style="color: #098658;">0</span>, partition(&<span style="color: blue;">mut</span> elements, <span style="color: #098658;">0</span>, len));</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> assert_eq!(expected, elements);</div><span style="background-color: #fffffe; font-family: Consolas, Liberation Mono, Courier, monospace, Droid Sans Mono, monospace, monospace, Droid Sans Fallback; font-size: 14px; white-space: pre;"><br /></span><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">let</span> <span style="color: blue;">mut</span> elements = vec![<span style="color: #098658;">15</span>, <span style="color: #098658;">5</span>, <span style="color: #098658;">10</span>];</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">let</span> expected = vec![<span style="color: #098658;">10</span>, <span style="color: #098658;">5</span>, <span style="color: #098658;">15</span>];</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">let</span> len = elements.len();</div><span style="background-color: #fffffe; font-family: Consolas, Liberation Mono, Courier, monospace, Droid Sans Mono, monospace, monospace, Droid Sans Fallback; font-size: 14px; white-space: pre;"><br /></span><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> assert_eq!(<span style="color: #098658;">2</span>, partition(&<span style="color: blue;">mut</span> elements, <span style="color: #098658;">0</span>, len));</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> assert_eq!(expected, elements);</div><span style="background-color: #fffffe; font-family: Consolas, Liberation Mono, Courier, monospace, Droid Sans Mono, monospace, monospace, Droid Sans Fallback; font-size: 14px; white-space: pre;"><br /></span><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> </div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;">}</div><span style="background-color: #fffffe; font-family: Consolas, Liberation Mono, Courier, monospace, Droid Sans Mono, monospace, monospace, Droid Sans Fallback; font-size: 14px; white-space: pre;"><br /></span><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;">#[test]</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"><span style="color: blue;">fn</span> quicksort_test()</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;">{</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">let</span> <span style="color: blue;">mut</span> vec = vec![<span style="color: #098658;">1</span>, <span style="color: #098658;">5</span>, <span style="color: #098658;">10</span>, <span style="color: #098658;">2</span>, <span style="color: #098658;">15</span>];</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">let</span> <span style="color: blue;">mut</span> vec2 = vec.clone();</div><span style="background-color: #fffffe; font-family: Consolas, Liberation Mono, Courier, monospace, Droid Sans Mono, monospace, monospace, Droid Sans Fallback; font-size: 14px; white-space: pre;"><br /></span><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> quicksort(&<span style="color: blue;">mut</span> vec);</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> vec2.sort();</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> assert_eq!(vec![<span style="color: #098658;">1</span>, <span style="color: #098658;">2</span>, <span style="color: #098658;">5</span>, <span style="color: #098658;">10</span>, <span style="color: #098658;">15</span>], vec);</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> assert_eq!(vec2, vec);</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> </div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">let</span> <span style="color: blue;">mut</span> vec = vec![<span style="color: #098658;">1.1</span>, <span style="color: #098658;">1.15</span>, <span style="color: #098658;">5.5</span>, <span style="color: #098658;">1.123</span>, <span style="color: #098658;">2.0</span>];</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> quicksort(&<span style="color: blue;">mut</span> vec);</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> assert_eq!(vec, vec![<span style="color: #098658;">1.1</span>, <span style="color: #098658;">1.123</span>, <span style="color: #098658;">1.15</span>, <span style="color: #098658;">2.0</span>, <span style="color: #098658;">5.5</span>]);</div><span style="background-color: #fffffe; font-family: Consolas, Liberation Mono, Courier, monospace, Droid Sans Mono, monospace, monospace, Droid Sans Fallback; font-size: 14px; white-space: pre;"><br /></span><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">let</span> <span style="color: blue;">mut</span> vec = vec![<span style="color: #098658;">1</span>, <span style="color: #098658;">5</span>, <span style="color: #098658;">10</span>, <span style="color: #098658;">15</span>, <span style="color: #098658;">2</span>];</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">let</span> <span style="color: blue;">mut</span> vec2 = vec.clone();</div><span style="background-color: #fffffe; font-family: Consolas, Liberation Mono, Courier, monospace, Droid Sans Mono, monospace, monospace, Droid Sans Fallback; font-size: 14px; white-space: pre;"><br /></span><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> quicksort(&<span style="color: blue;">mut</span> vec);</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> vec2.sort();</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> assert_eq!(vec2, vec);</div><span style="background-color: #fffffe; font-family: Consolas, Liberation Mono, Courier, monospace, Droid Sans Mono, monospace, monospace, Droid Sans Fallback; font-size: 14px; white-space: pre;"><br /></span><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">let</span> <span style="color: blue;">mut</span> vec = vec![<span style="color: #098658;">15</span>, <span style="color: #098658;">5</span>, <span style="color: #098658;">10</span>];</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">let</span> <span style="color: blue;">mut</span> vec2 = vec.clone();</div><span style="background-color: #fffffe; font-family: Consolas, Liberation Mono, Courier, monospace, Droid Sans Mono, monospace, monospace, Droid Sans Fallback; font-size: 14px; white-space: pre;"><br /></span><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> quicksort(&<span style="color: blue;">mut</span> vec);</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> vec2.sort();</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> assert_eq!(vec2, vec);</div><span style="background-color: #fffffe; font-family: Consolas, Liberation Mono, Courier, monospace, Droid Sans Mono, monospace, monospace, Droid Sans Fallback; font-size: 14px; white-space: pre;"><br /><br /></span><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">let</span> <span style="color: blue;">mut</span> vec = vec![<span style="color: #098658;">1</span>, <span style="color: #098658;">2</span>, <span style="color: #098658;">3</span>, <span style="color: #098658;">4</span>, <span style="color: #098658;">5</span>];</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">let</span> <span style="color: blue;">mut</span> vec2 = vec.clone();</div><span style="background-color: #fffffe; font-family: Consolas, Liberation Mono, Courier, monospace, Droid Sans Mono, monospace, monospace, Droid Sans Fallback; font-size: 14px; white-space: pre;"><br /></span><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> quicksort(&<span style="color: blue;">mut</span> vec);</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> vec2.sort();</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> assert_eq!(vec2, vec);</div><span style="background-color: #fffffe; font-family: Consolas, Liberation Mono, Courier, monospace, Droid Sans Mono, monospace, monospace, Droid Sans Fallback; font-size: 14px; white-space: pre;"><br /></span><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">let</span> <span style="color: blue;">mut</span> vec = vec![<span style="color: #098658;">5</span>, <span style="color: #098658;">4</span>, <span style="color: #098658;">3</span>, <span style="color: #098658;">2</span>, <span style="color: #098658;">1</span>];</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> <span style="color: blue;">let</span> <span style="color: blue;">mut</span> vec2 = vec.clone();</div><span style="background-color: #fffffe; font-family: Consolas, Liberation Mono, Courier, monospace, Droid Sans Mono, monospace, monospace, Droid Sans Fallback; font-size: 14px; white-space: pre;"><br /></span><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> quicksort(&<span style="color: blue;">mut</span> vec);</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> vec2.sort();</div><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;"> assert_eq!(vec2, vec);</div><span style="background-color: #fffffe; font-family: Consolas, Liberation Mono, Courier, monospace, Droid Sans Mono, monospace, monospace, Droid Sans Fallback; font-size: 14px; white-space: pre;"><br /></span><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; white-space: pre;">}</div><span style="background-color: #fffffe; font-size: 14px; white-space: pre;"><div style="font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", monospace, monospace, "Droid Sans Fallback"; line-height: 19px;"><span style="background-color: #fffffe; font-family: Consolas, Liberation Mono, Courier, monospace, Droid Sans Mono, monospace, monospace, Droid Sans Fallback; font-size: 14px; white-space: pre;"><br /></span></div><div style="font-size: medium; white-space: normal;"><span style="font-family: inherit;">Notice, the identification of the various conditions as bounds with a number in the partition algorithm. Looking at the algorithm, the following caught my attention</span></div></span><div><ol style="text-align: left;"><li><span style="font-family: inherit;">The use of the parameter high in the algorithm is unique, high is always one greater than the last element, so should the contract abstract it and expect a pointer to the last element? Notice the use of high-1 more than once in the code.</span></li><li><span style="font-family: inherit;">Rust itself has some quirks associated with the Borrow Checker, after taking a mutable reference to the vector, one cannot use elements.len(), since that internally grabs a shared reference (the compiler tells you).</span></li><li><span style="font-family: inherit;">The while loops use elements[i] <= elements[low], even though elements[low] is constant, using it before the loop causes a move of the element to the temporary variable used to cache it and that causes the Borrow Checker to complain, it might be possible to do some interesting things by having the template type T have a constraint that requires it to implement the Copy trait.</span></li><li><span style="font-family: inherit;">Typically quicksort partitions the elements at p and do a quicksort with 0, p-1 and p+1 to high, but since the bounds is [low, high), we need to ensure we pass p as oposed to p-1</span></li></ol><div style="text-align: left;"><span style="background-color: #fffffe; white-space: pre;"><span style="font-family: inherit;">To deal with the complexity of the algorithm (points 1 through 4 above), I decided to use a test driven</span></span></div><div style="text-align: left;"><span style="background-color: #fffffe; font-family: inherit; font-size: 14px; white-space: pre;"><div style="font-size: medium; white-space: normal;"><span style="white-space: pre;">approach and tried to cover as many cases as I could think off and extracted coverage.</span></div><div style="font-size: medium; white-space: normal;"><span style="white-space: pre;">(you need the nightly compiler for it).</span></div><div style="font-size: medium; white-space: normal;"><p></p><p></p><p></p><p></p></div></span><div></div></div><div style="text-align: left;"><span style="background-color: #fffffe; white-space: pre;"><span style="font-family: inherit;">Here is what the output looks like</span></span></div><div style="text-align: left;"><br /></div><div style="text-align: left;"><pre style="overflow-wrap: break-word; white-space: pre-wrap;"><span style="font-size: x-small;"> 1| 1|use std::cmp::PartialOrd;use std::cmp::PartialOrd;
2| |
3| |/// Quicksort
4| |/// Simple sort algorithm that is type aware and is unique in that it's test driven
5| |///
6| 49|fn partition<T: PartialOrd>(elements: &mut [T], low: usize, high: usize) -> usize {
7| 49| // Explictly set the pivot to the lowest element
8| 49| let mut i : usize;
9| 49| let mut j : usize;
10| 49|
11| 49| if high <= low {
12| 15| return low;
13| 34| }
14| 34|
15| 34| i = low; j = high -1; // Bounds 1, check
16| |
17| 37| while i < j {
18| 63| while elements[i] <= elements[low] && i < (high-1) { i = i + 1; } // Bounds 2
^45 ^36
19| 65| while elements[j] >= elements[low] && j > low { j = j - 1; } // Bounds 3
^50 ^38
20| |
21| 27| if i >= j {break; } // Bounds 4
^24
22| 3|
23| 3| elements.swap(i, j); // Check 5
24| | }
25| 34| elements.swap(low, j); // Check 6
26| 34| j
27| 49|}
</span></pre><div><pre style="overflow-wrap: break-word; white-space: pre-wrap;"><span style="font-size: x-small;"> 28| |
29| 43|fn __quicksort<T: PartialOrd + std::fmt::Debug>(elements: &mut [T], low: usize, high: usize)
30| 43|{
31| 43| let p = partition(elements, low, high);
32| 43| // p - 1 should not be negative
33| 43| if p > low {
34| 9| __quicksort(elements, low, p);
35| 34| }
36| 43| if p < high {
37| 28| __quicksort(elements, p+1, high);
38| 28| }
^15
39| 43|}
</span></pre></div><div><span style="font-size: x-small;"><br /></span></div><div><pre style="overflow-wrap: break-word; white-space: pre-wrap;"><span style="font-size: x-small;"> 41| 6|fn quicksort<T: PartialOrd + std::fmt::Debug>(elements: &mut [T])
42| 6|{
43| 6| let len = elements.len();
44| 6|
45| 6| __quicksort(elements, 0, len);
46| 6|}
</span></pre></div><div><br /></div></div><nav class="level" style="align-items: center; background-color: white; box-sizing: inherit; color: #4a4a4a; display: flex; font-size: 16px; justify-content: space-between; margin-bottom: 1.5rem; white-space: normal;"><div class="level-item has-text-centered" style="align-items: center; box-sizing: inherit; display: flex; flex: 1 0 auto; justify-content: center; text-align: center;"><div style="box-sizing: inherit;"><p class="heading" style="box-sizing: inherit; font-size: 11px; letter-spacing: 1px; margin: 0px 0px 5px; padding: 0px; text-transform: uppercase;"><br /></p></div></div></nav><p style="background-color: #fffffe; font-size: 14px; white-space: pre;"></p><p style="background-color: #fffffe;"><span style="font-family: inherit; font-size: medium; white-space: normal;">Not bad, but the branch coverage needs improvement. This variant of quicksort is prone to several errors, although it might seem faster at first look. Interestingly, the algorithms book by <a href="http://jeffe.cs.illinois.edu/teaching/algorithms/book/Algorithms-JeffE.pdf" target="_blank">Jeff Erickson</a> very correctly states </span></p><blockquote style="background-color: #fffffe;"><span style="font-family: inherit;">Hoare proposed a more complicated “two-way” partitioning algorithm that has some practical advantages over Lomuto’s algorithm. On the other hand, Hoare’s partitioning algorithm is one of the places off-by-one errors go to die</span></blockquote><p style="background-color: #fffffe;"><span style="font-family: inherit;">I do find the Lomuto's algorithm easier to parse and implement. What do you think? Is test-driven iterative development the right way forward for even things like data structures? What's the best way to compute the total number of branches and cover them? Should we search for easier alternatives that perform well and are easier to test? </span></p><p style="background-color: #fffffe;"><span style="font-family: inherit;"><br /></span></p><p style="background-color: #fffffe;"><b>Update</b>: I made some slice based improvements to the code, with the Lomuto algorithm as well</p><pre style="background-color: white; color: #080808; font-family: 'JetBrains Mono',monospace; font-size: 9.8pt;"><span style="color: #8c8c8c; font-style: italic;">/// Quicksort<br /></span><span style="color: #8c8c8c; font-style: italic;">/// Simple sort algorithm that is type aware and is unique in that it's test driven<br /></span><span style="color: #8c8c8c; font-style: italic;">/// <br /></span><span style="color: #0033b3;">fn </span><span style="color: #00627a;">partition</span><<span style="color: #20999d;">T</span>: <span style="color: black;">PartialOrd</span>>(elements: &<span style="color: #0033b3;">mut </span>[<span style="color: #20999d;">T</span>]) -> <span style="color: #0033b3;">usize </span>{<br /> <span style="color: #8c8c8c; font-style: italic;">// Explictly set the pivot to the lowest element<br /></span><span style="color: #8c8c8c; font-style: italic;"> </span><span style="color: #0033b3;">let mut </span><span style="color: black;">i </span>: <span style="color: #0033b3;">usize</span>;<br /> <span style="color: #0033b3;">let mut </span><span style="color: black;">j </span>: <span style="color: #0033b3;">usize</span>;<br /><br /> <span style="color: #0033b3;">if </span>elements.is_empty() { // Bounds 1<br /> <span style="color: #0033b3;">return </span><span style="color: #1750eb;">0</span>;<br /> }<br /><br /> <span style="color: #0033b3;">let </span><span style="color: black;">high </span>= elements.len();<br /><br /> <span style="color: black;">i </span>= <span style="color: #1750eb;">0</span>;<br /> <span style="color: black;">j </span>= <span style="color: black;">high </span>- <span style="color: #1750eb;">1</span>;<br /><br /> <span style="color: #0033b3;">while </span><span style="color: black;">i </span>< <span style="color: black;">j </span>{ // Bounds 2<br /> <span style="color: #0033b3;">while </span>elements[<span style="color: black;">i</span>] <= elements[<span style="color: #1750eb;">0</span>] && <span style="color: black;">i </span>< (<span style="color: black;">high</span>-<span style="color: #1750eb;">1</span>) { <span style="color: black;">i </span>+= <span style="color: #1750eb;">1</span>; } <span style="color: #8c8c8c; font-style: italic;">// Bounds 3<br /></span><span style="color: #8c8c8c; font-style: italic;"> </span><span style="color: #0033b3;">while </span>elements[<span style="color: black;">j</span>] >= elements[<span style="color: #1750eb;">0</span>] && <span style="color: black;">j </span>> <span style="color: #1750eb;">0 </span>{ <span style="color: black;">j </span>-= <span style="color: #1750eb;">1</span>; } <span style="color: #8c8c8c; font-style: italic;">// Bounds 4<br /></span><span style="color: #8c8c8c; font-style: italic;"> <br /></span><span style="color: #8c8c8c; font-style: italic;"> </span><span style="color: #0033b3;">if </span><span style="color: black;">i </span>>= <span style="color: black;">j </span>{<span style="color: #0033b3;">break</span>; } <span style="color: #8c8c8c; font-style: italic;">// Bounds 5<br /></span><span style="color: #8c8c8c; font-style: italic;"> <br /></span><span style="color: #8c8c8c; font-style: italic;"> </span>elements.swap(<span style="color: black;">i</span>, <span style="color: black;">j</span>); <span style="color: #8c8c8c; font-style: italic;">// Check 6<br /></span><span style="color: #8c8c8c; font-style: italic;"> </span>}<br /> elements.swap(<span style="color: #1750eb;">0</span>, <span style="color: black;">j</span>); <span style="color: #8c8c8c; font-style: italic;">// Check 7<br /></span><span style="color: #8c8c8c; font-style: italic;"> </span><span style="color: black;">j<br /></span>}<br /><br /><span style="color: #0033b3;">fn </span><span style="color: #00627a;">quicksort</span><<span style="color: #20999d;">T</span>: <span style="color: black;">PartialOrd </span>+ <span style="color: black;">std</span>::<span style="color: black;">fmt</span>::<span style="color: black;">Debug</span>>(elements: &<span style="color: #0033b3;">mut </span>[<span style="color: #20999d;">T</span>])<br />{<br /> <span style="color: #0033b3;">let </span><span style="color: black;">low </span>= <span style="color: #1750eb;">0</span>;<br /> <span style="color: #0033b3;">let </span><span style="color: black;">high </span>= elements.len();<br /><br /> <span style="color: #0033b3;">if </span>elements.is_empty() {<br /> <span style="color: #0033b3;">return</span>;<br /> }<br /><br /> <span style="color: #0033b3;">let </span><span style="color: black;">p </span>= partition(&<span style="color: #0033b3;">mut </span>elements[<span style="color: black;">low</span>..<span style="color: black;">high</span>]);<br /> <span style="color: #8c8c8c; font-style: italic;">// p - 1 should not be negative<br /></span><span style="color: #8c8c8c; font-style: italic;"> </span>quicksort(&<span style="color: #0033b3;">mut </span>elements[<span style="color: black;">low</span>..<span style="color: black;">p</span>]);<br /> quicksort(&<span style="color: #0033b3;">mut </span>elements[<span style="color: black;">p</span>+<span style="color: #1750eb;">1</span>..<span style="color: black;">high</span>]);<br />}<br /></pre><pre style="background-color: white; color: #080808; font-family: 'JetBrains Mono',monospace; font-size: 9.8pt;"><pre style="font-family: "JetBrains Mono", monospace; font-size: 9.8pt;"><span style="color: #8c8c8c; font-style: italic;"><br /></span></pre><pre style="font-family: "JetBrains Mono", monospace; font-size: 9.8pt;"><span style="color: #8c8c8c; font-style: italic;">///<br /></span><span style="color: #8c8c8c; font-style: italic;">/// Use the algorithm that has fewer boundary conditions to worry about<br /></span><span style="color: #0033b3;">fn </span><span style="color: #00627a;">lomuto_partition</span><<span style="color: #20999d;">T</span>: <span style="color: black;">std</span>::<span style="color: black;">cmp</span>::<span style="color: black;">PartialOrd</span>>(elements: &<span style="color: #0033b3;">mut </span>[<span style="color: #20999d;">T</span>]) -> <span style="color: #0033b3;">usize<br /></span>{<br /> <span style="color: #0033b3;">let mut </span><span style="color: black;">i</span>: <span style="color: #0033b3;">usize </span>= <span style="color: #1750eb;">0</span>;<br /> <span style="color: #0033b3;">let </span><span style="color: black;">size</span>: <span style="color: #0033b3;">usize </span>= elements.len();<br /> <span style="color: #0033b3;">let mut </span><span style="color: black;">j </span>: <span style="color: #0033b3;">usize </span>= <span style="color: #1750eb;">0</span>;<br /><br /> <span style="color: #0033b3;">if </span>elements.is_empty() { <span style="color: #8c8c8c; font-style: italic;">// bounds 1<br /></span><span style="color: #8c8c8c; font-style: italic;"> </span><span style="color: #0033b3;">return </span><span style="color: #1750eb;">0</span>;<br /> }<br /><br /> <span style="color: #0033b3;">while </span><span style="color: black;">i </span>< <span style="color: black;">size</span>-<span style="color: #1750eb;">1 </span>{ <span style="color: #8c8c8c; font-style: italic;">// bounds 2<br /></span><span style="color: #8c8c8c; font-style: italic;"> </span><span style="color: black;">i </span>+= <span style="color: #1750eb;">1</span>;<br /> <span style="color: #0033b3;">if </span>elements[<span style="color: black;">i</span>] <= elements[<span style="color: #1750eb;">0</span>] { <span style="color: #8c8c8c; font-style: italic;">// bounds 3<br /></span><span style="color: #8c8c8c; font-style: italic;"> </span><span style="color: black;">j </span>+= <span style="color: #1750eb;">1</span>;<br /> elements.swap(<span style="color: black;">i</span>, <span style="color: black;">j</span>); // bounds 4<br /> }<br /> }<br /><br /> elements.swap(<span style="color: #1750eb;">0</span>, <span style="color: black;">j</span>); // bounds 5<br /> <span style="color: black;">j<br /></span>}<br /></pre><pre style="font-family: "JetBrains Mono", monospace; font-size: 9.8pt;"><br /></pre><pre style="font-family: "JetBrains Mono", monospace; font-size: 9.8pt;"><span style="color: #0033b3;">fn </span><span style="color: #00627a;">quicksort</span><<span style="color: #20999d;">T</span>: <span style="color: black;">PartialOrd </span>+ <span style="color: black;">std</span>::<span style="color: black;">fmt</span>::<span style="color: black;">Debug</span>>(elements: &<span style="color: #0033b3;">mut </span>[<span style="color: #20999d;">T</span>])<br />{<br /> <span style="color: #0033b3;">let </span><span style="color: black;">low </span>= <span style="color: #1750eb;">0</span>;<br /> <span style="color: #0033b3;">let </span><span style="color: black;">high </span>= elements.len();<br /><br /> <span style="color: #0033b3;">if </span>elements.is_empty() {<br /> <span style="color: #0033b3;">return</span>;<br /> }<br /><br /> <span style="color: #0033b3;">let </span><span style="color: black;">p </span>= lomuto_partition(&<span style="color: #0033b3;">mut </span>elements[<span style="color: black;">low</span>..<span style="color: black;">high</span>]);<br /> <span style="color: #8c8c8c; font-style: italic;">// p - 1 should not be negative<br /></span><span style="color: #8c8c8c; font-style: italic;"> </span>quicksort(&<span style="color: #0033b3;">mut </span>elements[<span style="color: black;">low</span>..<span style="color: black;">p</span>]);<br /> quicksort(&<span style="color: #0033b3;">mut </span>elements[<span style="color: black;">p</span>+<span style="color: #1750eb;">1</span>..<span style="color: black;">high</span>]);<br />}<br /></pre><pre style="font-family: "JetBrains Mono", monospace; font-size: 9.8pt;"><br /></pre></pre><pre style="background-color: white; color: #080808; font-family: 'JetBrains Mono',monospace; font-size: 9.8pt;"><br /></pre><div style="background-color: #fffffe; font-family: Consolas, "Liberation Mono", Courier, monospace, "Droid Sans Mono", "monospace", monospace, "Droid Sans Fallback"; font-size: 14px; line-height: 19px; white-space: pre;"></div></div></div>Balbirhttp://www.blogger.com/profile/17752733091129859385noreply@blogger.com0tag:blogger.com,1999:blog-6194839.post-90322049554643229052020-06-07T20:33:00.001+05:302021-11-28T15:16:54.165+05:30Volume of a unit hyper sphere of radius 1<div dir="ltr" style="text-align: left;" trbidi="on">
Inspired by foundations of data science, the area of a circle is<br />
<div>
<br /></div>
<div>\( \int_{x=-1}^{x=1}\int_{y=-\sqrt{1-x^2}}^{y=\sqrt{1-x^2}}dydx \)</div>
<div>
<br /></div>
<div>
This further extended to a sphere is</div>
<div>
<br /></div>
<div>
<div>\(\ int_{x=-1}^{x=1}\int_{y=-\sqrt{1-x^2}}^{y=\sqrt{1-x^2}}\int_{z=-\sqrt{1-x^2-y^2}}^{z=\sqrt{1-x^2-y^2}}dzdydx \)</div>
<div>
<br /></div>
</div>
<div>
This when implemented via maxima is</div>
<div>
<br /></div>
<div>
<pre style="text-align: left;">(%i17)<span style="white-space: pre;"> </span>integrate(integrate(integrate(1, z, -sqrt(1-x^2-y^2), sqrt(1-x^2-y^2)),</pre>
<pre style="text-align: left;"> y, -sqrt(1-x^2), sqrt(1-x^2)), x, -1, 1);</pre>
<div>
<br /></div>
<div>
Maxima goes on to ask if</div>
<pre style="text-align: left;">"Is "(x-1)*(x+1)" positive or negative?"</pre>
For a circle this value is definitely negative and voila we get the answer as $4\pi/3$. Higher dimenisons lead to interesting results</div>
<div>
<br /></div>
<div>
For 4 dimensions, we use</div>
<div>
<br /></div>
<pre style="text-align: left;">integrate(integrate(integrate(integrate(1, x4, -sqrt(1-x1^2-x2^2-x3^2), </pre>
<pre style="text-align: left;"> sqrt(1-x1^2-x2^2-x3^2)), x3, -sqrt(1-x1^2-x2^2), </pre>
<pre style="text-align: left;"> sqrt(1-x1^2-x2^2)), x2, -sqrt(1-x1^2), sqrt(1-x1^2)), </pre>
<pre style="text-align: left;"> x1, -1, 1);</pre>
<div>
<br /></div>
<div>
and get the volume as $\pi^2/2$ as the answer which matches what the book predicts</div>
</div>
Balbirhttp://www.blogger.com/profile/17752733091129859385noreply@blogger.com0tag:blogger.com,1999:blog-6194839.post-72201141225963294022020-05-30T09:45:00.000+05:302020-05-30T09:45:10.149+05:30Passive reaction: Computer Science has changed/changing<div dir="ltr" style="text-align: left;" trbidi="on">
In their book <a href="https://www.cs.cornell.edu/jeh/book.pdf">Foundations of Data Science</a>, the authors state in the preface that:<br />
<br />
"Courses in theoretical computer science covered finite automata, regular expressions, context-free languages, and computability. In the 1970’s, the study of algorithms was added as an important component of theory. The emphasis was on making computers useful. Today, a fundamental change is taking place and the focus is more on a wealth of applications. There are many reasons for this change. The merging of computing and communications has played an important role. The enhanced ability to observe, collect, and store data in the natural sciences, in commerce, and in other fields calls for a change in our understanding of data and how to handle it in the modern setting. The emergence of the web and social networks as central aspects of daily life presents both opportunities and challenges for theory.<br />
<br />
While traditional areas of computer science remain highly important, increasingly researchers of the future will be involved with using computers to understand and extract usable information from massive data arising in applications, not just how to make computers useful on specific well-defined problems. With this in mind we have written this book to cover the theory we expect to be useful in the next 40 years, just as an under standing of automata theory, algorithms, and related topics gave students an advantage in the last 40 years. One of the major changes is an increase in emphasis on probability, statistics, and numerical methods.<br />
...<br />
<br />
Modern data in diverse fields such as information processing, search, and machine learning is often advantageously represented as vectors with a large number of components"<br />
<br />
Sounds like I am a student of the past that focused more on Automata Theory and algorithms (traditional) in the past. I am yet to catch up with the mentioned emergence and opportunities topics. Time to learn new things, but it's going to be tricky to do it by myself, but I am glad to see someone thinking of the next 40 years.<br />
<br />
<br /></div>
Balbirhttp://www.blogger.com/profile/17752733091129859385noreply@blogger.com0tag:blogger.com,1999:blog-6194839.post-7430850024629966912019-11-03T13:00:00.001+05:302019-11-03T13:00:14.196+05:30Frustration with the state of math in schools<div dir="ltr" style="text-align: left;" trbidi="on">
I remember growing up and enjoying math in class. The learning method used in school was not very exploratory, but my dad (who was a genius in my opinion) made it a lot of fun. My dad was very protective also about what I learnt, I used to look at my elder brothers book and learn calculus in grade 8, but my dad suggested that the wrong background would lead me down to a path of losing interest. I guess he was right, but then by 8th grade I was able to calculate square and cube roots using the Newton Raphson method.
<br />
<br />
<b>NOTE</b>: I had learnt the formula for squares and cubes without necessarliy mastering how we arrived at the differential, it was algorithm/formula for me to follow<br />
<br />
My frustration is with the math of today, some with the teachers where I put my son for some extra classes and he was asked to remember formulae without detailed concepts. I see why those topics are important, but it seems like:<br />
<br />
<br />
<ul style="text-align: left;">
<li>Teachers who want to clarify concepts and teach nicely are too slow in catching up with topics to be covered</li>
<li>Teachers catching up with topics and keeping good pace, don't spend enough time on concepts</li>
</ul>
<div>
<br /></div>
<div>
Short of explaining everything to my son and writing a book or blog posts it's going to be hard to find a balance. I have some hope in the form of Khan Academy, but my son is not too interested in it at the moment.</div>
<div>
<br /></div>
<div>
If someone has pointers to great graphics/programs that can help, please do. Otherwise, I'll try and cover ratio and proportions for my first post.</div>
</div>
Balbirhttp://www.blogger.com/profile/17752733091129859385noreply@blogger.com0tag:blogger.com,1999:blog-6194839.post-3503873854271945602017-07-09T06:34:00.000+05:302017-07-09T06:34:19.117+05:30Dynamic programming for the binomial coefficient<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
More fun things, this time with some visualisation of what happens when memoisation is used and what happens when we don't. I don't these these algorithms are the most efficient algorithms<br />
<br />
<br /></div>
<style type="text/css">
<!--
pre { white-space: pre-wrap; font-family: monospace; color: #000000; background-color: #ffffff; }
body { font-family: monospace; color: #000000; background-color: #ffffff; }
* { font-size: 1em; }
.Identifier { color: #008b8b; }
.Statement { color: #a52a2a; font-weight: bold; }
.Comment { color: #0000ff; }
.Constant { color: #ff00ff; }
</style>
</div>
<pre id="vimCodeElement"><span class="Comment">#</span>
<span class="Comment"># dynamic programming for binomial co-efficient</span>
<span class="Comment">#</span>
<span class="Statement">def</span> <span class="Identifier">dynamic_bc</span>(n, k, indent=<span class="Constant">0</span>):
<span class="Comment">#</span>
<span class="Comment"># return (n k) using dynamic programming</span>
<span class="Comment"># tail cases are k == 0 or k == 1</span>
<span class="Comment"># (n 0) = 1 and (n 1) = n</span>
<span class="Statement">for</span> i <span class="Statement">in</span> <span class="Identifier">range</span>(<span class="Constant">0</span>, indent):
<span class="Identifier">print</span> <span class="Constant">"</span><span class="Constant"> </span><span class="Constant">"</span>,
<span class="Identifier">print</span> <span class="Constant">"</span><span class="Constant">%d:%d</span><span class="Constant">"</span> %(n, k)
<span class="Statement">if</span> (k == <span class="Constant">0</span>):
arr[n][k] = <span class="Constant">1</span>
<span class="Statement">return</span> <span class="Constant">1</span>
<span class="Statement">if</span> (k == <span class="Constant">1</span>):
arr[n][k] = n
<span class="Statement">return</span> n
<span class="Statement">if</span> (n == k):
arr[n][k] = <span class="Constant">1</span>
<span class="Statement">return</span> <span class="Constant">1</span>
<span class="Comment"># (n k) = (n!)/(n-k)!k!, lets split it further</span>
<span class="Comment"># n!/(n-k)!k! = n(n-1)!/(n-k)!k(k-1)!</span>
<span class="Comment"># or (n k) = (n-1 k) + (n -1 k-1)</span>
<span class="Statement">if</span> (arr[n-<span class="Constant">1</span>][k-<span class="Constant">1</span>] == <span class="Constant">0</span>):
arr[n-<span class="Constant">1</span>][k-<span class="Constant">1</span>] = dynamic_bc(n-<span class="Constant">1</span>,k-<span class="Constant">1</span>,indent+<span class="Constant">1</span>)
<span class="Statement">if</span> (arr[n-<span class="Constant">1</span>][k] == <span class="Constant">0</span>):
arr[n-<span class="Constant">1</span>][k] = dynamic_bc(n-<span class="Constant">1</span>, k,indent+<span class="Constant">1</span>)
<span class="Statement">return</span> arr[n-<span class="Constant">1</span>][k] + arr[n-<span class="Constant">1</span>][k-<span class="Constant">1</span>]
<span class="Statement">def</span> <span class="Identifier">bc</span>(n, k, indent=<span class="Constant">0</span>):
<span class="Comment">#</span>
<span class="Comment"># tail cases are k == 0 or k == 1</span>
<span class="Comment"># (n 0) = 1 and (n 1) = n</span>
<span class="Statement">for</span> i <span class="Statement">in</span> <span class="Identifier">range</span>(<span class="Constant">0</span>, indent):
<span class="Identifier">print</span> <span class="Constant">"</span><span class="Constant"> </span><span class="Constant">"</span>,
<span class="Identifier">print</span> <span class="Constant">"</span><span class="Constant">%d:%d</span><span class="Constant">"</span> %(n, k)
<span class="Statement">if</span> (k == <span class="Constant">0</span>):
<span class="Statement">return</span> <span class="Constant">1</span>
<span class="Statement">if</span> (k == <span class="Constant">1</span>):
<span class="Statement">return</span> n
<span class="Statement">if</span> (n == k):
<span class="Statement">return</span> <span class="Constant">1</span>
<span class="Comment"># (n k) = (n!)/(n-k)!k!, lets split it further</span>
<span class="Comment"># n!/(n-k)!k! = n(n-1)!/(n-k)!k(k-1)!</span>
<span class="Comment"># or (n k) = (n-1 k) + (n -1 k-1)</span>
<span class="Statement">return</span> bc(n-<span class="Constant">1</span>,k,indent+<span class="Constant">1</span>) + bc(n-<span class="Constant">1</span>,k-<span class="Constant">1</span>,indent+<span class="Constant">1</span>)
number = <span class="Constant">6</span>
select = <span class="Constant">3</span>
arr = [[<span class="Constant">0</span> <span class="Statement">for</span> x <span class="Statement">in</span> <span class="Identifier">range</span>(<span class="Constant">0</span>, number)] <span class="Statement">for</span> x <span class="Statement">in</span> <span class="Identifier">range</span>(<span class="Constant">0</span>, number)]
<span class="Identifier">print</span> bc(number, select)
<span class="Identifier">print</span> dynamic_bc(number, select)</pre>
The output for the first call with full recursion
<pre>
6:3
5:3
4:3
3:3
3:2
2:2
2:1
4:2
3:2
2:2
2:1
3:1
5:2
4:2
3:2
2:2
2:1
3:1
4:1
20
</pre>
The output for For the first call with full recursion
<pre>
6:3
5:2
4:1
4:2
3:1
3:2
2:1
2:2
5:3
4:3
3:3
20
</pre>
Python supports memoization via functools (wraps, lru_cache, etc). I am using the wrapper (decorator pattern). Using the following pattern makes the programming so transparent
<pre id='vimCodeElement'>
<span class="Comment">#</span>
<span class="Comment"># dynamic programming for binomial co-efficient</span>
<span class="Comment">#</span>
<span class="PreProc">from</span> functools <span class="PreProc">import</span> wraps
<span class="Statement">def</span> <span class="Identifier">dynamic_bc2</span>(func):
cache = {}
<span class="Statement">def</span> <span class="Identifier">wrap</span>(*args):
<span class="Statement">if</span> args <span class="Statement">not</span> <span class="Statement">in</span> cache:
cache[args] = func(*args)
<span class="Statement">return</span> cache[args]
<span class="Statement">return</span> wrap
<span class="PreProc">@</span><span class="Identifier">dynamic_bc2</span>
<span class="Statement">def</span> <span class="Identifier">bc2</span>(n, k, indent=<span class="Constant">0</span>):
<span class="Comment">#</span>
<span class="Comment"># return (n k) using dynamic programming</span>
<span class="Comment"># tail cases are k == 0 or k == 1</span>
<span class="Comment"># (n 0) = 1 and (n 1) = n</span>
<span class="Statement">for</span> i <span class="Statement">in</span> <span class="Identifier">range</span>(<span class="Constant">0</span>, indent):
<span class="Identifier">print</span> <span class="Constant">"</span><span class="Constant"> </span><span class="Constant">"</span>,
<span class="Identifier">print</span> <span class="Constant">"</span><span class="Constant">%d:%d</span><span class="Constant">"</span> %(n, k)
<span class="Statement">if</span> (k == <span class="Constant">0</span>):
<span class="Statement">return</span> <span class="Constant">1</span>
<span class="Statement">if</span> (k == <span class="Constant">1</span>):
<span class="Statement">return</span> n
<span class="Statement">if</span> (n == k):
<span class="Statement">return</span> <span class="Constant">1</span>
<span class="Comment"># (n k) = (n!)/(n-k)!k!, lets split it further</span>
<span class="Comment"># n!/(n-k)!k! = n(n-1)!/(n-k)!k(k-1)!</span>
<span class="Comment"># or (n k) = (n-1 k) + (n -1 k-1)</span>
<span class="Statement">return</span> bc2(n-<span class="Constant">1</span>,k-<span class="Constant">1</span>,indent+<span class="Constant">1</span>) + bc2(n-<span class="Constant">1</span>,k,indent+<span class="Constant">1</span>)
number = <span class="Constant">6</span>
select = <span class="Constant">3</span>
<span class="Identifier">print</span> bc2(number, select)
</pre>
Comparing the output will show the affect of functools. The output with functools is:
<pre>
6:3
5:2
4:1
4:2
3:1
3:2
2:1
2:2
5:3
4:3
3:3
20
</pre>
Balbirhttp://www.blogger.com/profile/17752733091129859385noreply@blogger.com0tag:blogger.com,1999:blog-6194839.post-17115293219079483382017-07-06T13:36:00.001+05:302017-07-06T13:36:27.862+05:30Iterative combinations algorithm<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
The algorithm is quite straight forward, see the code in python below<br />
<br />
<br /></div>
<style type="text/css">
<!--
pre { white-space: pre-wrap; font-family: monospace; color: #000000; background-color: #ffffff; }
body { font-family: monospace; color: #000000; background-color: #ffffff; }
* { font-size: 1em; }
.Identifier { color: #008b8b; }
.Statement { color: #a52a2a; font-weight: bold; }
.Comment { color: #0000ff; }
.Constant { color: #ff00ff; }
</style>
</div>
<pre id="vimCodeElement"><span class="Comment">#</span>
<span class="Comment"># Do iterative combinations generation</span>
<span class="Comment"># From Knuth's observation, we know for (6 3) that</span>
<span class="Comment"># [0, 1, 2]</span>
<span class="Comment"># [0, 1, 3]</span>
<span class="Comment"># ..</span>
<span class="Comment"># [3, 4, 5]</span>
<span class="Comment"># Basically we can see a set of for loops, if we call the columns c1,c2 and c3 then</span>
<span class="Comment">#</span>
<span class="Comment"># for c3 = 2 to n-1</span>
<span class="Comment"># for c2 = 1 to c3-1</span>
<span class="Comment"># for c1 = 0 to c2-1</span>
<span class="Comment">#</span>
<span class="Comment"># The loop gives us what we need</span>
<span class="Comment"># My implementation is based on an index (i) and max (n)</span>
<span class="Comment"># which are used to determine the next value to generate</span>
<span class="Comment">#</span>
<span class="Statement">def</span> <span class="Identifier">iterative_combination</span>(n, k):
a = [i <span class="Statement">for</span> i <span class="Statement">in</span> <span class="Identifier">range</span>(<span class="Constant">0</span>, n)]
index = k - <span class="Constant">1</span>
done = <span class="Identifier">False</span>
<span class="Statement">while</span> (done == <span class="Identifier">False</span>):
<span class="Identifier">print</span> a[<span class="Constant">0</span>:k]
<span class="Statement">while</span> (a[index] == n - (k - index)): # boundary for that index
index = index - <span class="Constant">1</span>
<span class="Statement">if</span> (index < <span class="Constant">0</span>):
done = <span class="Identifier">True</span>
<span class="Statement">break</span>
a[index] = a[index] + <span class="Constant">1</span>
<span class="Statement">while</span> (index < k - <span class="Constant">1</span>):
index = index + <span class="Constant">1</span>
<span class="Statement">if</span> (a[index] == (n - (k - index))): # initialize the next neighbour
a[index] = a[index - <span class="Constant">1</span>] + <span class="Constant">1</span>
</pre>
</div>
Balbirhttp://www.blogger.com/profile/17752733091129859385noreply@blogger.com0tag:blogger.com,1999:blog-6194839.post-2100731972758833692017-07-06T12:29:00.002+05:302017-07-06T12:29:10.842+05:30Random CS picture<div dir="ltr" style="text-align: left;" trbidi="on">
Here is a random picture from a computer science topic<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjvcErkOgo5Wsj-qu8GI1fqJmJ5-yGR86qdo41gMvSaColOk88kUlwf4G77k4QuQhqKZxXJyHojtOezVjA8ZGSBx_Oq35M-3AlsgsVweGx5xAsquEMCUBsZr-i_X9et2CZ-FaHl/s1600/set_cover.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="181" data-original-width="172" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjvcErkOgo5Wsj-qu8GI1fqJmJ5-yGR86qdo41gMvSaColOk88kUlwf4G77k4QuQhqKZxXJyHojtOezVjA8ZGSBx_Oq35M-3AlsgsVweGx5xAsquEMCUBsZr-i_X9et2CZ-FaHl/s1600/set_cover.png" /></a></div>
<br />
<br />
The picture is a counter example of why greedy selection does not work optimally for the set cover problem. If the picture seems not so well done, it's because my asymptote skills are lacking :)<br />
<br />
You can probably guess what I'm reading by connecting set cover with combinatorial generation of combinations.</div>
Balbirhttp://www.blogger.com/profile/17752733091129859385noreply@blogger.com0tag:blogger.com,1999:blog-6194839.post-22351066773668994132017-07-05T16:29:00.001+05:302017-07-05T16:34:13.965+05:30Combinations revisited<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
I've been trying to relearn some of the combinatorics I used to know, I redid a nice recursive algorithm (from early university days), with python it looks so beautiful and nice. A simple implementation is below, so nice and simple.<br />
<br />
<br /></div>
<div dir="ltr" style="text-align: left;" trbidi="on">
<style>
pre { white-space: pre-wrap; font-family: monospace; color: #000000; background-color: #ffffff; }
body { font-family: monospace; color: #000000; background-color: #ffffff; }
* { font-size: 1em; }
.Identifier { color: #008b8b; }
.Statement { color: #a52a2a; font-weight: bold; }
.Comment { color: #0000ff; }
.Constant { color: #ff00ff; }
</style>
<br />
<pre id="vimCodeElement"><span class="Comment">#</span>
<span class="Comment"># I'm inspired by two algorithms I saw, both are recursive.</span>
<span class="Comment">#</span>
<span class="Comment"># Example:</span>
<span class="Comment"># ((1, 2, 3, 4), 2) - means select 2 out of 3</span>
<span class="Comment"># should produce (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)</span>
<span class="Comment">#</span>
<span class="Comment"># The idea from a recursive perspective is this</span>
<span class="Comment"># we pick an index - say 1, then we pick the next (n-1) elements</span>
<span class="Comment"># to go with it</span>
<span class="Comment">#</span>
<span class="Statement">def</span> <span class="Identifier">rec_comb</span>(a, i, j, k, n):
<span class="Comment">#</span>
<span class="Comment"># array a built upto index i</span>
<span class="Comment"># selected k at a time of max</span>
<span class="Comment"># length n</span>
<span class="Comment">#</span>
<span class="Statement">if</span> (i == k):
<span class="Identifier">print</span> a[<span class="Constant">0</span>:k]
<span class="Statement">return</span>
<span class="Statement">for</span> l <span class="Statement">in</span> <span class="Identifier">range</span>(j, n):
a[i] = l
rec_comb(a, i+<span class="Constant">1</span>, l+<span class="Constant">1</span>, k, n)
<span class="Statement">return</span>
<span class="Statement">def</span> <span class="Identifier">combination</span>(n, k):
<span class="Comment">#</span>
<span class="Comment"># n (numbers from 1..n), chosen k at a time</span>
<span class="Comment">#</span>
a = [<span class="Constant">0</span> <span class="Statement">for</span> i <span class="Statement">in</span> <span class="Identifier">range</span>(<span class="Constant">0</span>, n)]
rec_comb(a, <span class="Constant">0</span>, <span class="Constant">0</span>, k, n)</pre>
The sample output for ${6 \choose 3}$ is:
<br />
<pre id="vimCodeElement"></pre>
<pre id="vimCodeElement">[0, 1, 2]
[0, 1, 3]
[0, 1, 4]
[0, 1, 5]
[0, 2, 3]
[0, 2, 4]
[0, 2, 5]
[0, 3, 4]
[0, 3, 5]
[0, 4, 5]
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 4]
[1, 3, 5]
[1, 4, 5]
[2, 3, 4]
[2, 3, 5]
[2, 4, 5]
[3, 4, 5]
</pre>
The output lends itself to a simple and nice iterative algorithm, I'll follow up on.<br />
<br />
The interesting follow up to combinatorial generation algorithms is using ranking and unranking. At this point, I think we need a O(n) to identify if two combinations are the same -- given in any order of elements. For example to compare
$\{1, 2, 3\}, \{1, 3, 2\}, \{2, 1, 3\}, \{3, 1, 2\}, \{2, 3, 1\}, \{3, 2, 1\}$
we need to identify them and associate the same rank with them. I think for a subset of size $k$, the cost of ranking is $\theta(k)$, but I need to see if there is a better way to do it.
<br />
<br />
<br /></div>
</div>
Balbirhttp://www.blogger.com/profile/17752733091129859385noreply@blogger.com0tag:blogger.com,1999:blog-6194839.post-16189712868514136592016-07-01T18:51:00.001+05:302016-07-01T18:51:10.238+05:30Thoughts on Agile programming - team size<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
I've been thinking about this for a very long time. What would be an ideal agile team size -- what would be a core team size to be more precise. I've been told in the past that it's 5, but I think it's 4 and here is how I think the team should be organized<br />
<br />
<table>
<tbody>
<tr>
<th>Role</th>
<th>Role</th>
<th>Role</th>
<th>Role</th>
</tr>
<tr>
<td>Developer<sub>1</sub></td>
<td>Developer<sub>2</sub></td>
<td>Reviewer/Test<sub>1</sub></td>
<td>Reviewer/Test<sub>2</sub></td>
</tr>
</tbody>
</table>
</div>
Here Reviewer/Tester and Developers should exchange roles if required and be flexible to work both ways for maximum efficiency. Note the role of Reviewer/Tester could be easily done by another Developer.<br />
<br />
Here is how I would schedule their interactions<br />
<br /></div>
<table>
<tbody>
<tr>
<th>Day</th>
<th>Room<sub>1</sub></th>
<th>Room<sub>2</sub></th>
</tr>
<tr>
<td>1</td>
<td>Developer<sub>1</sub> and Reviewer/Test<sub>1</sub></td>
<td>Developer<sub>2</sub> and Reviewer/Test<sub>2</sub></td>
</tr>
<tr>
<td>2</td>
<td>Developer<sub>2</sub>, Developer<sub>1</sub> and Reviewer/Test<sub>1</sub></td>
<td>Reviewer/Test<sub>2</sub></td>
</tr>
<tr>
<td>3</td>
<td>Developer<sub>2</sub>, Developer<sub>1</sub> and Reviewer/Test<sub>2</sub></td>
<td>Reviewer/Test<sub>1</sub></td>
</tr>
<tr>
<td>4</td>
<td>Reviewer/Test<sub>2</sub>, Developer<sub>1</sub> and Reviewer/Test<sub>1</sub></td>
<td>Developer<sub>2</sub></td>
</tr>
<tr>
<td>5</td>
<td>Reviewer/Test<sub>2</sub>, Developer<sub>1</sub> and Reviewer/Test<sub>2</sub></td>
<td>Developer<sub>1</sub></td>
</tr>
<tr>
<td>6</td>
<td>Developer<sub>2</sub>, Developer<sub>1 </sub>Reviewer/Test<sub>2</sub> and Reviewer/Test<sub>1</sub></td></tr>
</tbody></table>
<br />
Teams will think I am crazy for suggesting working 6 days a week, this problem can be resolved by splitting day 6 into some hours each day. For example 1.5 hours a day could be kept aside each day for the developers/reviewer-tester to interact and day 6 could be eliminated all together<br />
<br />
In my scheme, each person gets a day/some time to themselves each week. All of them collaborate together and work together frequently. In this scheme indepedence is as important as the inter-dependance between each member<br />
<br />
What do you think?</div>
Balbirhttp://www.blogger.com/profile/17752733091129859385noreply@blogger.com0tag:blogger.com,1999:blog-6194839.post-10575787482425798512016-07-01T18:27:00.001+05:302016-07-01T18:27:06.663+05:30Live patching on PPC64LE<div dir="ltr" style="text-align: left;" trbidi="on">
Michael Ellerman has a great blog with all the technical details. There was a lot of work, brain storming and discussions involved. Check out <a href="http://mpe.github.io/posts/2016/05/23/kernel-live-patching-for-ppc64le/">http://mpe.github.io/posts/2016/05/23/kernel-live-patching-for-ppc64le/</a><br />
<br />
<br /></div>
Balbirhttp://www.blogger.com/profile/17752733091129859385noreply@blogger.com1tag:blogger.com,1999:blog-6194839.post-91362942144124988572015-10-15T13:15:00.002+05:302015-10-15T13:15:45.800+05:30Some programming basics<div dir="ltr" style="text-align: left;" trbidi="on">
As our programming knowledge grows, we sometimes forget that computers are not human. Although the incremental and consistent growth of AI techniques, mining may make us believe otherwise :) This is not a blog about AI or ML, but about some basics<br />
<br />
From my understanding of real numbers, I can easily postulate that<br />
<br />
0.1 + 0.1 = 0.2 -- (1)<br />
and<br />
0.1 + 0.1 + 0.1 = 0.3 -- (2)<br />
<br />
But for a computer formula (2) can be hard to comprehend and as a computer programmer we forget that from time to time<br />
<br />
I asked my python interpreter<br />
<br />
>>> 0.1+0.1+0.1 == 0.3<br />False<br />
<br />
and later asked what is 0.1+0.1+0.1<br />
<br />
>>> 0.1+0.1+0.1<br />0.30000000000000004<br />
<br />
Try this in your favorite language and see what you get -- the math underneath should be the same<br />
<br />
Reference - <a href="https://docs.python.org/2/tutorial/floatingpoint.html">https://docs.python.org/2/tutorial/floatingpoint.html</a></div>
Balbirhttp://www.blogger.com/profile/17752733091129859385noreply@blogger.com0tag:blogger.com,1999:blog-6194839.post-30839815838878621942015-09-27T23:44:00.001+05:302015-09-27T23:44:30.642+05:30Some more interesting combinatorics<div dir="ltr" style="text-align: left;" trbidi="on">
I tried to solve the following problems from the book by Lovasz and got wrong - well atleast the basic thinking was right :)
<br />
<br />
Problem 1: We have $20$ different presents that we want to distribute to $12$ different children. It is not required that all children get something, it is possible that all presents are given to the same child. In how many ways can we distribute the presents?<br />
Problem 2: We have $20$ kinds of presents with unlimited supply of each kind. We want to give this to $12$ children. It is not required that all children get something, it is possible that all presents are given to the same child. In how many ways can we distribute the presents?<br />
<br />
What do you think the answers are?</div>
Balbirhttp://www.blogger.com/profile/17752733091129859385noreply@blogger.com0tag:blogger.com,1999:blog-6194839.post-32573539703160311282015-01-12T21:30:00.000+05:302015-01-12T21:30:12.870+05:30Happy New Year 2015<div dir="ltr" style="text-align: left;" trbidi="on">
A happy/prosperous/safe/healthy new year to one and all. 2014 has been great, but also unexpected. My home Linux box crashed and I was forced to move to my MAC-MINI for my day-to-day work. Hopefully this year, I'll buy a good machine and get back to Linux soon. Desktops are getting harder to find and maintain (in terms of space), but still the best option IMHO. The sound of the spinning hard drive, powering on the desktop after a long vacation is just too much of fun to miss. My last desktop was AMD based, I have to move to Intel, may be I'll wait a bit more. May be I'll get lucky and someone will send me new cool hardware for free to hack on :) Hint, Hint!<br />
<br />
I did not mean to make this about my need for new compute. Here are my predictions for 2015/16 (yeah.. a bit more)<br />
<br />
<br />
<ol style="text-align: left;">
<li>Data center compute will get interesting with new processors and workloads</li>
<li>OS Wars will light up again</li>
<li>Children/Kids will get earlier access to computers and buy more hardware</li>
<li>Internet and bandwidth consolidation will across several devices - phone/computer/TV</li>
<li>People will start paying for cloud storage, storage is now a key bottleneck</li>
<li>MAC OS will continue to gain desktop share</li>
</ol>
<div>
I am avoiding any security based predictions, you can guess why? I'll revise these soon, some time in Q2 this year</div>
<br />
<br />
<br /></div>
Balbirhttp://www.blogger.com/profile/17752733091129859385noreply@blogger.com0tag:blogger.com,1999:blog-6194839.post-80872044836963323862014-10-07T22:51:00.001+05:302014-10-07T22:51:17.400+05:30Quick Review - The race of my life<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="separator" style="clear: both; text-align: center;">
<a href="http://upload.wikimedia.org/wikipedia/en/0/0f/The_Race_of_My_Life.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://upload.wikimedia.org/wikipedia/en/0/0f/The_Race_of_My_Life.jpeg" height="320" width="207" /></a></div>
I just finished reading Milkha's autobiography - The race of my life. I loved the simple writing and the length of the book. I must confess that having seen the movie earlier made it easier for me to read the book, however the movie and the book do not map 1:1.<br />
<br />
Milkha's book is filled with a story of tragedy of the bloody partition, determinism of a father to educate a child, hardwork and struggle of the youth of Milkha and his progress from an Army Jawan to almost a lieutenant, his days as sports administrator and his feelings for the current state of sports.<br />
<br />
All the events in which he participated, the cultural gaps between India and the rest of the world and his ability to learn & improve and work hard with the coaches is clearly demonstrated. They are some hilarious moments about his sister Isher thinking he was shot during a race :)<br />
<br />
A great read, should not take you very long to complete and you'll end up feeling motivated to reach your goals.</div>
Balbirhttp://www.blogger.com/profile/17752733091129859385noreply@blogger.com0tag:blogger.com,1999:blog-6194839.post-3008762356195381322014-08-17T22:14:00.002+05:302014-08-17T22:14:43.064+05:30Math by brute force<div dir="ltr" style="text-align: left;" trbidi="on">
I came across a problem in a book on Combinatorics<br />
<br />
In how many ways can 5 gentleman and 3 ladies be seated such that no two ladies sit next to each other?<br />
<br />
The book's answer was 5!. Clearly not very believable, I decided to warm myself up and try and find an answer.<br />
<br />
My first answer was<br />
<br />
8! - 2.7! - 6.6!<br />
<br />
Something did not seem right, so I decided to use brute force. I wrote quick python code to list 8! permutations (all of them) and discard positions with two ladies together (yes, I permuted classes with numbers and types). The answer was 14400. Clearly I missed something and the computer cannot be wrong - well brute force is usually slow but right :)<br />
<br />
A little more thought and use of common sense got me to the right answer<br />
<br />
8! - (3 C 2)*2*7! + 6.6! (via inclusion/exclusion principle)<br />
<br />
I am so excited to use brute force to check my answers - do you?<br />
<br />
<br />
<br />
<br /></div>
Balbirhttp://www.blogger.com/profile/17752733091129859385noreply@blogger.com0tag:blogger.com,1999:blog-6194839.post-24018219368701094102014-05-23T08:05:00.002+05:302014-05-23T08:05:15.803+05:30Lessons learnt - cheap Android devices<div dir="ltr" style="text-align: left;" trbidi="on">
One of the best things about an Android device is that it comes in various form factors and various price ranges. Over the years I've bought close to 6 Android devices. My first device was expensive and had no GPU hardware. I could not play games on it, so I decided to move to another one. This time I got a Nexus 4 as a gift<br />
<br />
Then I decided to buy a device from an Indian manufacturer with a quad-core CPU/1GB RAM/GPU and a decent display resolution with a 5" screen (<a href="http://www.karbonnmobiles.com/karbonn-TITANIUMS5Plus-proid-202.html">Karbonn S5</a>). The device was cheap and I could not help but compare the device and be delighted with my purchase. Over the year of usage of this device, I learnt my lesson<br />
<br />
<br />
<ol style="text-align: left;">
<li>There are absolutely no updates for the device - why do I care, what this meant is that I was left open to <a href="http://xkcd.com/1353/">OpenSSL heartbleed</a>.</li>
<li>The phone's hardware, touch screen started failing, some areas stopped responding</li>
<li>The firmware on the phone was signed using test-keys. A lot of useful software started detecting the phone as rooted :)</li>
<li>The key bottleneck for most software is not number of CPU's, but the amount of RAM/Speed of the processor and the quality of the GPU</li>
</ol>
<br />
<br />
<b>Lesson learnt - buy a phone with good reliable hardware and frequent updates, use the cheap ones for experimentation and development</b><br />
<br />
The good news is that since the hardware was cheap, I could easily replace it and keep the phone to try a <a href="http://www.cyanogenmod.org/">cyanogenmod</a> upgrade on it. Can't do much about the bad hardware though except use it as a device to try experiments on :)<br />
<br />
</div>
Balbirhttp://www.blogger.com/profile/17752733091129859385noreply@blogger.com0tag:blogger.com,1999:blog-6194839.post-22459068061820007162013-12-11T21:26:00.002+05:302013-12-11T21:26:46.214+05:30Interesting combinatorics problem<div dir="ltr" style="text-align: left;" trbidi="on">
I saw this problem in an old book on combinatorics I had, it took me a while to solve, but it is easy if you are familiar with the work of Euler.<br />
<br />
<b>Prove that an even length palindrome of integers is divisible by 11</b><br />
<b><br /></b>
If you know the answer - post it in the comments. If not, wait for a post by me :)</div>
Balbirhttp://www.blogger.com/profile/17752733091129859385noreply@blogger.com0tag:blogger.com,1999:blog-6194839.post-44966195697639464452013-10-28T13:12:00.001+05:302013-10-28T13:12:24.523+05:30My first useful JavaScript program<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
I was recently going through my son's workbook and it had an interest way of teaching addition - probably the Montessori method. The idea was to create a table of sum's of a few numbers and color numbers to see a pattern. I was quite amused and decided to see if I could write the code in JavaScript, a language I am trying to learn, I am going to do some additional work like graphical Towers of Hanoi with it as well, but for now I wanted to start simple<br />
<br />
Guess what - I succeeded in writing what I consider as a useful program (although I wrote it quite badly)<br />
<br />
Here is the code<br />
<script src="https://gist.github.com/bsingharora/f11da47a00a3dd026e5f.js"></script>
Here is the Javascript
<script src="https://gist.github.com/bsingharora/0a5cc16ec9892292927e.js"></script>
Here is the output<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiJBPIxqHM5i-aeTNUhcVLsMEW7yBUrm5WVlsK1sJEG7IcsBpqm4hNgtzxawOOq00y2VtcKcwu5IJGVlEzpb0YgKwvAgdr2aFYI-avzFU_x0OnfJKMGqZ7yeHBifaA-4ysO1HrC/s1600/Screenshot+from+2013-10-28+11:07:55.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiJBPIxqHM5i-aeTNUhcVLsMEW7yBUrm5WVlsK1sJEG7IcsBpqm4hNgtzxawOOq00y2VtcKcwu5IJGVlEzpb0YgKwvAgdr2aFYI-avzFU_x0OnfJKMGqZ7yeHBifaA-4ysO1HrC/s320/Screenshot+from+2013-10-28+11:07:55.png" width="248" /></a></div>
<br />
<br />
<br />
<br /></div>
</div>
</div>
</div>
</div>
</div>
</div>
Balbirhttp://www.blogger.com/profile/17752733091129859385noreply@blogger.com1tag:blogger.com,1999:blog-6194839.post-81715383941758900612013-10-11T08:37:00.001+05:302013-10-11T08:37:26.438+05:30Your code is only as good as the tests you run on it<div dir="ltr" style="text-align: left;" trbidi="on">
Computer programs have an interesting well known quality - even incorrect programs can produce the desired output for a subset of inputs. I recently re-learnt this while doing my graphical convex hull implementation<br />
<br />
I started with a test strategy of random test generation. Use a good random number generator to generate<br />
<br />
<ol style="text-align: left;">
<li>Number of random points as input</li>
<li>The random points themselves</li>
</ol>
<br />
<br />
This strategy helped me test the program from crashes/instability and showed a potential functional issue that showed up when a large number of points were generated. See the diagram below<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi6rgroy2uX9vqQCmHXB6e0nb00ekYMR5JoupGU8uSEPRNvFsxhxXsIoTv_ihReP_RfRSRAtriu_DfNOy6rl7x8ZiClkvlF5V0tFFLqJom5lBrR_nkPuPmAO6I9uvzfg39awiUs/s1600/brokenhull.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi6rgroy2uX9vqQCmHXB6e0nb00ekYMR5JoupGU8uSEPRNvFsxhxXsIoTv_ihReP_RfRSRAtriu_DfNOy6rl7x8ZiClkvlF5V0tFFLqJom5lBrR_nkPuPmAO6I9uvzfg39awiUs/s320/brokenhull.png" width="320" /></a></div>
Can you spot the problem? I now need a specific test case to isolate the problem, random inputs did not provide the necessary clue with smaller inputs. Luckily for me, I found a good set of inputs at <a href="http://stackoverflow.com/questions/482278/test-case-data-for-convex-hull">http://stackoverflow.com/questions/482278/test-case-data-for-convex-hull</a><br />
<br />
I ran three test cases and found the first two ran fine<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjN_iuh20LfVLjIw317CiyhBOp34euN13BjcRcPfDbt_v4bHoX7WZm3jY0taFnwbUZYgTmqpPZeavOzhyphenhyphenbY9E2mHf4OAFdVxiWtwB2nWn3dq4osXeQUTe5ACY77ffiFr2aCQa5G/s1600/test1cv.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjN_iuh20LfVLjIw317CiyhBOp34euN13BjcRcPfDbt_v4bHoX7WZm3jY0taFnwbUZYgTmqpPZeavOzhyphenhyphenbY9E2mHf4OAFdVxiWtwB2nWn3dq4osXeQUTe5ACY77ffiFr2aCQa5G/s320/test1cv.png" width="320" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg1yMh3HVdUBhjbIZ3WsY7RLIIAZmNl74CHdGYA2aVdwc-vIj9ypcS-JCvlWXVIejhltMG1GQPioPeMariuACffiNKSwN6Fb3T38e94TGUTZweO7_WbFBq1jB5XHkagOgODeh9P/s1600/test2cv.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg1yMh3HVdUBhjbIZ3WsY7RLIIAZmNl74CHdGYA2aVdwc-vIj9ypcS-JCvlWXVIejhltMG1GQPioPeMariuACffiNKSwN6Fb3T38e94TGUTZweO7_WbFBq1jB5XHkagOgODeh9P/s320/test2cv.png" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
The third one was a hit, it broke my algorithm</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhyMxp751-sTec3WwjW9FlDxFs5bgTH-U2S-ZPVYJvEG5qP2kvDjftpJo3Btcm8vrnPQ0Jn5QdKPxlwfiJnWZLi2RN9bgEI6aoYmdao1DcsutxmqU_yMkGOZJ8MdGp4TlRApqRu/s1600/brokenhull2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhyMxp751-sTec3WwjW9FlDxFs5bgTH-U2S-ZPVYJvEG5qP2kvDjftpJo3Btcm8vrnPQ0Jn5QdKPxlwfiJnWZLi2RN9bgEI6aoYmdao1DcsutxmqU_yMkGOZJ8MdGp4TlRApqRu/s320/brokenhull2.png" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: left;">
Beautiful visualization, but the code was clearly broken. After looking at the diagram and looking at the code, I realized that I was not handling co-linear points correctly. Finally, I got</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhGnIKZfiWfaxVQMO5OCog7CfFkRVF5rnUcODv9jIIPtdbm3K0GGcw_BG64ozyhTGXsEJV7Qj5XTSO0KDHAKmkfSHaEL1UKLcmvax-OHsPTssWoYH5Nx14hoTEUZS1mUvd_Wgwm/s1600/test3cv.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhGnIKZfiWfaxVQMO5OCog7CfFkRVF5rnUcODv9jIIPtdbm3K0GGcw_BG64ozyhTGXsEJV7Qj5XTSO0KDHAKmkfSHaEL1UKLcmvax-OHsPTssWoYH5Nx14hoTEUZS1mUvd_Wgwm/s320/test3cv.png" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
Now, I am back to the random testing strategy and have gotten satisfactory results so far</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
NOTE: My test feedback strategy is based on visualization, one could even automate the tests</div>
</div>
Balbirhttp://www.blogger.com/profile/17752733091129859385noreply@blogger.com0tag:blogger.com,1999:blog-6194839.post-57783029682770511972013-09-25T08:41:00.001+05:302013-09-25T08:41:16.028+05:30Who inspires you?<div dir="ltr" style="text-align: left;" trbidi="on">
Many of us are inspired by role models around us, in person, in media, in history, men and women who lead by example. I remember an instance - a colleague of mine was asked about role models and he was selected because he mentioned his grandfather. Other colleagues who mentioned names like Mahatma Gandhi were rejected, because in the HR's mind, a role model has to be someone you personally know. I felt those were very strong opinions to make a judgement for employment<br />
<br />
In the past, I've had several role models<br />
<br />
<br />
<ul style="text-align: left;">
<li>My dad - for simplicity, integrity and courage to do the right thing and caring for others. Ability to network, empathize. Social causes and care for poor.</li>
<li>My mom - for her ability to manage so many things, manage the family, swiftness, love and extreme courage. Her ability to network</li>
<li>Mahatma Gandhi - For large traits of what I saw in my dad.</li>
<li>Don Knuth - For being so nice, smart and humble</li>
<li>Ex-leads - technical leads in my first job, software architects, distinguished engineers from whom I've learnt a lot. Learnt virtues of caring for people beyond the scope of work.</li>
<li>Relatives and friends - who've stood by thick and thin, good and bad times</li>
</ul>
<div>
Today I was inspired by our security guard. His simplicity, his dedication to work and sincerity inspired me. I write this blog and dedicate it to all those who inspired me. I think we don't need to look very far for inspiration, it is right around the corner, in my case right at my doorstep.</div>
<div>
<br /></div>
<div>
I hope all of us find many role models who inspire us to do the right thing for ourselves and the society we build together.</div>
<div>
<br /></div>
<br />
<br /></div>
Balbirhttp://www.blogger.com/profile/17752733091129859385noreply@blogger.com0tag:blogger.com,1999:blog-6194839.post-60277455734539255642013-09-19T08:28:00.003+05:302013-09-19T08:28:28.983+05:30The call for better reading/writing skills<div dir="ltr" style="text-align: left;" trbidi="on">
I am sure you've faced it and done it to others - <b>not read</b> the <b>entire email in totality</b> or communication in full and <i>missed parts</i> of it. With the abundance of information comes the challenge for the new age of engineers to read and parse information completely. There is a challenge that people writing blog posts such as me, do a good job of delivering the information in manner that key points are not missed<br />
<br />
<h3 style="text-align: left;">
Summary of the problem</h3>
<br />
<ul style="text-align: left;">
<li>Of late, I've seen people ask questions already answered in the email they are replying too</li>
<li>People chain emails expecting everybody to read things top to bottom</li>
<li>Most people reply on top of emails. Top Posting</li>
</ul>
<br />
<br />
I think the open source community solved this problem with rules and netiquettes, but most of us who are not aware of them - fail to see the importance of communicating clearly so as to get maximum retention benefits from the audience of the communication.<br />
<br />
<h3 style="text-align: left;">
In my mind, here are the best practices</h3>
<br />
<br />
<ul style="text-align: left;">
<li>Make sure that the key information is not hidden in a paragraph, but upfront</li>
<li>Try to summarize, re-emphasize</li>
<li>Use best practices, netiquettes</li>
<li>Don't forward or reply to long chains, clearly snip out irrelevant content</li>
<li>Use smart subjects</li>
<li>Highlight important points</li>
</ul>
<br />
<br />
<h3 style="text-align: left;">
If you are on the receiving side</h3>
<br />
<br />
<ul style="text-align: left;">
<li>Spend some time on important emails, if required re-read</li>
<li>Try to limit the amount of emails you read - batch process, don't switch too often</li>
<li>Remember, email is official communication</li>
</ul>
<br />
<br /></div>
Balbirhttp://www.blogger.com/profile/17752733091129859385noreply@blogger.com0tag:blogger.com,1999:blog-6194839.post-61244805721128450932013-09-18T20:36:00.003+05:302013-09-18T20:38:12.488+05:30A poor way to do sorting in an OO language (java)<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
Going back to Java after so many years is an interesting experience. I made the classic rookie mistake with implementation of a sorting library. All good programming practices tell you that manipulation methods on a collection should always be static and not bound to the class. To top it all, this was the first time I was using generics after spending some time reading about them :)<br />
<br />
I had done things the other way around, almost as if I had implemented a stack with data. My ego was too big for me not to succeed with that technique. Here is an implementation of selection sort. Below is what I ended up implementing<br />
<br />
<pre>/**
*
* @author balbir
* @param <item>
*/
public class SelectionSort < Item extends Comparable ><item comparable="" extends=""><item comparable="" extends=""><item comparable="" extends=""> {
private Item[] elements;
SelectionSort(int N)
{
elements = (Item[]) new Comparable[N];
}
public void sort()
{
int min;
for (int i = 0; i < elements.length; i++)
{
min = i;
for (int j = i+1; j < elements.length; j++)
{
if (elements[j].compareTo(elements[min]) < 0)
min = j;
}
Item tmp;
tmp = elements[i];
elements[i] = elements[min];
elements[min] = tmp;
}
}
public void dump()
{
for (int i = 0; i < elements.length; i++)
System.out.print(elements[i] + " ");
System.out.println();
}
public void load(Item a[])
{
for (int i = 0; i < elements.length; i++)
elements[i] = a[i];
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Integer[] a = {1, 2, -1, 3, 0, 5, 7, 9, 4};
SelectionSort<integer> s = new SelectionSort<integer>(a.length);
s.load(a);
s.dump();
s.sort();
s.dump();
}
}
</integer></integer></item></item></item></item></pre>
<div>
<br /></div>
<div>
It is funny how I had to use a load class to get the data and call the sort method. What a bad decision, the reason I shared this post is just to show that with generics one can indeed mix classes and class templates. I for example mixed Integer and Comparable and the default implementation worked.</div>
<div>
<br /></div>
</div>
</div>
</div>
</div>
Balbirhttp://www.blogger.com/profile/17752733091129859385noreply@blogger.com0