fundamentals of algorithmic problem solving

Chapter: Introduction to the Design and Analysis of Algorithms

Fundamentals of Algorithmic Problem Solving

Let us start by reiterating an important point made in the introduction to this chapter:

We can consider algorithms to be procedural solutions to problems.

These solutions are not answers but specific instructions for getting answers. It is this emphasis on precisely defined constructive procedures that makes computer science distinct from other disciplines. In particular, this distinguishes it from the-oretical mathematics, whose practitioners are typically satisfied with just proving the existence of a solution to a problem and, possibly, investigating the solution’s properties.

We now list and briefly discuss a sequence of steps one typically goes through in designing and analyzing an algorithm (Figure 1.2).

Understanding the Problem

From a practical perspective, the first thing you need to do before designing an algorithm is to understand completely the problem given. Read the problem’s description carefully and ask questions if you have any doubts about the problem, do a few small examples by hand, think about special cases, and ask questions again if needed.

There are a few types of problems that arise in computing applications quite often. We review them in the next section. If the problem in question is one of them, you might be able to use a known algorithm for solving it. Of course, it helps to understand how such an algorithm works and to know its strengths and weaknesses, especially if you have to choose among several available algorithms. But often you will not find a readily available algorithm and will have to design your own. The sequence of steps outlined in this section should help you in this exciting but not always easy task.

An input to an algorithm specifies an instance of the problem the algorithm solves. It is very important to specify exactly the set of instances the algorithm needs to handle. (As an example, recall the variations in the set of instances for the three greatest common divisor algorithms discussed in the previous section.) If you fail to do this, your algorithm may work correctly for a majority of inputs but crash on some “boundary” value. Remember that a correct algorithm is not one that works most of the time, but one that works correctly for all legitimate inputs.

Do not skimp on this first step of the algorithmic problem-solving process; otherwise, you will run the risk of unnecessary rework.

Ascertaining the Capabilities of the Computational Device

Once you completely understand a problem, you need to ascertain the capabilities of the computational device the algorithm is intended for. The vast majority of 

algorithms in use today are still destined to be programmed for a computer closely resembling the von Neumann machine—a computer architecture outlined by the prominent Hungarian-American mathematician John von Neumann (1903– 1957), in collaboration with A. Burks and H. Goldstine, in 1946. The essence of this architecture is captured by the so-called random-access machine ( RAM ). Its central assumption is that instructions are executed one after another, one operation at a time. Accordingly, algorithms designed to be executed on such machines are called sequential algorithms .

The central assumption of the RAM model does not hold for some newer computers that can execute operations concurrently, i.e., in parallel. Algorithms that take advantage of this capability are called parallel algorithms . Still, studying the classic techniques for design and analysis of algorithms under the RAM model remains the cornerstone of algorithmics for the foreseeable future.

Should you worry about the speed and amount of memory of a computer at your disposal? If you are designing an algorithm as a scientific exercise, the answer is a qualified no. As you will see in Section 2.1, most computer scientists prefer to study algorithms in terms independent of specification parameters for a particular computer. If you are designing an algorithm as a practical tool, the answer may depend on a problem you need to solve. Even the “slow” computers of today are almost unimaginably fast. Consequently, in many situations you need not worry about a computer being too slow for the task. There are important problems, however, that are very complex by their nature, or have to process huge volumes of data, or deal with applications where the time is critical. In such situations, it is imperative to be aware of the speed and memory available on a particular computer system.

Choosing between Exact and Approximate Problem Solving

The next principal decision is to choose between solving the problem exactly or solving it approximately. In the former case, an algorithm is called an exact algo-rithm ; in the latter case, an algorithm is called an approximation algorithm . Why would one opt for an approximation algorithm? First, there are important prob-lems that simply cannot be solved exactly for most of their instances; examples include extracting square roots, solving nonlinear equations, and evaluating def-inite integrals. Second, available algorithms for solving a problem exactly can be unacceptably slow because of the problem’s intrinsic complexity. This happens, in particular, for many problems involving a very large number of choices; you will see examples of such difficult problems in Chapters 3, 11, and 12. Third, an ap-proximation algorithm can be a part of a more sophisticated algorithm that solves a problem exactly.

Algorithm Design Techniques

Now, with all the components of the algorithmic problem solving in place, how do you design an algorithm to solve a given problem? This is the main question this book seeks to answer by teaching you several general design techniques.

What is an algorithm design technique?

An algorithm design technique (or “strategy” or “paradigm”) is a general approach to solving problems algorithmically that is applicable to a variety of problems from different areas of computing.

Check this book’s table of contents and you will see that a majority of its chapters are devoted to individual design techniques. They distill a few key ideas that have proven to be useful in designing algorithms. Learning these techniques is of utmost importance for the following reasons.

First, they provide guidance for designing algorithms for new problems, i.e., problems for which there is no known satisfactory algorithm. Therefore—to use the language of a famous proverb—learning such techniques is akin to learning to fish as opposed to being given a fish caught by somebody else. It is not true, of course, that each of these general techniques will be necessarily applicable to every problem you may encounter. But taken together, they do constitute a powerful collection of tools that you will find quite handy in your studies and work.

Second, algorithms are the cornerstone of computer science. Every science is interested in classifying its principal subject, and computer science is no exception. Algorithm design techniques make it possible to classify algorithms according to an underlying design idea; therefore, they can serve as a natural way to both categorize and study algorithms.

