fundamentals of algorithmic problem solving javatpoint

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-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.

What are the Fundamentals of algorithmic problem solving in Data Structures

In this blog, we are going to learn about the Fundamentals of algorithmic problem solving in Data Structures.

Fundamentals of algorithmic problem solving

• Understanding the problem.
• Ascertaining the capabilities of a computational device.
• Choosing between exact and approximate problem solving.
• Deciding an appropriate Data Structure.
• Algorithm design techniques.
• Methods of specifying an algorithm.
• Proving an algorithms correctness.
• Analyzing an algorithm.
• Coding an algorithm.

1. Understanding the problem

• Understand the given problem completely.
• Read the problem description carefully.
• Ask doubts about the problem.
• Do few examples.
• Think about special cases like boundary value.
• Know about the already known algorithms for solving that problem.
• Clear about the input to an algorithm.

2. Ascertaining the Capabilities of a computational device

• Sequential Algorithms: Instructions are executed one after another and one operation at a time.
• Algorithms designed to be executed on such machine are called sequential algorithms
• Parallel Algorithms : Modern computers that can execute instructions in parallel. Algorithms designed to be executed on such machine are called parallel algorithms.

3. Choosing between exact and approximate problem solving

• Exact Algorithm: Solving problem exactly.
• Approx. Algorithm: Solving problem approximately.

Why Approx. Algorithm.?

• Some problems cannot be solved exactly.
• Solving problem exactly can be unacceptably slow because of the problem complexity.

4. Deciding on appropriate Data Structures

• A Data structure is defined as a particular scheme of organizing related data items.
• Decide on the suitable data structure.

5. Algorithm Design techniques

• An algorithm design technique is a general approach to solve problems algorithmically.

The various design techniques are:

• Brute force
• Divide and conquer
• Decrease and conquer
• Transform and conquer
• Greedy approach
• Dynamic programming
• Backtracking and Branch and bound
• Space and time tradeoffs

6. Method of specifying an algorithm

There are 3 methods:

• Natural language : Easy but ambiguous
• Pseudo code : Mixture of programming language and natural language.
• Flow chart : It is pictorial representation of the algorithm. Here symbols are used.

7. Proving an algorithm’s correctness

• Correctness : Prove that the algorithm Yields the required result for every legitimate input in a finite amount of time.
• A common technique for proving correctness is to use mathematical induction.
• In order to show the algorithm Is incorrect, we have to take just one instance of its input for which the algorithm Fails.
• If a algorithm is found to be incorrect, then reconsider one or more those decisions.
• For approx. algorithm We should show that the error produced by the algorithm does not exceed the predefined limit.

8. Analyzing an algorithm

Analyze the following qualities of the algorithm.

• Efficiency : Time efficiency and Space efficiency
• Simplicity : Simple algorithms mean easy to understand and easy to program.
• Generality : Design an algorithm for a problem in more general terms. In some cases, designing more general algorithm Is unnecessary or difficult.

9. Coding an algorithm

• Algorithms are designed to be implemented as computer programs.
• Use code tuning technique. For eg., replacing costlier multiplication operation with cheaper addition operation.

If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

To log in and use all the features of Khan Academy, please enable JavaScript in your browser.

Unit 1: Algorithms

About this unit.

We've partnered with Dartmouth college professors Tom Cormen and Devin Balkcom to teach introductory computer science algorithms, including searching, sorting, recursion, and graph theory. Learn with a combination of articles, visualizations, quizzes, and coding challenges.

Intro to algorithms

• What is an algorithm and why should you care? (Opens a modal)
• A guessing game (Opens a modal)
• Route-finding (Opens a modal)
• Discuss: Algorithms in your life (Opens a modal)

Binary search

• Binary search (Opens a modal)
• Implementing binary search of an array (Opens a modal)
• Challenge: Binary search (Opens a modal)
• Running time of binary search (Opens a modal)
• Running time of binary search 5 questions Practice

Asymptotic notation

