fundamentals of algorithmic problem solving mcq

For Solo Learner Computer science

Fundamentals of algorithms and problem-solving mcqs.

Home » Computer Science MCQs Sets » Computer Basics MCQs » Fundamentals of Algorithms and problem-solving MCQs

PRACTICE IT NOW TO SHARPEN YOUR CONCEPT AND KNOWLEDGE

1. Which graph algorithm can be used to find the longest path in a directed acyclic graph (DAG)?

• Depth-first search (DFS)
• Breadth-first search (BFS)
• Topological sort
• Dijkstra's algorithm

Topological sort can be used to find the longest path in a directed acyclic graph (DAG).

Learn more about : Which graph algorithm can be used to find the longest path in a directed acyclic graph (DAG)?

2. What does "brute force" mean in the context of problem-solving?

• Using the most complex approach to solve a problem
• Trying all possible solutions without optimization
• Solving problems without a plan
• Applying advanced mathematics to solve a problem

"Brute force" in problem-solving means trying all possible solutions without optimization.

Learn more about : What does "brute force" mean in the context of problem-solving?

3. What is "trial and error" as a problem-solving strategy?

• A systematic approach to problem-solving
• Randomly trying different solutions until one works
• A method used only in mathematics
• A formal proof technique

"Trial and error" as a problem-solving strategy involves randomly trying different solutions until one succeeds.

Learn more about : What is "trial and error" as a problem-solving strategy?

4. What is "divide and conquer" as a problem-solving technique?

• A strategy that avoids breaking problems into smaller subproblems
• A strategy that involves solving the largest subproblem first
• A strategy that breaks a problem into smaller subproblems and solves them independently
• A strategy that only works for small-scale problems

"Divide and conquer" is a problem-solving technique that breaks a problem into smaller subproblems and solves them independently.

Learn more about : What is "divide and conquer" as a problem-solving technique?

5. In problem-solving, what is a "heuristic"?

• An optimal solution to a problem
• A rule of thumb or a practical approach to find a solution
• A random choice among multiple solutions

A heuristic is a rule of thumb or a practical approach used to find a solution in problem-solving.

Learn more about : In problem-solving, what is a "heuristic"?

6. What is "trial division" as a technique in number theory and prime factorization?

• A method to find the smallest prime number
• A method to verify if a number is prime by dividing it by smaller primes
• A method to find the largest prime number
• A method to add prime numbers

"Trial division" is a technique in number theory and prime factorization used to verify if a number is prime by dividing it by smaller primes.

Learn more about : What is "trial division" as a technique in number theory and prime factorization?

7. What is the primary purpose of "backtracking" in problem-solving?

• To find the optimal solution
• To explore all possible solutions systematically
• To avoid exploring all possible solutions
• To simplify the problem

The primary purpose of "backtracking" in problem-solving is to explore all possible solutions systematically, typically in a recursive manner.

Learn more about : What is the primary purpose of "backtracking" in problem-solving?

8. What is an algorithm?

• A data structure used to store information
• A sequence of steps to solve a problem
• A programming language
• A type of computer hardware

An algorithm is a sequence of steps or instructions designed to solve a specific problem or perform a task.

Learn more about : What is an algorithm?

9. What is the primary goal of algorithm analysis?

• To design algorithms
• To implement algorithms
• To compare algorithms and evaluate their efficiency
• To debug algorithms

The primary goal of algorithm analysis is to compare algorithms and evaluate their efficiency.

Learn more about : What is the primary goal of algorithm analysis?

10. Which of the following is NOT a characteristic of a good algorithm?

• Clarity and simplicity
• Efficiency in terms of time and space
• The use of complex data structures
• Correctness

A good algorithm is characterized by clarity, simplicity, efficiency, and correctness. Complex data structures may be used if necessary, but simplicity is preferred.

Learn more about : Which of the following is NOT a characteristic of a good algorithm?

11. What is the purpose of pseudocode in algorithm development?

• To hide the algorithm's logic
• To provide a step-by-step implementation guide
• To obfuscate the algorithm
• To prevent others from understanding the algorithm

Pseudocode is used to provide a step-by-step implementation guide for an algorithm, making it easier to understand and develop.

Learn more about : What is the purpose of pseudocode in algorithm development?

12. Which algorithm design technique involves breaking a problem into smaller subproblems and solving each subproblem recursively?

• Divide and conquer
• Dynamic programming
• Greedy algorithm
• Backtracking

The "divide and conquer" algorithm design technique involves breaking a problem into smaller subproblems and solving each subproblem recursively.

Learn more about : Which algorithm design technique involves breaking a problem into smaller subproblems and solving each subproblem recursively?

13. What is the time complexity of an algorithm?

• The number of steps required to execute the algorithm
• The amount of memory used by the algorithm
• The analysis of the algorithm's efficiency in terms of input size
• The number of loops in the algorithm

Time complexity is the analysis of an algorithm's efficiency in terms of input size.

Learn more about : What is the time complexity of an algorithm?

14. What is the "Big O notation" used for in algorithm analysis?