Designing an Algorithm and Data Structures

While the algorithm design techniques do provide a powerful set of general ap-proaches to algorithmic problem solving, designing an algorithm for a particular problem may still be a challenging task. Some design techniques can be simply inapplicable to the problem in question. Sometimes, several techniques need to be combined, and there are algorithms that are hard to pinpoint as applications of the known design techniques. Even when a particular design technique is ap-plicable, getting an algorithm often requires a nontrivial ingenuity on the part of the algorithm designer. With practice, both tasks—choosing among the general techniques and applying them—get easier, but they are rarely easy.

Of course, one should pay close attention to choosing data structures appro-priate for the operations performed by the algorithm. For example, the sieve of Eratosthenes introduced in Section 1.1 would run longer if we used a linked list instead of an array in its implementation (why?). Also note that some of the al-gorithm design techniques discussed in Chapters 6 and 7 depend intimately on structuring or restructuring data specifying a problem’s instance. Many years ago, an influential textbook proclaimed the fundamental importance of both algo-rithms and data structures for computer programming by its very title: Algorithms + Data Structures = Programs [Wir76]. In the new world of object-oriented programming, data structures remain crucially important for both design and analysis of algorithms. We review basic data structures in Section 1.4.

Methods of Specifying an Algorithm

Once you have designed an algorithm, you need to specify it in some fashion. In Section 1.1, to give you an example, Euclid’s algorithm is described in words (in a free and also a step-by-step form) and in pseudocode. These are the two options that are most widely used nowadays for specifying algorithms.

Using a natural language has an obvious appeal; however, the inherent ambi-guity of any natural language makes a succinct and clear description of algorithms surprisingly difficult. Nevertheless, being able to do this is an important skill that you should strive to develop in the process of learning algorithms.

Pseudocode is a mixture of a natural language and programming language-like constructs. Pseudocode is usually more precise than natural language, and its usage often yields more succinct algorithm descriptions. Surprisingly, computer scientists have never agreed on a single form of pseudocode, leaving textbook authors with a need to design their own “dialects.” Fortunately, these dialects are so close to each other that anyone familiar with a modern programming language should be able to understand them all.

This book’s dialect was selected to cause minimal difficulty for a reader. For the sake of simplicity, we omit declarations of variables and use indentation to show the scope of such statements as for , if , and while . As you saw in the previous section, we use an arrow “ ← ” for the assignment operation and two slashes “ // ” for comments.

In the earlier days of computing, the dominant vehicle for specifying algo-rithms was a flowchart , a method of expressing an algorithm by a collection of connected geometric shapes containing descriptions of the algorithm’s steps. This representation technique has proved to be inconvenient for all but very simple algorithms; nowadays, it can be found only in old algorithm books.

The state of the art of computing has not yet reached a point where an algorithm’s description—be it in a natural language or pseudocode—can be fed into an electronic computer directly. Instead, it needs to be converted into a computer program written in a particular computer language. We can look at such a program as yet another way of specifying the algorithm, although it is preferable to consider it as the algorithm’s implementation.

Proving an Algorithm’s Correctness

Once an algorithm has been specified, you have to prove its correctness . That is, you have to prove that the algorithm yields a required result for every legitimate input in a finite amount of time. For example, the correctness of Euclid’s algorithm for computing the greatest common divisor stems from the correctness of the equality gcd (m, n) = gcd (n, m mod n) (which, in turn, needs a proof; see Problem 7 in Exercises 1.1), the simple observation that the second integer gets smaller on every iteration of the algorithm, and the fact that the algorithm stops when the second integer becomes 0.

For some algorithms, a proof of correctness is quite easy; for others, it can be quite complex. A common technique for proving correctness is to use mathemati-cal induction because an algorithm’s iterations provide a natural sequence of steps needed for such proofs. It might be worth mentioning that although tracing the algorithm’s performance for a few specific inputs can be a very worthwhile activ-ity, it cannot prove the algorithm’s correctness conclusively. But in order to show that an algorithm is incorrect, you need just one instance of its input for which the algorithm fails.

The notion of correctness for approximation algorithms is less straightforward than it is for exact algorithms. For an approximation algorithm, we usually would like to be able to show that the error produced by the algorithm does not exceed a predefined limit. You can find examples of such investigations in Chapter 12.

Analyzing an Algorithm

We usually want our algorithms to possess several qualities. After correctness, by far the most important is efficiency . In fact, there are two kinds of algorithm efficiency: time efficiency , indicating how fast the algorithm runs, and space ef-ficiency , indicating how much extra memory it uses. A general framework and specific techniques for analyzing an algorithm’s efficiency appear in Chapter 2.

Another desirable characteristic of an algorithm is simplicity . Unlike effi-ciency, which can be precisely defined and investigated with mathematical rigor, simplicity, like beauty, is to a considerable degree in the eye of the beholder. For example, most people would agree that Euclid’s algorithm is simpler than the middle-school procedure for computing gcd (m, n) , but it is not clear whether Eu-clid’s algorithm is simpler than the consecutive integer checking algorithm. Still, simplicity is an important algorithm characteristic to strive for. Why? Because sim-pler algorithms are easier to understand and easier to program; consequently, the resulting programs usually contain fewer bugs. There is also the undeniable aes-thetic appeal of simplicity. Sometimes simpler algorithms are also more efficient than more complicated alternatives. Unfortunately, it is not always true, in which case a judicious compromise needs to be made.