• Asymptotic notation (Opens a modal)
• Big-θ (Big-Theta) notation (Opens a modal)
• Functions in asymptotic notation (Opens a modal)
• Big-O notation (Opens a modal)
• Big-Ω (Big-Omega) notation (Opens a modal)
• Comparing function growth 4 questions Practice
• Asymptotic notation 5 questions Practice

Selection sort

• Sorting (Opens a modal)
• Challenge: implement swap (Opens a modal)
• Selection sort pseudocode (Opens a modal)
• Challenge: Find minimum in subarray (Opens a modal)
• Challenge: implement selection sort (Opens a modal)
• Analysis of selection sort (Opens a modal)
• Project: Selection sort visualizer (Opens a modal)

Insertion sort

• Insertion sort (Opens a modal)
• Challenge: implement insert (Opens a modal)
• Insertion sort pseudocode (Opens a modal)
• Challenge: Implement insertion sort (Opens a modal)
• Analysis of insertion sort (Opens a modal)

Recursive algorithms

• Recursion (Opens a modal)
• The factorial function (Opens a modal)
• Challenge: Iterative factorial (Opens a modal)
• Recursive factorial (Opens a modal)
• Challenge: Recursive factorial (Opens a modal)
• Properties of recursive algorithms (Opens a modal)
• Using recursion to determine whether a word is a palindrome (Opens a modal)
• Challenge: is a string a palindrome? (Opens a modal)
• Computing powers of a number (Opens a modal)
• Challenge: Recursive powers (Opens a modal)
• Multiple recursion with the Sierpinski gasket (Opens a modal)
• Improving efficiency of recursive functions (Opens a modal)
• Project: Recursive art (Opens a modal)

Towers of Hanoi

• Towers of Hanoi (Opens a modal)
• Towers of Hanoi, continued (Opens a modal)
• Challenge: Solve Hanoi recursively (Opens a modal)
• Move three disks in Towers of Hanoi 3 questions Practice
• Divide and conquer algorithms (Opens a modal)
• Overview of merge sort (Opens a modal)
• Challenge: Implement merge sort (Opens a modal)
• Linear-time merging (Opens a modal)
• Challenge: Implement merge (Opens a modal)
• Analysis of merge sort (Opens a modal)
• Overview of quicksort (Opens a modal)
• Challenge: Implement quicksort (Opens a modal)
• Linear-time partitioning (Opens a modal)
• Challenge: Implement partition (Opens a modal)
• Analysis of quicksort (Opens a modal)

Graph representation

• Describing graphs (Opens a modal)
• Representing graphs (Opens a modal)
• Challenge: Store a graph (Opens a modal)
• Describing graphs 6 questions Practice
• Representing graphs 5 questions Practice

Breadth-first search

• Breadth-first search and its uses (Opens a modal)
• The breadth-first search algorithm (Opens a modal)
• Challenge: Implement breadth-first search (Opens a modal)
• Analysis of breadth-first search (Opens a modal)

Further learning

• Where to go from here (Opens a modal)

• DSA Tutorial
• Data Structures
• Linked List
• Dynamic Programming
• Binary Tree
• Binary Search Tree
• Divide & Conquer
• Mathematical
• Backtracking
• Branch and Bound
• Pattern Searching

Learn Data Structures and Algorithms | DSA Tutorial

• Data Structures Tutorial
• Array Data Structure
• String in Data Structure
• Linked List Data Structure
• Stack Data Structure
• Queue Data Structure
• Tree Data Structure
• Heap Data Structure
• Hashing in Data Structure
• Graph Data Structure And Algorithms
• Matrix Data Structure
• Introduction to Set – Data Structure and Algorithm Tutorials
• Introduction to Map – Data Structure and Algorithm Tutorials
• Advanced Data Structures

Algorithm Tutorial

• Searching Algorithms
• Sorting Algorithms
• Recursion Algorithms
• Backtracking Algorithm
• Greedy Algorithms
• Dynamic Programming or DP
• What is Pattern Searching ?
• Divide and Conquer
• Mathematical Algorithms
• Geometric Algorithms
• Bitwise Algorithms
• Randomized Algorithms
• Branch and Bound Algorithm
• Algorithms Tutorial