• To measure the algorithm's popularity
• To describe the algorithm's internal details
• To express the upper bound of an algorithm's time complexity
• To provide pseudocode for the algorithm

The Big O notation is used to express the upper bound of an algorithm's time complexity.

Learn more about : What is the "Big O notation" used for in algorithm analysis?

15. Which of the following time complexities represents the most efficient algorithm?

O(1) represents constant time complexity, which is the most efficient algorithm in terms of time.

Learn more about : Which of the following time complexities represents the most efficient algorithm?

16. What is the space complexity of an algorithm?

• The analysis of the algorithm's efficiency in terms of output size

Space complexity is the amount of memory used by the algorithm.

Learn more about : What is the space complexity of an algorithm?

17. What does "optimization" refer to in the context of algorithms?

• The process of making an algorithm more complex
• The process of making an algorithm run slower
• The process of improving an algorithm's efficiency
• The process of making an algorithm more obscure

Optimization in the context of algorithms refers to the process of improving an algorithm's efficiency.

Learn more about : What does "optimization" refer to in the context of algorithms?

18. Which searching algorithm works by repeatedly dividing the search range in half until the target element is found?

• Linear search
• Binary search
• Quick search
• Merge search

Binary search works by repeatedly dividing the search range in half until the target element is found.

Learn more about : Which searching algorithm works by repeatedly dividing the search range in half until the target element is found?

19. Which sorting algorithm has an average time complexity of O(n log n) and is often used for large datasets?

• Bubble sort
• Insertion sort
• Selection sort

Merge sort has an average time complexity of O(n log n) and is efficient for large datasets.

Learn more about : Which sorting algorithm has an average time complexity of O(n log n) and is often used for large datasets?

20. What is the primary advantage of quicksort over some other sorting algorithms like bubble sort and insertion sort?

• Quicksort always has a time complexity of O(1).
• Quicksort is a stable sorting algorithm.
• Quicksort has an average time complexity of O(n log n).
• Quicksort uses fewer comparisons.

Quicksort has an average time complexity of O(n log n), which is more efficient than the average case time complexity of bubble sort and insertion sort.

Learn more about : What is the primary advantage of quicksort over some other sorting algorithms like bubble sort and insertion sort?

21. Which sorting algorithm repeatedly selects the smallest element from the unsorted part of the array and places it at the beginning of the sorted part?

Selection sort repeatedly selects the smallest element from the unsorted part and places it at the beginning of the sorted part.

Learn more about : Which sorting algorithm repeatedly selects the smallest element from the unsorted part of the array and places it at the beginning of the sorted part?

22. What is the time complexity of the bubble sort algorithm in the worst-case scenario?

The worst-case time complexity of the bubble sort algorithm is O(n^2).

Learn more about : What is the time complexity of the bubble sort algorithm in the worst-case scenario?

23. What data structure represents a collection of nodes connected by edges, where each edge has a direction?

• Linked list

A graph represents a collection of nodes connected by edges, where edges can have directions.

Learn more about : What data structure represents a collection of nodes connected by edges, where each edge has a direction?

24. In a binary tree, how many children can each node have at most?

In a binary tree, each node can have at most two children: a left child and a right child.

Learn more about : In a binary tree, how many children can each node have at most?

25. What is the root node in a tree data structure?

• The node with the highest value
• The first node in the tree
• The node with the lowest value
• The topmost node from which all other nodes descend

The root node in a tree data structure is the topmost node from which all other nodes descend.

Learn more about : What is the root node in a tree data structure?

26. Which traversal method starts from the root node and explores as far as possible along each branch before backtracking?

• Inorder traversal
• Preorder traversal
• Postorder traversal
• Depth-first traversal

Preorder traversal starts from the root node and explores as far as possible along each branch before backtracking.

Learn more about : Which traversal method starts from the root node and explores as far as possible along each branch before backtracking?

27. What is a common application of breadth-first search (BFS) in graph algorithms?

• Finding the shortest path between two nodes
• Sorting the nodes in a graph
• Calculating the depth of a tree
• Traversing a tree in preorder

A common application of breadth-first search (BFS) is finding the shortest path between two nodes in a graph.

Learn more about : What is a common application of breadth-first search (BFS) in graph algorithms?

28. What is dynamic programming commonly used for in algorithm design?

• Solving problems that cannot be solved by algorithms
• Solving problems by breaking them into smaller subproblems and caching their solutions
• Creating algorithms without any optimization
• Generating random solutions to problems

Dynamic programming is commonly used for solving problems by breaking them into smaller subproblems and caching their solutions to avoid redundant computation.

Learn more about : What is dynamic programming commonly used for in algorithm design?

29. What is memoization in the context of dynamic programming?

• A technique for generating random numbers
• A method for optimizing algorithms using parallel processing
• Caching and reusing previously computed results to avoid redundant calculations
• A type of sorting algorithm

Memoization in dynamic programming involves caching and reusing previously computed results to avoid redundant calculations.

Learn more about : What is memoization in the context of dynamic programming?

30. Which dynamic programming technique typically uses a table to store and retrieve solutions to subproblems?