Yet another desirable characteristic of an algorithm is generality . There are, in fact, two issues here: generality of the problem the algorithm solves and the set of inputs it accepts. On the first issue, note that it is sometimes easier to design an algorithm for a problem posed in more general terms. Consider, for example, the problem of determining whether two integers are relatively prime, i.e., whether their only common divisor is equal to 1. It is easier to design an algorithm for a more general problem of computing the greatest common divisor of two integers and, to solve the former problem, check whether the gcd is 1 or not. There are situations, however, where designing a more general algorithm is unnecessary or difficult or even impossible. For example, it is unnecessary to sort a list of n numbers to find its median, which is its n/ 2 th smallest element. To give another example, the standard formula for roots of a quadratic equation cannot be generalized to handle polynomials of arbitrary degrees.

As to the set of inputs, your main concern should be designing an algorithm that can handle a set of inputs that is natural for the problem at hand. For example, excluding integers equal to 1 as possible inputs for a greatest common divisor algorithm would be quite unnatural. On the other hand, although the standard formula for the roots of a quadratic equation holds for complex coefficients, we would normally not implement it on this level of generality unless this capability is explicitly required.

If you are not satisfied with the algorithm’s efficiency, simplicity, or generality, you must return to the drawing board and redesign the algorithm. In fact, even if your evaluation is positive, it is still worth searching for other algorithmic solutions. Recall the three different algorithms in the previous section for computing the greatest common divisor: generally, you should not expect to get the best algorithm on the first try. At the very least, you should try to fine-tune the algorithm you already have. For example, we made several improvements in our implementation of the sieve of Eratosthenes compared with its initial outline in Section 1.1. (Can you identify them?) You will do well if you keep in mind the following observation of Antoine de Saint-Exupery,´ the French writer, pilot, and aircraft designer: “A designer knows he has arrived at perfection not when there is no longer anything to add, but when there is no longer anything to take away.” 1

Coding an Algorithm

  Most algorithms are destined to be ultimately implemented as computer pro-grams. Programming an algorithm presents both a peril and an opportunity. The peril lies in the possibility of making the transition from an algorithm to a pro-gram either incorrectly or very inefficiently. Some influential computer scientists strongly believe that unless the correctness of a computer program is proven with full mathematical rigor, the program cannot be considered correct. They have developed special techniques for doing such proofs (see [Gri81]), but the power of these techniques of formal verification is limited so far to very small programs.

As a practical matter, the validity of programs is still established by testing. Testing of computer programs is an art rather than a science, but that does not mean that there is nothing in it to learn. Look up books devoted to testing and debugging; even more important, test and debug your program thoroughly whenever you implement an algorithm.

Also note that throughout the book, we assume that inputs to algorithms belong to the specified sets and hence require no verification. When implementing algorithms as programs to be used in actual applications, you should provide such verifications.

Of course, implementing an algorithm correctly is necessary but not sufficient: you would not like to diminish your algorithm’s power by an inefficient implemen-tation. Modern compilers do provide a certain safety net in this regard, especially when they are used in their code optimization mode. Still, you need to be aware of such standard tricks as computing a loop’s invariant (an expression that does not change its value) outside the loop, collecting common subexpressions, replac-ing expensive operations by cheap ones, and so on. (See [Ker99] and [Ben00] for a good discussion of code tuning and other issues related to algorithm program-ming.) Typically, such improvements can speed up a program only by a constant factor, whereas a better algorithm can make a difference in running time by orders of magnitude. But once an algorithm is selected, a 10–50% speedup may be worth an effort.

A working program provides an additional opportunity in allowing an em-pirical analysis of the underlying algorithm. Such an analysis is based on timing the program on several inputs and then analyzing the results obtained. We dis-cuss the advantages and disadvantages of this approach to analyzing algorithms in Section 2.6.

In conclusion, let us emphasize again the main lesson of the process depicted in Figure 1.2:

As a rule, a good algorithm is a result of repeated effort and rework.

Even if you have been fortunate enough to get an algorithmic idea that seems perfect, you should still try to see whether it can be improved.

Actually, this is good news since it makes the ultimate result so much more enjoyable. (Yes, I did think of naming this book The Joy of Algorithms .) On the other hand, how does one know when to stop? In the real world, more often than not a project’s schedule or the impatience of your boss will stop you. And so it should be: perfection is expensive and in fact not always called for. Designing an algorithm is an engineering-like activity that calls for compromises among competing goals under the constraints of available resources, with the designer’s time being one of the resources.

In the academic world, the question leads to an interesting but usually difficult investigation of an algorithm’s optimality . Actually, this question is not about the efficiency of an algorithm but about the complexity of the problem it solves: What is the minimum amount of effort any algorithm will need to exert to solve the problem? For some problems, the answer to this question is known. For example, any algorithm that sorts an array by comparing values of its elements needs about n log 2 n comparisons for some arrays of size n (see Section 11.2). But for many seemingly easy problems such as integer multiplication, computer scientists do not yet have a final answer.

Another important issue of algorithmic problem solving is the question of whether or not every problem can be solved by an algorithm. We are not talking here about problems that do not have a solution, such as finding real roots of a quadratic equation with a negative discriminant. For such cases, an output indicating that the problem does not have a solution is all we can and should expect from an algorithm. Nor are we talking about ambiguously stated problems. Even some unambiguous problems that must have a simple yes or no answer are “undecidable,” i.e., unsolvable by any algorithm. An important example of such a problem appears in Section 11.3. Fortunately, a vast majority of problems in practical computing can be solved by an algorithm.