Competititve Programming

• Competitive Programming - A Complete Guide

Data Structures and Algorithms (DSA) refer to the study of methods for organizing and storing data and the design of procedures (algorithms) for solving problems, which operate on these data structures. DSA is one of the most important skills that every computer science student must have. It is often seen that people with good knowledge of these technologies are better programmers than others and thus, crack the interviews of almost every tech giant.

DSA Full Form

The term DSA stands for  Data Structures and Algorithms , in the context of Computer Science.

What is DSA?

Data Structures and Algorithms (DSA) refer to the study of methods for organizing and storing data and the design of procedures (algorithms) for solving problems, which operate on these data structures.

How to learn DSA?

The first and foremost thing is dividing the total procedure into little pieces which need to be done sequentially. The complete process to learn DSA from scratch can be broken into 5 parts:

• Learn at least one programming language (We leave this to your choice.)
• Learn Data Structures

Learn Algorithms

• Learn about Time and Space complexities
• Practice Problems on DSA

Hoping you have learned a programming language of your choice, let us move forward with the next step to learn DSA in this DSA tutorial.

Here comes the most important and the most awaited stage of the roadmap for learning data structure and algorithm – the stage where you start learning about DSA. The topic of DSA consists of two parts: 

• Algorithms 

Though they are two different things, they are highly interrelated, and it is very important to follow the right track to learn them most efficiently. If you are confused about which one to learn first, we recommend you to go through our detailed analysis on the topic: What should I learn first- Data Structures or Algorithms?

Here we have followed the flow of learning a data structure and then the most related and important algorithms used by that data structure.

1. Learn Data Structures

Data structures  are essential components that help organize and store data efficiently in computer memory. They provide a way to manage and manipulate data effectively, enabling faster access, insertion, and deletion operations. Common data structures include  arrays, linked lists, stacks, queues, trees, and graphs  , each serving specific purposes based on the requirements of the problem at hand. Understanding data structures is fundamental for designing efficient algorithms and optimizing software performance.

Common Data Structures to learn:

Array is a linear data structure that stores a collection of elements of the same data type. Elements are allocated contiguous memory, allowing for constant-time access. Each element has a unique index number.

• Traversal : Iterating through the elements of an array.
• Insertion : Adding an element to the array at a specific index.
• Deletion : Removing an element from the array at a specific index.
• Searching : Finding an element in the array by its value or index.
• One-dimensional array : A simple array with a single dimension.
• Multidimensional array : An array with multiple dimensions, such as a matrix.
• Storing data in a sequential manner
• Implementing queues, stacks, and other data structures
• Representing matrices and tables
• Arrays Tutorial
• Top 50 Array Coding Problems for Interviews
• Practice problems on Arrays

A string is a sequence of characters, typically used to represent text. It is considered a data type that allows for the manipulation and processing of textual data in computer programs.

• Concatenation : Joining two strings together.
• Comparison : Comparing two strings lexicographically.
• Substring extraction : Extracting a substring from a string.
• Search : Searching for a substring within a string.
• Modification : Changing or replacing characters within a string.
• Text processing
• Pattern matching
• Data validation
• Database management
• String Tutorial
• Top 50 String Coding Problems for Interviews
• Practice Problems on String

3. Linked Lists

A linked list is a linear data structure that stores data in nodes, which are connected by pointers. Unlike arrays, linked lists are not stored in contiguous memory locations.

• Dynamic : Linked lists can be easily resized by adding or removing nodes.
• Non-contiguous : Nodes are stored in random memory locations and connected by pointers.
• Sequential access : Nodes can only be accessed sequentially, starting from the head of the list.
• Creation : Creating a new linked list or adding a new node to an existing list.
• Traversal : Iterating through the list and accessing each node.
• Insertion : Adding a new node at a specific position in the list.
• Deletion : Removing a node from the list.
• Search : Finding a node with a specific value in the list.
• Singly Linked List : Each node points to the next node in the list.
• Doubly Linked List : Each node points to both the next and previous nodes in the list.
• Circular Linked List : The last node points back to the first node, forming a circular loop.
• Linked lists are used in various applications, including:
• Implementing queues and stacks
• Representing graphs and trees
• Maintaining ordered data
• Memory management
• Linkded List Tutorial
• Top 50 Problems on Linked List for Interviews
• Practice problems on Linked Lists