• Memoization

Tabulation is a dynamic programming technique that typically uses a table to store and retrieve solutions to subproblems.

Learn more about : Which dynamic programming technique typically uses a table to store and retrieve solutions to subproblems?

31. In dynamic programming, what does "optimal substructure" mean?

• The process of finding the best algorithm
• The property that the optimal solution to a problem can be constructed from the optimal solutions of its subproblems
• The use of greedy algorithms
• The analysis of algorithm efficiency

Optimal substructure is the property that the optimal solution to a problem can be constructed from the optimal solutions of its subproblems.

Learn more about : In dynamic programming, what does "optimal substructure" mean?

32. What is the primary advantage of dynamic programming over brute-force methods?

• Dynamic programming always produces the correct result.
• Dynamic programming is faster.
• Dynamic programming requires less memory.
• Dynamic programming optimally solves all problems.

The primary advantage of dynamic programming is that it is often faster than brute-force methods because it avoids redundant computations.

Learn more about : What is the primary advantage of dynamic programming over brute-force methods?

33. What is a greedy algorithm in algorithm design?

• An algorithm that always selects the largest available option
• An algorithm that makes a series of choices, each one being the best decision at the moment
• An algorithm that never backtracks
• An algorithm that solves problems by brute force

A greedy algorithm makes a series of choices, each being the best decision at the moment, with the hope of finding a globally optimal solution.

Learn more about : What is a greedy algorithm in algorithm design?

34. In the context of greedy algorithms, what is a "greedy choice property"?

• The property that a locally optimal choice leads to a globally optimal solution
• The property that a greedy algorithm is always the best choice
• The property that a greedy algorithm never makes a mistake
• The property that a greedy algorithm selects the largest option first

The greedy choice property states that a locally optimal choice in a greedy algorithm leads to a globally optimal solution.

Learn more about : In the context of greedy algorithms, what is a "greedy choice property"?

35. Which classic greedy algorithm is used to solve the problem of finding the minimum number of coins needed to make change for a given amount of money?

• Kruskal's algorithm
• Huffman coding
• Coin change algorithm

The coin change algorithm is used to find the minimum number of coins needed to make change for a given amount of money.

Learn more about : Which classic greedy algorithm is used to solve the problem of finding the minimum number of coins needed to make change for a given amount of money?

36. What is the primary drawback of greedy algorithms?

• They are slow and inefficient.
• They can sometimes lead to suboptimal solutions.
• They require a lot of memory.
• They are difficult to implement.

The primary drawback of greedy algorithms is that they can sometimes lead to suboptimal solutions because they make locally optimal choices at each step.

Learn more about : What is the primary drawback of greedy algorithms?

37. What is a "cycle" in a directed graph?

• A path that visits every node exactly once
• A path that visits the same node twice or more, starting and ending at the same node
• A path that visits every node in the graph
• A path that visits all leaf nodes

In a directed graph, a cycle is a path that visits the same node twice or more, starting and ending at the same node.

Learn more about : What is a "cycle" in a directed graph?

38. Which algorithm is commonly used to find the shortest path between nodes in a weighted graph?

Dijkstra's algorithm is commonly used to find the shortest path between nodes in a weighted graph.

Learn more about : Which algorithm is commonly used to find the shortest path between nodes in a weighted graph?

39. What is a "topological sort" of a directed acyclic graph (DAG)?

• An arrangement of nodes in ascending order based on their values
• An arrangement of nodes in descending order based on their values
• A linear ordering of nodes such that for every directed edge (u, v), node u comes before node v
• A linear ordering of nodes that connects all nodes in a graph

A topological sort of a directed acyclic graph (DAG) is a linear ordering of nodes such that for every directed edge (u, v), node u comes before node v.

Learn more about : What is a "topological sort" of a directed acyclic graph (DAG)?

40. What is a "spanning tree" of a graph?

• A tree that includes all nodes of the graph
• A tree with the fewest number of nodes
• A tree with the most number of nodes
• A tree with no nodes

A spanning tree of a graph is a tree that includes all nodes of the graph.

Learn more about : What is a "spanning tree" of a graph?

41. In dynamic programming, what is "bottom-up" or "tabulation" approach?

• Starting with the largest subproblems and solving them first
• Starting with the smallest subproblems and solving them first
• Starting with the middle-sized subproblems and solving them first
• Starting with the most complex subproblems and solving them first

The "bottom-up" or "tabulation" approach in dynamic programming starts with the smallest subproblems and solves them first, building up to the larger problem.

Learn more about : In dynamic programming, what is "bottom-up" or "tabulation" approach?

42. In dynamic programming, what is the "optimal substructure" property?

• The property that an algorithm always produces the optimal solution
• The property that an algorithm never uses subproblems
• The property that the optimal solution can be constructed from optimal solutions of subproblems
• The property that subproblems cannot be solved independently

The "optimal substructure" property in dynamic programming states that the optimal solution can be constructed from optimal solutions of subproblems.

Learn more about : In dynamic programming, what is the "optimal substructure" property?