Before leaving this section, let us be sure that you do not have the misconception—possibly caused by the somewhat mechanical nature of the diagram of Figure 1.2—that designing an algorithm is a dull activity. There is nothing further from the truth: inventing (or discovering?) algorithms is a very creative and rewarding process. This book is designed to convince you that this is the case.

Exercises 1.2

             Old World puzzle A peasant finds himself on a riverbank with a wolf, a goat, and a head of cabbage. He needs to transport all three to the other side of the river in his boat. However, the boat has room for only the peasant himself and one other item (either the wolf, the goat, or the cabbage). In his absence, the wolf would eat the goat, and the goat would eat the cabbage. Solve this problem for the peasant or prove it has no solution. (Note: The peasant is a vegetarian but does not like cabbage and hence can eat neither the goat nor the cabbage to help him solve the problem. And it goes without saying that the wolf is a protected species.)

            New World puzzle There are four people who want to cross a rickety bridge; they all begin on the same side. You have 17 minutes to get them all across to the other side. It is night, and they have one flashlight. A maximum of two people can cross the bridge at one time. Any party that crosses, either one or two people, must have the flashlight with them. The flashlight must be walked back and forth; it cannot be thrown, for example. Person 1 takes 1 minute to cross the bridge, person 2 takes 2 minutes, person 3 takes 5 minutes, and person 4 takes 10 minutes. A pair must walk together at the rate of the slower person’s pace. (Note: According to a rumor on the Internet, interviewers at a well-known software company located near Seattle have given this problem to interviewees.)

            Which of the following formulas can be considered an algorithm for comput-ing the area of a triangle whose side lengths are given positive numbers a , b , and c ?

            Write pseudocode for an algorithm for finding real roots of equation ax 2 + bx + c = 0 for arbitrary real coefficients a, b, and c. (You may assume the availability of the square root function sqrt (x). )

            Describe the standard algorithm for finding the binary representation of a positive decimal integer

                     in English.

                     in pseudocode.

            Describe the algorithm used by your favorite ATM machine in dispensing cash. (You may give your description in either English or pseudocode, which-ever you find more convenient.)

            a.  Can the problem of computing the number π be solved exactly?

                     How many instances does this problem have?

Look up an algorithm for this problem on the Internet.

                                                                    Give an example of a problem other than computing the greatest common divisor for which you know more than one algorithm. Which of them is simpler? Which is more efficient?

                                                                    Consider the following algorithm for finding the distance between the two closest elements in an array of numbers.

ALGORITHM                       MinDistance (A [0 ..n − 1] )

//Input: Array A [0 ..n − 1] of numbers

//Output: Minimum distance between two of its elements dmin ← ∞

for i ← 0 to n − 1 do

for j ← 0 to n − 1 do

if i  = j and |A[i] − A[j ]| < dmin dmin ← |A[i] − A[j ]|

return dmin

Make as many improvements as you can in this algorithmic solution to the problem. If you need to, you may change the algorithm altogether; if not, improve the implementation given.

One of the most influential books on problem solving, titled How To Solve It [Pol57], was written by the Hungarian-American mathematician George Polya´ (1887–1985). Polya´ summarized his ideas in a four-point summary. Find this summary on the Internet or, better yet, in his book, and compare it with the plan outlined in Section 1.2. What do they have in common? How are they different?

Related Topics

Privacy Policy , Terms and Conditions , DMCA Policy and Compliant

Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.

