<?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 Vineet on Medium]]></title>
        <description><![CDATA[Stories by Vineet on Medium]]></description>
        <link>https://medium.com/@svineet?source=rss-fd67c612c31d------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*MqZLN05MuxufEfzzVdpq-Q.jpeg</url>
            <title>Stories by Vineet on Medium</title>
            <link>https://medium.com/@svineet?source=rss-fd67c612c31d------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 15:54:47 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@svineet/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[GSoC 2020: the first milestone]]></title>
            <link>https://svineet.medium.com/gsoc-2020-the-first-milestone-a4dfc97ca078?source=rss-fd67c612c31d------2</link>
            <guid isPermaLink="false">https://medium.com/p/a4dfc97ca078</guid>
            <category><![CDATA[gnome-gsoc-svineet]]></category>
            <dc:creator><![CDATA[Vineet]]></dc:creator>
            <pubDate>Wed, 01 Jul 2020 17:26:03 GMT</pubDate>
            <atom:updated>2020-07-01T17:26:03.704Z</atom:updated>
            <content:encoded><![CDATA[<p><em>Please read the</em><a href="https://medium.com/@svineet/gsoc-2020-with-gnome-a-beginning-9d3f9e79881b"><em> previous post</em></a><em> for context!</em></p><p>It has been one complete month since the coding period of Google Summer of Code started. In this period, I have learnt a huge number of things, and have made visible progress towards the goal of my project.</p><p>The aim of my project was to remove the speed issues present in the TreeView of the files plugin in <a href="https://wiki.gnome.org/Apps/Gitg/">gitg</a>. The plan was to make a custom TreeModel that would lazily load up nodes, and preserve expanded nodes when the model changes (i.e jumping from commit to commit)</p><p>During the community bonding period, I had a video call with my absolutely amazing mentor Alberto, who told me about GNOME culture, and about his inspiring journey with GNOME as contributor. In the last month, I have been welcomed by the community and am very proud to be contributing to GNOME.</p><p>Here’s a summary of the technical work that has been done in the last month.</p><h3>Setting up the test-bed</h3><p>In order to test the various algorithms and implementations we had in mind, Alberto recommended we start a small separate project that would only contain the necessary code from gitg, so that we could directly work on the core issues and not get bogged down in unnecessary details.</p><p>I spent the first week of June building a test bed project in Vala, with Meson as the build system. <a href="https://gitlab.gnome.org/svineet/lazytreestore">Here it is</a>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/552/1*0ouzwX7W1xfi7cxUP5j9WA.png" /><figcaption>Trees are represented in JSON for convenience’s sake.</figcaption></figure><p>Along with the main application, I’ve added scripts that generate large trees for testing purposes. It loads trees in JSON format, and two TextViews which take source tree and destination trees.</p><h3>Making progress: with libdazzle</h3><p>After a week of researching various ideas for the optimisation, I stumbled upon <a href="https://gitlab.gnome.org/GNOME/libdazzle/">libdazzle</a>. libdazzleis a collection of widgets and features that are very useful, but out of Gtk and GObject’s scope. I discovered that there is a lazy loaded TreeView subclass in libdazzle called Dazzle.Tree. Of course, it did not have the tree switching algorithm that we desired, but I could still use it a very solid foundation for our usage.</p><p>Unfortunately, libdazzle is under-documented, and I could not find any examples for Dazzle.Tree, which uses a separate data loading mechanism than normal TreeViews. After a week of digging around the source code and finding examples in the GNOME Builder codebase, and good help from hergertme on #gnome-builder, I was finally able to make it work.</p><p>After that, I applied a simple algorithm that retained previously expanded nodes and we have the implementation available in <a href="https://gitlab.gnome.org/svineet/lazytreestore/-/merge_requests/2">this merge request</a> to the test-bed project. Currently, it works perfectly and is fast enough for our uses in gitg. I am still testing everything out to make sure it works well.</p><h3>Looking forward</h3><p>It has been an amazing month of learning with the GNOME community, and I’ve learnt a lot about how Vala works, how to read and understand C code, Meson build systems, and many more things that I cannot list in a single blog post.</p><p>In the next month, I aim to integrate the lazy tree view directly into gitg, and start writing tests for the same functionality. Dazzle.Tree has quite a few features that can be useful for gitg, such as the MIME based icons, and I plan to eventually start integrating those as well.</p><p>I would like to thank the GNOME community for welcoming me, and Alberto for being an amazing mentor.</p><p>See ya next month, hopefully we’ll have even more good news by then! 😄</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a4dfc97ca078" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[GSoC 2020 with GNOME: a beginning]]></title>
            <link>https://svineet.medium.com/gsoc-2020-with-gnome-a-beginning-9d3f9e79881b?source=rss-fd67c612c31d------2</link>
            <guid isPermaLink="false">https://medium.com/p/9d3f9e79881b</guid>
            <category><![CDATA[gnome-gsoc-svineet]]></category>
            <dc:creator><![CDATA[Vineet]]></dc:creator>
            <pubDate>Tue, 19 May 2020 15:20:54 GMT</pubDate>
            <atom:updated>2020-05-21T06:21:04.947Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/655/1*rcI8yvjriuOxFqj8RvocPw.png" /></figure><p>I have been accepted into <a href="https://summerofcode.withgoogle.com/dashboard/project/4753159408320512/overview/">Google Summer of Code 2020 with GNOME Foundation</a>!</p><p>I am grateful to my mentor albfan and the whole GNOME developer community to have helped me become capable enough to tackle this project. Can’t wait to get my hands dirty and become a strong member of the GNOME community!</p><h3>My Project</h3><p><a href="https://wiki.gnome.org/Apps/Gitg/">Gitg</a> is a GUI git client. It allows you to explore the history of a git repository, make commits, branches, refs, and do complex operations like cherry picking via an intuitive GUI. Visualising the merge history of a large repository is often useful in large FOSS initiatives.</p><p>Gitg has two major plugins, the files plugin which allows interactive exploration of a file through it’s history in the repository, and the diff plugin which allows viewing changes between commits visually (imagine a change in a image asset, or a GIF asset, GUIs do come handy here)</p><p>The current issue with the files plugin is that the side-tree that shows the directory structure of a selected commit is quite slow. This is a classic problem faced with GtkTreeView with a huge number of rows are involved.</p><p>My task during GSoC will be developing a new TreeModel that will lazy load the directory structure of a git repository commit.</p><p>This will involve learning about git internals, libgit2, tree diff algorithms, and trying out<br>many different algorithms to speed up the loading and dynamic changes.</p><p>Best case, we might end up with a generalised LazyTreeStore that would be usable within any Vala codebase, solving a very common problem in numerous projects that utilise high performance TreeViews</p><h3>Going forward</h3><p>As a small beginning, during my proposal itself I had started a Vala+Gtk project to test various algorithms. <a href="https://gitlab.gnome.org/svineet/lazytreestore">Here it is.</a></p><p>I will be making merge requests with various algorithms and techniques, and tests for the required features and see how much of an improvement each one of them is.</p><p>I will be documenting my findings as I go, so stay tuned! 😃</p><h3>Conclusion</h3><p>I am looking forward to a great summer with GNOME, working on algorithms and learning a lot about how the GNOME developer community functions. By the end, I hope to have made a significant contribution towards the GNOME community, and become an integral part of it. 😄</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9d3f9e79881b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Analysing the COVID-19 “Binary Search” testing algorithm via Monte Carlo method (Part 2)]]></title>
            <link>https://svineet.medium.com/analysing-the-covid-19-binary-search-testing-algorithm-via-monte-carlo-method-part-2-3ee0ae511954?source=rss-fd67c612c31d------2</link>
            <guid isPermaLink="false">https://medium.com/p/3ee0ae511954</guid>
            <category><![CDATA[coronavirus]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[math]]></category>
            <dc:creator><![CDATA[Vineet]]></dc:creator>
            <pubDate>Sat, 11 Apr 2020 18:00:50 GMT</pubDate>
            <atom:updated>2020-04-11T18:00:50.381Z</atom:updated>
            <content:encoded><![CDATA[<p>Link to <a href="https://medium.com/@svineet/analysing-the-covid-19-binary-search-testing-algorithm-via-monte-carlo-method-part-1-951049cdb212">Part 1</a>. (You won’t understand much of what this post is about if you don’t read Part 1)</p><h3>Where we are, and where we are going</h3><p><a href="https://github.com/svineet/monte-carlo-algo-analyser/blob/master/Monte%20Carlo%20Algorithm%20Complexity%20Analyser.ipynb">Notebook from Part 1</a></p><p>So now we have a bare bones system that takes the code for an algorithm, it’s input space, and spits out a graph of T(N). Great! Now let’s get down to implementing the actual COVID-19 testing algorithm.</p><h3>Implementing the algorithm</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/591/1*enYAnmInU1KTsk9wzxY5ng.png" /><figcaption>reference</figcaption></figure><p>Here’s what I’ve gathered from the tweet above.</p><ol><li>Take N people. Mix their blood, and check for COVID.</li><li>If positive, we split the group into two of N/2 each. Recursively test.</li><li>If negative, stop testing. None of these people are positive (probably… since COVID testing isn’t really 100% accurate. But we have to make assumptions.), so no more tests are required. This is where we’re supposed to gain performance.</li></ol><p>Now that we have the algorithm, we need the input space. Let K% of the tested population be actually infected with COVID-19. To generate a sample from this space we need a data structure that can do the following</p><ol><li>Store the infected/non-infected status of N people, out of which K% are infected</li><li>Supports bool pooled_test() that will tell us if the group as a whole is infected</li><li>Supports something like(Group, Group) half_split() returns two new groups with N/2 elements each.</li></ol><p>To generate a sample, we will generate a group like this and mark K% of them as infected.</p><h3>Writing up the data structure</h3><p>We store the indices of the infected. When queried, given left and right bounds, we check via binary search if there are elements in the array that lie between left and right. This gives us logarithmic query time, and group splitting is just done down the middle, so splitting takes constant time.</p><p>Might as well try to keep the complexity low, given that Monte Carlo is such an expensive place. (<a href="https://brrr.money/">Money Printer go brrrrr</a>)</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f06144bfaf7305aff750fedd32541220/href">https://medium.com/media/f06144bfaf7305aff750fedd32541220/href</a></iframe><h3>Writing up the algorithm</h3><p>Pretty simple stuff.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/662cbf4a207cac19b6823d7e3293cb1f/href">https://medium.com/media/662cbf4a207cac19b6823d7e3293cb1f/href</a></iframe><p><a href="https://github.com/svineet/monte-carlo-algo-analyser/blob/master/(Part%202)%20Monte%20Carlo%20Algorithm%20Complexity%20Analyser.ipynb">Link to final notebook</a></p><h3>Last visit to Monte Carlo</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/402/1*a7AT28-YwzzJMM8iB0MXrw.png" /><figcaption>o noe</figcaption></figure><p>Doesn’t look like a 10x improvement to me, more like 2x. But well, I’m not really a doctor so I will reserve my judgement. And that too at 5% infection rate. Which is a low estimate of the population that will be tested, because if you have gathered up people for testing, wouldn’t you have guessed that more of them are infected?</p><p>Also looks quite linear to me. Question to the reader: Why the squiggly nature of the line? (Hint: floors and ceilings in binary search)</p><h3>Conclusion</h3><p>And there ends our brief trip to Monte Carlo. Now we have a probabilistic algorithm performance analyser.</p><p>Some possible improvements</p><ol><li>Fit complexity classes, via linear regression with changed bases. For example, if we hypothesise it’s a logarithmic function, fit a linear regression with bases as log(N) and 1.</li><li>Parallelize. I didn’t see much performance improvement while attempting this, maybe because of memory allocation overheads, but please feel free to message me if you have good ideas!</li></ol><p>And that brings us to the end of the series! Feel free to send ideas and PRs to the <a href="https://github.com/svineet/monte-carlo-algo-analyser">GitHub repo</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3ee0ae511954" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Analysing the COVID-19 “Binary Search” testing algorithm via Monte Carlo method (Part 1)]]></title>
            <link>https://svineet.medium.com/analysing-the-covid-19-binary-search-testing-algorithm-via-monte-carlo-method-part-1-951049cdb212?source=rss-fd67c612c31d------2</link>
            <guid isPermaLink="false">https://medium.com/p/951049cdb212</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[math]]></category>
            <dc:creator><![CDATA[Vineet]]></dc:creator>
            <pubDate>Sat, 04 Apr 2020 20:42:25 GMT</pubDate>
            <atom:updated>2020-08-02T16:47:00.884Z</atom:updated>
            <content:encoded><![CDATA[<p>A few days ago, a tweet popped up in my feed. Here it is:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/591/1*enYAnmInU1KTsk9wzxY5ng.png" /></figure><p>As a Computer Science undergraduate, this piqued my interest. How much of an improvement would this algorithm be? A normal test, through N people would take time O(N), and n testing kits. Clearly, the worst case scenario for the above algorithm is the same, if all the patients are positive.</p><p>However, given that only a percentage of the population that is being tested is actually infected, say X%, what kind of improvement would this algorithm bring? The tweet claims 10x which is pretty interesting. Since we are in probability land now, we will have to calculate the expected running time, i.e E[T(N)] instead of just T(N), which by itself would be a random variable depending on the population being tested.</p><p>So how do we calculate this probability, and other interesting facts about the distribution of T(N)? As a lazy person who wants to avoid putting pen to paper, I propose a simple system for calculating expected complexity class of a probabilistic algorithm that utilises Monte Carlo simulations, and we’ll use it to analyse how the given algorithm performs given X.</p><h3>Monte Carlo Simulation, explained with Minecraft mining strategies</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3mTxslREq7Tjp2EGtliDWg.jpeg" /><figcaption>muh diamonds</figcaption></figure><p>Lately I’ve been playing a lot of Minecraft. I was desperately looking for better mining strategies, so I can get more diamond, and make progress in the game. The world in Minecraft is procedurally generated, which means it’s sort of kind of random. All blocks generated are random variables, that it to say.</p><p>So now I thought, well. I would like to know the expected number of diamond blocks I would find at a depth say, N, so I will only mine at that level and not waste time in low diamond areas. I am not a hacker, and have no access to the code generating the system, and I have anti-Google syndrome. What do I do? How do I find out the best depth for mining?</p><p>So here’s an idea. Make Minecraft generate many worlds. For each depth, say at level 18, we record the amount of diamond blocks generated at that depth. Now we take the average across all worlds, and by the central limit theorem, we have an estimate for the expected number of diamond blocks at that depth.</p><p>Now do that for each depth, and we have a function Diamond(D), with depth as a parameter!</p><h3>Sidenote: Mean is not all that matters</h3><p>Being a wise miner, I would want to mine at the depth where the expectation of diamond blocks is highest, right? But wait. There’s way more to this story than you would realise.</p><p>Would you mine a depth with mean 10 and variance 6 or a depth with mean 8 but variance 1? The first one is more profitable on average, but it involves more risk too. The second is safer, but less profitable on average. Any more, and we would enter risk management territory.</p><h3>Monte Carlo is an expensive place</h3><p>But there are issues here. How many worlds before the average depths actually converge to the expected depth? That’s a lot of compute we’re going to have to consume there, generating worlds. What if the world generator doesn’t even do the same thing across worlds? Questions, questions. We’ll see how this pans out later on.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/900/1*ry2FqESoD62-V_IVWGdaZA.jpeg" /><figcaption>the actual Monte Carlo</figcaption></figure><p><strong>Monte Carlo, in many ways of interpretation, is an expensive place</strong>. In fact, the method is named after a casino called Monte Carlo, in Monaco, Italy. Good trivia.</p><p>But anyway, what we pulled off here is called going to Monte Carlo. Let’s make it concrete. We have a function that lets us generate a sample from that distribution. We have no information how it works, but we can make samples at will. We <strong>generate samples</strong>, <strong>take sample statistics</strong>, <strong>analyse as required</strong>, and <em>stay home</em>.</p><h3>Another example of Monte Carlo</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/250/1*PkARGV4aIcFb6u5LhuQWCw.png" /><figcaption>A square with a closed loop (circle in this case) inside it. Find the area.</figcaption></figure><p>Let’s say I give you a unit area square with side length 1, and inside that square is a closed loop. I want you to find the area of that loop. I will only provide you with one function, nothing else. Call it bool sampler(). Sampler picks a random point from the square (uniformly random, mind it) and gives you true if that point is inside the closed loop, false if not.</p><p>How would you find the area enclosed by the closed loop? Left as an exercise to the reader 😉.</p><h3>Designing a system for complexity class inference of probabilistic algorithms</h3><p>So to analyse the average complexity of the COVID-19 “binary search” algorithm above, we would like a system that takes a function and it’s input space as inputs, and spits out a graph or complexity class of the T(N) function.</p><p>We apply the same idea. We generate random samples from the domain of input space given, and then run the algorithm on it. We record the number of costly operations utilised, and then visualise the distribution obtained.</p><p>Now we should probably pick an easy starting function so that we know that the system actually works before using it on the “binary search” algorithm. So we start with actual binary search 😄</p><h3>A simple start</h3><p><a href="https://github.com/svineet/monte-carlo-algo-analyser/blob/master/Monte%20Carlo%20Algorithm%20Complexity%20Analyser.ipynb">Notebook Link</a></p><p>I’ve made a starter notebook for this system, and it seems to work well on vanilla binary search, giving a very pretty logarithmic graph when run with huge number of samples.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/412/1*XvYx0j2iR-l85OZFHosDEQ.png" /><figcaption>muh logarithms</figcaption></figure><p><strong>Update! </strong><a href="https://medium.com/@svineet/analysing-the-covid-19-binary-search-testing-algorithm-via-monte-carlo-method-part-2-3ee0ae511954"><strong>Part 2 is out!</strong></a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=951049cdb212" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[What is a neural net thinking about? (an experiment)]]></title>
            <link>https://svineet.medium.com/what-is-a-neural-net-thinking-about-an-experiment-dd2186522cdd?source=rss-fd67c612c31d------2</link>
            <guid isPermaLink="false">https://medium.com/p/dd2186522cdd</guid>
            <category><![CDATA[deep-learning]]></category>
            <category><![CDATA[machine-learning]]></category>
            <dc:creator><![CDATA[Vineet]]></dc:creator>
            <pubDate>Wed, 22 May 2019 22:09:18 GMT</pubDate>
            <atom:updated>2019-05-22T22:09:18.203Z</atom:updated>
            <content:encoded><![CDATA[<p>So lately I’ve been feeling interest towards deep learning and so I started doing Stanford’s CS231n and it’s assignments.</p><p>On Assignment 1, you have to implement a fully connected neural network of two layers, and train it on CIFAR-10. Well that’s not very fun because it doesn’t work very well on CIFAR-10, you get like 40% accuracy. That’s no fun.</p><p>So I searched for an easier problem, a gateway drug let’s say. And then I found MNIST’s dataset on Kaggle. Handwritten digit recognition using deep learning! And you can actually get 90+% accuracy quite easily! Best drug.</p><p>The problem goes like this. You have a 28 by 28 image of a handwritten digit and you have to detect what digit that is. So I deployed my two layer net on it and after tuning it got to 91% accuracy on Kaggle’s test dataset.</p><h3>But what is it thinking about?</h3><p>Natural question to ask. Does it now have a notion of what a ‘1’ or a ‘0’ looks like? I’d like to see that notion. So what’s the image that will get the least loss for correct label as 1?</p><p>Here’s what it thinks the best 1 in the world is.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/472/1*S4NHWG0C72ixa6xFnRm4IA.png" /><figcaption>MY NEURAL NET’S WET DREAM OF DIGIT 1</figcaption></figure><p>Yup. That’s it. Doesn’t look much like a one to me personally but hey who am I to judge? :P</p><p>Here’s a 5 for you. NSFW.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/478/1*jTziIWTm9xce4-d4oCb5Nw.png" /><figcaption>MY NEURAL NET’S WET DREAM OF DIGIT 5</figcaption></figure><p>OK this is getting disturbing. Let me now tell you how I generated these images.</p><h3>Generating the best image</h3><p>We train networks through backpropagation. That means we calculate the analytic gradients of a loss function and backpropagate those using the chain rule of multivariate calculus. Backpropagation through a fully connected layer will give three gradients. dW, db and dx, that is the gradient wrt the weight matrix, then the bias and finally the input.</p><p>We get the gradient wrt to the input too! So during gradient descent instead of changing the weights, what if we change the x instead? Loss will still decrease obviously.</p><p>So here’s what I did. I took a fully trained two layer neural net. It had 91% accuracy on Kaggle. Now I will initialize an input image of all zeros or maybe some random initialization.</p><p>Now if I want to make it look like a 9 then I will calculate the loss function on that input image as if it was a 9. Then once I backprop and get dx we just gradient descent. That is how the images above are generated. So these images are the ones that will produce the least loss when given label say 1 and 5.</p><p>So if one day you took these images and gave it to my net, it would say with utmost certainty that it is a 5 and it is the most beautiful 5 in the world it has ever seen.</p><h3>Why the funky images?</h3><p>I don’t know. Please tell me. This is my first neural network.</p><p>Also does the algorithm I carried out to generate images have a name already? I bet it does given how many people are researching this stuff. Please tell me about it!</p><p>So that was my experiment. An experiment that has no conclusion, sadly.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=dd2186522cdd" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[How to win Google Code-in]]></title>
            <link>https://svineet.medium.com/how-to-win-google-code-in-ef1e173b2575?source=rss-fd67c612c31d------2</link>
            <guid isPermaLink="false">https://medium.com/p/ef1e173b2575</guid>
            <category><![CDATA[open-source]]></category>
            <category><![CDATA[google-code-in]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Vineet]]></dc:creator>
            <pubDate>Thu, 21 Feb 2019 07:20:06 GMT</pubDate>
            <atom:updated>2019-02-21T07:20:48.969Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*D6NnUiquEcdzXYLBgV9DzA.png" /></figure><p>This is a copy of a Quora answer I wrote to “How many tasks should be completed to win Google Code-in?”</p><p>Hello.</p><p>I was a Grand Prize Winner back in 2015, so I think I can help you with this.</p><p>The question by itself is flawed, but I will try to answer what you were getting at. I assume you wanted to know “How to win Google Code-in”.</p><p>The judging mechanism in GCI is a very subjective mechanism. Even if you did more tasks than someone else, there is a good chance you might not win.</p><p>In general there are some principles that seem to hold, in my 3 years of GCI experience</p><p><strong>Code tasks are more important</strong> <strong>than other tasks</strong>, given you’re actually contributing to a project and not doing a “learning task”. In recent years I’ve noticed there are some tasks that goes like “Learn node.js and make a chat server” or “Implement a unigram tagger”. These tasks might not involved actual contribution to a project but are intended to make you capable enough to eventually be able to contribute fully to the projects. These tasks don’t really hold much weight in my opinion. They’re like better versions of beginner tasks.</p><p><strong>Mentors should remember you and your contributions. </strong>The best way to ensure this is to truly do good work. All other prescriptions will fail. Your work should make an impact to the community, or at least make more impact than your competitors.</p><p><strong>Quality is greater than quantity, but only to an extent.</strong></p><p>You will often see this phrase thrown about in IRC logs and mailing lists discussing GCI: “Quality &gt; Quantity”. That is true, but it is not complete. It should say, “Quality &gt; Quantity but only when you quality is clearly visible”</p><p>First we must understand what is meant by quality here. From my observations it seems to be a mix of something like code quality, community behaviour (how chatty you are, how helpful, can you really collaborate smoothly?, etc), impact of your work, whether you are willing to contribute long term or not, etc. This is a great ideal to keep and Google has done a very good job of emphasising this. This encourages proper contribution and is an attempt to prevent “over-gamification” of GCI.</p><p>However, it is difficult to weight these factors properly and mentors often have different perspectives of these factors. To one mentor, impact might mean more than long term dedication. To some, code quality is more important. After averaging these out, eventually we are left with another random weighting of these factors. We can know that all of these matter, more or less, but we cannot know what matter more. Sometimes mentors even struggle to distinguish between two participants qualitatively, because they’re contributing to different parts of the organization. This is what happened with me once, and finally quantity has to be taken into account. <strong>Quantity is the tie breaker when it is hard to perceive quality</strong>.</p><p>So what is a good strategy. Alas, it’s to contribute in good will and have fun while doing it. Did you expect a prescription? “Do this, do that, and you’ll win”? Prescriptions are not strong enough for these things :)</p><p>Did you expect a mathematical checkmate? I did too. Turns out ethics works. :)</p><p>Anyway, play the game for the fun of it. Don’t aim to win and struggle for it endlessly. Life is long.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ef1e173b2575" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Wonders of Breadth First Search]]></title>
            <link>https://svineet.medium.com/wonders-of-breadth-first-search-789b89f3061b?source=rss-fd67c612c31d------2</link>
            <guid isPermaLink="false">https://medium.com/p/789b89f3061b</guid>
            <dc:creator><![CDATA[Vineet]]></dc:creator>
            <pubDate>Sun, 13 Jul 2014 17:58:58 GMT</pubDate>
            <atom:updated>2014-07-13T17:58:58.350Z</atom:updated>
            <content:encoded><![CDATA[<h4>Breadth First Search, you beauty!</h4><p>I was watching the MIT OCW Video about Breadth First Search, with Erik Demaine teaching. I have to say, this guy is awesome.</p><p>So what is Breadth First Search(BFS)? It is a graph search algorithm. A graph, is what you say? A graph is, well, like a map. There are vertices, interconnected with each other (or maybe alone) by “edges”.</p><p>Think of it like a city. There are intersections of roads. And the length of road between each intersection varies (Obviously). The intersections are vertices and the roads are edges. The lengths are called weights, but its not really related to BFS as we will know soon.</p><p>What does BFS do exactly? BFS is a graph search algorithm. What it does is, go through all of the graph vertices exploring all paths possible. Yes. That is it. But this is in fact a very useful thing.</p><p>For example BFS can be used to solve a Rubik’s Cube theoretically at least, but it can surely solve a Pocket Cube (2x2) fairly fast using a normal computer. BFS is also used by web crawlers (Google uses a bit modified BFS, if Erik Demaine is to be believed). BFS can also solve shortest path problems in some cases.</p><p>When I’m ending this post, I’ll also throw in a BFS example about the game we call “Chopsticks”. Read on!</p><p>But first. How can I represent a graph as a data stucture? Now there are two data structures usually used, Adjacency lists and Adjacency Matrices. List is what I find cool. An Adjacency list is basically a dict (HashMap) which has vertices as keys and values are lists of where the vertex leads to. Like if I have a adj. list:</p><pre>adj = {<br>&quot;A&quot;: [&quot;B&quot;, &quot;C&quot;], <br>&quot;B&quot;: [&quot;C&quot;],<br>&quot;C&quot;: []<br>}</pre><p>Then vertex A can lead to Band C, vertex B can lead to C, and so on.</p><p>Usually we have to make an adjacency list out of input data, like a maze is given, and we have to make an adjacency list out of it and then run BFS or any graph related algorithm.Now lets get into the actual algorithm.</p><p>Here is the basic outline of what BFS does, I’ll throw in a code example afterwards.</p><ol><li>Get hold of a starting point. Usually we know which vertex to start the journey from. Let’s call it A. We can reach this vertex in 0 steps.</li><li>Now let’s make a list of where we can go from this vertex. We can go from A to B and A to C, says the adjacency list. Good then. We can reach these vertices in 1 step. Now next iterations I’ll try going to B and then C. Let’s add them to a list called “next”.</li><li>Now I will loop through “next” and look at each vertex. next[0] is “B”. Where can I go from “B”? adj list says “C”. Let’s pay “C” a visit next iteration, add it to a list “next2”. Note here we did not check if we have visited it before or it is in next already or not. Because we want to explore all <strong>paths</strong>, not only all <strong>vertices</strong>.</li><li>next[1] is “C”. And the graph ends at “C”. No where to go, nothing to add to “next2”.</li><li>Let’s see what we have in next2. These vertices can be reached in 3 steps as well. “C” again ends the search. So we are done.</li></ol><p>That is the basic outline. We list the places we go next time, and then visit them and keep doing this until we are out of places to go. It’s called Breadth first because it traverses the breadth of the graph as opposed to it’s close sibling DFS(depth).</p><p>Now this is here a problem. There are two types of graphs. Cyclic and Acyclic. In cyclic graphs, there are cycles, i.e loops, for example this adj list: {“A”: “B”, “B”: “A”}. If I follow BFS, you obviously see that it’ll never end the search. So no BFS in cyclic graphs. Not yet. But there is some black magic too. If we count, for each vertex, how many edges are in bound to it, called the “indegree”, then each time we visit it we can update the number of times we have been there and if we have already visited it, scrap it, don’t visit again. Nice.</p><p>Now in Acyclic graphs, BFS without any modifications can give you shortest paths to the vertices. In the above outline, the number of iterations you needed to go to a vertice is the shortest path length. Great! (obviously store the minimum, this will work for cyclic too! But a better way is just end the search when you first hit the vertex. Guess why.)</p><p>Code to solve a maze(hardcoded):</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d8d3703bba5499b3a56b2974c93e90ed/href">https://medium.com/media/d8d3703bba5499b3a56b2974c93e90ed/href</a></iframe><p>Gives output as 4. Perfect.</p><p>Chopsticks solving using BFS next time. Stay tuned.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=789b89f3061b" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>