43. What is the purpose of a "memoization table" in dynamic programming?

• To store the algorithm's pseudocode
• To store the names of subproblems
• To cache and retrieve previously computed results of subproblems
• To store debugging information

A memoization table in dynamic programming is used to cache and retrieve previously computed results of subproblems to avoid redundant calculations.

Learn more about : What is the purpose of a "memoization table" in dynamic programming?

44. What is the "overlap" property in dynamic programming?

• The property that two subproblems share a common solution
• The property that subproblems do not share any common elements
• The property that all subproblems have identical solutions

The "overlap" property in dynamic programming refers to the property that two or more subproblems share a common solution, leading to the need for memoization.

Learn more about : What is the "overlap" property in dynamic programming?

45. In the context of dynamic programming, what is "pruning"?

• The process of removing nodes from a graph
• The process of reducing the complexity of an algorithm
• The process of removing unnecessary branches from a search
• The process of rearranging data structures

In dynamic programming, pruning is the process of removing unnecessary branches from a search to reduce computational effort.

Learn more about : In the context of dynamic programming, what is "pruning"?

46. Which dynamic programming technique uses a bottom-up approach and fills a table iteratively to solve problems?

• Greedy approach

The tabulation technique in dynamic programming uses a bottom-up approach and fills a table iteratively to solve problems.

Learn more about : Which dynamic programming technique uses a bottom-up approach and fills a table iteratively to solve problems?

47. What is a "weighted graph" in graph theory?

• A graph with no edges
• A graph in which each edge has a numerical weight or cost
• A graph with a large number of nodes
• A directed graph

A weighted graph is a graph in which each edge has a numerical weight or cost associated with it.

Learn more about : What is a "weighted graph" in graph theory?

48. Which graph algorithm is used to find the minimum spanning tree of a weighted, connected graph?

• Bellman-Ford algorithm

Kruskal's algorithm is used to find the minimum spanning tree of a weighted, connected graph.

Learn more about : Which graph algorithm is used to find the minimum spanning tree of a weighted, connected graph?

49. What is a "strongly connected component" in a directed graph?

• A component that contains only one node
• A component in which any two nodes are connected by a single edge
• A component in which there is a directed path from any node to any other node
• A component with the fewest edges

A strongly connected component in a directed graph is a component in which there is a directed path from any node to any other node within the component.

Learn more about : What is a "strongly connected component" in a directed graph?

50. What is a "cycle detection" algorithm used for in graph theory?

• Detecting loops or cycles in a graph
• Finding the maximum flow in a network

A cycle detection algorithm is used to detect loops or cycles in a graph.

Learn more about : What is a "cycle detection" algorithm used for in graph theory?

Looking for more? Check out the below resources.

Copyright © 2023 | ExamRadar. | Contact Us | Copyright || Terms of Use || Privacy Policy

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, 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)

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.

• Algorithms MCQ Questions and Answers – Fundamentals – Part 2

C omputer architecture MCQ questions and answers for the preparation of tests, exams, and certifications. So you will find questions about loops and conditionals, data structure, complexity, flowchart, pseudocode, and much more. This systematic learning method will easily prepare anyone to pass their exam.  

1. Programming languages give instructions to the computer?

2. we can show the sequence of steps of an algorithm in a structural diagram called flowchart.

3. When an algorithm is written in a programming language, it becomes a _________?

A flowchart

C pseudo-code

4. Which of the following statements is wrong?

Algorithms can be represented:   A As pseudo codes

B As syntax

C As a program

• As a program
• As a flowchart
• As pseudo codes

5. Any algorithm is a program.

6. when you write an algorithm, the order of the instructions is very important, 7. what should be considered when designing an algorithm.

A If the hardware is used correctly

B If the software is used correctly

C If there is more than one way to solve the problem

D All the answers are true

8. In a flowchart, how are the symbols connected?

A Symbols are not connected together in a flowchart

B With lines and arrows to indicate the direction of flow

C With dotted lines and numbers

D With continuous lines to link events

9. When can we use algorithms?

A Only with computers

B Only when programming

C Only when we want to put our flowchart in place.

D At any time to design solutions to problems

10. What is shown in the image below?

B This is an algorithm

C This is a diagram

D This is a decision

• Algorithms MCQ Questions and Answers – Fundamentals – Part 1
• Algorithms MCQ Questions and Answers – Fundamentals – Part 3
• Algorithms MCQ – Data Structures & Complexity – Part 1
• Algorithms MCQ – Data Structures & Complexity – Part 2
• Algorithms MCQ – Data Structures & Complexity – Part 3
• Algorithms MCQ – Data Structures & Complexity – Part 4

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Save my name, email, and website in this browser for the next time I comment.

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

• Explore Our Geeks Community
• Algorithms Tutorial

What is Algorithm | Introduction to Algorithms

• Definition, Types, Complexity and Examples of Algorithm
• Algorithms Design Techniques
• Why the Analysis of Algorithm is important?

Analysis of Algorithms

• 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

Types of Algorithms