• Data Structure & Algorithm Classes (Live)
• System Design (Live)
• DevOps(Live)
• Explore More Live Courses
• Interview Preparation Course
• Data Science (Live)
• GATE CS & IT 2024
• Data Structure & Algorithm-Self Paced(C++/JAVA)
• Data Structures & Algorithms in Python
• Explore More Self-Paced Courses
• C++ Programming - Beginner to Advanced
• Java Programming - Beginner to Advanced
• C Programming - Beginner to Advanced
• Full Stack Development with React & Node JS(Live)
• Java Backend Development(Live)
• Android App Development with Kotlin(Live)
• Python Backend Development with Django(Live)
• Complete Data Science Program(Live)
• Mastering Data Analytics
• DevOps Engineering - Planning to Production
• CBSE Class 12 Computer Science
• School Guide
• All Courses
• Linked List
• Binary Tree
• Binary Search Tree
• Advanced Data Structure
• All Data Structures
• Asymptotic Analysis
• Worst, Average and Best Cases
• Asymptotic Notations
• Little o and little omega notations
• Lower and Upper Bound Theory
• Analysis of Loops
• Solving Recurrences
• Amortized Analysis
• What does 'Space Complexity' mean ?
• Pseudo-polynomial Algorithms
• Polynomial Time Approximation Scheme
• A Time Complexity Question
• Searching Algorithms
• Sorting Algorithms
• Graph Algorithms
• Pattern Searching
• Geometric Algorithms
• Mathematical
• Bitwise Algorithms
• Randomized Algorithms
• Greedy Algorithms
• Dynamic Programming
• Divide and Conquer
• Backtracking
• Branch and Bound
• All Algorithms
• Company Preparation
• Practice Company Questions
• Interview Experiences
• Experienced Interviews
• Internship Interviews
• Competitive Programming
• Design Patterns
• System Design Tutorial
• Multiple Choice Quizzes
• Go Language
• Tailwind CSS
• Foundation CSS
• Materialize CSS
• Semantic UI
• Angular PrimeNG
• Angular ngx Bootstrap
• jQuery Mobile
• jQuery EasyUI
• React Bootstrap
• React Rebass
• React Desktop
• React Suite
• ReactJS Evergreen
• ReactJS Reactstrap
• BlueprintJS
• TensorFlow.js
• English Grammar
• School Programming
• Number System
• Trigonometry
• Probability
• Mensuration
• Class 8 Syllabus
• Class 9 Syllabus
• Class 10 Syllabus
• Class 11 Syllabus
• Class 12 Syllabus
• Class 8 Notes
• Class 9 Notes
• Class 10 Notes
• Class 11 Notes
• Class 12 Notes
• Class 8 Formulas
• Class 9 Formulas
• Class 10 Formulas
• Class 11 Formulas
• Class 8 Maths Solution
• Class 9 Maths Solution
• Class 10 Maths Solution
• Class 11 Maths Solution
• Class 12 Maths Solution
• Class 7 SS Syllabus
• Class 8 SS Syllabus
• Class 9 SS Syllabus
• Class 10 SS Syllabus
• Class 7 Notes
• History Class 7
• History Class 8
• History Class 9
• Geo. Class 7
• Geo. Class 8
• Geo. Class 9
• Civics Class 7
• Civics Class 8
• Business Studies (Class 11th)
• Microeconomics (Class 11th)
• Statistics for Economics (Class 11th)
• Business Studies (Class 12th)
• Accountancy (Class 12th)
• Macroeconomics (Class 12th)
• Machine Learning
• Data Science
• Mathematics
• Operating System
• Computer Networks
• Computer Organization and Architecture
• Theory of Computation
• Compiler Design
• Digital Logic
• Software Engineering
• GATE 2024 Live Course
• GATE Computer Science Notes
• Last Minute Notes
• GATE CS Solved Papers
• GATE CS Original Papers and Official Keys
• GATE CS 2023 Syllabus
• Important Topics for GATE CS
• GATE 2023 Important Dates
• Software Design Patterns
• HTML Cheat Sheet
• CSS Cheat Sheet
• Bootstrap Cheat Sheet
• JS Cheat Sheet
• jQuery Cheat Sheet
• Angular Cheat Sheet
• Facebook SDE Sheet
• Amazon SDE Sheet
• Apple SDE Sheet
• Netflix SDE Sheet
• Google SDE Sheet
• Wipro Coding Sheet
• Infosys Coding Sheet
• TCS Coding Sheet
• Cognizant Coding Sheet
• HCL Coding Sheet
• FAANG Coding Sheet
• Love Babbar Sheet
• Mass Recruiter Sheet
• Product-Based Coding Sheet
• Company-Wise Preparation Sheet
• Array Sheet
• String Sheet
• Graph Sheet
• ISRO CS Original Papers and Official Keys
• ISRO CS Solved Papers
• ISRO CS Syllabus for Scientist/Engineer Exam
• UGC NET CS Notes Paper II
• UGC NET CS Notes Paper III
• UGC NET CS Solved Papers
• Campus Ambassador Program
• School Ambassador Program
• Geek of the Month
• Campus Geek of the Month
• Placement Course
• Testimonials
• Student Chapter
• Geek on the Top
• Geography Notes
• History Notes
• Science & Tech. Notes
• Ethics Notes
• Polity Notes
• Economics Notes
• UPSC Previous Year Papers
• SSC CGL Syllabus
• General Studies
• Subjectwise Practice Papers
• Previous Year Papers
• SBI Clerk Syllabus
• General Awareness
• Quantitative Aptitude
• Reasoning Ability
• SBI Clerk Practice Papers
• SBI PO Syllabus
• SBI PO Practice Papers
• IBPS PO 2022 Syllabus
• English Notes
• Reasoning Notes
• Mock Question Papers
• IBPS Clerk Syllabus
• Apply for a Job
• Apply through Jobathon
• Hire through Jobathon
• All DSA Problems
• Problem of the Day
• GFG SDE Sheet
• Top 50 Array Problems
• Top 50 String Problems
• Top 50 Tree Problems
• Top 50 Graph Problems
• Top 50 DP Problems
• Solving For India-Hackthon
• GFG Weekly Coding Contest
• Job-A-Thon: Hiring Challenge
• BiWizard School Contest
• All Contests and Events
• Saved Videos
• What's New ?
• Data Structures
• Interview Preparation
• Topic-wise Practice
• Latest Blogs
• Write & Earn
• Web Development

Table of Contents

• Write Articles
• Pick Topics to write
• Guidelines to Write
• Get Technical Writing Internship
• Write an Interview Experience
• What is Algorithm | Introduction to Algorithms
• What is an Algorithm? Definition, Types, Complexity, Examples
• Algorithms Design Techniques
• What is algorithm and why analysis of it is important?
• Asymptotic Notation and Analysis (Based on input size) in Complexity Analysis of Algorithms
• Worst, Average and Best Case Analysis of Algorithms
• Types of Asymptotic Notations in Complexity Analysis of Algorithms
• How to Analyse Loops for Complexity Analysis of Algorithms
• How to analyse Complexity of Recurrence Relation
• Introduction to Amortized Analysis
• Backtracking Algorithms
• Mathematical Algorithms
• Graph Data Structure And Algorithms
• Branch and Bound Algorithm
• The Role of Algorithms in Computing
• Most important type of Algorithms
• Discuss(230+)