4. Matrix/Grid

A matrix is a two-dimensional array of elements, arranged in rows and columns. It is represented as a rectangular grid, with each element at the intersection of a row and column.

• Rows : Horizontal lines of elements in a matrix.
• Columns : Vertical lines of elements in a matrix.
• Dimensions : The number of rows and columns in a matrix (e.g., a 3×4 matrix has 3 rows and 4 columns).
• Element Access : Elements can be accessed using row and column indices (e.g., M[2][3] refers to the element in row 2, column 3).
• Image processing
• Data analysis
• Optimization problems
• Matrix/Grid Tutorial
• Top 50 Problems on Matrix/Grid for Interviews
• Practice Problems on Matrix/Grid

Stack is a linear data structure that follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out) . LIFO implies that the element that is inserted last, comes out first and FILO implies that the element that is inserted first, comes out last.

• Push : Adds an element to the top of the stack
• Pop : Removes and returns the element at the top of the stack
• Peek : Returns the element at the top of the stack without removing it
• Size : Returns the number of elements in the stack
• IsEmpty : Checks if the stack is empty
• Function calls
• Expression evaluation
• Undo/redo operations
• Stack Tutorial
• Top 50 Problems on Stack for Interviews
• Practice problems on Stack

A Queue Data Structure is a fundamental concept in computer science used for storing and managing data in a specific order. It follows the principle of “ First in, First out ” ( FIFO ), where the first element added to the queue is the first one to be removed

• Enqueue : Adds an element to the rear of the queue
• Dequeue : Removes an element from the front of the queue
• Peek : Retrieves the front element without removing it
• IsEmpty : Checks if the queue is empty
• IsFull : Checks if the queue is full
• Circular Queue : Last element connects to the first element
• Double-Ended Queue (Deque) : Operations can be performed from both ends
• Priority Queue : Elements are arranged based on priority
• Job scheduling
• Message queuing
• Simulation modeling
• Data buffering
• Queue Tutorial
• Top 50 Problems on Queue for Interviews
• Practice problems on Queue

A Heap is a complete binary tree data structure that satisfies the heap property: for every node, the value of its children is less than or equal to its own value. Heaps are usually used to implement priority queues , where the smallest (or largest) element is always at the root of the tree.

• Insert : Adds a new element to the heap while maintaining heap properties.
• Extract-Max/Extract-Min : Removes the root element and restructures the heap.
• Increase/Decrease-Key : Updates the value of a node and restructures the heap.
• Max-Heap : Root node has the maximum value among its children.
• Min-Heap : Root node has the minimum value among its children.
• Priority queues
• Graph algorithms (e.g., Dijkstra’s algorithm)
• Heap Tutorial
• Top 50 Problems on Heap for Interviews
• Practice Problems on Heap

Hashing is a technique that generates a fixed-size output (hash value) from an input of variable size using mathematical formulas called hash functions . Hashing is used to determine an index or location for storing an item in a data structure, allowing for efficient retrieval and insertion.

• Hash Function : A mathematical function that maps an input to a hash value.
• Hash Table : A data structure that stores key-value pairs, where the key is a hash value and the value is the actual data.
• Collision : When two different keys produce the same hash value.
• Division Method : Divides the input by a constant and uses the remainder as the hash value.
• Mid Square Method: Squares the input and takes the middle digits as the hash value.
• Folding Method : Divides the input into equal-sized blocks and adds them together to get the hash value.
• Multiplication Method : Multiplies the input by a constant and takes the fractional part as the hash value.
• Separate Chaining (Open Hashing) : Stores colliding elements in a linked list at the corresponding hash value.
• Open Addressing (Closed Hashing) : Uses various strategies to find an alternative location for colliding elements within the hash table.
• Efficiently storing and retrieving data in databases and file systems.
• Verifying passwords and digital signatures.
• Distributing requests across multiple servers.
• Generating secure hashes for data integrity and authentication.
• Hash Tutorial
• Practice Problems on Hashing