• Sorting Algorithms
• Searching Algorithms
• Greedy Algorithms
• Backtracking Algorithms
• Divide and Conquer
• Mathematical Algorithms
• Geometric Algorithms
• Bitwise Algorithms
• Graph Data Structure And Algorithms
• Randomized Algorithms
• Branch and Bound Algorithm
• The Role of Algorithms in Computing
• Most important type of Algorithms

Definition of Algorithm

The word Algorithm means ” A set of finite rules or instructions 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 involves recursive operations” .

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

Use of the Algorithms:

Algorithms play a crucial role in various fields and have many applications. Some of the key areas where algorithms are used include:

• Computer Science: Algorithms form the basis of computer programming and are used to solve problems ranging from simple sorting and searching to complex tasks such as artificial intelligence and machine learning.
• Mathematics: Algorithms are used to solve mathematical problems, such as finding the optimal solution to a system of linear equations or finding the shortest path in a graph.
• Operations Research : Algorithms are used to optimize and make decisions in fields such as transportation, logistics, and resource allocation.
• Artificial Intelligence: Algorithms are the foundation of artificial intelligence and machine learning, and are used to develop intelligent systems that can perform tasks such as image recognition, natural language processing, and decision-making.
• Data Science: Algorithms are used to analyze, process, and extract insights from large amounts of data in fields such as marketing, finance, and healthcare.

These are just a few examples of the many applications of algorithms. The use of algorithms is continually expanding as new technologies and fields emerge, making it a vital component of modern society.

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

It can be understood by taking the example of cooking a new recipe. To cook a new recipe, one reads the instructions and steps and executes them one by one, in the given sequence. The result thus obtained is the new dish is cooked perfectly. Every time you use your phone, computer, laptop, or calculator you are using Algorithms. Similarly, algorithms help to do a task in programming to get the expected output.

The Algorithm designed are language-independent, i.e. they are just plain instructions that can be implemented in any language, and yet the output will be the same, as expected.

What is the need for algorithms?

• Algorithms are necessary for solving complex problems efficiently and effectively. 
• They help to automate processes and make them more reliable, faster, and easier to perform.
• Algorithms also enable computers to perform tasks that would be difficult or impossible for humans to do manually.
• They are used in various fields such as mathematics, computer science, engineering, finance, and many others to optimize processes, analyze data, make predictions, and provide solutions to problems.

What are the Characteristics of an Algorithm?

As one would not follow any written instructions to cook the recipe, but only the standard one. Similarly, not all written instructions for programming are an algorithm. For some instructions to be an algorithm, it must have the following characteristics:

• Clear and Unambiguous : The algorithm should be unambiguous. Each of its steps should be clear in all aspects and must lead to only one meaning.
• Well-Defined Inputs : If an algorithm says to take inputs, it should be well-defined inputs. It may or may not take input.
• Well-Defined Outputs: The algorithm must clearly define what output will be yielded and it should be well-defined as well. It should produce at least 1 output.
• Finite-ness: The algorithm must be finite, i.e. it should terminate after a finite time.
• Feasible: The algorithm must be simple, generic, and practical, such that it can be executed with the available resources. It must not contain some future technology or anything.
• Language Independent: The Algorithm designed must be language-independent, i.e. it must be just plain instructions that can be implemented in any language, and yet the output will be the same, as expected.
• Input : An algorithm has zero or more inputs. Each that contains a fundamental operator must accept zero or more inputs.
•   Output : An algorithm produces at least one output. Every instruction that contains a fundamental operator must accept zero or more inputs.
• Definiteness: All instructions in an algorithm must be unambiguous, precise, and easy to interpret. By referring to any of the instructions in an algorithm one can clearly understand what is to be done. Every fundamental operator in instruction must be defined without any ambiguity.
• Finiteness: An algorithm must terminate after a finite number of steps in all test cases. Every instruction which contains a fundamental operator must be terminated within a finite amount of time. Infinite loops or recursive functions without base conditions do not possess finiteness.
• Effectiveness: An algorithm must be developed by using very basic, simple, and feasible operations so that one can trace it out by using just paper and pencil.

Properties of Algorithm:

• It should terminate after a finite time.
• It should produce at least one output.
• It should take zero or more input.
• It should be deterministic means giving the same output for the same input case.
• Every step in the algorithm must be effective i.e. every step should do some work.

Types of Algorithms:

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

1. Brute Force Algorithm :

It is the simplest approach to 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 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 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 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 for the next part is built based on the immediate benefit of the next part. The one solution that gives 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.

To learn more about the types of algorithms refer to the article about “ Types of Algorithms “.

Advantages of Algorithms:

• It is easy to understand.
• An algorithm is a step-wise representation of a solution to a given problem.
• In an Algorithm the problem is broken down into smaller pieces or steps hence, it is easier for the programmer to convert it into an actual program.

Disadvantages of Algorithms :

• Writing an algorithm takes a long time so it is time-consuming.
• Understanding complex logic through algorithms can be very difficult.
• Branching and Looping statements are difficult to show in Algorithms (imp) .

How to Design an Algorithm?

To write an algorithm, the following things are needed as a pre-requisite: 