Learn more about Algorithms in DSA Self Paced Course Practice Problems on all Algorithms Recent articles on Algorithms

What is an Algorithm?

The word Algorithm means ” A  set of rules to be followed in calculations or other problem-solving operations ” Or ” A procedure for solving a mathematical problem in a finite number of steps that frequently by recursive operations “. 

Therefore Algorithm refers to a sequence of finite steps to solve a particular problem.

Algorithms can be simple and complex depending on what you want to achieve.

Types of Algorithms:

There are several types of algorithms available. Some important algorithms are:

1. Brute Force Algorithm: It is the simplest approach for a problem. A brute force algorithm is the first approach that comes to finding when we see a problem.

2. Recursive Algorithm : A recursive algorithm is based on recursion . In this case, a problem is broken into several sub-parts and called the same function again and again.

3. Backtracking Algorithm : The backtracking algorithm basically builds the solution by searching among all possible solutions. Using this algorithm, we keep on building the solution following criteria. Whenever a solution fails we trace back to the failure point and build on the next solution and continue this process till we find the solution or all possible solutions are looked after.

4. Searching Algorithm : Searching algorithms are the ones that are used for searching elements or groups of elements from a particular data structure. They can be of different types based on their approach or the data structure in which the element should be found.

5. Sorting Algorithm : Sorting is arranging a group of data in a particular manner according to the requirement. The algorithms which help in performing this function are called sorting algorithms. Generally sorting algorithms are used to sort groups of data in an increasing or decreasing manner.

6. Hashing Algorithm : Hashing algorithms work similarly to the searching algorithm. But they contain an index with a key ID. In hashing, a key is assigned to specific data.

7. Divide and Conquer Algorithm : This algorithm breaks a problem into sub-problems, solves a single sub-problem and merges the solutions together to get the final solution. It consists of the following three steps:

8. Greedy Algorithm : In this type of algorithm the solution is built part by part. The solution of the next part is built based on the immediate benefit of the next part. The one solution giving the most benefit will be chosen as the solution for the next part.

9. Dynamic Programming Algorithm : This algorithm uses the concept of using the already found solution to avoid repetitive calculation of the same part of the problem. It divides the problem into smaller overlapping subproblems and solves them.

10. Randomized Algorithm : In the randomized algorithm we use a random number so it gives immediate benefit. The random number helps in deciding the expected outcome.

• Analysis of Algorithms
• Searching and Sorting
• Bit Algorithms

Analysis of Algorithms:

• What does ‘Space Complexity’ mean?
• Accounting Method | Amortized Analysis
• Potential Method in Amortized Analysis

Searching and Sorting:

• Introduction to Searching Algorithms
• Introduction to Sorting Algorithm
• Stable and Unstable Sorting Algorithms
• Lower bound for comparison based sorting algorithms
• Can Run Time Complexity of a comparison-based sorting algorithm be less than N logN?
• Which sorting algorithm makes minimum number of memory writes?

Greedy Algorithms:

• Introduction to Greedy Algorithms
• Activity Selection Problem
• Huffman Coding
• Job Sequencing Problem
• Quiz on Greedy Algorithms
• Minimum Number of Platforms Required for a Railway/Bus Station

Dynamic Programming:

• Introduction to Dynamic Programming
• Overlapping Subproblems Property
• Optimal Substructure Property
• Longest Increasing Subsequence
• Longest Common Subsequence
• Min Cost Path
• Coin Change
• Matrix Chain Multiplication
• 0-1 Knapsack Problem
• Longest Palindromic Subsequence
• Palindrome Partitioning

Pattern Searching:

• Introduction to Pattern Searching
• Naive Pattern Searching
• KMP Algorithm
• Rabin-Karp Algorithm
• Pattern Searching using a Trie of all Suffixes
• Aho-Corasick Algorithm for Pattern Searching
• Z algorithm (Linear time pattern searching Algorithm)

Backtracking:

• Introduction to Backtracking
• Print all permutations of a given string
• The Knight’s tour problem
• Rat in a Maze
• N Queen Problem
• m Coloring Problem
• Hamiltonian Cycle

Divide and Conquer:

• Introduction to Divide and Conquer
• Write your own pow(x, n) to calculate x*n
• Count Inversions
• Closest Pair of Points
• Strassen’s Matrix Multiplication

Geometric Algorithm:

• Introduction to Geometric Algorithms
• Closest Pair of Points | O(nlogn) Implementation
• How to check if a given point lies inside or outside a polygon?
• How to check if two given line segments intersect?
• Given n line segments, find if any two segments intersect
• How to check if given four points form a square
• Convex Hull using Jarvis’ Algorithm or Wrapping

Mathematical Algorithms:

• Introduction to Mathematical Algorithms
• Write an Efficient Method to Check if a Number is Multiple of 3
• Write a program to add two numbers in base 14
• Program for Fibonacci numbers
• Average of a stream of numbers
• Multiply two integers without using multiplication, division and bitwise operators, and no loops
• Babylonian method for square root
• Sieve of Eratosthenes
• Pascal’s Triangle
• Given a number, find the next smallest palindrome
• Program to add two polynomials
• Multiply two polynomials
• Count trailing zeroes in factorial of a number

