Algorithmic Problems & their applications in S/W development

Hi Medium Readers,

Img Courtesy — Google

I’ll be presenting some of my view points on Competitive Programming and its impact on professional software development.

“Competitive Programming Vs Development” → This has been a debated topic for a long time amongst college grads and software professionals.

A lot of guys (including Kalpit Veerwal) have bashed CP. However, there are some other guys like Aman Goel who strongly support the sport of programming. I am not a CS grad. However, I have been a fan of competitive programming mainly because it sharpens the mind and increases the thinking capacity.

There is this statement that has been going around → “You will probably never use these algorithms (asked in CP) while working on a project in a corporate setting”. I however strongly disagree with this statement. I belong to the Semiconductors domain and algorithms are aggressively used in EDA firms.

AFAIK, Algorithms are used heavily in professional software development in the following areas →

1. EDA Companies. (Synopsys, Cadence, Mentor Graphics etc)
2. Quants/Hedge Funds/ Asset Management Firms to generate alphas. (Bridgewater Associates, Renaissance Technologies, Two Sigma, Citadel, Tower Research, World Quant, D.E Shaw etc)
3. Research divisions of Organisations (like IBM, Apple,NVIDIA, Samsung, Google, Intel etc)
4. Artificial Intelligence firms (DeepMind etc).
5. Startups like Code Nation etc. for their Compiler Design Projects.

(There might be other areas that I am unaware of).

The semiconductors stream is heavily dependent on “EDA Tools” (EDA → Electronic Design Automation). And all these tools are developed using C++ or Java. I’ll cite an example to give better clarity.

Semiconductor chips are designed using software suites/tools provided by Cadence, Synopsys and Mentor Graphics majorly. These are EDA companies and their products are these EDA tools. I am a SoC Design Engineer and my work is dependant on a software tool named “Innovus” from Cadence and “ICC2” from Synopsys. Innovus and ICC2 have the following engines built inside them namely (but not limited to)→

1. Placement & Optimisation Engine.
2. DRC Engine.
3. Extraction Engine.
4. CTS & Optimisation Engine.
5. Legalisation Engine.
6. Routing & Optimisation Engine.
7. Timing Engine.
8. Power Analysis Engine.
9. Verification Engines
10. Search Engines etc.

These “Engines” are nothing but sub-routines written in C++ that target very specific tasks and building these tools require advanced knowledge of discrete mathematics & algorithms (specifically graph algorithms). These tools are mainly developed by CAD Researchers (most of them are PhD’s). This is where competitive programming helps. For eg. CodeForces DIV-1 problems are so hard that they can be used for building a full fledged EDA tool-chain. It’s unfortunate that most CS grads are not interested in developing EDA tools (mostly because of lack of interest or awareness) and are more keen on working for FAANG companies. Once they land in these firms they are given tasks that do not require algorithms and eventually they loose interest in knowing more about algorithms.

Conclusions → Algorithms are definitely helpful for anyone who is interested in it and it is used in professional software development. CS grads who are interested in EDA Tool development are warmly welcomed at these EDA companies.

Img Courtesy — Google

A detailed application of a competitive programming problem in a VLSI-EDA setting is presented here →

sethupathib/final_layout_generator

— Sethupathi Balakrishnan.