• The problem that is to be solved by this algorithm i.e. clear problem definition.
• The constraints of the problem must be considered while solving the problem.
• The input to be taken to solve the problem.
• The output is to be expected when the problem is solved.
• The solution to this problem is within the given constraints.

Then the algorithm is written with the help of the above parameters such that it solves the problem.

Example: Consider the example to add three numbers and print the sum.

Step 1: Fulfilling the pre-requisites  

As discussed above, to write an algorithm, its prerequisites must be fulfilled. 

• The problem that is to be solved by this algorithm : Add 3 numbers and print their sum.
• The constraints of the problem that must be considered while solving the problem : The numbers must contain only digits and no other characters.
• The input to be taken to solve the problem: The three numbers to be added.
• The output to be expected when the problem is solved: The sum of the three numbers taken as the input i.e. a single integer value.
• The solution to this problem, in the given constraints: The solution consists of adding the 3 numbers. It can be done with the help of the ‘+’ operator, or bit-wise, or any other method.

Step 2: Designing the algorithm

Now let’s design the algorithm with the help of the above pre-requisites:

Algorithm to add 3 numbers and print their sum:  

• Declare 3 integer variables num1, num2, and num3.
• Take the three numbers, to be added, as inputs in variables num1, num2, and num3 respectively.
• Declare an integer variable sum to store the resultant sum of the 3 numbers.
• Add the 3 numbers and store the result in the variable sum.
• Print the value of the variable sum

Step 3: Testing the algorithm by implementing it.

To test the algorithm, let’s implement it in C language.

Here is the step-by-step algorithm of the code:

• Declare three variables num1, num2, and num3 to store the three numbers to be added.
• Declare a variable sum to store the sum of the three numbers.
• Use the cout statement to prompt the user to enter the first number.
• Use the cin statement to read the first number and store it in num1.
• Use the cout statement to prompt the user to enter the second number.
• Use the cin statement to read the second number and store it in num2.
• Use the cout statement to prompt the user to enter the third number.
• Use the cin statement to read and store the third number in num3.
• Calculate the sum of the three numbers using the + operator and store it in the sum variable.
• Use the cout statement to print the sum of the three numbers.
• The main function returns 0, which indicates the successful execution of the program.

Time complexity: O(1) Auxiliary Space: O(1) 

One problem, many solutions: The solution to an algorithm can be or cannot be more than one. It means that while implementing the algorithm, there can be more than one method to implement it. For example, in the above problem of adding 3 numbers, the sum can be calculated in many ways:

• Bit-wise operators

How to analyze an Algorithm? 

For a standard algorithm to be good, it must be efficient. Hence the efficiency of an algorithm must be checked and maintained. It can be in two stages:

1. Priori Analysis:

“Priori” means “before”. Hence Priori analysis means checking the algorithm before its implementation. In this, the algorithm is checked when it is written in the form of theoretical steps. This Efficiency of an algorithm is measured by assuming that all other factors, for example, processor speed, are constant and have no effect on the implementation. This is done usually by the algorithm designer. This analysis is independent of the type of hardware and language of the compiler. It gives the approximate answers for the complexity of the program.

2. Posterior Analysis:

“Posterior” means “after”. Hence Posterior analysis means checking the algorithm after its implementation. In this, the algorithm is checked by implementing it in any programming language and executing it. This analysis helps to get the actual and real analysis report about correctness(for every possible input/s if it shows/returns correct output or not), space required, time consumed, etc. That is, it is dependent on the language of the compiler and the type of hardware used.

What is Algorithm complexity and how to find it?

An algorithm is defined as complex based on the amount of Space and Time it consumes. Hence the Complexity of an algorithm refers to the measure of the time that it will need to execute and get the expected output, and the Space it will need to store all the data (input, temporary data, and output). Hence these two factors define the efficiency of an algorithm.  The two factors of Algorithm Complexity are:

• Time Factor : Time is measured by counting the number of key operations such as comparisons in the sorting algorithm.
• Space Factor : Space is measured by counting the maximum memory space required by the algorithm to run/execute.

Therefore the complexity of an algorithm can be divided into two types :

1. Space Complexity : The space complexity of an algorithm refers to the amount of memory required by the algorithm to store the variables and get the result. This can be for inputs, temporary operations, or outputs. 

How to calculate Space Complexity? The space complexity of an algorithm is calculated by determining the following 2 components:   

• Fixed Part: This refers to the space that is required by the algorithm. For example, input variables, output variables, program size, etc.
• Variable Part: This refers to the space that can be different based on the implementation of the algorithm. For example, temporary variables, dynamic memory allocation, recursion stack space, etc. Therefore Space complexity S(P) of any algorithm P is S(P) = C + SP(I) , where C is the fixed part and S(I) is the variable part of the algorithm, which depends on instance characteristic I.

Example: Consider the below algorithm for Linear Search