Bitwise Algorithms:

• Introduction to Bitwise Algorithms
• Little and Big Endian
• Detect opposite signs
• Turn off the rightmost set bit
• Rotate bits
• Next higher number with same number of set bits
• Swap two nibbles in a byte

Graph Algorithms:

• Introduction to Graph Algorithms
• Cycles in Graph
• Shortest paths
• Topological Sorting
• Connectivity

Randomized Algorithms:

• Introduction to Randomized Algorithms
• Linearity of Expectation
• Expected Number of Trials until Success
• Randomized Algorithms | Set 0 (Mathematical Background)
• Randomized Algorithms | Set 1 (Introduction and Analysis)
• Randomized Algorithms | Set 2 (Classification and Applications)
• Randomized Algorithms | Set 3 (1/2 Approximate Median)
• Reservoir Sampling

Branch and Bound:

• Branch and Bound | Set 1 (Introduction with 0/1 Knapsack)
• Branch and Bound | Set 2 (Implementation of 0/1 Knapsack)
• Branch and Bound | Set 3 (8 puzzle Problem)
• Branch And Bound | Set 4 (Job Assignment Problem)
• Branch and Bound | Set 5 (N Queen Problem)
• Branch And Bound | Set 6 (Traveling Salesman Problem)
• NP Complete
• Analysis of Algorithms (Recurrences)
• Graph Traversals
• Graph Shortest Paths
• Graph Minimum Spanning Tree

Please see Data Structures and Advanced Data Structures for Graph, Binary Tree, BST and Linked List based algorithms.

Start Your Coding Journey Now!

We've updated our privacy policy. Click here to review the details. Tap here to review the details.

Activate your 30 day free trial to unlock unlimited reading.

Algorithmic problem solving

You are reading a preview.

Activate your 30 day free trial to continue reading.

Check these out next

Download to read offline

Recommended

More Related Content

Slideshows for you (20).

Similar to Algorithmic problem solving (20)

More from Prabhakaran V M (8)

Recently uploaded (20)

• 1. V.M.Prabhakaran, Department of CSE, KIT- Coimbatore Problem Solving and Python Programming 1
• 2. Definition • Algorithms are procedural solutions to problems. • These solutions are not answers but specific instructions for getting answers. Problem Solving and Python Programming 2
• 3. Techniques are, • Understanding the problem • Ascertain the capabilities of the computational device • Exact/approximate solution • Decide on the appropriate data structure • Algorithm design technique • Methods of specifying an algorithm • Proving an algorithm correctness • Analyzing an algorithm • Coding an algorithm Problem Solving and Python Programming 3
• 4. Algorithm design and Analysis process Problem Solving and Python Programming 4
• 5. 1.Understanding the problem • The Problem given should be understood properly. • Creating an algorithm is an art which may never be fully automated. • An input to an algorithm specifies an instance of the problem the algorithm solves. • Correct algorithm should work for all possible inputs. Problem Solving and Python Programming 5
• 6. 2. Ascertain the capabilities of the computational device • The second step is to ascertain the capabilities of a machine. • This can be done by knowing the type of the architecture, speed and memory availability. • Computational device of the algorithm is intended for sequential algorithms and parallel algorithms. Problem Solving and Python Programming 6
• 7. 3. Exact/approximate solution • Once algorithm is devised, it is necessary to show that it compute answer for all the possible inputs. • The solution is stated in two forms: • Solving the problem exactly is called an Exact solution • Solving it approximately is called approximate solution. • Examples: Finding a square root of number Problem Solving and Python Programming 7
• 8. 4. Decide on the appropriate data structure • Data structures remain important for both design and analysis of algorithms. • Data structures can be defined as a particular scheme of organizing related data items. • Some of the elementary data structures are arrays, lists, set. • Algorithm + Data Structure= Programs Problem Solving and Python Programming 8
• 9. 5. Algorithm design technique • General approach to solving problem algorithmically that is applicable to a variety of problems from different areas of computing. • Some important design techniques are, – Brute force – Greedy method – Divide and conquer – Dynamic programming – Backtracking – Linear programming Problem Solving and Python Programming 9
• 10. 6. Methods of specifying an algorithm • There are mainly two options for specifying an algorithm, – Use of natural language – Pseudo code and Flowcharts Problem Solving and Python Programming 10
• 11. 7. Proving an algorithm correctness • Correctness has to be proved for every algorithm. • To prove that the algorithm yields a required result for every legitimate input in a finite amount of time. • A proof of correctness requires that the solution to be stated in two forms : Assertions that deals about input and output variables of the program and Specifications that is expressed in predicate calculus. Problem Solving and Python Programming 11
• 12. 8. Analyzing an algorithm • There are two kinds of algorithm efficiency: time and space efficiency. • Time Efficiency : Indicates how fast the algorithm runs. • Space Efficiency : Indicates how much extra memory the algorithm needs. • Simpler algorithms are easier to understand and program, the resulting programs will be easier to debug. Problem Solving and Python Programming 12
• 13. 9. Coding an algorithm • Program the algorithm by using programming language. • Formally verification is done through small programs. • Validity is done through testing and debugging. • A good algorithm is a result of repeated effort and work. Problem Solving and Python Programming 13

Share Clipboard

Public clipboards featuring this slide, select another clipboard.

Looks like you’ve clipped this slide to already.

You just clipped your first slide!

