<?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 Yash Gaherwar on Medium]]></title>
        <description><![CDATA[Stories by Yash Gaherwar on Medium]]></description>
        <link>https://medium.com/@yashgaherwar2002?source=rss-7dc54494f608------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*w35vQM18nAnblg4RlMYLug.jpeg</url>
            <title>Stories by Yash Gaherwar on Medium</title>
            <link>https://medium.com/@yashgaherwar2002?source=rss-7dc54494f608------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sun, 22 Nov 2026 23:17:07 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@yashgaherwar2002/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[Building Resilient APIs with API Gateway and AWS WAF]]></title>
            <link>https://medium.com/@yashgaherwar2002/building-resilient-apis-with-api-gateway-and-aws-waf-fc68ead6cd8e?source=rss-7dc54494f608------2</link>
            <guid isPermaLink="false">https://medium.com/p/fc68ead6cd8e</guid>
            <category><![CDATA[api-development]]></category>
            <category><![CDATA[api-gateway]]></category>
            <category><![CDATA[aws-waf]]></category>
            <category><![CDATA[software-development]]></category>
            <category><![CDATA[aws]]></category>
            <dc:creator><![CDATA[Yash Gaherwar]]></dc:creator>
            <pubDate>Thu, 15 Aug 2024 18:35:45 GMT</pubDate>
            <atom:updated>2024-08-15T18:35:45.762Z</atom:updated>
            <content:encoded><![CDATA[<p>In this article we will be discussing about how we can safeguard our APIs by integrating Amazon API Gateway with AWS Web Application Firewall (WAF). As we know that modern applications rely heavily on APIs for inter-service data exchange and interaction. Nevertheless, APIs tend to get targeted by threats such as SQL injections, cross-site scripting or distributed denial of service — DDOS attacks. So lets deep dive into this amazing topic.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/850/1*NpCBkHPB_xGTRahtrPQlwA.png" /></figure><p>In today’s world of API driven development, the security is one of the major concern in any application development. Some of the malicious attacks including SQL injection, cross-site scripting (XSS), and denial of service (DOS) efforts are increasingly being directed towards APIs. To overcome that we have Amazon API Gateway and AWS Web Application Firewall integration which allows developers to create strong defence against these attacks while maintaining scalability and seamless performance.</p><h4><strong>How AWS WAF and API Gateway ensure API safety?</strong></h4><p>AWS WAF and Amazon API Gateway work together to ensure API safety by providing multiple layers of protection against various threats.</p><blockquote><strong>1) Rate limitation and Throttling:-</strong><br>The built in rate limitation and throttling provided by API Gateway helps guard against abuses like brute-force assaults and flooding the API with request volume i.e. DDoS. Setting limitations on the quantity of requests per second ans enables us to stop questionable activity before it has an impact on our application.</blockquote><blockquote><strong>2) IP Blocking:- </strong><br>Traffic originating from particular IP addresses, ranges or geographic regions that are recognized as malicious activity sources can be blocked by AWS WAF. This guarantees that only safe areas and customers are able to use the API.</blockquote><blockquote><strong>3) Custom Filtering:-</strong><br>WAF rules that block traffic according to particular patterns, behaviours or circumstances can be written by developers. This reduces vulnerability to attacks designed to take advantage of certain flaws by enabling fine grained control over the requests that are permitted to get through to the API.</blockquote><blockquote><strong>4) WAF for DDOS Protection:-</strong><br>APIs are shielded from attempts to overwhelm the service by distributed DDOS assaults by utilizing WAF in conjunction with AWS Shield. More advanced defences and extensive assault monitoring are added by Shield Advanced. AWS WAF protects APIs against typical online threats such as cross site request forgery, SQL injection, and cross site scripting. Before harmful traffic reaches the API, WAF inspects incoming requests and applies managed or custom rules to stop it. To find attack patterns, it enables in-depth examination of HTTP headers, query strings and URIs.</blockquote><p><em>When combined, AWS WAF and API Gateway offer a strong security framework that inspects, filters, and manages API access while protecting it from malicious traffic and a range of web-based threats.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/208/1*TQLR7f9m3mDU1c5fnVoegg.png" /></figure><h4>Steps involved in securing API using AWS services (Flow):-</h4><ol><li><strong>Client Request:-</strong> A client sends a request to the API Gateway endpoint eg:- GET/POST request.</li><li><strong>AWS WAF checks:-</strong> AWS WAF checks the request against pre-configured security criteria before it reaches the API Gateway.</li></ol><blockquote>a) Stop Malicious Traffic: WAF stops malicious traffic and records the attempt if the request includes malicious patterns, such as SQL injection.</blockquote><blockquote>b) Permit Lawful Traffic: The request is sent to the API Gateway after passing inspection.</blockquote><p><strong>3. API Gateway handling:-</strong> API Gateway uses throttling, rate limitation, and any other customizations such authorization checks by using AWS Cognito.</p><p><strong>4. Backend Service Processing:-</strong> AWS Lambda and other backend services handle requests, communicate with other AWS services like DynamoDB and then provide a response.</p><p><strong>5. Response Back to Client:- </strong>The data is safely delivered to the client by means of the API Gateway.</p><p><strong>6. CloudWatch Monitoring:-</strong> For security and performance monitoring, logs and metrics from backend services, API Gateway and WAF are continuously tracked in CloudWatch.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/499/1*olRxh-4mQP0FNe8M6TkVJQ.png" /><figcaption><strong>Flow Diagram for how API’s where secured using AWS Services</strong></figcaption></figure><p>The above flow ensures that:-</p><blockquote><strong>1) WAF</strong> filters out malicious requests and applies security rules.</blockquote><blockquote><strong>2) API Gateway</strong> manages API traffic and enforces rate limiting.</blockquote><blockquote><strong>3) CloudWatch</strong> provides insights into security and performance metrics for continuous monitoring.</blockquote><p>Conclusion:-</p><p>From hereby we can conclude that in today’s fast paced development world where there are frequently the target of a wide range of threats, API security is essential. We can create a reliable and safe API infrastructure that guarantees scalability and performance while blocking fraudulent traffic by utilizing AWS WAF and Amazon API Gateway. APIs are safe from outside threats while meeting the needs of authentic users with AWS WAF’s real-time protection against popular online vulnerabilities like SQL injection and cross-site scripting and API Gateway’s enforcement of rate limiting and authentication. These security features will grow with our architecture as our APIs do, letting you concentrate on innovation while still keeping a solid security posture.</p><p><strong><em>Hope this blog will be helpful in understanding the importance of securities of APIs and application from the outside threats and attacks. AWS provides many such several features for the safe and secure development. Keep learning and keep growing!!!</em></strong></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=fc68ead6cd8e" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Adversarial Machine Learning -Attacks & Prevention's]]></title>
            <link>https://medium.com/@yashgaherwar2002/adversarial-machine-learning-attacks-preventions-640c5ffc2404?source=rss-7dc54494f608------2</link>
            <guid isPermaLink="false">https://medium.com/p/640c5ffc2404</guid>
            <category><![CDATA[prevention]]></category>
            <category><![CDATA[adversarial-attack]]></category>
            <category><![CDATA[artificial-intelligence]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[generative-adversarial]]></category>
            <dc:creator><![CDATA[Yash Gaherwar]]></dc:creator>
            <pubDate>Fri, 13 Oct 2023 15:27:07 GMT</pubDate>
            <atom:updated>2023-11-20T13:46:19.477Z</atom:updated>
            <content:encoded><![CDATA[<p>Authors:- <a href="https://medium.com/@yashgaherwar2002">Yash Gaherwar</a>, <a href="https://medium.com/@shreyansh.srivastava20">Shreyansh Srivastava</a>, <a href="https://medium.com/@akash.sinha20">Akash Sinha</a>, <a href="https://medium.com/@vishal.sirvi20">Vishal Sirvi</a></p><p>In this article we are focusing on the understanding of the topic <strong>“Adversarial Machine Learning”. </strong>We are discussing about the AML, whitebox &amp; blackbox attack, working of Adversarial attacks, methods to prevent it and etc. Lets start the journey of AML.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/612/0*I6H_oawH0Ub1v9CZ" /></figure><p><strong>What is Adversarial Machine Learning ?</strong></p><p>The practice of using malicious input to deceive or lead a machine learning model is known as Adversarial Machine Learning(AML). Contrary to popular belief, the most typical use of adversarial machine learning is to launch an attack or bring about a malfunction in a machine learning system. The same attack instance can easily be modified to run on many models of various data sets or architectural designs.</p><p>Large data sets related to the topic being learnt about are used to train machine learning models. For instance, if an automobile manufacturer wanted to train an automated vehicle to recognize a stop sign, it may send hundreds of images of stop signs into a machine learning algorithm. When deployed in either practice or production, a malicious attack like adversarial machine learning could be used against that machine learning algorithm, exploiting the input data (in this case, images of stop signs) to misinterpret that data and causing the overall system to incorrectly identify stop signs.</p><p>The majority of adversarial attacks essentially “fool” the machine learning system by aiming to reduce the model’s performance on particular tasks. The area of adversarial machine learning investigates a class of attacks meant to degrade a model’s performance on particular tasks.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/720/0*iGzOt4oCR74nMNgu" /><figcaption><strong>Fig 1. Explaining and harnessing adversarial example</strong></figcaption></figure><blockquote>In Fig 1. an image that was previously identified as a panda has a carefully designed set of adversarial “noise” applied to it (i.e., changes to the pixel values) that results in the new image being identified as a gibbon, even though the image continues to seem as a panda to human viewers. While this is intriguing and there are many real-world uses for picture and video subversion, the scenario is unquestionably different from what we face in information security.</blockquote><p><strong>Whitebox vs Blackbox attack in AML:</strong></p><p>Adversarial machine learning can be considered as either a white or black box attack. A white box attack in adversarial machine learning occurs when we are fully aware of the deployed model, including its inputs, architecture, and particular internals like weights or coefficient values. This typically indicates that we have access to the model’s internal gradients. However, this is not necessarily required for evasion. Some researchers additionally include knowing the entire training data set in white box attacks. In contrast, a black box attack is when we just have access to the model inputs and can ask an oracle for the output labels or confidence levels.</p><blockquote>In adversarial ML, evasion can be conceptualized as gradient climb rather than gradient descent, where the goal is to increase the loss for one or more samples rather than decrease it. Adversarial machine learning (ML) is a subclass of max-min problems. While minimizing the changes we make to the sample (sometimes referred to as adversarial perturbations), we want to maximize the error for one or more samples.</blockquote><p>As we may use the internal model gradients to more correctly complete the gradient ascending process in a white box method rather than a black box approach, white box attacks are typically more effective than black box attacks at this task. As a result, figuring out the smallest adjustment required to produce an adversarial sample is quicker and more effective.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/305/0*8YyJvoUKPQDjH-my" /></figure><p><strong>How Adversarial attack works :-</strong></p><p>Machine learning systems are vulnerable to a wide range of various adversarial assaults. Many of them employ classic machine learning models like linear regression and support vector machines (SVM), as well as deep learning systems. The majority of adversarial assaults essentially fool the machine learning system by aiming to reduce classifier performance on particular tasks. The area of adversarial machine learning investigates a class of assaults meant to degrade classifier performance on particular tasks. The following categories can be used to classify adversarial attacks.</p><blockquote>1. Model Extraction Attack</blockquote><blockquote>2. Poisoning Attack</blockquote><blockquote>3. Evasion Attack</blockquote><h4>1. Model Extraction Attack</h4><blockquote>An attacker exploring a black box machine learning system to either reconstruct the model or recover the data it was built on is known as model stealing or model extraction. This is especially important if the model itself or the training data are private and sensitive information.</blockquote><blockquote>An adversary could utilize a stock market prediction model stolen through a model extraction attack to their own financial advantage.</blockquote><h4><strong>2. Poisoning Attack</strong></h4><blockquote>By manipulating the training data or its labels, the attacker can make the model perform poorly during deployment. As a result, poisoning can be thought of as a hostile contamination of training data. An attacker may contaminate the data by injecting malicious samples during operation, which would then disrupt or affect re-training because ML systems can be re-trained using data acquired during operation.</blockquote><h4>3. Evasion Attack</h4><blockquote>The most common and most studied types of attacks are evasion attacks. During deployment, the attacker tampers with the data to trick classifiers that have already been trained. They are the most common sorts of attacks employed in intrusion and malware scenarios since they are carried out during the deployment phase. The content of malware or spam emails is frequently obscured by attackers in an effort to avoid detection. Since this classification does not directly affect the training data, samples are altered to avoid detection. Spoofing attacks against biometric verification systems are an example of evasion.</blockquote><h4><strong>Different Adversarial attack methods:</strong></h4><ol><li><strong>Limited-memory BFGS (L-BFGS):</strong></li></ol><p>Limited-memory BFGS (L-BFGS) is an optimization algorithm used to find the minimum of a function. It is an extension of the Broyden Fletcher Goldfarb Shanno (BFGS) algorithm that addresses memory efficiency for large-scale optimization problems. This algorithm is designed to handle large datasets efficiently. This optimization algorithm is used in adversarial attacks on machine learning models. L-BFGS is a smart way to make small changes to fool a computer program. It does this by estimating how to change the data it is given in a way that the program gets confused, but it does this in a way that uses less computer memory and is faster.</p><p><strong>2. FastGradient Sign method (FGSM):</strong></p><p>The Fast Gradient Sign Method (FGSM) is a quick and effective adversarial attack technique. It calculates the direction in which the model’s prediction will change the most and modifies the input data accordingly. This modification is done by adding a small amount of noise (perturbation) to each feature of the input data, aiming to mislead the model’s predictions. FGSM is simple and powerful, making it a popular choice for adversarial attacks.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/700/0*GdBC907yHpVZ9_QC" /><figcaption><strong>Fig 2. Adversarial attacks with FGSM</strong></figcaption></figure><p><strong>3. Jacobian-based Saliency Map Attack (JSMA):</strong></p><p>Jacobian-based Saliency Map Attack (JSMA) method identifies and modifies specific features in the input data to deceive a machine learning model. It calculates the gradient (Jacobian) of the model’s output with respect to the input features, identifying the most influential features. JSMA then alters these features in a way that maximizes the model’s prediction error, aiming to create adversarial examples that mislead the model while keeping the changes small.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/696/0*M4ds6yH_2_5cXGO0" /><figcaption><strong>Fig 3. Illustration of JSMA algorithm</strong></figcaption></figure><p><strong>4. Deepfool Attack:</strong></p><p>The DeepFool attack method misleads a deep learning model by iteratively finding the closest decision boundary for a given input. It computes the gradient of the model’s output with respect to the input and adjusts the input in the direction of decreasing confidence in the current predicted class. By iteratively applying small perturbations in this direction, it guides the input towards a different class boundary, ultimately creating an adversarial example that’s misclassified by the model. The attack aims to find the minimal perturbation needed to achieve this misclassification.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*mKNd8z86_kgCkXyG" /><figcaption><strong>Fig 4. Illustration of Deepfool Attack</strong></figcaption></figure><p><strong>5. Carlini &amp; Wagner Attack (C&amp;W):</strong></p><p>The Carlini &amp; Wagner (C&amp;W) attack is a sophisticated adversarial attack method designed to find minimal perturbations that can fool machine learning models. It formulates the adversarial perturbation as an optimization problem, seeking to minimize a combined objective function that balances perturbation size and misclassification. C&amp;W employs a powerful optimization algorithm to find the smallest perturbation that leads to a change in the model’s prediction while ensuring it remains within a certain perturbation constraint. This attack is effective against a variety of models and is known for generating strong adversarial examples.</p><p><strong>6. Generative Adversarial Networks (GAN):</strong></p><p>Generative Adversarial Networks (GANs) are not typically used as adversarial attack methods. Instead, GANs are a type of machine learning architecture consisting of two neural networks, a generator and a discriminator, that are trained simultaneously.</p><p>In a GAN, the generator creates data (e.g., images) to try and mimic real data, while the discriminator’s role is to distinguish between real and generated data. The two networks engage in a competitive process, with the generator aiming to create data that is increasingly indistinguishable from real data, and the discriminator getting better at telling real from generated data.</p><p>The adversarial aspect of GANs is an internal competition between the generator and the discriminator, resulting in the generation of high-quality, realistic data.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Qzi69hCmetAT3pjv4iPOLg.jpeg" /><figcaption>Fig 5. Architecture of Generative Adversarial Networks</figcaption></figure><p>7. Zeroth-order Optimization (ZOO) adversarial attack method doesn’t rely on direct access to a model’s gradients or internal information. Instead, it manipulates the model by querying it for predictions and using the responses to craft adversarial examples. ZOO iteratively adjusts the input features to minimize the model’s confidence in predicting the correct class. It strategically samples and perturbs the input, learning from model predictions, to eventually generate adversarial examples that mislead the model while having limited access to gradient or model details. This approach makes ZOO more versatile and applicable to various models.</p><h4><strong>Comparative Analysis of different Adversarial attack methods</strong></h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/711/1*7yYAgNRj8wMV5px0tHBkqw.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/716/1*P_Z5EdTqNk6wcm1pvRMUww.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/716/1*5Qbd8uJnHKoA_mUYNXQ-5g.png" /></figure><h4><strong>Real life example where these attacks happened</strong></h4><p><strong>1. Adversarial Attacks Targeting Computer Vision Systems:</strong></p><p>Much of the research in adversarial machine learning revolves around developing algorithms for manipulating visual data. To illustrate this, consider the ‘lane-changing trick’ mentioned earlier, which exemplifies a type of visual adversarial attack. In a noteworthy 2018 case, researchers conducted an experiment by applying stickers to a stop sign. The outcome was the misidentification of the sign as a speed limit sign by the computer vision system of a self-driving car.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/793/0*kjDeA4UDPeB1gq7L" /><figcaption><strong>Fig 6.Adversarial Attacks Targeting Computer Vision Systems</strong></figcaption></figure><p><strong>2. Adversarial Attacks on Voice-Controlled Systems:</strong></p><p>In the world of cybersecurity, adversarial attacks have expanded their horizons far beyond the domain of computer vision systems. In the year 2018, a pivotal discovery emerged, shedding light on the vulnerability of automated speech recognition (ASR) systems. These ASR systems are the bedrock upon which popular voice-command platforms like Amazon Alexa, Apple Siri, and Microsoft Cortana are built.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*xTIqZQyB6y5_Tkigkh1TpA.jpeg" /><figcaption><strong>Fig 7. Adversarial attacks on voice controlled systems</strong></figcaption></figure><p>Imagine this: someone with bad intentions, who understands how voice technology works, takes a regular audio file like a song on YouTube. They’re really careful and skillful, so they sneakily put a hidden voice command inside that audio file. To most people, this change sounds like nothing at all — it blends in perfectly with the music. But if you had a super-smart computer listening, it would suddenly notice something unusual in the sound. Now, here’s where it gets tricky. These secret voice commands can be used to quietly control smart speakers without anyone noticing. It’s like a sneaky way to make these voice-activated gadgets do things they shouldn’t.</p><p><strong>3. Adversarial attacks against Text Classifiers:</strong></p><p>In the ever-evolving landscape of cybersecurity and machine learning, the concept of adversarial attacks has proven to be an enduring enigma. While initially associated with visual data and computer vision systems, these cunning strategies have transcended boundaries and have now set their sights on another frontier: the realm of text classification.</p><p>Termed ‘paraphrasing attacks,’ these text-based adversarial maneuvers are both subtle and ingenious in their execution. The essence of the attack involves skillfully altering sequences of words within a piece of text, all with the ultimate goal of inducing a misclassification error within the targeted machine learning algorithm. Much like a masterful magician performing sleight of hand, these alterations are meticulously designed to deceive, eluding detection by human readers while confounding the artificial intelligence tasked with comprehension.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/733/0*vX_VuWrG-WdMWiez" /><figcaption><strong>Fig 8. Adversarial attacks against Text Classifiers</strong></figcaption></figure><p>Consider the implications of such an endeavor. Spam filters, designed to shield our inboxes from a barrage of unwanted messages, and sentiment detectors, entrusted with deciphering the emotional tone of text, are now confronted with a new breed of adversary. These paraphrasing attacks challenge the very foundations of our digital defenses, subtly distorting the messages we send and receive, potentially causing misclassification and misinterpretation.</p><p><strong>4. Adversarial Attacks against Black-Box vs. White-Box:</strong></p><p>In the world of cyberattacks, the success of adversarial strategies hinges on how much information the attacker possesses about the targeted machine learning model. This classification of adversarial attacks can be split into two categories: black-box and white-box attacks.</p><p>“Black-box attacks” unfold within a practical context where attackers have restricted access and limited knowledge of the target ML model. Their capabilities align with those of a regular user, constrained by the functions allowed within the system. Importantly, these attackers remain oblivious to the model’s inner workings and the data it relies on. To illustrate, envision an attacker attempting to exploit a publicly available API like Amazon Recognition, their strategy involves repeatedly testing the system with diverse inputs, evaluating responses in the quest to unveil any vulnerabilities.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/806/0*pZ-NiQC9jd7d0TJE" /><figcaption><strong>Fig 9.Adversarial Attacks against Black-Box vs. White-Box</strong></figcaption></figure><p>On the other hand, “white-box attacks” operate under the assumption of comprehensive knowledge and full transparency concerning the target model and its data. In this scenario, attackers gain access to the model’s intricate workings, positioning themselves advantageously to uncover vulnerabilities.</p><p>Choosing between these strategies depends on perspective and goals. “Black-box attacks” prove practical when evaluating the resilience of deployed and access-limited ML models from an adversary’s standpoint. Conversely, “white-box attacks” become invaluable tools for model developers aiming to comprehensively comprehend their ML models’ limitations and enhance robustness during the training process.</p><h4>Conclusion</h4><p>So in this article we got the insights on different Adversarial attacks and their comparative analytics with preventive measures. Adversarial machine learning stands as a burgeoning field, bringing with it a complex set of challenges that span the domains of artificial intelligence (AI) and machine learning (ML). As this field continues to gain prominence, a pressing question arises: are we at risk of adversaries exploiting our machine learning models through adversarial attacks?</p><p>The answer to this question is far from straightforward. Adversarial attacks represent a genuine and evolving threat to the integrity of our machine learning systems. These attacks are characterized by their ability to manipulate, deceive, and ultimately compromise the accuracy and reliability of machine learning models. Yet, the full scope of this threat remains difficult to delineate comprehensively. One fundamental truth underscores this ongoing battle: there are no silver bullets when it comes to defending against adversarial attacks. These adversaries are not only cunning but also adaptive, continuously refining their tactics to exploit vulnerabilities. Consequently, the defense against such attacks becomes a multifaceted challenge that lacks a one-size-fits-all solution.</p><p>Nevertheless, the world of AI and ML is far from complacent in the face of this threat. Researchers, experts, and practitioners worldwide are engaged in a relentless quest to devise techniques and strategies aimed at bolstering our defenses. The future, as it unfolds, holds the promise of innovative solutions to protect our machine learning models from adversarial attacks.</p><p>Hope this blog will helpful in understanding the modern day adversarial attacks and its preventive measures.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=640c5ffc2404" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Golang goroutines v/s Java-21 Virtual Threads]]></title>
            <link>https://medium.com/@yashgaherwar2002/golang-goroutines-v-s-java-21-virtual-threads-b0bd3e86caa1?source=rss-7dc54494f608------2</link>
            <guid isPermaLink="false">https://medium.com/p/b0bd3e86caa1</guid>
            <category><![CDATA[software-development]]></category>
            <category><![CDATA[golang]]></category>
            <category><![CDATA[java21]]></category>
            <category><![CDATA[virtual-threads]]></category>
            <category><![CDATA[goroutines]]></category>
            <dc:creator><![CDATA[Yash Gaherwar]]></dc:creator>
            <pubDate>Fri, 22 Sep 2023 21:02:28 GMT</pubDate>
            <atom:updated>2023-09-22T21:02:28.339Z</atom:updated>
            <content:encoded><![CDATA[<p>In this article we will be discussing regarding the recently launched<strong> Java-21 version</strong>. It has one of the main feature i.e. <strong>virtual threads</strong> that they have added and it is recently a trending topic because as we know that we already had <strong>Golang go-routines</strong> which is performing extremely well and providing an amazing concurrency properties. So lets deep dive into the functionality of both Java-21 and Golang.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*KjHFzPcy4BYiPt_LeZFNTA.png" /></figure><p>Golang go-routines and Java-21 virtual threads are concurrency technologies that are used to build thin execution threads. They share some characteristics, yet they also differ greatly from one another. Let’s contrast Go go-routines with Java 21 virtual threads:-</p><blockquote>1) Concurrency Model :-</blockquote><p>Virtual threads were unveiled as a new concurrency technique in Java 21. User-mode threads known as virtual threads are managed and scheduled by the Java Virtual Machine thread scheduler.</p><p>And on the other side a key component of Go’s concurrency paradigm are goroutines. They are user-mode threads that the Go runtime manages and the Go scheduler schedules.</p><blockquote>2) Parallelism Primitives :-</blockquote><p>Java offers the CompletableFuture class for asynchronous programming and the Thread class for conventional threads. The Thread API is used to manage virtual threads.</p><p>Golang offers the go keyword to launch goroutines and includes built-in channel support for synchronisation and data transfer across goroutines.</p><blockquote>3) Lightweight :-</blockquote><p>Virtual threads in Java-21 can be created in huge numbers without using up a lot of system resources because they are comparatively lightweight.<br>But while in Golang, programmes can construct thousands or even millions of goroutines since they are incredibly lightweight and have a minimal memory footprint.<br>This is one of the reason why Golang is in trend and growing rapidly.</p><blockquote>4) Scheduling :-</blockquote><p>The JVM thread scheduler, which can use several native threads underneath, schedules virtual threads.<br>But the scheduler for the Go runtime efficiently multiplexes go-routines onto fewer OS threads, which is often the same as the number of CPU cores.</p><blockquote>5) Handling Errors :-</blockquote><p>Java-21 adds additional features, such as structured concurrency structures, to handle failures and exceptions in virtual threads.<br>On the other hand Golang encourages the use of return values and channels for managing errors and coordinating inter-goroutine communication.</p><blockquote>6) Development Method :-</blockquote><p>Java has a more comprehensive type system and is more oriented towards object-oriented programming.<br>Golang places a strong emphasis on simplicity and offers a more constrained but useful set of capabilities.</p><blockquote>7) Native Libraries and Ecosystem :-</blockquote><p>Java is ideal for a variety of applications since it has a large ecosystem and a comprehensive collection of libraries.<br>While Go’s ecosystem is expanding and is particularly strong in fields like web development and systems computing.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*-4xQmKwauWm6AdrD.png" /></figure><h3>Application where go-routines are used :-</h3><p>Golang is renowned for its go-routine-based, lightweight concurrency paradigm. Go-routines are used in many different kinds of applications to effectively manage multiple processes at once. Here are some typical scenarios and applications for go-routines :-</p><ol><li><strong><em>Web Servers :-</em></strong></li></ol><blockquote>Go is commonly used to create web servers, such as the well-known ‘net/http’ HTTP server package. The server may process multiple requests at once without having to start a new operating system thread for every connection since each incoming HTTP request can be dealt with independently by a single go-routine.</blockquote><p><strong><em>2. Concurrency Patterns :-</em></strong></p><blockquote>Go-routines are used to implement a variety of concurrency patterns, including worker pools, fan-out/fan-in, and parallel processing. These design patterns are frequently employed in applications like data processing pipelines that demand parallelism and responsiveness.</blockquote><p><strong><em>3. Microservices :-</em></strong></p><blockquote>Goroutines are used in microservices designs to handle communication between services and coordinate parallel processing operations. Incoming requests, computations, and concurrent communication with other services can all be handled by each microservice using go-routines.</blockquote><p><strong><em>4. Parallelism :-</em></strong></p><blockquote>Go-routines can be used by applications that need parallelism to efficiently split jobs into smaller units of work that can be run concurrently.</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/259/0*dzrvAkcei7km7FnQ" /></figure><h3>Big projects where Golang and Go-routines where used:-</h3><p>Golang and go-routines is now impacting the tech industry and are widely used in many big products of reputed companies:-</p><p><strong><em>Google:-</em></strong></p><blockquote>Kubernetes, a well-known container orchestration technology that mainly relies on Go, is one of the projects that Google has been employing Go in. Go is also used for various parts of Google’s Infrastructure-as-a-Service (IaaS) and Platform-as-a-Service (PaaS) products.</blockquote><p><strong><em>Uber:-</em></strong></p><blockquote>Go was used to develop various components of Uber’s technology stack. They created a number of Go libraries and tools, such as the Uber Go framework formerly known as “Tchannel”, for creating scalable and effective microservices.</blockquote><p><strong><em>Docker :-</em></strong></p><blockquote>The containerization platform Docker is mostly built in Go. Goroutines and channels are used by Docker to manage containers effectively.</blockquote><p><strong><em>Twitch :-</em></strong></p><blockquote>The live-streaming platform Twitch employs Go for services that need to be scalable and have low latency performance. Additionally, they have open-sourced a few Go projects.</blockquote><p><strong><em>Cloudflare :-</em></strong></p><blockquote>Cloudflare, a worldwide content delivery network (CDN) provider, uses Go to develop serverless services and other performance-critical parts of its distributed network.</blockquote><p><strong><em>DigitalOcean :-</em></strong></p><blockquote>Go is used by cloud infrastructure company DigitalOcean to develop networking and APIs, among other parts of its cloud platform.</blockquote><p><strong><em>Dropbox :-</em></strong></p><blockquote>Adoption of Dropbox Consider improving the speed and effectiveness of the backend services, especially those that deal with file synchronization and data storage operations.</blockquote><p><strong><em>Stripe :-</em></strong></p><blockquote>Go is a programming language that is used by Stripe, an online payment processing platform, to create some of its backend services, where low latency and high concurrency are crucial.</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/263/0*b_sBQ9Ju2lE7xauq" /></figure><p><strong>Conclusion:-</strong></p><p>From hereby we can conclude that Java 21 virtual threads and Golang go-routines are two different programming paradigms for concurrency that are contrasted. The Go runtime and Go’s go-routines provide lightweight concurrency, simplicity, and an elegant architecture for task management. Go’s go-routines and channels make writing concurrent software simple and effective, making it an excellent choice for developing scalable, real-time, and network-intensive applications.</p><p>The decision between go-routines and virtual threads ultimately comes down to the particular needs of a project, the developer’s level of knowledge with the language and ecosystem, and other factors. While both methods have their advantages, Java’s virtual threads strive to bridge the gap between conventional Java threading and contemporary concurrency requirements, whereas Go’s goroutines shine in terms of usability and real-time speed.</p><p>Both Go and Java are useful tools in the constantly changing world of concurrent programming, each providing particular advantages. Developers now have the option to select the concurrency model that most closely fits the needs and aims of their projects as technology develops.</p><p><strong><em>Hope this blog will be helpful in understanding the differences and similarities between go-routines and Java-21 Virtual thread feature.</em></strong></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b0bd3e86caa1" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Usage of Syntax Directed Translation and DAG in Compiler Design]]></title>
            <link>https://medium.com/@yashgaherwar2002/usage-of-syntax-directed-translation-and-dag-in-compiler-design-741f2c95e4f5?source=rss-7dc54494f608------2</link>
            <guid isPermaLink="false">https://medium.com/p/741f2c95e4f5</guid>
            <category><![CDATA[compiler-design]]></category>
            <category><![CDATA[directed-acyclic-graph]]></category>
            <category><![CDATA[complexity]]></category>
            <category><![CDATA[parse-tree]]></category>
            <category><![CDATA[abstract-syntax-tree]]></category>
            <dc:creator><![CDATA[Yash Gaherwar]]></dc:creator>
            <pubDate>Sun, 16 Apr 2023 06:10:04 GMT</pubDate>
            <atom:updated>2023-04-17T15:54:35.079Z</atom:updated>
            <content:encoded><![CDATA[<p>Authors:- <a href="https://medium.com/@yashgaherwar2002">Yash Gaherwar</a>, <a href="https://medium.com/@tanishq252002">Tanishq Deshpande</a>, <a href="https://medium.com/@devanshukd27">Devanshu Dalal</a>, <a href="https://medium.com/@avinashdhakne">Avinash Dhakne</a></p><p>In this article we will be discussing regarding some of the most important topics in “Compiler Design” i.e. <strong>Syntax Directed Translation (SDT)</strong> and <strong>Directed Acyclic Graph (DAG)</strong>. We will be discussing the usage of SDT and DAG in Compiler Design, about their applications, advantages, disadvantages and complexity analysis of DAG and Parse Tree.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/513/1*XxZWsMHN2WKx6AB6aON5_w.png" /></figure><p><strong>What is Syntax Directed Translation?</strong></p><p>As we are all aware, the Parser checks the input string for accuracy before producing output for the following stage of the compiler. A parse tree or an abstract syntax tree could be the output. Now we employ Syntax Directed Translation to sandwich semantic analysis between the compiler’s syntax analysis step.</p><p>Grammar rules that are enhanced by Syntax Directed Translation make it easier to perform semantic analysis. SDT entails feeding the parse tree data that is attached to the nodes as attributes from the bottom up or from the top down. The<strong> lexical values of nodes, constants, and characteristics related to non-terminals</strong> are all used in the formulations of syntax-directed translation rules.</p><p><strong>Flow Diagram:-</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/763/0*6Ccaq8X4KQQWGANO" /></figure><p><strong>Syntax-directed translation benefits include:</strong></p><ol><li><strong>Implementation simplicity:</strong> SDT is a straightforward and simple method for translating a programming language. It offers a straightforward and organized way to define translation rules using grammatical rules.</li><li><strong>Separation of concerns:</strong> SDT divides the parsing and translation processes, which makes it simpler to update and maintain the compiler. Additionally, it separates the problems about translation from the concerns about parsing, enabling more modular and adaptable compiler designs.</li><li><strong>Effective code generation:</strong> SDT makes it possible to generate code that is effective by streamlining the translation procedure. It permits the application of strategies like intermediate code creation and code optimisation.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/630/1*xu_ACQBKUjw0oEzSeRV8tw.png" /></figure><p><strong>Syntax Directed Translation’s drawbacks:-</strong></p><ol><li>SDT’s expressiveness is constrained when compared to other translation techniques, like attribute grammars. The kinds of translations that can be carried out using SDT are so constrained.</li><li>SDT may be rigid in circumstances where the translation rules are complicated and difficult to express using simple grammatical principles.</li><li><strong>Limited mistake recovery:</strong> The ability of SDT to correct translation errors is constrained. This may lead to subpar error messages and make it more challenging to find and correct input programme issues.</li></ol><p><strong>What is Directed Acyclic Graph?</strong></p><p>A Directed Acyclic Graph (DAG) is a directed graph that contains nodes connected by edges, with the property that the graph contains no directed cycles. This means that it is impossible to start at any node and follow a sequence of edges that eventually loops back to the starting node.</p><p>The absence of cycles makes DAGs useful in a variety of applications, particularly in compiler design and optimization. For example, in a compiler, a DAG can be used to represent the control flow and data dependencies of a program, enabling the compiler to perform optimizations such as common sub-expression elimination and loop invariant code motion.</p><p>DAGs are also commonly used in scheduling problems, where the goal is to schedule a set of tasks subject to constraints such as precedence relations and resource availability. The tasks are represented as nodes in the DAG, with edges representing the precedence relations between tasks.</p><p>In addition, DAGs are used in a variety of other applications, such as in data processing pipelines, where each node in the graph represents a processing step and the edges represent the flow of data between steps.</p><p>Overall, the Directed Acyclic Graph is a powerful and versatile data structure that finds many applications in computer science and related fields.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/808/1*ZDAYPBvwdJibAdbR_PAzmQ.png" /><figcaption><strong>Directed Acyclic Graph Example</strong></figcaption></figure><p><strong>Usage of DAG in Compiler Design:-</strong></p><ol><li>In compiler design, a Directed Acyclic Graph (DAG) is commonly used to represent the control flow and data dependencies of a program. This representation is often used as an intermediate representation (IR) that facilitates program optimization and transformation.</li><li>When a program is compiled, it goes through several stages, including lexical analysis, parsing, semantic analysis, and code generation. During these stages, the compiler constructs a DAG representation of the program that captures the control flow and data dependencies between its components.</li><li>One common use of DAGs in compiler design is to represent expressions. An expression can be represented as a DAG in which each node represents a sub-expression, and each edge represents a dependency between sub-expressions. The use of DAGs in this context enables the compiler to perform optimizations such as common sub-expression elimination and constant folding, which can significantly improve the performance of the generated code.</li><li>Another use of DAGs in compiler design is to represent the control flow of a program. A control flow DAG is a representation of the program’s control flow in which each node represents a basic block of code, and each edge represents a control flow transfer between basic blocks. Control flow DAGs can be used to perform optimizations such as dead code elimination and loop unrolling.</li><li>Overall, the use of DAGs in compiler design provides an efficient and effective approach to representing the control flow and data dependencies of a program, enabling the compiler to perform a variety of optimizations that can significantly improve the performance of the generated code.</li></ol><p><strong>Usage of Syntax Directed Translation (SDT) in Compiler Design:-</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/499/1*v26riUzhY-0sRrYZztrfUQ.png" /></figure><ul><li>Syntax Directed Translation (SDT) is a technique used in compiler design to define the translation of a programming language’s source code into machine code or some other intermediate representation. In SDT, translation rules are associated with the grammar productions of the language, and these rules are executed during the parsing process to produce the desired output.</li><li>One of the main advantages of SDT is that it enables the compiler designer to specify the translation process in a declarative manner, which is much easier to understand and maintain than a procedural implementation. Additionally, SDT can enable certain optimizations, such as constant folding and common sub-expression elimination, by associating translation rules with particular productions in the grammar.</li><li>The basic steps involved in using SDT in compiler design are as follows:</li></ul><blockquote>1) Define the grammar of the programming language.</blockquote><blockquote>2) Each grammatical production should be associated with a set of translation rules.</blockquote><blockquote>3) Use a parser generator to generate a parser for the language.</blockquote><blockquote>4) As the parser processes the input program, execute the translation rules associated with each production to produce the desired output.</blockquote><ul><li>Overall, the use of Syntax Directed Translation in Compiler Design provides a powerful and flexible approach to defining the translation process for a programming language. By associating translation rules with the grammar productions, SDT enables the compiler to generate efficient and optimized code, while also making the translation process easier to understand and maintain.</li></ul><p><strong>Complexity Analysis of DAG in Compiler Analysis:-</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3T6rdeFCVKZePG6_Psa3AA.png" /></figure><ul><li>In compiler design, Directed Acyclic Graphs (DAGs) are often used to represent the control flow and data dependencies of a program, and they play a crucial role in optimizing the generated code. The complexity analysis of DAGs in compiler design depends on the specific optimization being performed.</li><li>Here are some common optimizations that use DAGs and their associated time complexities:</li></ul><ol><li><strong>Common Subexpression Elimination</strong> (CSE):<strong> O(n²)</strong></li></ol><p>→ CSE is an optimization that eliminates redundant computations by identifying common subexpressions in the program. The time complexity of CSE using DAGs is <strong>O(n²)</strong>, where n is the number of nodes in the DAG.</p><p><strong>2. Dead Code Elimination</strong> (DCE): <strong>O(n)</strong></p><p>→ DCE is an optimization that eliminates code that is never executed. The time complexity of DCE using DAGs is<strong> O(n)</strong>, where n is the number of nodes in the DAG.</p><p><strong>3. Register Allocation</strong>: <strong>O(n³)</strong></p><p>→ Register allocation is an optimization that assigns variables to hardware registers to minimize the number of memory accesses. The time complexity of <strong>register allocation using DAG</strong> is <strong>O(n³),</strong> where n is the number of nodes in the DAG.</p><p><strong>4. Loop Optimization</strong>: <strong>O(n²)</strong></p><p><strong>→ </strong>Loop optimization is an optimization that optimizes the performance of loops in the program. The time complexity of loop optimization using DAGs is O(n²), where n is the number of nodes in the DAG.</p><ul><li>Overall, the time complexity of using DAGs in compiler design depends on the specific optimization being performed, but in general, it tends to be relatively efficient. Most optimizations take quadratic or cubic time in the size of the DAG, which is usually much smaller than the size of the original program.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/596/1*AU-T340LuK7iuOZmsxdnJw.png" /></figure><p><strong>Can Syntax Directed Translation be Performed using Parse Tree?</strong></p><p>→ SDT can be performed using a <strong>parse tree</strong> or an <strong>abstract syntax tree</strong> (AST).</p><ul><li>The syntactic structure of source code is represented as a tree in a parse tree, where each node corresponds to a production in the grammar used to parse the input program. Parse trees are often used in bottom-up parsing techniques, such as LR parsing.</li></ul><blockquote><strong>For Example:- Parse Tree Construction for =&gt; 2*(4+5)</strong></blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/381/1*e2VK_LjvyBtk2SsEDbRhgg.png" /></figure><ol><li>In SDT using a parse tree, translation rules are associated with each production in the grammar, and these rules are executed during the parsing process to produce the desired output.</li><li>The translation rules are typically expressed as semantic actions associated with the grammar productions, which are executed when the corresponding production is reduced during parsing.</li><li>The main advantage of using a parse tree for SDT is that it provides a detailed representation of the syntactic structure of the input program, which makes it easier to perform context-sensitive analysis and generate accurate error messages.</li><li>However, parse trees tend to be more complex and memory-intensive than ASTs.</li></ol><p><strong>Can Syntax Directed Translation be Performed using Abstract Syntax Tree?</strong></p><ul><li>In contrast, an abstract syntax tree (AST) is a simplified representation of the syntactic structure of the input program that only includes the essential information for performing the desired translation. ASTs are often used in top-down parsing techniques, such as recursive descent parsing.</li></ul><blockquote><strong>For Example:- Abstract Syntax Tree Construction for =&gt; 2*(4+5)</strong></blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/267/1*bb6CrCjzMK960z93330Z2A.png" /></figure><ol><li>In SDT using an AST, translation rules are associated with the nodes in the tree, and these rules are executed during a traversal of the tree to produce the desired output. The translation rules are typically expressed as methods or functions associated with the node types in the AST.</li><li>Overall, both parse trees and ASTs can be used for SDT in compiler design, and the choice of representation depends on the specific requirements of the compiler and the parsing technique being used.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/564/1*sQJtKImvgKOp80NzBPYBdA.png" /></figure><p><strong>Conclusion:-</strong></p><p>From hereby we can conclude that Directed Acyclic Graphs (DAGs) and Syntax Directed Translation (SDT) are two essential techniques used in compiler design to optimize and translate source code into machine code or other intermediate representations. DAGs provide a powerful tool for representing the control flow and data dependencies of a program, which is critical for optimizing the generated code. Meanwhile, SDT allows for a straightforward and efficient translation process that associates semantic actions with the nodes in the parse tree or AST, allowing for accurate and efficient code generation. The combination of DAGs and SDT techniques in compiler design can lead to efficient, optimized, and reliable code generation, making them essential tools for modern compilers.</p><p>Hope this blog will be helpful in understanding the the core concept of compiler design i.e. Syntax Directed Translation and Directed Acyclic Graph.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=741f2c95e4f5" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Graph Theoretical Algorithms]]></title>
            <link>https://medium.com/@yashgaherwar2002/graph-therotical-algorithms-5e8698706550?source=rss-7dc54494f608------2</link>
            <guid isPermaLink="false">https://medium.com/p/5e8698706550</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[competitive-programming]]></category>
            <category><![CDATA[data-structure-algorithm]]></category>
            <category><![CDATA[graph]]></category>
            <category><![CDATA[complexity-analysis]]></category>
            <dc:creator><![CDATA[Yash Gaherwar]]></dc:creator>
            <pubDate>Wed, 23 Nov 2022 13:19:54 GMT</pubDate>
            <atom:updated>2022-11-25T10:00:37.439Z</atom:updated>
            <content:encoded><![CDATA[<p>Authors:- <a href="https://medium.com/@yashgaherwar2002">Yash Gaherwar</a>, <a href="https://medium.com/@tanishq252002">Tanishq Deshpande</a>, <a href="https://medium.com/@devanshukd27">Devanshu Dalal</a>, <a href="https://medium.com/@avinashdhakne">Avinash Dhakne</a></p><p>In this article we will be discussing regarding one of the most important topics of “<strong>Design Analysis of Algorithms”</strong> i.e <strong>Graph</strong>. We will be discussing different Algorithms with their Implementation Strategy, Complexity Analysis and Applications.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*uIv1ewPv28bXSY597hbr2g.png" /></figure><h4>What is Graph?</h4><p>A graph is a visual representation of a collection of things where some object pairs are linked together. Vertices are the points used to depict the interconnected items, while edges are the connections between them.</p><p>A graph is defined in formal terms as a pair of sets (V, E), where V is the set of vertices and E is the set of edges that connect the pairs of vertices.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/295/1*EtexuaCNgIeiYPdHZUTB7w.png" /><figcaption><strong>Graph</strong></figcaption></figure><h4><strong>What is Graph Theory?</strong></h4><p>The study of graphs is known as “Graph Theory”. Graph Theory focuses on how edges and vertices relate to one another. It is a well-liked subject with applications in fields like Computer science, Information technology, bio-sciences, and mathematics.</p><h4><strong>Representation of Graph:-</strong></h4><p>There where two different ways of representing Graphs:-</p><ol><li><strong><em>Adjacency Matrix:-</em></strong></li></ol><p>→ Adjacency matrix is a form of representation in order.<br> → It is utilized to show which nodes are close to one another. i.e., does a graph have any edges that connect its nodes.</p><p>→ We can save the edge’s weight in place of 1&#39;s and 0&#39;s if the graph is weighted.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/715/1*Hr37dAVcK2Zl4idFqRXpbw.png" /><figcaption><strong>Adjacency Matrix Representation</strong></figcaption></figure><p>2. <strong><em>Adjacency List:-</em></strong></p><p>→ A linked representation is called an adjacency list.<br> → In this model, we keep track of each vertex’s neighbors for each node in the graph. As a result, each vertex in the network has a list of the vertices that are immediately close to it.<br> → For each vertex v, the associated array element points to a singly linked list of v’s neighbors. The array of vertices is indexed by the vertex number.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/554/1*8VJWkVYMl4YoOIDCMcPzng.png" /><figcaption><strong>Adjacency List Representation</strong></figcaption></figure><h3>Different Graph Theory Algorithms:-</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/375/1*pVoze1iRu000gJAXGgdUYQ.jpeg" /></figure><h4>1) Depth First Search (DFS) Algorithm:-</h4><p>→ Each vertex of the graph is assigned to one of the two categories in a typical DFS implementation:-</p><p>a)Visited b) Not-Visited.</p><blockquote><strong>How DFS Algorithm operates:-</strong></blockquote><ol><li>Start by stacking any vertex of the graph on top of another.</li><li>Add the item at the top of the stack to the visited list.</li><li>Make a list of the nodes that are close to that vertex. Place the items that haven’t been visited to the top of the stack.</li><li>Repeat actions 2 and 3 until the stack is completely gone.</li></ol><blockquote><strong>Complexity Analysis:-</strong></blockquote><p>(V-&gt; Vertices and E -&gt; No. of Edges)</p><ol><li><strong>Time Complexity of DFS:- O(V+E)</strong></li><li><strong>Space Complexity of DFS:-</strong> <strong>O(V)</strong></li></ol><blockquote><strong>Applications of DFS:-</strong></blockquote><ol><li>Detecting Cycle</li><li>To determine if a graph is bipartite or not.</li><li>To identify the strongly related graph elements (Connected Components).</li></ol><h4>2) Breadth First Search (BFS) Algorithm:-</h4><p>Each vertex of the graph is assigned to one of the two categories in a typical BFS implementation:-</p><p>a)Visited b) Not-Visited.</p><blockquote><strong>How BFS Algorithm operates:-</strong></blockquote><ol><li>Put any vertex of the graph at the end of the queue to get started.</li><li>Add the item at the front of the line to the visited list.</li><li>Make a list of the nodes that are close to that vertex. Place the items that haven’t been visited at the end of the list.</li><li>Repeat actions 2 and 3 until the line is free.</li></ol><blockquote><strong>Complexity Analysis:-</strong></blockquote><p>(V-&gt; Vertices and E -&gt; No. of Edges)</p><ol><li><strong>Time Complexity of DFS:- O(V+E)</strong></li><li><strong>Space Complexity of DFS:-</strong> <strong>O(V)</strong></li></ol><blockquote><strong>Applications of BFS:-</strong></blockquote><ol><li>To create an index for each search.</li><li>Used in GPS navigation algorithms.</li><li>Using the Ford-Fulkerson algorithm, find the network’s maximum flow.</li><li>Cycle detection in a network that is not directed.</li><li>Minimal spanning tree.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/295/1*el2onObM6MbCYGAsiOW5Wg.png" /></figure><h4>3) Bellman Ford’s Algorithm:-</h4><blockquote><strong>How Bellman Ford’s Algorithm operates:-</strong></blockquote><p>→ The Bellman Ford’s Algorithm functions by overestimating the distance between the beginning vertex and each subsequent vertex.</p><p>→ Then, by uncovering fresh paths that are shorter than the outdated, overstated paths, it iteratively reduces those estimates.</p><blockquote><strong>Complexity Analysis:-</strong></blockquote><p>(V-&gt; Vertices and E -&gt; No. of Edges)</p><ol><li><strong>Best Case Complexity:- </strong>O(E)</li><li><strong>Average Case Complexity:-</strong> O(V*E)</li><li><strong>Worst Case Complexity:-</strong> O(V*E)</li></ol><p><strong>→ Space Complexity of Bellman Ford:-</strong> <strong>O(V)</strong></p><blockquote><strong>Applications of Bellman Ford’s:-</strong></blockquote><p>→ In routing algorithms, to determine the shortest paths.<br> → To determine the quickest route.</p><h4>4) <strong>Floyd-Warshall Algorithm:-</strong></h4><p>→ A weighted Graph’s Floyd-Warshall algorithm is used to determine the shortest route between all of the vertex pairs.</p><p>→ In both the directed and undirected weighted graphs can be solved using this approach.</p><p>→ However, it is ineffective for graphs with negative cycles (where the sum of the edges in a cycle is negative).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*skLATDfDc5-0sP-bbAKxrQ.png" /><figcaption><strong>Pseudocode:- Floyd-Warshall Algorithm</strong></figcaption></figure><blockquote><strong>Complexity Analysis:-</strong></blockquote><ol><li><strong>Time Complexity of Floyd-Warshall:- O(n³)</strong></li><li><strong>Space Complexity of Floyd-Warshall:-</strong> <strong>O(n²)</strong></li></ol><blockquote><strong>Applications of Floyd-Warshall:-</strong></blockquote><ol><li>In a directed graph, used to determine shortest path.</li><li>locate directed graphs’ transitive closure.</li><li>To determine real matrices’ inversion.</li><li>To determine if a bipartite undirected graph exists.</li></ol><h4>5) Prims Algorithm:-</h4><p>→ It belongs to a category of algorithms known as greedy algorithms, which locate the local optimum with the intention of locating a global optimum.</p><p>→ Beginning with one vertex, we continue to add edges with the lowest weight until we attain our objective.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/547/0*RuH1eiyuLQTG-p3J.gif" /></figure><blockquote><strong>How Prims Algorithm operates:-</strong></blockquote><p>Implementing Prim’s algorithm involves the following steps:</p><ol><li>Set up the minimum spanning tree using a randomly selected vertex.</li><li>Find the minimum of all the edges connecting the tree to new vertices, then add it to the tree.</li><li>Repeat step 2 as necessary to obtain a minimum spanning tree.</li></ol><blockquote><strong>Complexity Analysis:-</strong></blockquote><p>(V-&gt; Vertices and E -&gt; No. of Edges)</p><ol><li><strong>Time Complexity of Prims:- O(E*log(V))</strong></li></ol><blockquote><strong>Applications of Prims:-</strong></blockquote><ol><li>Installing electrical wiring cables</li><li>To create protocols in network cycles, the network was built.</li></ol><h4>6) Kruskal’s Algorithm:-</h4><p>→ It belongs to a category of algorithms known as greedy algorithms, which locate the local optimum with the intention of locating a global optimum.</p><p>→ The edges with the lowest weight are where we start, and we keep adding edges until we reach our destination.</p><blockquote><strong>How Kruskal Algorithm operates:-</strong></blockquote><p>The following are the stages for applying Kruskal’s algorithm:</p><ol><li>Order every edge from light to heavy.</li><li>Add the edge to the spanning tree that has the lowest weight.</li><li>Reject this edge if adding it resulted in a cycle.</li><li>Up till we reach all vertices, keep adding edges.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/480/0*6dUgl7VW_F96Z5F5.gif" /><figcaption><strong>Kruskal’s Algorithm Implementation</strong></figcaption></figure><blockquote><strong>Complexity Analysis:-</strong></blockquote><p>(V-&gt; Vertices and E -&gt; No. of Edges)</p><ol><li><strong>Time Complexity of Prims:- O(E*log(E))</strong></li></ol><blockquote><strong>Applications of Kruskal’s:-</strong></blockquote><ol><li>Used when designing electrical wiring.</li><li>Networking in computers.</li></ol><h4>7) Dijkstra’s Algorithm:-</h4><p>→ We can determine the shortest route between any two graph vertices using Dijkstra’s approach. Because not all of the vertices of the graph may be included in the shortest distance between two vertices, it is different from the minimal spanning tree.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*kA70NsGuwHz70Cykp4bhAQ.png" /><figcaption><strong>Pseudocode:- Dijkstra’s Algorithm</strong></figcaption></figure><blockquote><strong>Complexity Analysis:-</strong></blockquote><p>(V-&gt; Vertices and E -&gt; No. of Edges)</p><ol><li><strong>Time Complexity of Dijkstra’s Algorithm:- O(E*log(V))</strong></li><li><strong>Space Complexity of Dijkstra’s Algorithm:-</strong> <strong>O(V)</strong></li></ol><blockquote><strong>Applications of Dijkstra’s Algorithm:-</strong></blockquote><ol><li>To determine the quickest route</li><li>In applications for social networking</li><li>Used Within a phone network.</li><li>Used to locate the places on the map.</li></ol><h4>Different Applications of Graph Theory :-</h4><blockquote>1) The design of circuit connections frequently makes use of graph theory principles in electrical engineering. Topologies refer to the varieties or configurations of connections. Star, bridge, series, and parallel topologies are a few examples of topologies.</blockquote><blockquote>2) For the study of algorithms, Graph Theory is used. Few algorithms are Prims, Kruskals and Dijkstra’s.</blockquote><blockquote>3) In CN (Computer Network) Graph theory is used to explain the connections between the connected machines in the network.</blockquote><blockquote>4) In Science Graphs are used to represent the molecular structure, chemical structure, DNA structure, and other physical properties of substances.</blockquote><blockquote>5) General Graphs can be used to show the routes between the cities. A special kind of graph called a “tree” can be used to represent hierarchically arranged information, such as a family tree.</blockquote><h4>Conclusion:-</h4><p>From hereby we can conclude that <strong>Graph</strong> is one of the very Interesting and Important <strong>Advanced Data Structure</strong> that is widely used in Industry as well. <strong>Graph theory</strong> make it possible to guarantee a reliable service for example in the navigation services including Google Maps and all. And every second we use it whether in the form of Social Networking or implementing it. In this article we learned about different Algorithms Techniques of Graph with their Complexity and implement strategies.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5e8698706550" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Hash Table and Sliding Window Problem: “Minimum Consecutive Cards to Pick Up”]]></title>
            <link>https://medium.com/@yashgaherwar2002/hash-table-and-sliding-window-problem-minimum-consecutive-cards-to-pick-up-77e7b469d9ac?source=rss-7dc54494f608------2</link>
            <guid isPermaLink="false">https://medium.com/p/77e7b469d9ac</guid>
            <category><![CDATA[dynamic-programming]]></category>
            <category><![CDATA[hashmap]]></category>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[competitive-programming]]></category>
            <category><![CDATA[sliding-window-algorithm]]></category>
            <dc:creator><![CDATA[Yash Gaherwar]]></dc:creator>
            <pubDate>Thu, 27 Oct 2022 03:48:25 GMT</pubDate>
            <atom:updated>2022-10-27T03:48:25.634Z</atom:updated>
            <content:encoded><![CDATA[<p>Lets start with the Problem of the Day from the “Programming with DPwala” series by <a href="https://medium.com/u/7dc54494f608">Yash Gaherwar</a>.</p><p>-“𝐎𝐧𝐞 𝐂𝐨𝐝𝐢𝐧𝐠 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐚 𝐝𝐚𝐲 𝐤𝐞𝐞𝐩𝐬 𝐭𝐡𝐞 𝐏𝐥𝐚𝐜𝐞𝐦𝐞𝐧𝐭 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐚𝐰𝐚𝐲 !!”</p><p>-Yash Gaherwar</p><h4>Problem Statement :-</h4><p>You are given an integer array cards where cards[i] represents the value of the i-th card. A pair of cards are matching if the cards have the same value.</p><p>Return the minimum number of consecutive cards you have to pick up to have a pair of matching cards among the picked cards. If it is impossible to have matching cards, return -1.</p><p><strong>Sample Input :- </strong>cards = [3,4,2,3,4,7]</p><p><strong>Output :-</strong> 4</p><p><strong>Given Explanation:- </strong>We can pick up the cards [3,4,2,3] which contain a matching pair of cards with value 3. Note that picking up the cards [4,2,3,4] is also optimal.</p><p><strong>Constraints:-</strong></p><ul><li>1 &lt;= cards.length &lt;= 10⁵</li><li>0 &lt;= cards[i] &lt;= 10⁶</li></ul><p><strong>Approach Required:- <em>“</em></strong><em>Hash Table and Sliding Window Technique”</em> .</p><p><strong>My Approach to solve this Problem :-</strong></p><p>First Approach:-</p><ol><li>Firstly the question can be easily solved using Sliding window technique.</li><li>In Sliding window approach we will keep on calculating the frequency of every Element in Map and if we encountered any character which having frequency greater than one from their we started shrinking our window till we get that value again and updating our ans variable.</li><li>And at last we simply return ans if we have a matching card else we return -1 if it is impossible to have it (when ans==INT_MAX in our case).</li></ol><p>Second Approach:-</p><ol><li>We can simply do this question in O(N) Time Complexity rather than using Sliding window technique which take O(N*log(N)) time.</li><li>We will using map and mp.find() function to check whether the element is present in our map or not if it is present than we simply calculate the window length and update our ans variable. And all the time we are storing corresponding index of every element.</li></ol><p><strong>CODE:-</strong></p><p><strong>Approach 1:- Sliding Window Approach.</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ydamRHdWXfIzLfXcyK9_3g.png" /><figcaption><strong>Sliding Window Approach</strong></figcaption></figure><p><strong>Complexity Analysis for Approach 1:-</strong></p><blockquote><strong><em>Time Complexity : O(N*log(N))</em></strong></blockquote><blockquote><strong><em>Space Complexity : O(N)</em></strong></blockquote><p><strong>Approach 2:- Hash Table (using Map in C++) Approach.</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*XxuLfHlwOyZvuT1sVMfFLg.png" /><figcaption><strong>Map Approach (Optimized Approach)</strong></figcaption></figure><p><strong>Complexity Analysis for Approach 2:-</strong></p><blockquote><strong><em>Time Complexity : O(N)</em></strong></blockquote><blockquote><strong><em>Space Complexity : O(N)</em></strong></blockquote><p>Hope you might learned the approach required to solve this Problems. I tried to explain the Problem using both <em>Hash Table and Sliding Window Approach</em>.</p><p>Hope this <strong>“Daily Coding Problem with Yash Gaherwar”</strong> initiative will help many to solve at least one Coding Problem daily and remove their fear related to Programming and maintaining consistency.</p><p>Join the Programming Community:- <strong>“Programming with DPwala”</strong></p><p>Link for Joining the Programming Community:- <a href="https://www.linkedin.com/groups/9249623/">Programming with DPwala</a></p><p><a href="https://www.linkedin.com/groups/9249623/">https://www.linkedin.com/groups/9249623/</a></p><p>Stay connected with me on Medium and LinkedIn for daily updates..</p><p><strong>LinkedIn:- </strong><a href="https://www.linkedin.com/in/yash-gaherwar-21a671208/"><strong>https://www.linkedin.com/in/yash-gaherwar-21a671208/</strong></a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=77e7b469d9ac" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[DP + Priority Queue Problem: “Find Kth Largest XOR Coordinate Value”]]></title>
            <link>https://medium.com/@yashgaherwar2002/dp-priority-queue-problem-find-kth-largest-xor-coordinate-value-9fc86f21e68d?source=rss-7dc54494f608------2</link>
            <guid isPermaLink="false">https://medium.com/p/9fc86f21e68d</guid>
            <category><![CDATA[data-structure-algorithm]]></category>
            <category><![CDATA[dynamic-programming]]></category>
            <category><![CDATA[priority-queue]]></category>
            <category><![CDATA[competitive-programming]]></category>
            <category><![CDATA[matrix]]></category>
            <dc:creator><![CDATA[Yash Gaherwar]]></dc:creator>
            <pubDate>Tue, 25 Oct 2022 06:13:03 GMT</pubDate>
            <atom:updated>2022-10-25T06:13:03.368Z</atom:updated>
            <content:encoded><![CDATA[<p>Lets start with the Problem of the Day from the “Programming with DPwala” series by <a href="https://medium.com/u/7dc54494f608">Yash Gaherwar</a> .</p><p>-“𝐎𝐧𝐞 𝐂𝐨𝐝𝐢𝐧𝐠 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐚 𝐝𝐚𝐲 𝐤𝐞𝐞𝐩𝐬 𝐭𝐡𝐞 𝐏𝐥𝐚𝐜𝐞𝐦𝐞𝐧𝐭 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐚𝐰𝐚𝐲 !!”</p><p>-Yash Gaherwar</p><h4>Problem Statement :-</h4><p>You are given a 2-D matrix of size m x n, consisting of non-negative integers. You are also given an integer k.</p><p>The value of coordinate (a, b) of the matrix is the XOR of all matrix[i][j] where 0 &lt;= i &lt;= a &lt; m and 0 &lt;= j &lt;= b &lt; n (0-indexed).</p><p>Find the k-th largest value (1-indexed) of all the coordinates of matrix.</p><p><strong>Sample Input :- </strong>matrix = [[5,2],[1,6]], k = 1</p><p><strong>Output :-</strong> 7</p><p><strong>Given Explanation:- </strong>The value of coordinate (0,1) is 5 XOR 2 = 7, which is the largest value.</p><p><strong>Constraints:-</strong></p><p>m == matrix.length<br>n == matrix[i].length<br>1 &lt;= m, n &lt;= 1000<br>0 &lt;= matrix[i][j] &lt;= 10⁶<br>1 &lt;= k &lt;= m * n</p><p><strong>Approach Required:- <em>“</em></strong><em>Priority Queue + Dynamic Programming”</em> .</p><p><strong>My Approach to solve this Problem :-</strong></p><p>Simply we need to calculate the xor at (i, j) as:-</p><ol><li>matrix[i][j-1]</li><li>matrix[i-1][j]</li><li>matrix[i-1][j-1]</li></ol><blockquote>matrix[i][j] = matrix[i-1][j] ^ matrix[i][j-1] ^ matrix[i-1][j-1] ^ matrix[i][j].</blockquote><p>Then simply we need to return the k-th largest element. For this we can use Priority Queue.</p><p><strong>CODE:-</strong></p><p><strong>Approach:- Priority Queue + Dynamic Programming Approach.</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*aSzk5WK_5z_CttW0DVs60w.png" /><figcaption><strong>Priority Queue + Dynamic programming Approach</strong></figcaption></figure><p><strong>Complexity Analysis:-</strong></p><blockquote><strong><em>Time Complexity : O(m*n)</em></strong></blockquote><blockquote><strong><em>Space Complexity : O(n)</em></strong></blockquote><p>Hope you might learned the approach required to solve this Problems. I tried to explain the Problem using <em>Priority Queue + Dynamic Programming</em>.</p><p>Hope this <strong>“Daily Coding Problem with Yash Gaherwar”</strong> initiative will help many to solve at least one Coding Problem daily and remove their fear related to Programming and maintaining consistency.</p><p>Join the Programming Community:- <strong>“Programming with DPwala”</strong></p><p>Link for Joining the Programming Community:- <a href="https://www.linkedin.com/groups/9249623/">Programming with DPwala</a></p><p><a href="https://www.linkedin.com/groups/9249623/">https://www.linkedin.com/groups/9249623/</a></p><p>Stay connected with me on Medium and LinkedIn for daily updates..</p><p><strong>LinkedIn:- </strong><a href="https://www.linkedin.com/in/yash-gaherwar-21a671208/"><strong>https://www.linkedin.com/in/yash-gaherwar-21a671208/</strong></a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9fc86f21e68d" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Greedy Problem: “Previous Permutation With One Swap”]]></title>
            <link>https://medium.com/@yashgaherwar2002/greedy-problem-previous-permutation-with-one-swap-48eaf549a010?source=rss-7dc54494f608------2</link>
            <guid isPermaLink="false">https://medium.com/p/48eaf549a010</guid>
            <category><![CDATA[competitive-programming]]></category>
            <category><![CDATA[data-structure-algorithm]]></category>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[greedy-algorithms]]></category>
            <category><![CDATA[cpp]]></category>
            <dc:creator><![CDATA[Yash Gaherwar]]></dc:creator>
            <pubDate>Sat, 22 Oct 2022 06:54:56 GMT</pubDate>
            <atom:updated>2022-10-22T06:54:56.000Z</atom:updated>
            <content:encoded><![CDATA[<p>Lets start with the Problem of the Day from the “Programming with DPwala” series by <a href="https://medium.com/u/7dc54494f608?source=post_page-----954c25766566--------------------------------">Yash Gaherwar</a> .</p><p>-“𝐎𝐧𝐞 𝐂𝐨𝐝𝐢𝐧𝐠 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐚 𝐝𝐚𝐲 𝐤𝐞𝐞𝐩𝐬 𝐭𝐡𝐞 𝐏𝐥𝐚𝐜𝐞𝐦𝐞𝐧𝐭 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐚𝐰𝐚𝐲 !!”</p><p>-Yash Gaherwar</p><h4>Problem Statement :-</h4><p>Given an array of positive integers arr (not necessarily distinct), return the lexicographically largest permutation that is smaller than arr, that can be made with exactly one swap (A swap exchanges the positions of two numbers arr[i] and arr[j]). If it cannot be done, then return the same array.</p><p><strong>Sample Input :- </strong>arr = [3,2,1]</p><p><strong>Output :-</strong> [3,1,2]</p><p><strong>Given Explanation:- </strong>Swapping 2 and 1.</p><p><strong>Constraints:-</strong></p><p>1 &lt;= arr.length &lt;= 10⁴<br>1 &lt;= arr[i] &lt;= 10⁴</p><p><strong>Approach Required:- <em>“</em></strong><em>Greedy Approach”</em> .</p><p><strong>My Approach to solve this Problem :-</strong></p><ol><li>First we need to check whether the given permutation is the smallest one or not. If yes than simply return that permutation only, otherwise we need to find the smallest permutation.</li><li>For finding the smallest permutation we need to traverse the array from (n-2) index element and check whether it is smaller than its next neighboring element in right side. If not than we got out first element that need to be swapped with.</li><li>As by getting the first element we need to search for the second element in the right part of that element. And need to find just next element which is smaller than it. We also store index of both the two elements that we get as we require to swap them.</li><li>And after getting both the elements with their indices we simply swap them and return the updated array (Permutation).</li></ol><p><strong>CODE:-</strong></p><p><strong>Approach :- Greedy Approach .</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*C87l9rVoQRFPXgFEz6BcOA.png" /><figcaption><strong>Greedy Approach</strong></figcaption></figure><p><strong>Complexity Analysis:-</strong></p><blockquote><strong><em>Time Complexity : O(N)</em></strong></blockquote><blockquote><strong><em>Space Complexity : O(1)</em></strong></blockquote><p>Hope you might learned the approach required to solve this Problems. I tried to explain the Problem using Greedy Approach.</p><p>Hope this <strong>“Daily Coding Problem with Yash Gaherwar”</strong> initiative will help many to solve at least one Coding Problem daily and remove their fear related to Programming and maintaining consistency.</p><p>Join the Programming Community:- <strong>“Programming with DPwala”</strong></p><p>Link for Joining the Programming Community:- <a href="https://www.linkedin.com/groups/9249623/">Programming with DPwala</a></p><p><a href="https://www.linkedin.com/groups/9249623/">https://www.linkedin.com/groups/9249623/</a></p><p>Stay connected with me on Medium and LinkedIn for daily updates..</p><p><strong>LinkedIn:- </strong><a href="https://www.linkedin.com/in/yash-gaherwar-21a671208/"><strong>https://www.linkedin.com/in/yash-gaherwar-21a671208/</strong></a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=48eaf549a010" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Sliding Window Problem: “Number of Sub-arrays of Size K and Average Greater than or Equal to…]]></title>
            <link>https://medium.com/@yashgaherwar2002/sliding-window-problem-number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-954c25766566?source=rss-7dc54494f608------2</link>
            <guid isPermaLink="false">https://medium.com/p/954c25766566</guid>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[dpwala]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[competitive-programming]]></category>
            <category><![CDATA[problem-solving]]></category>
            <dc:creator><![CDATA[Yash Gaherwar]]></dc:creator>
            <pubDate>Fri, 21 Oct 2022 08:20:08 GMT</pubDate>
            <atom:updated>2022-10-21T08:20:08.038Z</atom:updated>
            <content:encoded><![CDATA[<h3>Sliding Window Problem: “Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold”</h3><p>Lets start with the Problem of the Day from the “Programming with DPwala” series by <a href="https://medium.com/u/7dc54494f608">Yash Gaherwar</a>.</p><p>-“𝐎𝐧𝐞 𝐂𝐨𝐝𝐢𝐧𝐠 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐚 𝐝𝐚𝐲 𝐤𝐞𝐞𝐩𝐬 𝐭𝐡𝐞 𝐏𝐥𝐚𝐜𝐞𝐦𝐞𝐧𝐭 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐚𝐰𝐚𝐲 !!”</p><p>-Yash Gaherwar</p><h4>Problem Statement :-</h4><p>Given an array of integers arr and two integers k and threshold, return the number of sub-arrays of size k and average greater than or equal to threshold.</p><p><strong>Sample Input :- </strong>arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4</p><p><strong>Output :-</strong> 3</p><p><strong>Given Explanation:- </strong>Sub-arrays [2,5,5],[5,5,5] and [5,5,8] have averages 4, 5 and 6 respectively. All other sub-arrays of size 3 have averages less than 4 (the threshold).</p><p><strong>Constraints:-</strong></p><p>1 &lt;= arr.length &lt;= 10⁵<br>1 &lt;= arr[i] &lt;= 10⁴<br>1 &lt;= k &lt;= arr.length<br>0 &lt;= threshold &lt;= 10⁴</p><p><strong>Approach Required:- <em>“</em></strong><em>Sliding Window Technique”</em> .</p><p><strong>My Approach to solve this Problem :-</strong></p><ol><li>Firstly we calculated the sum of the first k elements.</li><li>And after that we apply the sliding window Technique on the remaining elements of the array.</li><li>Rather than calculating the average we simply check if the sum is greater than or equal to <strong>threshold * k</strong> .</li></ol><blockquote>→ since ( sum/k &gt;= threshold ) is equivalent to ( sum &gt;= threshold*k )</blockquote><blockquote>→ sum/k → Average</blockquote><p><strong>CODE:-</strong></p><p><strong>Approach :- Sliding Window Approach</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3gASuGxgQGsgGPmbYSDmGQ.png" /><figcaption><strong>Sliding Window Approach</strong></figcaption></figure><p><strong>Complexity Analysis:-</strong></p><blockquote><strong><em>Time Complexity : O(N)</em></strong></blockquote><blockquote><strong><em>Space Complexity : O(1)</em></strong></blockquote><p>Hope you might learned the approach required to solve this Problems. I tried to explain the Problem using Sliding Window Techhnique.</p><p>Hope this <strong>“Daily Coding Problem with Yash Gaherwar”</strong> initiative will help many to solve at least one Coding Problem daily and remove their fear related to Programming and maintaining consistency.</p><p>Join the Programming Community:- <strong>“Programming with DPwala”</strong></p><p>Link for Joining:- <a href="https://www.linkedin.com/groups/9249623/">Programming with DPwala</a></p><p><a href="https://www.linkedin.com/groups/9249623/">https://www.linkedin.com/groups/9249623/</a></p><p>Stay connected with me on Medium and LinkedIn for daily updates..</p><p><strong>LinkedIn:- </strong><a href="https://www.linkedin.com/in/yash-gaherwar-21a671208/"><strong>https://www.linkedin.com/in/yash-gaherwar-21a671208/</strong></a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=954c25766566" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[DP-23 (DP: Kadanes + Prefix Sum + Suffix Sum) : “K-Concatenation Maximum Sum”]]></title>
            <link>https://medium.com/@yashgaherwar2002/dp-23-dp-kadanes-prefix-sum-suffix-sum-k-concatenation-maximum-sum-39eb41107de4?source=rss-7dc54494f608------2</link>
            <guid isPermaLink="false">https://medium.com/p/39eb41107de4</guid>
            <category><![CDATA[kadanes-algorithm]]></category>
            <category><![CDATA[data-structure-algorithm]]></category>
            <category><![CDATA[competitive-programming]]></category>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[dynamic-programming]]></category>
            <dc:creator><![CDATA[Yash Gaherwar]]></dc:creator>
            <pubDate>Sat, 15 Oct 2022 01:00:23 GMT</pubDate>
            <atom:updated>2022-10-15T01:00:23.846Z</atom:updated>
            <content:encoded><![CDATA[<h3>DP-23 (DP: Kadanes + Prefix Sum + Suffix Sum) : “K-Concatenation Maximum Sum”</h3><p>Lets start with the Twenty Third problem of the “Daily DP problem with <a href="https://medium.com/u/7dc54494f608">Yash Gaherwar</a>”.</p><h4>Problem Statement :-</h4><p>Given an integer array arr and an integer k, modify the array by repeating it k times.</p><p>For example, if arr = [1, 2] and k = 3 then the modified array will be [1, 2, 1, 2, 1, 2].</p><p>Return the maximum sub-array sum in the modified array. Note that the length of the sub-array can be 0 and its sum in that case is 0.</p><p>As the answer can be very large, return the answer modulo 10⁹ + 7.</p><p><strong>Sample Input I :- </strong>arr = [1,2], k = 3</p><p><strong>Output :-</strong> 9</p><p><strong>Sample Input II :- </strong>arr = [1,-2,1], k = 5</p><p><strong>Output :-</strong> 2</p><p><strong>Constraints:-</strong></p><p>1 &lt;= arr.length &lt;= 10⁵<br>1 &lt;= k &lt;= 10⁵<br>-10⁴ &lt;= arr[i] &lt;= 10⁴</p><p><strong>Approach Required:- Dynamic Programming (Kadanes Algorithm), Prefix sum, Suffix sum.</strong></p><p><strong>My Approach to solve this Problem :-</strong></p><blockquote>Kadanes Algorithm → Iterative Dynamic Programming Algorithm</blockquote><p>To solve this Problem we need to consider three important conditions which is very necessary.</p><ol><li>We may get our answer by calculating Largest Sum Contiguous Subarray which is a famous Kadanes Algorithm. This is our first case.</li><li>Second answer may come from calculating maximum from Prefix Sum (maxi1) and maximum from suffix sum (maxi2). (maxi1 + maxi2). This is our second case.</li><li>Third and last case is by considering the whole array. means by considering maxi1 + maxi2 and the most important:-</li></ol><blockquote>→ Sum of whole array * (k-2)</blockquote><p>Third case = maxi1 + maxi2 + (sum of whole array)*(k-2)</p><p>This is our third case.</p><p>4. Now our Final answer is:-</p><blockquote>ans = max(case1, case2, case3)</blockquote><p>5. Base Condition is when k==1</p><p>→ Simply return the Largest Sum Contiguous Subarray (kadanes Algorithm).</p><p><strong>CODE:-</strong></p><p><strong>Approach :- Dynamic Programming (Kadanes Algorithm), Prefix sum, Suffix sum.</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*EeyYDGtIgr_qfQa-9oWFEQ.png" /><figcaption><strong>Dynamic Programming Approach(Kadanes Algorithm, Prefix Sum and Suffix Sum)</strong></figcaption></figure><p><strong>Complexity Analysis:-</strong></p><blockquote><strong><em>Time Complexity : O(N)</em></strong></blockquote><blockquote><strong><em>Space Complexity : O(N)</em></strong></blockquote><p>Hope you might learned the approach required to solve this Problems. I tried to explain the Problem using Dynamic Programming (Kadanes Algorithm), Prefix sum, Suffix sum.</p><p>Hope this <strong>“Daily DP problem with Yash Gaherwar”</strong> initiative will help many to solve at least one Dynamic Programming problem daily and remove their fear related to DP.</p><p>Stay connected with me on Medium and LinkedIn for daily updates..</p><p><strong>LinkedIn:- </strong><a href="https://www.linkedin.com/in/yash-gaherwar-21a671208/"><strong>https://www.linkedin.com/in/yash-gaherwar-21a671208/</strong></a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=39eb41107de4" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>