Step 1: START Step 2: Get n elements of the array in arr and the number to be searched in x Step 3: Start from the leftmost element of arr[] and one by one compare x with each element of arr[] Step 4: If x matches with an element, Print True. Step 5: If x doesn’t match with any of the elements, Print False. Step 6: END Here, There are 2 variables arr[], and x, where the arr[] is the variable part of n elements and x is the fixed part. Hence S(P) = 1+n. So, the space complexity depends on n(number of elements). Now, space depends on data types of given variables and constant types and it will be multiplied accordingly.

2. Time Complexity : The time complexity of an algorithm refers to the amount of time required by the algorithm to execute and get the result. This can be for normal operations, conditional if-else statements, loop statements, etc.

How to Calculate , Time Complexity? The time complexity of an algorithm is also calculated by determining the following 2 components: 

• Constant time part: Any instruction that is executed just once comes in this part. For example, input, output, if-else, switch, arithmetic operations, etc.

Example: In the algorithm of Linear Search above, the time complexity is calculated as follows:

Step 1: –Constant Time Step 2: — Variable Time (Taking n inputs) Step 3: –Variable Time (Till the length of the Array (n) or the index of the found element) Step 4: –Constant Time Step 5: –Constant Time Step 6: –Constant Time Hence, T(P) = 1 + n + n(1 + 1) + 1 = 2 + 3n, which can be said as T(n).

How to express an Algorithm?

• Natural Language:- Here we express the Algorithm in the natural English language. It is too hard to understand the algorithm from it.
• Flow Chart :- Here we express the Algorithm by making a graphical/pictorial representation of it. It is easier to understand than Natural Language.
• Pseudo Code :- Here we express the Algorithm in the form of annotations and informative text written in plain English which is very much similar to the real code but as it has no syntax like any of the programming languages, it can’t be compiled or interpreted by the computer. It is the best way to express an algorithm because it can be understood by even a layman with some school-level knowledge.

Solve DSA problems on GfG Practice.

• DSA in Java
• DSA in Python
• DSA in JavaScript

Please Login to comment...

• RishabhPrabhu
• pushpeshrajdx01
• AnubhavMittal
• kingrishabdugar
• shivanisinghss2110
• itskawal2000
• susobhanakhuli
• shraddhajain3131
• amartyaghoshgfg
• piyushsri20146
• utkarshstm2016
• newsandeepkushwaha
• laxmishinde5t82
• snehalmahasagar

Please write us at contrib[email protected] to report any issue with the above content

Improve your Coding Skills with Practice

Computer Science Courses

Computer Fundamentals Practice Tests

Computer Fundamentals Tests

Steps in Problem Solving MCQ Quiz PDF Download

The Book Steps in Problem Solving Multiple Choice Questions (MCQ Quiz) , Steps in Problem Solving quiz answers PDF to learn online courses, computer fundamentals tests. Study Using Computers to Solve Problems Multiple Choice Questions and Answers (MCQs) , Steps in Problem Solving quiz questions for computer information science. The eBook Steps in Problem Solving MCQ App Download: representing algorithms flowcharts and structure diagram, steps in systems analysis and design, computer systems, program design and implementation test prep to learn online certificate courses.

The MCQ: Last step in process of problem solving is to PDF, "Steps in Problem Solving" App Download (Free) with design a solution, define a problem, practicing the solution, and organizing the data choices for computer information science. Practice steps in problem solving quiz questions , download Amazon eBook (Free Sample) for computer software engineer online degree.

Computer Fundamentals: Steps in Problem Solving MCQs PDF Download

MCQ : Last step in process of problem solving is to

MCQ : Second step in problem solving process is to

MCQ : Thing to keep in mind while solving a problem is

MCQ : First step in process of problem solving is to

Practice Tests: Computer Fundamentals Exam Prep

Download free apps (android & ios).

Download Computer Fundamentals Quiz App, Database Management System MCQ App, and Operating Systems MCQs App to install for Android & iOS devices. These Apps include complete analytics of real time attempts with interactive assessments. Download Play Store & App Store Apps & Enjoy 100% functionality with subscriptions!

ALL-in-ONE Courses App Download

Computer Fundamentals App Download

Database Management System Quiz App

Operating Systems Quiz App

Computer Fundamentals MCQs eBook Download

Computer Fundamentals MCQ Book PDF

Computer Networks Practice Questions

Computer networks mcq questions, steps in problem solving mcqs book questions, try web app.

Try our FREE mobile apps for an amazing & interactive experience. Buy PREMIUM with trial period to see all analytics, complete history, answer keys to improve your premium insights. We assure you to enjoy PREMIUM!

Computer Fundamentals MCQ with Answers PDF Download (Class 7-12 CS Book‪)‬

Quiz questions chapter 1-16 & practice tests with answers key (computer fundamentals mcqs pdf: textbook notes & study material), publisher description.