Create a clipboard

Get slideshare without ads, special offer to slideshare readers, just for you: free 60-day trial to the world’s largest digital library..

The SlideShare family just got bigger. Enjoy access to millions of ebooks, audiobooks, magazines, and more from Scribd.

You have now unlocked unlimited access to 20M+ documents!

Unlimited Reading

Learn faster and smarter from top experts

Unlimited Downloading

Download to take your learnings offline and on the go

Instant access to millions of ebooks, audiobooks, magazines, podcasts and more.

Read and listen offline with any device.

Free access to premium services like Tuneln, Mubi and more.

Help us keep SlideShare free

It appears that you have an ad-blocker running. By whitelisting SlideShare on your ad-blocker, you are supporting our community of content creators.

We've updated our privacy policy.

We’ve updated our privacy policy so that we are compliant with changing global privacy regulations and to provide you with insight into the limited ways in which we use your data.

You can read the details below. By accepting, you agree to the updated privacy policy.

Class Notes: Algorithmic Thinking

Lecture video optional reading problem solving with programming programming patterns top-down design practice, lecture video, 1/31/19, optional reading.

• Or you can read the entire book: Polya, How to Solve It
• Wikipedia section on Common Barriers to Problem Solving

Problem Solving with Programming

• Define the problem precisely .
• Generate test cases based on the prompt, or carefully read through test cases if they're provided.
• Make sure you can restate the problem in your own words, or explain it to someone else.
• Translate a provided algorithm into code? You can skip to the Step 3.
• Apply a known algorithm pattern to the problem? You can skip to Step 2.4.
• Generate an algorithm to solve a problem? Keep reading!
• Induction : Investigate several examples (test cases) to find a pattern that can be generalized into an algorithm.
• Top-Down Design: Break down a complex problem into several simpler problems, then solve each of the simpler problems individually. See more here
• Human Computer : Pretend that you need to carry out the task by hand. Determine the steps you would take in order to complete the task.
• Clarity : How clear is the approach to you?
• Simplicity : How straightforward will the approach be to implement?
• Efficiency : How much work will the algorithm need to do?
• Generality : How well will this algorithm adapt to new inputs?
• Future concerns (after more CS courses) : usability, accessibility, security, privacy, testability, reliability, scalability, compatibility, extensibility, durability, maintainability, portability, provability, ...
• If you need to remember a thing, give it a name- those names will later become variables.
• Write the test cases that you generated in Step 1.
• Review the relevant course materials to find a programming tool that approximately meets your need.
• Experiment with that programming tool in the interpreter until you understand how it works.
• Apply the new concept to the step in your algorithm.
• Run your function on a test input to make sure it works. If your code has a syntax or runtime error, use debugging to identify the problem and fix it.
• Run your test cases on the code to make sure they all pass. If a test case fails, use debugging to identify the algorithmic problem and fix it.
• Once all test cases pass, read over your code and make sure it makes sense based on common sense.
• (After the deadline) Discuss and compare your solution with others to learn about alternative approaches to solving the problem.

Programming Patterns

• There are many algorithmic patterns that appear in various problems, patterns which can be adapted to suit new circumstances at need. We'll see many of these patterns in class; for now, here are a few common patterns from the first weeks of class.
• nthSomething def nthSomething(n): found = 0 guess = 0 while found <= n: guess += 1 if isSomething(guess): found += 1 return guess
• propertyTrueForAll def propertyTrueForAll(s): for c in s: if property(c) == False: return False return True
• countProperty def countProperty(s): count = 0 for c in s: if property(c) == True: count += 1 return count
• mostCommonItem def mostCommonItem(s): bestCount = 0 bestItem = None for c in s: tmpCount = count(s, c) if tmpCount > bestCount: bestCount = tmpCount bestItem = c elif tmpCount == bestCount and c > bestItem: bestItem = c return bestItem

Top-Down Design

• We often ask you to solve problems that are too complicated to be solved by one function alone. In these cases, you will need to break the problem down into sub-problems that can be mapped directly to helper functions.
• To identify a sub-problem, start writing the algorithm out. When you get to a step that seems too complicated, imagine you have a helper function that can solve that step. If you can write the function by including a call to this imaginary function, you've taken a step towards solving the problem! The process can then be repeated on the helper functions until the solution is complete.
• When testing multi-function problems, test the simplest functions first. It's important to ensure that your helper functions are working before you move on to test the main function.
• Example: nthThreeDigitPrime # First, we can write the part that we know how to do already: a basic nth function. def nthThreeDigitPrime(n): found = 0 guess = 0 while found <= n: guess += 1 if isThreeDigitPrime(guess): found += 1 return guess # Next, break down the problem further def isThreeDigitPrime(n): return hasThreeDigits(n) and isPrime(n) # Once the helper functions seem simple enough, write them directly. def hasThreeDigits(n): return 100 <= n <= 999 def isPrime(n): if n < 2: return False for factor in range(2, n): if n % factor == 0: return False return True # Start testing with isPrime and hasThreeDigits, then isThreeDigitPrime. # Finally test nthThreeDigitPrime, and you're done!
• In the end, the best way to learn problem solving is to practice with feedback . If you're struggling with problem solving, ask a TA or a friend to sit with you while you while you work through designing algorithms for practice problems, or ask them to demonstrate how they approach problem solving themselves. Practice should eventually lead to better understanding of how to approach problem solving in general.