<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Rabin Gaire on Medium]]></title>
        <description><![CDATA[Stories by Rabin Gaire on Medium]]></description>
        <link>https://medium.com/@rabingaire?source=rss-c7ca25640693------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/2*0GPOPyxy7CLYjFvrIloVQA.jpeg</url>
            <title>Stories by Rabin Gaire on Medium</title>
            <link>https://medium.com/@rabingaire?source=rss-c7ca25640693------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Mon, 16 Nov 2026 20:28:32 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@rabingaire/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Integration test on golang using Docker]]></title>
            <link>https://rabingaire.medium.com/integration-test-on-golang-using-docker-852f4c933cbe?source=rss-c7ca25640693------2</link>
            <guid isPermaLink="false">https://medium.com/p/852f4c933cbe</guid>
            <category><![CDATA[golang]]></category>
            <category><![CDATA[docker]]></category>
            <category><![CDATA[integration-testing]]></category>
            <category><![CDATA[rabbitmq]]></category>
            <dc:creator><![CDATA[Rabin Gaire]]></dc:creator>
            <pubDate>Mon, 09 Mar 2020 09:03:29 GMT</pubDate>
            <atom:updated>2020-03-09T15:55:15.139Z</atom:updated>
            <content:encoded><![CDATA[<p>According to Wikipedia, the integration test is the phase in software testing, where you combine individual software modules and test them as a group. Integration tests are required to test if the software fulfills the specified functional requirement.</p><p>In this article, I am going to show you how to write integration tests. The code example provided here is written in go programming language but the concept is easily transferable to any other languages.</p><p>Let us set a premise first, here we are trying to publish and subscribe a message to and from rabbitmq using amqp protocol. We have two functions Publish and Subscribe. Publish takes []byte as an input. Subscribe returns &lt;-chan []byte (channel of []byte).</p><p>Let’s look at the code example:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/b3f98a50b96bf8f73f15efe8000bad34/href">https://medium.com/media/b3f98a50b96bf8f73f15efe8000bad34/href</a></iframe><blockquote>Note: The Code example above is a wrapper around the amqp package. The purpose of the wrapper package is to hide complexity and expose a simpler API.</blockquote><p>Now let’s look at the test file for the above code example:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/af2fd015e8abffa3032a81b5a119fac5/href">https://medium.com/media/af2fd015e8abffa3032a81b5a119fac5/href</a></iframe><blockquote>Note: In the above code example, I have used a package called testify to create a test suite and run assertion easily.</blockquote><p>We are done with go code, now let’s write Dockerfile and docker-compose.yml to run integration tests using Docker.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/826e32d69782d737ad21df5c0aa9f5e7/href">https://medium.com/media/826e32d69782d737ad21df5c0aa9f5e7/href</a></iframe><p>Dockerfile is fairly simple. The only thing that I want to point out is CMD instruction that uses a Makefile target called integration-tests. I will get back to the Makefile in a while, for now, let’s look at the docker-compose.yml file.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/8bea66b872b9fe4672e9472ada3f716d/href">https://medium.com/media/8bea66b872b9fe4672e9472ada3f716d/href</a></iframe><p>docker-compose.yml file is also fairly simple. We have two services called tests and rabbitmq, tests service depends upon rabbitmq and both of these services are bound to a network called queue-test.</p><p>Let’s look at Makefile now:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/00259849731acbcb95da77e8581f5bcb/href">https://medium.com/media/00259849731acbcb95da77e8581f5bcb/href</a></iframe><p>The Makefile target tests help us run integration tests and do clean up once we are done. I also want to point out flag --abort-on-container-exit on command docker-compose up this flag helps us terminate rabbitmq once we are done running tests using docker-compose.yml</p><p>Now, look at the Makefile target integration-tests, something interesting is going with this command</p><pre>sh -c “while ! curl -s <a href="http://rabbitmq:15672/">http://rabbitmq:15672</a> &gt; /dev/null; do echo waiting for 3s; sleep 3; done”</pre><p>here rabbitmq takes a few seconds to completely start-up; we wait for 3sec and check if rabbitmq is up yet using curl on the URL <a href="http://rabbitmq:15672/">http://rabbitmq:15672</a>. If it’s up we go to the next command on target (that runs tests) else we again wait for 3sec.</p><p>Using tools like Docker and Make we can run integration tests on isolation and clean up after we are done testing our code. Using Docker to run tests also helps us be consistent across the local environment and CI/CD environment making it a lot easier to maintain our test suite. Thank you for reading, look at this <a href="https://github.com/rabingaire/go-integration-test-example">Github repo</a> to see the above snippets into action.</p><p><a href="https://github.com/rabingaire/go-integration-test-example">rabingaire/go-integration-test-example</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=852f4c933cbe" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Let’s Talk LLVM]]></title>
            <link>https://rabingaire.medium.com/lets-talk-llvm-796131006dc4?source=rss-c7ca25640693------2</link>
            <guid isPermaLink="false">https://medium.com/p/796131006dc4</guid>
            <category><![CDATA[compilers]]></category>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[compiler-design]]></category>
            <category><![CDATA[llvm]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Rabin Gaire]]></dc:creator>
            <pubDate>Sun, 25 Aug 2019 16:45:34 GMT</pubDate>
            <atom:updated>2019-11-11T08:40:26.329Z</atom:updated>
            <cc:license>https://creativecommons.org/publicdomain/mark/1.0/</cc:license>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*gE-QXRSJZsaVtL1Qw6eNuA.png" /><figcaption>LLVM Project</figcaption></figure><p>What’s LLVM?</p><p>According to Wikipedia, “The LLVM compiler infrastructure project is a set of compiler and toolchain technologies which can be used to develop a front end for any programming language and a back end for any instruction set architecture.”</p><p>LLVM was developed at the University of Illinois by Vikram Adve and Chris Lattner. It was originally developed as a research infrastructure to investigate dynamic compilation techniques for static and dynamic programming languages. Back then LLVM was an Acronym to Low-Level Virtual Machine but since the project has evolved significantly the Acronym has been removed in favor of LLVM name itself.</p><p>Today there are a lot of developer/compiler toolchains under the umbrella of LLVM project, now LLVM project consists of a debugger, optimizer, internal representation(IR) and many more.</p><p>Before getting to know about the importance of the LLVM project, let’s look into the monolithic structure of compiler technology. Suppose I wanted to develop a language called X, I would have to write my own, scanner/lexer, Parser, Intermediate Representation, Optimizer, and a Targeted Instruction set for all the chips where my language X is supposed to run. You can already see this was a big hassle in designing a programming language. To get around this; languages like Python and Ruby choose target language as C so that they don’t have to write N number of compilers for N set of architecture that they wanted to support.</p><p>The big idea of the LLVM project was to make this process easier, rather targeting some other programming language, language designer nowdays can target to LLVM IR, where LLVM IR is then passed to LLVM IR Optimizer and then to targeted machine code. Since LLVM is built by the community of smart developers around the world and has been around for a while now, it supports a variety of computer architecture and, there have been a lot of optimizations done towards this project making it one of the top compiler toolchain in the world.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Nzxg9Ztzj2xfdwdzFjuB8Q.jpeg" /><figcaption>LLVM Frontend-Backend Compiler Architecture</figcaption></figure><p>So the big questions remain? Why does anyone want to write yet another new language?</p><blockquote>Scenario one:</blockquote><blockquote>You are solving a domain-specific problem, you are looking for a lightweight language to run on top of custom-designed hardware. You could write a new language on top of LLVM infrastructure giving complete control over the hardware and software aspect of the project.</blockquote><blockquote>Scenario Two:</blockquote><blockquote>You have a very old system written on a very old programming language. It takes a lot of time, money and resource to rewrite that system on a modern programming language. What you could do is write an optimized compiler for the language that the old system is running, making it faster and capable of running on newer hardware. There is an agency called <a href="https://strumenta.com/">strumenta</a> that helps businesses building domain-specific languages like this.</blockquote><p>So you have seen the use cases of language design, I might as well have convinced you that you don’t have to build the next big language that will eventually take over the world. I also want you guys to understand that language design is also a career choice and there is a lot of opportunity laying around for the people who are interested in this field of computer science.</p><p>Before I sign off languages like C/C++ (clang compiler), Rust, Swift, Julia and many more are powered by LLVM compiler infrastructure, this blog post tried to give an introduction on what LLVM project is and next blog will try to shed some light on LLVM IR stay tuned. Bye Bye.</p><h3>References:</h3><p>LLVM Project Logo taken from LLVM project webpage (<a href="http://llvm.org/">http://llvm.org</a>)</p><p>LLVM Frontend-Backend Compiler Architecture Image has been taken from (<a href="https://medium.com/@JMangia/swift-c-llvm-compiler-optimization-842012568bb7">https://medium.com/@JMangia/swift-c-llvm-compiler-optimization-842012568bb7</a>)</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=796131006dc4" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Memory Management & Rust]]></title>
            <link>https://rabingaire.medium.com/memory-management-rust-cf65c8465570?source=rss-c7ca25640693------2</link>
            <guid isPermaLink="false">https://medium.com/p/cf65c8465570</guid>
            <category><![CDATA[rust]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[ownership]]></category>
            <dc:creator><![CDATA[Rabin Gaire]]></dc:creator>
            <pubDate>Sat, 09 Feb 2019 18:21:13 GMT</pubDate>
            <atom:updated>2020-01-31T16:36:41.414Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*M_gidRclLKQET4Ez_fhVfg.png" /></figure><p>I have always been fascinated by the programming languages. I always try out different programming languages and always interested to learn internals by cherry picking its feature; one at a time. The story behind all those design choices is always exciting and something worth to pursue.</p><p>Over the years I have learned a lot of programming languages, however, I am not an expert on any of them; the fact is I never intended to be. The only thing<strong> </strong>that motivates me is the reason behind their design, simply, “why languages are designed the way they are?”. What makes them unique from the other languages? What are the tradeoffs, and what are the benefits of those design choices?</p><h3>Rust</h3><p>A couple of weeks ago, I tried out Rust. One of its concept, called ownership, made me excited. It is the concept that Rust compiler use under the hood for memory safety that helped to solve null pointer error that most of the other low-level programming languages face.</p><p>Rust is a programming language designed with safety in mind. The designers of the language wanted Rust to be safe, low level, efficient, and fast. But the problem was you can only get one, either low-level control or more safety. For a lot of years, programmers had to be careful while dealing with low-level stuff, languages like C and C++ allowed low-level control but developers had to write a lot of code to ensure memory safety and avoid memory leaks. On the other hand, languages like Haskell, Python, and Ruby were safe but did not allow low-level control, so basically it’s mostly a tradeoff between low-level control and safety.</p><p>Now, Rust came to existence, it’s basically C++ with newer syntax that guides programmer towards safety still allowing low-level control, how does it do it? The concept like ownership and borrowing (I will write a new blog on this topic) helps it to achieve the memory safety that other low-level language could not incorporate.</p><h3>Malloc and Garbage Collector</h3><p>Before taking about ownership, I want to mention concepts like malloc and garbage collector. Language like C and C++ use malloc to allocate memory on a heap, this gives the programmer a lot of low-level memory management control but if the developer is not careful enough then leads to a lot of bugs like double free, dangling pointers, and memory leaks. Let me explain a little bit about these problems, double free is a problem where two sections of the code are pointing to a same block of memory and both of them tries to free the allocated memory. One of the section successfully frees up the memory, but the other one does not have anything to free. We can also explain another problem called dangling pointers with the same example as above when one section frees the memory and other section pointing to the same block does not have anything to point to. Likewise, a memory leak occurs when an allocated memory block is not deallocated even after we don’t plan to use the same block of memory later in the future.</p><p>To solve all of the above problems languages like Haskell, Python, and Ruby has something called garbage collector. The garbage collector is a service on a compiler and an interpreter that automatically identifies the memory location that is no longer in use and frees up the memory. This is a nice concept but garbage collector needs time to analyze and clean up memory at run time which might make our program execution time a little bit longer as the program needs to be paused to let garbage collector do its job. As language itself is on the charge of allocating and deallocating memory the low-level memory management is out of the window.</p><h3>Ownership</h3><p>So if Rust is safe and gives a lot of low-level memory control then what is ownership? When a Rust program starts to execute it creates a stack that keeps a track of everything happening on the program. First, the main method is executed which is then added to the stack, in more technical terms the very stack is called call stack. Let us suppose (as many variables as possible are stored inside registers) every function that we encounter is then added to the stack with variable, and values defined on the function, hence creating a scope system (everything defined on a stack can only be accessed on the following stack). Stack can’t hold a large set of data, we need to have a data with definite length (static data type) as the stacks on the computer is limited so we tend to store larger sets of data (dynamic data types) over a heap memory (which is also limited but is much larger in size than stack) and add pointer reference (reference to the heap location) at the stack.</p><p>When a function execution is over the respective variable and values stored on the stack is thrown away hence cleaning up the memory resources captured. This is one of the reasons Rust does not need a garbage collector. So far everything looks great, right? Let us take an example, we have a large collection of data on a vector (data structure) that is stored on a heap and has reference to it on a stack. Suppose a function now wants to copy the collection of data stored on a vector (data structure) to a new variable name, is it efficient to copy the whole data set to yet another memory location? Hell, no copying a large collection of data is inefficient and takes up a lot of space in memory. We don’t copy the actual data rather we copy the memory reference (pointer) making code much more efficient, fast and saving a lot of space on memory. Now we have created two variables pointing to the same memory location at the heap leading towards a problem I have mentioned above like double free and dangling pointers.</p><p>In this situation, Rust defines ownership to a given set of data structure, at any instance of time only one variable has ownership to a data structure. Let’s try to understand this with a real-world example, suppose you have bought a book, at this instance, you are the owner of the book, you own this book no other person but you. If someone wants to read this book they can’t have a copy of it, if they do it’s a different book. Once you finish reading, you can destroy the book. The same happens to a data structure on Rust, at any given instance of time only one stack frame can own this data structure, this has a nice implication as we can safely free the data structure from heap once the stack frame that owns it is out of the stack. Cool right? no more dangling pointers.</p><p>But there is a problem in the above scenario, we are not reusing the book or resource. If you and one of your friend want the same book then instead of destroying the book after reading it, you can give it to your friend.</p><p>The same case can happen here as well, like, what if two variables are pointing to the same data structure. For this, Rust has a concept called move. Like in the real-world example when someone wants to read your book he/she asks you for that book you transfer the ownership to him/her now you no longer have access to this book you have already transferred the ownership, now book belongs to your friend. The same thing happens on Rust when two variables are pointing to the same data structure. The ownership is moved to the new variable when this new variable is out of the scope only then the memory is freed hence fixing the issue of double free.</p><p>Concluding this is one of the reasons Rust does not need a garbage collector. It uses the stack to keep track of the program. Using ownership Rust gives safety while freeing up memory. Rust frees up the memory when respective variable owning the data is out of the scope after the complete execution of the respective function.</p><p>In the next blog post, I will talk about borrowing the concept used by Rust to manage pointer return type from a function. Stay tuned.</p><blockquote>Thank you Achyut Pokhrel for reviewing the content before publication.</blockquote><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=cf65c8465570" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[What is Object Spread Operator in Javascript?]]></title>
            <link>https://rabingaire.medium.com/what-is-object-spread-operator-in-javascript-95cf76e2a51b?source=rss-c7ca25640693------2</link>
            <guid isPermaLink="false">https://medium.com/p/95cf76e2a51b</guid>
            <category><![CDATA[javascript]]></category>
            <dc:creator><![CDATA[Rabin Gaire]]></dc:creator>
            <pubDate>Mon, 04 Feb 2019 15:40:28 GMT</pubDate>
            <atom:updated>2019-02-05T10:16:08.688Z</atom:updated>
            <content:encoded><![CDATA[<h3>Damm Object Spread Operator.</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/668/1*j5gdLo_DjSyOBDS32MEgcg.png" /></figure><p>What is Object Spread Operator in Javascript?</p><p>I thought I was very much familiar with this concept, I have written a lot of code with the help of this syntax, Object Spread Operator in Javascript makes it really easy to update the value of the keys. I love the concise syntax and Its much cleaner and easier to write and understand.</p><p>Here it is how we use Object Spread Operator in Javascript:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6e7de89ccd6a58677b8628c044ea20f7/href">https://medium.com/media/6e7de89ccd6a58677b8628c044ea20f7/href</a></iframe><p>It looks clean, readable and concise, right?</p><p>And it is also an immutable approach, meaning the changes on the new object updatedInfo does not mutate the values of the keys on myInfo. Cool Right?</p><p>Previously we used to write the above code similar to this:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/e27b4c732cddec35416c6d877c73dd42/href">https://medium.com/media/e27b4c732cddec35416c6d877c73dd42/href</a></iframe><p>Did you Spot the problem?</p><p>Changing the value of age and address on updatedInfo also changes the value of myInfo. Because while copying the myInfo object into updatedInfo we are not copying the actual value but we are copying the reference type, meaning both updatedInfo and myInfo points to the same memory location, this was a big problem and lead to a lot of bugs if the programmer was not careful enough.</p><p>To solve this problem developer used to write code similar to this:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f5130baefe2e5ec065b162b9cab6e7f0/href">https://medium.com/media/f5130baefe2e5ec065b162b9cab6e7f0/href</a></iframe><p>Object.assign solved the problem of mutation, as it used to create a new object at different memory location by copying the value of the parent/root object as in our case myInfo.</p><p>Above syntax is great but it looks weird, people coming from a different programming background can find it a bit confusing.</p><blockquote>Why the hell are you assigning this object with the empty object are the most common questions.</blockquote><p>So here comes the Object Spread Operator to rescue but it is also a double-edged sword. Why? Let me explain !!!</p><p>A couple of days ago I was working on this project where I wrote a code similar to this:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/b1552a57ebe9724e08158da579896c4a/href">https://medium.com/media/b1552a57ebe9724e08158da579896c4a/href</a></iframe><p>Looks good right?</p><p>But this code has a big problem, It does not actually update the value of age and address, hell it does not do a thing. Why? Because what we are actually doing is we have an object with keys age and address and we are updating those values with the respective values from myInfo. Making the code useless.</p><p>I thought I was doing everything right, but after an hour of debugging I finally figured it out and felt stupid for the kind of mistake I have made.</p><p>To be fair a lot of developers trip with this, while maintaining a huge code base we sometimes write code similar to this, I suggest everyone reading this blog to be extra careful while writing Object Spread Operator else you might have to say Damm Object Spread Operator.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=95cf76e2a51b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Models of Computation, Document Distance]]></title>
            <link>https://rabingaire.medium.com/models-of-computation-document-distance-7be4a9850067?source=rss-c7ca25640693------2</link>
            <guid isPermaLink="false">https://medium.com/p/7be4a9850067</guid>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Rabin Gaire]]></dc:creator>
            <pubDate>Tue, 20 Mar 2018 18:36:55 GMT</pubDate>
            <atom:updated>2018-09-24T07:42:34.598Z</atom:updated>
            <content:encoded><![CDATA[<p>Hello, This is a 47 part series that tries to give an introduction to algorithms. The content that I am using here to write this series is from MIT 6.006 Introduction to Algorithms, Fall 2011. In this second part of the series, we are going to talk about the Models of Computation and an Algorithm called Document Distance.</p><p>Before talking about anything else let’s first try to define Algorithm.</p><p><strong>What is Algorithm?</strong></p><p>According to the professor of MIT 6.006 Introduction to Algorithms, Erik Demaine Algorithm is a</p><ul><li>Computational Procedure to solve a problem</li><li>Algorithm is a mathematical analog (mathematical abstraction) of a computer program</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/880/0*o9QQ5UuW_IHPFhtm." /></figure><p>Here the picture above describes that the algorithm is a mathematical analog of a computer program, A computer program is built on top of a programming language whereas an algorithm is written in pseudocode (pseudocode is just a fancy word for structured English or any other natural language). A computer program written on any programming language runs on a computer, and the analog of a computer on a mathematical world is called model of computation. Model of computation says what your computer can do, what it allows to do in constant time.</p><h3><strong>Model of Computation</strong></h3><p>Model of computation specifies</p><ul><li>What operation an algorithm is allowed</li><li>How much does it cost (What is complexity?)(time, space, …)</li><li>Cost of algorithm = sum of operation cost</li></ul><p>Let’s talk about two models of computation</p><ul><li>Random Access Machine ( also known as RAM not Random Access Memory, this is not a typing mistake)</li><li>Pointer Machine</li></ul><h3><strong>Random Access Machine</strong></h3><p>Random Access Machine falls on the side of a mathematical model of computation, whereas Random Access Memory falls on the side of a computer device. These two things are quite similar but we can’t call same. Anyway, we will use Random Access Memory to define Random Access Machine which is more of a mathematical analog of an actual Random Access Memory on a real computer.</p><p>Talking about Random Access Memory, it’s basically a large array. Random Access Memory is usually organized by word.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/580/0*BRzYYDcuNrh1pp-m." /></figure><p>In order to compute with it we can say in Θ(1) (Constant Time) an algorithm can</p><ul><li>Load Θ(1) constant amount of word from memory</li><li>Do Θ(1) amount of computation (+, -, *, /, ^, &amp;, |)</li><li>Store Θ(1) words</li></ul><p>This Random Access Machine is how we think about computers, it’s an accurate model of computation that loading, computing and storing all takes about Θ(1) constant amount of time. We can manipulate a whole word in a constant amount of time.</p><p>We introduced word a while ago, what does word mean</p><ul><li>We know computer these are are of 32 bits and 64 bits, but being a little bit more abstract a word is w bits.</li></ul><p>Let’s not worry much about word, let’s just assume it a value with w bits, that our computational model accepts, word comes in as inputs and we compute on them.</p><p>So, Random Access Machine is a realistic model and it’s also a powerful model, but a lot of code doesn’t use Arrays and we might not need it, So we must think about more abstract models that are not as powerful but offer a simpler way of thinking about things. For example Random Access Model don’t have dynamic memory allocation, we know we can allocate memory dynamically, we have seen them implemented on our computers. But it’s nice to think about some kind of model that already takes cares of things like dynamic memory allocation, It’s like a higher level programming abstraction. We have one model that basically helps us get around easily with dynamic memory allocation called Pointer Machine.</p><h3><strong>Pointer Machine</strong></h3><p>Pointer Machine corresponds to Object-Oriented Programming in a simpler version. So we have</p><ul><li>Dynamically allocated objects</li><li>Objects have constant amount Θ(1) of fields</li><li>Field = Word (e.g. int) or a pointer (This is where pointer machine gets its name). What is pointer? A pointer is something that points to another object or has special value null.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/520/0*tAydhqUVFERavsk7." /></figure><p>The image above shows us a linked list, linked list have a bunch of field in each node, we might have a pointer to the previous element, a pointer to next element and some value. To be precise the image shows a type of linked list called <strong>Doubly Linked List</strong> we call it Doubly because each node has two pointers that point to the previous node and next node. Pointer <em>prev</em> of the initial node and the pointer <em>next</em> of the last node points to a null value. We actually have a two node doubly linked list in the picture.</p><p>So this is a structure in a pointer machine, it’s a type of a data structure, in python, we might call this as a tuple or an object with three attributes and the value in this structure can be called as a word. We can implement this model in Random Access Machine and a pointer becomes an index of a giant table which is basically an array in Random Access Machine, Actually this is how a pointer in C programming language has been implemented.</p><p>We will talk a lot more about link list in upcoming blogs but for now everything we do in linked list takes constant amount of time, following a pointer cost constant amount of time, adding a node cost constant amount of time, changing any value on a node cost constant amount of time, basically all the usual things that we might do to the objects on a node cost constant amount of time. Due to this factor, it is considered Linked List an efficient and important data structure in computer science.</p><p>So pointer machine is a weaker model than random access machine as we can implement pointer machine with random access machine but pointer machine allows us to think differently and lots of data structure are build using this concept.</p><p>This was all about theory, so let’s talk about a practical approach using python model.</p><h3><strong>Python Model</strong></h3><p>Let’s talk why do we use python model, it’s because both of the models we talked earlier (Random Access Machine, Pointer Machine) are old model of computation, and python is a recent programming language and also python implements somewhat amount of older model of computational perspective. Python has arrays, as we have already discussed arrays resemble Random Access Machine perspective and also it has pointers which resemble Pointer Machine perspective. Older models of computation (Random Access Machine, Pointer Machine) are simple and theoretical so whatever we do on them only takes a constant amount of time, but in python model, some operation takes a lot of time while other still takes a constant amount of time. So whenever we are thinking about an algorithm in python model or implementing in Python programming language, we must know which operation is faster and which operation is slower.</p><p>Let’s spend some of our time trying to figure out which operation of python is faster and slower.</p><p>Let’s take an operation <em>L[i] = L[j] + 5</em> where L is the list, In python this operation will always take Θ(1) time (This example resemble Random Access Machine). In other programming languages, this might take linear time as it has to scan list L to j add 5 and place the result by scanning the list L again to i.</p><p>Objects (Resemble pointer machine model) with O(1) attributes. <em>x = x.next </em>here x being the pointer in a linked list, when there is an operation like this it also takes Θ(1) time in python model.</p><p>It’s been a while I am talking about constant time Θ(1), we don’t care much about this constant time because what we only care about is scalability with n and there is no n in these case.</p><h4>List (Arrays are called list in Python)</h4><p><strong>L.append(x) (Here L being a list) </strong>To understand how much does it cost, we should think by how it’s implemented in terms of the basic operation (<em>L[i] = L[j] + 5,Objects x = x.next) </em>. Most of the things we do can be reduced to those two terms. So let’s get back to append. Basically thinking about how does an append work, we have a certain size of an array and want to append an element to make it one element larger, how do we do it? The obvious way is to create a new array with one more larger size than of the original one and copy all the contents over to the new array and add the new element at the last. If you have written C program before then this is how malloc/realloc works. This approach is fine but it takes linear time. In case of python it does not do in this way, we will talk in detail how this works in a later blog post, but for now, let’s say it just do something called <strong>table doubling</strong> which cost around constant time Θ(1) most of the time.</p><p><strong>L = L1 + L2 (L, L1, L2 are lists)</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/932/1*R_KX73ko4DMWkFhBgRK4Zg.png" /></figure><blockquote>append takes Θ(1) time</blockquote><blockquote>Θ(|L1|) order of length of L1</blockquote><blockquote>Θ(|L2|) order of length of L2</blockquote><p>At last this operation takes Θ(1+ |L1| + |L2|), where did 1 come from? If a length of L1 and L2 is zero it still takes constant time to build the empty array.</p><p>Most of the time people get confused and say operation L = L1 + L2 takes constant time because they see + on the operation, It takes constant time only if L1 and L2 are simple variables but in our case they are not rather they are entire data structure called list(array), so while analyzing the algorithm we must take account the data structure in use.</p><p><strong>x in L ( L is a list )</strong></p><p>This operation takes linear time in worst case scenario as we have to scan through the items in the list to find the value.</p><p><strong>len(L) (L is a list)</strong></p><p>This operation takes Θ(1) time, How does this operation in python take constant time? Because in python list are implemented with a counter built in, which makes it easier to find the length of a list. In other programming languages, this operation might take linear time as it has to go through the entire list to count the length of the list, to be fair this is all related to how an operation is implemented in a programming language.</p><p>I am not going to talk more about this anymore as it is obvious how to find the cost of an operation if you want more information about how much does it cost to perform a certain operation in python please refer to python documentation.</p><p>Before dropping this topic I have a quiz question, answer this in the comment box.</p><blockquote>Q. Let’s assume we have a two long integer x and y, how much does it cost to add them both?</blockquote><h3><strong>Document Distance Problem</strong></h3><p>In document distance problem we have two document D1 and D2 and we want to compute the distance between them represented as:</p><p>d(D1, D2)</p><p>So the big question is what does distance mean?</p><p>Distance here means finding out whether two document are similar or not/Duplicate or not</p><p>Document = Sequence of words</p><p>Word = Sequence of alphanumeric characters</p><p>So the idea in this problem is to find the shared word between documents and use that to define distance (Document distance).</p><p>We can also think document as a vector so</p><p>D[W] = # Occurance of word W in document D</p><p>For example</p><p>Let’s take two documents</p><blockquote>D1 = “the cat”</blockquote><blockquote>D2 = “the dog”</blockquote><p>We can represent them in 3D space because we just have three different words here in our document D1 and D2</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/626/0*hCHOzj0gsn1TGExP." /></figure><p>D1 and D2 in the above figure are vectors.</p><p>So at first attempt, we can define document distance using an inner product of vector calculus which is also called dot product which can be used to find the difference between vectors. ( Math Math Math )</p><blockquote>d’(D1, D2) = D1.D2 = wD1[W].D2[W]</blockquote><p>But we have a problem because a long document with 99% same word is said to be farther than the short document with 10% same word. To fix this issue we have to divide the above equation with the length of the vectors which turn out to be like this</p><blockquote>d’’(D1, D2) = (D1.D2)/(|D1|.|D2|)</blockquote><p>Well, this was quite a long blog. Hope you got what I meant in this blog. If you want the reference from where I took content to write this blog then the reference has been listed below</p><ul><li><a href="https://www.youtube.com/watch?v=Zc54gFhdpLA">Models of Computation, Document Distance</a></li><li><a href="https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec02.pdf">Notes of MIT 6.006</a></li><li>Images used in the blog are the screenshots of the Notes from MIT 6.006</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7be4a9850067" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Algorithmic Thinking, Peak Finding]]></title>
            <link>https://rabingaire.medium.com/algorithmic-thinking-peak-finding-ad6f7415d154?source=rss-c7ca25640693------2</link>
            <guid isPermaLink="false">https://medium.com/p/ad6f7415d154</guid>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Rabin Gaire]]></dc:creator>
            <pubDate>Sun, 11 Mar 2018 11:04:04 GMT</pubDate>
            <atom:updated>2018-03-11T14:54:58.699Z</atom:updated>
            <content:encoded><![CDATA[<p>Hello, This is a 47 part series that tries to give an introduction to algorithms. The content that I am using here to write this series is from MIT 6.006 Introduction to Algorithms, Fall 2011. In this first part of the series, we are going to talk about the way of Algorithmic Thinking using a fairly easy Algorithm called Peak Finding.</p><p>Before starting out let’s first define Algorithmic Thinking</p><p>According to the professor of MIT 6.006 Introduction to Algorithms Srini Devadas and I quote “Algorithmic Thinking is all about efficient procedures for solving problems on large inputs”</p><p>What actually does large inputs mean?</p><p>Some fair example of large inputs are</p><ul><li>US — highway system</li><li>Human genome (Which has billions letters in its alphabet)</li><li>Social network (like facebook and twitter)</li></ul><p>Here in 21st century definition of large input is in trillions. The World is moving faster than ever, things are getting bigger, we have the computational power that could handle large data (trillions) this does not mean efficiency is the main concern. I agree we can scan billions of element in a matter of second but if you had an algorithm that required cubit complexity suddenly we are not talking about 10 to the power 9 we are talking about 10 to the power 27 and even current computer can’t handle that kind of numbers. So efficiency is a concern as input gets larger it becomes more of a concern.</p><p>So in this series we mostly concern about</p><ul><li>Efficient procedures for solving large scale problems and</li><li>Scalability</li></ul><p>We are going to tackle above concern using the classic data structure like arrays, linked list, stack and queue along with classic algorithms like Search Algorithms, Sort algorithms, and Tree Algorithms.</p><p>This series is not about algorithmic design it’s about algorithmic analysis. We are going to do a lot of analysis and think efficient procedures to solve large-scale problems. We also concern about Scalability because back in the day’s large input was in thousands, today it is in trillions it’s just a matter of time we call 10 to the power 18 fairly a large input. Hence the algorithm we design should be scalable to the growth of the input.</p><h3><strong>Peak Finder</strong></h3><p>Let’s start with the <strong>one dimensional</strong> version of peak Finder</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/466/1*qH1o9twZ6wxguNvj0Bs-EQ.png" /></figure><p>Let us consider a number of arrays, we are representing them in symbols ( a — i ), we also assume that all the numbers are positive numbers.</p><p>Here position 2 is a peak if and only if b &gt;= a and b &gt;=c.</p><p>If you are equal and greater than the elements on left and right side than you are the peak. In case of the edges, you only have to look at only one side. For example, position 9 is a peak if i &gt;= h.</p><p>So the problem we solve right now is represented as “Find a peak if exists”. I highly emphasis on the part “if exists”, this is an approach of Algorithmic Thinking. What we are trying to advocate for this problem is that the algorithms we design should be general. We use “if exists” because whenever we want to argue about the correctness of the algorithm we have a proof of concept that we will find or not find the peak from the given set of data. In our case, we will always find a peak but if we change the problem definition we will still have the starting point to go attack the second version of the problem. In this case we have defined that there is greater than and equal to (b &gt;= a and b &gt;=c) we can easily argue that any array will definitely have a peak but let’s tweak this problem a bit and say we only have a greater than, then we can’t for sure say there will be a peak.</p><p>Many time you are asked to do something, and you can’t answer the question or find something that satisfies all the constraints required. And in that case, you want to be able to give an argument that you searched hard but could not find it. Otherwise, there is always a case that you didn’t search hard enough. You searched hard and could not find the answer is the proof of concept that the solution might not be available.</p><p>Now let’s look at a <strong>Straightforward Algorithm</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/436/1*YlWyj6ykur0MoTCrwbS3VA.png" /></figure><p>Let us assume that the peak is in the middle, the numbers start increasing from left up to the middle and start decreasing. Here the algorithm will have to look at n/2 elements to find a peak.</p><p>Let us again assume that the peak is all the way to the right, so you start searching peak from the left all the way to the right, you will be looking at n elements to find a peak.</p><p>So in the worst case scenario, the complexity will be Θ(n), i.e it has to look at all the elements in the array. So what we are really saying here is that the asymptotic complexity of the algorithm is linear.</p><h4><strong>Divide and Conquer</strong></h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/612/1*UeaZ2wSzjnwuqQE3-0kmPA.png" /></figure><p>This is a divide and conquer algorithm. We are mostly going to look at the n/2 position.</p><blockquote>If [n/2] &lt; [n/2–1] then only look at left half from 1 to [n/2–1] to look for a peak</blockquote><blockquote>Else if [n/2] &lt; [n/2+1] then only look at right half from [n/2+1] to n</blockquote><blockquote>Else n/2 is the peak.</blockquote><p>Given the problem, we agree that this algorithm is correct and finds a peak. Given the fact that we agreed on the correctness of the algorithm now let us talk about the complexity of the algorithm.</p><p>First, let’s define a recurrence relation in terms of T(n) to this recursive algorithm Divide and Conquer</p><blockquote>T(n) = T(n/2) + Θ(1)</blockquote><p>Standing on the base of computational standpoint this algorithm does T(n) amount of work on the input size of n.</p><p>Here on the equation Theta 1 corresponds to the two comparisons we have to do since 2 is constant we represent it as Θ(1)</p><p>So we take the above equation and expand it eventually we will get to the best case which is T(1) = Θ(1).</p><p>We will reach to the array with a single value, for this array will return the value as a peak.</p><p>So we could also write the equation as</p><blockquote>T(n) = Θ(1) + …… + Θ(1) [This is a expanded form of the above equation]</blockquote><p>We gonna expand it log n times. So the complexity of the algorithm is Θ(log n)</p><p>So if you compare divide and conquer with straightforward algorithm there is an exponential difference in terms of complexity. Divide and Conquer is way faster than the straightforward algorithm. So we can conclude that it is always better to reduce complexity as the input gets large.</p><p>Now let’s look at the <strong>two</strong> <strong>dimensional</strong> version of peak finder</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/584/0*l7jbVo93cm7EEgko." /></figure><p>As we can guess a is a 2D peak if and only if</p><p>a &gt;= b, a &gt;= c, a &gt;= d and a &gt;= e</p><p>So we have again used greater than and equal to here as well so it’s similar to that of one dimensional that the peak will exist.</p><p>In this version also let’s start with a <strong>Straightforward algorithm called Greedy Ascent Algorithm</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/402/0*8dLHdI_Xtvis6BzG." /></figure><p>In Greedy Ascent Algorithm, we have to make a choice from where to start.</p><p>So if we say we want to start with 12, we are going to look for something to left. And if it’s greater than, we’re going to follow that direction. If it’s not, then you’re going the other direction. So, in this case, we will go to 12, 13, 14, 15, 16, 17,19, and 20. And we will find a peak. In this algorithm, if we try to find a peak we might have to touch the half part of the elements or even worse all the parts of the elements in a matrix. So if we try to do the worst case analysis of the algorithm we will find that it would be Θ(nm) where n is the number of rows and m be the number of columns. In the case where n = m the worst case complexity would be Θ(n²).</p><p>Now let’s try to<strong> improve the complexity by Extending 1D Divide and Conquer to 2D</strong>.</p><p><strong>Attempt # 1</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/436/0*z4CDN01S2awOl_ql." /></figure><p>Let’s pick middle column j = m/2 and find a 1D peak at (i, j). Use (i, j) as a start point on row i to find 1D-peak on row i. I am really happy that we reduced the complexity to Θ(log n) as the complexity to find a peak in the 1D array is Θ(log n). But the problem is that this algorithm is efficient but not correct. As of old saying goes by</p><blockquote>“It is better to have an algorithm that is inefficient but correct rather have efficient incorrect algorithm”.</blockquote><p>So what’s the problem with this algorithm?</p><p>The problem is 2D peak my not exist in row i.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/392/0*luMpaOMyTxInFZix." /></figure><p>Let’s look at the example:</p><p>Let’s choose the 3rd column from left as a middle. We start finding a peak and returned 12 as a peak, it’s quite possible to return 12 as a peak even though 19 is the actual peak because the value that surrounds 12 are less than 12. So I choose 12 as a pick and start finding peak on a row where 12 is located. Looking at the row the peak is at 14. And the algorithm will return 14 as a peak of the matrix. It’s true that 14 is a peak in a 1D case but looking from the perspective of a 2D 14 is not a peak which means the algorithm is incorrect. This looks like an efficient algorithm but does not work.</p><p>So the last algorithm that will solve this problem is:</p><p><strong>Attempt # 2</strong></p><ul><li>Pick middle column j = m/2</li><li>Find global maximum on column j at (i, j)</li><li>Compare (i, j − 1),(i, j),(i, j + 1)</li><li>Pick left columns if(i, j − 1) &gt; (i, j)</li><li>Similarly for right if (i, j) &lt; (i, j + 1)</li><li>(i, j) is a 2D-peak if neither condition holds</li><li>Solve the new problem with half the number of columns.</li><li>When you have a single column, find global maximum and you‘re done</li></ul><p>Example of Attempt # 2</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/898/0*_QdkbU7IbbqAAslv." /></figure><p>So the recurrence relation in terms of T(n,m) to this recursive algorithm is</p><blockquote>T(n, m) = T(n, m/2) + Θ(n)</blockquote><p>Why is this the equation because n is the number of rows and m is the number of columns, In one case we will be breaking things down into half number of columns which is m/2 and In order to find the global maximum we will be doing Θ(n) work.</p><p>So we take the above equation and expand it eventually we will get to the best case which is</p><p>T(n,1) = Θ(n).</p><p>So we could also write the equation as</p><blockquote>T(n, m) = Θ(n) + …… + Θ(n) [This is a expanded form of the above equation]</blockquote><p>We gonna expand it log m times. So the complexity of the algorithm is Θ(n log m)</p><p>Well, this was quite a long blog. Hope you got what I meant in this blog. If you want the reference from where I took content to write this blog then the reference has been listed below</p><ul><li><a href="https://www.youtube.com/watch?v=HtSuA80QTyo">Algorithmic Thinking, Peak Finding Video</a></li><li><a href="https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec01.pdf">Notes of MIT 6.006</a></li><li>Images used in the blog are the screenshots of the Notes from MIT 6.006</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ad6f7415d154" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>