The Book Computer Fundamentals MCQ PDF Download (Class 7-12 CS Book 2023-24): MCQ Questions Chapter 1-16 & Practice Tests with Answers Key (Grade 7-12 Computer MCQs PDF: Textbook Notes & Study Guide) includes revision guide for problem solving with hundreds of solved MCQs. Computer Fundamentals MCQ with Answers PDF book covers basic concepts, analytical and practical assessment tests. "Computer Fundamentals MCQ" PDF book helps to practice test questions from exam prep notes. The eBook Computer Fundamentals MCQs with Answers PDF includes revision guide with verbal, quantitative, and analytical past papers, solved MCQs. Computer Fundamentals Multiple Choice Questions and Answers (MCQs) PDF Download , a book covers solved quiz questions and answers on chapters: Applications of computers, commercial applications, central processing unit and execution of programs, communications hardware-terminals and interfaces, introduction to computer software and hardware, data preparation and input, digital logic, file systems, information processing, input errors and program testing, jobs in computing, processing systems, representation of data, storage devices and media, using computers to solve problems, and programming languages tests for school and college revision guide. Computer Fundamentals Quiz Questions and Answers PDF download, free eBook’s sample covers beginner's solved questions, textbook's study notes to practice tests. The Book Class 7-12 Computer Fundamentals MCQs Chapter 1-16 PDF includes high school question papers to review practice tests for exams. Computer Fundamentals Multiple Choice Questions (MCQ) with Answers PDF digital edition eBook, a study guide with textbook chapters' tests for NEET/Jobs/Entry Level competitive exam. Grade 7-12 Computer Fundamentals Practice Tests Chapter 1-16 PDF covers problem solving exam tests from computer science textbook and practical eBook chapter-wise as: Chapter 1: Applications of Computers: Commercial Applications MCQ Chapter 2: Central Processing Unit and Execution of Programs MCQ Chapter 3: Communications Hardware: Terminals and Interfaces MCQ Chapter 4: Computer Software MCQ Chapter 5: Data Preparation and Input MCQ Chapter 6: Digital Logic Design MCQ Chapter 7: File Systems MCQ Chapter 8: Information Processing MCQ Chapter 9: Input Errors and Program Testing MCQ Chapter 10: Introduction to Computer Hardware MCQ Chapter 11: Jobs in Computing MCQ Chapter 12: Processing Systems MCQ Chapter 13: Programming Languages and Style MCQ Chapter 14: Representation of Data MCQ Chapter 15: Storage Devices and Media MCQ Chapter 16: Using Computers to Solve Problems MCQ Practice Applications of Computers: Commercial Applications MCQ book, chapter 1 test to solve MCQ questions: Stock control software. Practice Central Processing Unit and Execution of Programs MCQ book, chapter 2 test to solve MCQ questions: Fetch execute cycle, programs and machines, computer registers, typical instruction format, and set. Practice Communications Hardware: Terminals and Interfaces MCQ book, chapter 3 test to solve MCQ questions: Communication, user interfaces, remote and local, and visual display terminals. Practice Computer Software MCQ book, chapter 4 test to solve MCQ questions: Applications, system programs, applications programs, operating systems, program libraries, software evaluation, and usage. Practice Data Preparation and Input MCQ book, chapter 5 test to solve MCQ questions: Input devices, bar codes, document readers, input at terminals and microcomputers, tags and magnetic stripes, computer plotters, types of computer printers, and use of keyboards. Practice Digital Logic Design MCQ book, chapter 6 test to solve MCQ questions: Logic gates, logic circuits, and truth tables. Practice File Systems MCQ book, chapter 7 test to solve MCQ questions: File usage, file storage and handling of files, sorting files, master and transaction files, updating files, computer architecture, computer organization and access, databases and data banks, searching, merging, and sorting. Practice Information Processing MCQ book, chapter 8 test to solve MCQ questions: Processing of data, data processing cycle, data and information, data collection and input, encoding, and decoding. Practice Input Errors and Program Testing MCQ book, chapter 9 test to solve MCQ questions: Program errors, detection of program errors, error correction, and integrity of input data. Practice Introduction to Computer Hardware MCQ book, chapter 10 test to solve MCQ questions: Peripheral devices, digital computers, microprocessors, and microcomputers. Practice Jobs in Computing MCQ book, chapter 11 test to solve MCQ questions: Computer programmer, data processing manager, and software programmer. Practice Processing Systems MCQ book, chapter 12 test to solve MCQ questions: Batch processing in computers, real time image processing, multi access network, and multi access system. Practice Programming Languages and Style MCQ book, chapter 13 test to solve MCQ questions: Introduction to high level languages, programs and program languages, program style and layout, control statements, control statements in basic and Comal language, data types and structural programming, structures, input output, low level programming, subroutines, procedures, and functions. Practice Representation of Data MCQ book, chapter 14 test to solve MCQ questions: Binary representation of characters, data accuracy, binary representation of numbers, methods of storing integers, octal and hexadecimal, positive and negative integers, representation of fractions in binary, two states, and characters. Practice Storage Devices and Media MCQ book, chapter 15 test to solve MCQ questions: Backing stores, backup storage in computers, main memory storage, storage devices, and types of storage. Practice Using Computers to Solve Problems MCQ book, chapter 16 test to solve MCQ questions: Steps in problem solving, steps in systems analysis and design, computer systems, program design and implementation, program documentation.

More Books by Arshad Iqbal

Other books in this series.