Lessons from the Approximations to the Travelling Salesman Problem[Math Mondays]
The shared video is a little long, but worth it.
To learn more about the newsletter, check our detailed About Page + FAQs
To help me understand you better, please fill out this anonymous, 2-min survey. If you liked this post, make sure you hit the heart icon in this email.
Recommend this publication to Substack over here
I have something very special to start off your Mondays,
The Travelling Salesman Problem is one of the legendary problems in Computer Science. As a developer, knowing about it will boost your repertoire considerably. The video I’m sharing with you below will cover the TSP, along with some of the techniques being used to come up with solutions for it. These techniques are pretty advanced so I will do separate posts for them all. For now, as you watch the video, I want you to take note of the following highlights.
Key Highlights
Look at the heuristics- Notice how when the problem is very hard (as in this case), the task immediately switches to finding ways to approximate solutions/lower bounds. This is extremely common in computing. Too many developers beat their heads against the wall trying to gain an optimal solution. As a general rule of thumb- a good solution that can be deployed quickly will beat an extremely complex optimal solution. Build something good and ship it. Improve iteratively based on the requirements (both the ones faced by the users and the ones you anticipate by looking at the results or knowing about the domain).
Random Swapping, Simulated Annealing, and Evolution- To those of you that watch the part about random swapping of created candidate solutions, I want you to think of evolutionary algorithms. One of the most interesting parallels b/w the two is that in evolutionary algorithms, introducing mutations that reduce a solution’s fitness in the short term can be amazing in the long term. Sometimes random mutations might even lead to beastly offspring. A lot of you will work on problems where you’re working on a heuristic instead of a provably optimal solution. Introducing a bit of mutation into your solutions might just be the winning play. If any of you want some input on how it could be done, you know how to reach out to me.
Stack solutions on top of each other- When most of us are taught computer science or take these online courses/boot camps, the ideas and theories we’re taught are often shown to us in an insular manner. My class on finite state machines taught me about them and the Chomsky Normal Form. My graph theory class taught me about graphs. Combining the two was never really touched. As you start to look at the valuable solutions that were implemented in the world, you will see they combine ideas from multiple domains (take this Leetcode solution for example). Cultivate this skill, and you will be a demon. As you learn about a new idea, take some time to really appreciate the nuances of the problems this idea solves. For more details, check out my recommended way of learning Math/Computer Science theory.
Think about the domain you’re currently working in/want to transition into. What kinds of simplifications/heuristics are being implemented in it to come up with the solutions? Take some time to really explore this. If you want to master that domain, understanding this is a must.
I created Technology Interviews Made Simple using new techniques discovered through tutoring multiple people into top tech firms. The newsletter is designed to help you succeed, saving you from hours wasted on the Leetcode grind. I have a 100% satisfaction policy, so you can try it out at no risk to you. You can read the FAQs and find out more here. Use the button below to get 20% off for upto a whole year.
Before proceeding, if you have enjoyed this post so far, please make sure you like it (the little heart button in the email/post). I also have a special request for you.
***Special Request***
This newsletter has received a lot of love. If you haven’t already, I would really appreciate it if you could take 5 seconds to let Substack know that they should feature this publication on their pages. This will allow more people to see the newsletter.
There is a simple form in Substack that you can fill up for it. Here it is. Thank you.
https://docs.google.com/forms/d/e/1FAIpQLScs-yyToUvWUXIUuIfxz17dmZfzpNp5g7Gw7JUgzbFEhSxsvw/viewform
To get your Substack URL, follow the following steps-
Open - https://substack.com/
If you haven’t already, log in with your email.
In the top right corner, you will see your icon. Click on it. You will see the drop-down. Click on your name/profile. That will show you the link.
You will be redirected to your URL. Please put that in to the survey. Appreciate your help.
In the comments below, share what topic you want to focus on. I’d be interested in learning and will cover them. To learn more about the newsletter, check our detailed About Page + FAQs
If you liked this post, make sure you fill out this survey. It’s anonymous and will take 2 minutes of your time. It will help me understand you better, allowing for better content.
https://forms.gle/XfTXSjnC8W2wR9qT9
I see you living the dream.
Go kill all and Stay Woke,
Devansh <3
To make sure you get the most out of Math Mondays, make sure you’re checking in the rest of the days as well. Leverage all the techniques I have discovered through my successful tutoring to easily succeed in your interviews and save your time and energy by joining the premium subscribers down below. Get a discount (for a whole year) using the button below
Reach out to me on:
Instagram: https://www.instagram.com/iseethings404/
Message me on Twitter: https://twitter.com/Machine01776819
My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/
My content:
Read my articles: https://rb.gy/zn1aiu
My YouTube: https://rb.gy/88iwdd
Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75