A tree is a non-linear hierarchical data structure consisting of nodes connected by edges, with a top node called the root and nodes having child nodes. It is used in computer science for organizing data efficiently.

• In-Order : Visit left subtree, current node, then right subtree.
• Pre-Order : Visit current node, left subtree, then right subtree.
• Post-Order : Visit left subtree, right subtree, then current node.
• Classifications of Trees refer to grouping trees based on certain characteristics or criteria. This can involve categorizing trees based on their balance factor, degree of nodes, ordering properties, etc. Below are some important classification of Tree.
• File systems
• XML documents
• Artificial intelligence
• Tree Tutorial
• Top 50 Tree Coding Problems
• Practice problems on Tree

A Graph is a non-linear data structure consisting of a finite set of vertices(or nodes) and a set of edges that connect a pair of nodes.

• Breadth-First Search (BFS) : Visits nodes level by level.
• Depth-First Search (DFS) : Visits nodes recursively, exploring one branch at a time.
• Social networks
• Maps and navigation
• Data mining
• Graph Representation
• Types of graphs
• Graph Tutorial
• Practice problems on Graph

Once you have cleared the concepts of Data Structures , now its time to start your journey through the Algorithms . Based on the type of nature and usage, the Algorithms are grouped together into several categories, as shown below:

1. Searching Algorithm

Searching algorithms are used to locate specific data within a larger set of data. It helps find the presence of a target value within the data. There are various types of searching algorithms, each with its own approach and efficiency.

• Linear Search : Iterative search from one end to the other.
• Binary Search : Divide-and-conquer search on a sorted array, halving the search space at each iteration.
• Ternary Search : Divide-and-conquer search on a sorted array, dividing the search space into three parts at each iteration.
• Jump Search
• Interpolation Search  
• Exponential Search  
• Practice problems on Searching algorithm

2. Sorting Algorithm

Sorting algorithms are used to arranging the elements of a list in a specific order, such as numerical or alphabetical. It organizes the items in a systematic way, making it easier to search for and access specific elements.

There are a lot of different types of sorting algorithms. Some widely used algorithms are:

Related Topics:

• Sorting Algorithm Tutorial
• Top Sorting Interview Questions and Problems
• Practice problems on Sorting algorithm

3. Divide and Conquer Algorithm

Divide and conquer algorithms follow a recursive strategy to solve problems by dividing them into smaller subproblems, solving those subproblems, and combining the solutions to obtain the final solution.

• Divide : Partition the problem into smaller, independent subproblems.
• Conquer : Recursively solve each subproblem.
• Combine : Merge the solutions of the subproblems to obtain the final solution.
• Merge Sort: Divides the array into two halves, sorts each half recursively, and merges the sorted halves.
• Quick Sort: Selects a pivot element, partitions the array into two subarrays based on the pivot, and recursively sorts each subarray.
• Binary Search: Divides the search space in half repeatedly until the target element is found or the search space is exhausted.

Related Articles:

• Divide and Conquer Tutorial
• Practice problems on Divide And Conquer algorithm

4. Greedy Algorithms

As the name suggests, this algorithm builds up the solution one piece at a time and chooses the next piece which gives the most obvious and immediate benefit i.e., which is the most optimal choice at that moment. So the problems where choosing locally optimal also leads to the global solutions are best fit for Greedy.

Some Important Problem of Greedy Algorithms are:

• Greedy Algorithm Tutorial
• Practice problems on Greedy algorithm

5. Recursion

Recursion is a programming technique where a function calls itself within its own definition. It is usually used to solve problems that can be broken down into smaller instances of the same problem. For Example: Towers of Hanoi (TOH) , Factorial Calculation and Fibonacci Sequence etc.

