DSA IN THE WILD - PART 1

View on LinkedIn


What’s the use of all this π™‡π™šπ™šπ™©π™˜π™€π™™π™š?


I often find myself facing this question, and so do a lot of my developer friends. And most of the time, I believe this frustration is valid. Swapping integers in an array smartly to find a certain subarray following a certain condition will not find any practical application in the real world, but unlike this, understanding the fundamentals of data structures like stacks, linked lists, queues help you π™™π™šπ™¨π™žπ™œπ™£ solutions (for instance a process queue in you OS, or a function call stack for a program) and these are used to build algorithms that often 𝒏𝒐𝒕 than do require any witty manipulation of an integer array but instead only need you to understand the constraints to the problem at hand and work to arrive at solutions you can call β€œoptimal” (I say this because it’s only optimal until someone else finds a better one). Look for instance at the many scheduling algorithms for processes in OS, or routing algorithms in a network/internet, or the congestion control protocols for TCP. Look, for instance at a blockchain, that will take into account some cryptography, some concepts of P2P networks, and explore those things in detail, where each functionality is works using a certain algorithm, and scholars work to find more efficient algorithms.


Now, not to say that all leetcode is impractical (I do not say that). You can find famous problems like β€œLRU cache” or β€œTwo Sum” and concepts like binary search, backtracking, dynamic programming, and algorithms on graphs, are practically applied in some famous tools, but we do not know about this because these things are not highlighted as much, πŸ„°πŸ„±πŸ…‚πŸ…ƒπŸ…πŸ„°πŸ„²πŸ…ƒπŸ„΄πŸ„³ πŸ„΅πŸ…πŸ„ΎπŸ„Ό πŸ…„πŸ…‚, to say.


One such case I want to highlight is the use of dynamic programming to find the β€œdiff” in two files, as applied in git diff. I tried out making a version of mine and am satisfied with the output ( 𝗰𝗡𝗲𝗰𝗸 π—Όπ˜‚π˜ π—΄π—Άπ˜π—΅π˜‚π—― 𝗿𝗲𝗽𝗼 ), ignoring the horrible space complexity and impractical-ness (in cases of large files) for now.

After some initial research I had found out there have been two proposed algorithms Hunt and McIlroy (which was used for git diff previously) and Myers algorithm (more efficient, is used now). My implementation is based on the idea borrowed from Hunt and Mcllroy to use LCS, but I haven’t seen that algorithm as of now, pretty sure mine is worse.


I will and encourage you as well to look at them if you want to see a practical use case of DSA. also enjoy this dalle generated image for "dsa in the wild".