Design and Analysis of Algorithms

In this post, we’ll cover the design and analysis of algorithms, which involve the careful creation of algorithms that are intended to work well for common problems. This article will also explore how to implement these algorithms from scratch. To do this, we’ll go over a few different methods, starting with divide and conquer strategies.

Divide and conquer strategies —

Designing algorithms is a tricky business! One way to make things easier on yourself is by using divide and conquer strategies. These approaches generally involve breaking up a problem into subproblems until you reach something easy enough to solve.

Application-

1. Quick Sort
2. Merge Sort

Greedy Algorithms —

Greedy is an algorithm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. So the problems where choosing locally optimal also leads to the global solution. This approach follows the local optimal choice of each stage with the intent of finding a global optimum solution.

Application -

1. Knapsack Problem
2. Job Sequencing
3. Minimum Spanning Tree — 1) Kruskal’s Algorithm 2)PRIM’S Algorithm
4. Shortest Path Problem-1) Dijkstra’s Algorithm

Dynamic Programming-

Dynamic programming is a technique for solving problems with overlapping subproblems and saves the result for future purposes so that we do not need to compute the result again.

Application —

1. Transitive Closure using Warshall’s Algorithm
2. 0/1 Knapsack Problem
3. All-pairs shortest path Floyd’s Algorithm
4. Travelling Salesperson problem

Backtracking -

Backtracking is an algorithmic technique for solving problems recursively by trying to build a solution incrementally and removing those solutions that fail to satisfy the constraints of the problem at any point in time is backtracking.

Application —

1. Maze Solving Problems
2. To Solve the N Queen Problem
3. The Knight’s Tour Problem.

Recurrence Relation -

A recurrence is an equation or inequality that describes a function in terms of its values on smaller inputs. To solve a Recurrence Relation means to obtain a function defined on the natural numbers that satisfy the recurrence. There are four methods for solving Recurrence:

1. Substitution Method
2. Iteration Method
3. Recursion Tree Method
4. Master Method

The beauty of this approach is that anyone who understands the basics of these Algorithms can boost his/her Competitive Programming Skills to a great extent.