• Base Case : Define a condition that stops the recursive calls and provides a solution.
• Recursive Case : Define the steps to break down the problem into smaller instances and make recursive calls.
• Return : Return the solution from the recursive calls and combine them to solve the original problem.

The point which makes Recursion one of the most used algorithms is that it forms the base for many other algorithms such as Tree traversals , Graph traversals , Divide and Conquers Algorithms and Backtracking algorithms .

• Recursion Tutorial
• Recursive Functions
• Tail Recursion
• Top 50 Problems on Recursion Algorithm for Interview
• Practice problems on Recursion algorithm

6. Backtracking Algorithm

As mentioned earlier, the Backtracking algorithm is derived from the Recursion algorithm, with the option to revert if a recursive solution fails, i.e. in case a solution fails, the program traces back to the moment where it failed and builds on another solution. So basically it tries out all the possible solutions and finds the correct one.

Some important and most common problems of backtracking algorithms, that you must solve before moving ahead, are:

Related Article:

• Backtracking Tutorial
• Practice problems on Backtracking algorithm

7. Dynamic Programming

Dynamic Programming is a method used in mathematics and computer science to solve complex problems by breaking them down into simpler subproblems. By solving each subproblem only once and storing the results, it avoids redundant computations, leading to more efficient solutions for a wide range of problems.

Key Concepts:

• Optimal Substructure : The optimal solution to a problem can be constructed from the optimal solutions to its subproblems.
• Overlapping Subproblems : Subproblems are often repeated in the larger problem, leading to redundant computations.
• Memoization / Tabulation : Storing the solutions to subproblems to avoid recomputation.

Some important and most common problems of dynamic programming algorithms, that you must solve before moving ahead, are:

• Tabulation vs Memoization
• How to solve a Dynamic Programming Problem?
• Dynamic Programming Tutorial
• Top 50 Dynamic Programming Coding Problems for Interviews
• Practice problems on Dynamic Programming algorithm

8. Graph Algorithms :

Graph algorithms in data structures and algorithms (DSA) are a set of techniques and methods used to solve problems related to graphs, which are a collection of nodes and edges. These algorithms are designed to perform various operations on graphs, such as searching, traversing, finding the shortest path , and determining connectivity . They are essential for solving a wide range of real-world problems, including network routing, social network analysis, and resource allocation.

• Top 50 Graph Coding Problems for Interviews
• Practice Problem on Graph Algorithms

9 . Pattern Searching

Pattern searching is a fundamental technique in DSA used to find occurrences of a specific pattern within a given text.

Below are some some standard pattern searching algorithms:

• Pattern Searching Tutorial
• Practice Problem on Pattern Searching

10 . Mathematical Algorithms

Mathematical algorithms are a class of algorithms that solve problems related to mathematical concepts. They are widely used in various fields, including Computer graphics, Numerical analysis, Optimization and Cryptography.

• Practice Problem on Mathmatical Algorithm

11. Geometric Algorithms

Geometric algorithms are a class of algorithms that solve problems related to geometry. Geometric algorithms are essential for solving a wide range of problems in computer science, such as:

• Practice Problem on Geometric Algorithms

12. Bitwise Algorithms

Bitwise algorithms are algorithms that operate on individual bits of numbers. These algorithms manipulate the binary representation of numbers to perform tasks such as bit manipulation, bitwise logical operations (AND, OR, XOR), shifting bits , and setting or clearing specific bits within a number. Bitwise algorithms are commonly used in low-level programming, cryptography, and optimization tasks where efficient manipulation of individual bits is required.

• Bitwise Algorithms Tutorial
• Practice Problem on Bitwise Algorithms

13. Randomized Algorithms

Randomized algorithms are algorithms that use randomness to solve problems. They make use of random input to achieve their goals, often leading to simpler or more efficient solutions.

Types of Randomized Algorithms:

• Las Vegas : Always produces a correct result, but the running time is random.
• Monte Carlo : May produce an incorrect result with a small probability, but the running time is usually faster.

Important Algorithms that uses Randomization Algorithms:

14. Branch and Bound Algorithm

The Branch and Bound Algorithm is a method used in combinatorial optimization problems to systematically search for the best solution. It works by dividing the problem into smaller subproblems, or branches, and then eliminating certain branches based on bounds on the optimal solution. This process continues until the best solution is found or all branches have been explored.

Standard Problems on Branch and Bound Algorithm:

• Branch and Bound Algorithm Tutorial

Learn about Complexities

In Data Structures and Algorithms (DSA), the main goal is to solve problems effectively and efficiently. To determine the efficiency of a program, we look at two types of complexities:

• Time Complexity : This tells us how much time our code takes to run.
• Space Complexity : This tells us how much memory our code uses.

Asymptotic Notation :

To compare efficiencies of algorithms, we use asymptotic notation, a mathematical tool that estimates time based on input size without running the code. It focuses on the number of basic operations in the program.

The most commonly used notation for code analysis is Big O Notation , providing an upper limit on the running time or memory usage concerning the input size.

• Understanding Time Complexity with Simple Examples
• Time complexities of different data structures
• How to Analyse Loops for Complexity Analysis of Algorithms
• Practice Questions on Time Complexity Analysis

Practice Problem Cheat Sheets:

Curated lists of problems from below articles:

• DSA Roadmap by Sandeep Jain
• SDE SHEET – A Complete Guide for SDE Preparation
• GeeksforGeeks Master Sheet – List of all Cheat Sheets

Please Login to comment...

Similar reads.

• DSA Tutorials

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

• school Campus Bookshelves
• menu_book Bookshelves
• perm_media Learning Objects
• login Login
• how_to_reg Request Instructor Account
• hub Instructor Commons
• Download Page (PDF)
• Download Full Book (PDF)
• Periodic Table
• Physics Constants
• Scientific Calculator
• Reference & Cite
• Tools expand_more
• Readability

selected template will load here

This action is not available.

1: Fundamental Design and Analysis Techniques

• Last updated
• Save as PDF
• Page ID 46775

• Godfry Justo
• University of Dar es Salaam via African Virtual University

Unit Objectives

Upon completion of this unit you should be able to:

• Describe concepts of algorithm design and analysis
• Demonstrate knowledge of algorithm complexity analysis
• Apply iteration and recursion in problem solving
• Apply dynamic programming in problem solving

Unit Introduction

The design and analysis of algorithms has become an indispensable skill in applied computer science as it is the core for developing efficient software applications, especially, due increasing demand for complex software systems to support the contemporary world applications. This unit acts as prelude to the study of advanced data structure and algorithms discussed in this course. It highlights the basic concepts related to this subject and introduces the notions of algorithm analysis and design.

The unit provides a concise description of the key concepts used in algorithm analysis under the time and space complexity dimensions. Furthermore, a review of algorithm design methods is provided including the iteration, recursion and dynamic programming.

• 1.1: Activity 1 - Overview of Algorithm Design and Analysis
• 1.2: Activity 2 - Recursion and Recursive Backtracking
• 1.3: Activity 3 - Dynamic Programming
• 1.4: Unit Summary

• Data Structure
• Design Pattern

DS Tutorial

Ds linked list, ds searching, differences.

• Send your Feedback to [email protected]

Help Others, Please Share

Learn Latest Tutorials

Transact-SQL

Reinforcement Learning

R Programming

React Native

Python Design Patterns

Python Pillow

Python Turtle

Preparation

Verbal Ability

Interview Questions

Company Questions

Trending Technologies

Artificial Intelligence

Cloud Computing

Data Science

Machine Learning

B.Tech / MCA

Data Structures

Operating System

Computer Network

Compiler Design

Computer Organization

Discrete Mathematics

Ethical Hacking

Computer Graphics

Software Engineering

Web Technology

Cyber Security

C Programming

Control System

Data Mining

Data Warehouse