Designing algorithms

7 Key excerpts on "Designing algorithms"

• 

  eBook - ePub

  Hands-On Data Structures and Algorithms with Python

  • Dr. Basant Agarwal(Author)
  • 2022(Publication Date)
  • Packt Publishing

    (Publisher)

  3 Algorithm Design Techniques and Strategies In the field of computing, algorithm design is very important for IT professionals for improving their skills and enabling growth in the industry. The algorithm design process starts with a substantial number of real-world computing problems, which must be clearly formulated for efficiently building the solution using one of the possible techniques from the range of algorithm design techniques available. The world of algorithms contains a plethora of techniques and design principles, mastery of which is required to tackle more difficult problems in the field. Algorithm designs are important in computer science, in general, to efficiently design the solution for a precisely formulated problem since a very sophisticated and complex problem can easily be solved with an appropriate algorithm design technique. In this chapter, we will discuss the ways in which different kinds of algorithms can be categorized. Design techniques will be described and illustrated, and we will further discuss the analysis of algorithms. Finally, we will provide detailed implementations for a few very important algorithms. In this chapter, we will look at the following algorithm design techniques: Divide and conquer Dynamic programming Greedy algorithms Algorithm design techniques Algorithm design is a powerful tool for viewing and clearly understanding well-posed, real-world problems. A straightforward, or brute-force, approach is available that is very simple, yet effective, for many problems. The brute-force approach is trying all possible combinations of solutions in order to solve any problem. For example, suppose a salesperson has to visit 10 cities across the country

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  C Programming

  Learn to Code

  • Sisir Kumar Jena(Author)
  • 2021(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  Section 3.5 will introduce the concept of programming and the different components involved in executing them.

  3.3 Algorithm Design

  Before we jump into the definition of an algorithm, let us look at the image shown in Figure 3.3 . We have taken this image from a cook book by Sanjeev Kapoor. The objective of using this image is to introduce you to different features of an algorithm. We are not here to learn cooking; instead, the picture will help you to understand how to write unambiguous statements in making a recipe. The procedure written in the image has a high resemblance to algorithm design.

  Figure 3.3 A cooking recipe.

  If you analyze the recipe, you can easily see that the steps are well written, and whoever follows the steps will able to cook a tasty “crisp pohe”. No actions are ambiguous, and the procedure mentions all the ingredients required to prepare the recipe. We can say that the method specified in the image is a step-by-step method to make the food, and the ingredients are known as the input for processing. Finally, the “crisp pohe” will be the output of this process.

  Now we are ready to explain the algorithm. By following the similar analogy discussed above, we can define an algorithm as follows:

  An algorithm is a sequence of unambiguous instructions for solving a problem in a finite amount of time.

  According to the programmer’s perspective, we write the algorithm to solve a given programming task that can easily be converted into a program statement irrespective of any programming language. For example, let the job be to add two numbers; then how do we write an algorithm for that? Following the problem-solving technique, we need to analyze and identify the input to our algorithm and what should be the output produced by it. In our case, the algorithm needs two numbers, and it will provide their addition as the result. After that, we need to write the step-by-step procedure to perform the addition operation. Every step must instruct the computer to do something, and upon completion of all the steps, the machine should produce the required result. The complete algorithm to solve the addition of two numbers will be discussed in the subsequent section.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  50 Algorithms Every Programmer Should Know

  An unbeatable arsenal of algorithmic solutions for real-world problems

  • Imran Ahmad(Author)
  • 2023(Publication Date)
  • Packt Publishing

    (Publisher)

  4

  Designing algorithms

  This chapter presents the core design concepts of various algorithms. It discusses the strengths and weaknesses of various techniques for Designing algorithms. By understanding these concepts, we will learn how to design efficient algorithms.

  This chapter starts by discussing the different choices available to us when Designing algorithms. Then, it discusses the importance of characterizing the particular problem that we are trying to solve. Next, it uses the famous Traveling Salesperson Problem (TSP ) as a use case and applies the different design techniques that we will be presenting. Then, it introduces linear programming and discusses its applications. Finally, it presents how linear programming can be used to solve a real-world problem.

  By the end of this chapter, you should be able to understand the basic concepts of designing an efficient algorithm. The following concepts are discussed in this chapter:

  • The various approaches to designing an algorithm
  • Understanding the trade-offs involved in choosing the correct design for an algorithm
  • Best practices for formulating a real-world problem
  • Solving a real-world optimization problem

  Let’s first look at the basic concepts of designing an algorithm.

  Introducing the basic concepts of designing an algorithm

  An algorithm, according to the American Heritage Dictionary, is defined as follows:

  A finite set of unambiguous instructions that given some set of initial conditions can be performed in a prescribed sequence to achieve a certain goal and that has a recognizable set of end conditions.

  Designing an algorithm is about coming up with this “finite set of unambiguous instructions ” in the most efficient way to “achieve a certain goal

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Computer Science, Algorithms and Complexity

  • Adele Kuzmiakova(Author)
  • 2020(Publication Date)
  • Arcler Press

    (Publisher)

  1.1.1. Analyzing Algorithms An algorithm is defined as a series of steps for solving a problem. The design and analysis process of algorithms is crucial for developing algorithms for solving different kinds of issues in computing and information technology. In abstract analysis of algoithms, it i’s common to approximate their complexity through the asymptotic sense, which is, estimating the complexity role for arbitrarily massive input. The word “analysis of algorithms” originally was developed by Donald Knuth. The algorithm analysis consists of an essential aspect of computational complexity concept, which offers theoretical valuation for the needed resources of the algorithm to resolve a particular computational problem. Many algorithms are developed to work with arbitrary length inputs. The analysis of algorithms refers to determining the aggregate of time or space resources needed to implement it. Typically, the proficiency or running period of an algorithm can be mentioned as a function pertaining to the input length of a number of steps, commonly referred to as time-complexity, memory capacity, or space complexity (KABAT, 2013). 1.1.1.1. Importance of Aalysis There i’s a need for discussing the analysis orithms and, plus how to select an advanced algorithm for solvinutational matters. Through analyarticuar problem, it i’s possible to start developing pattern recognition such that same kinds of problems may be solved with help from the algorithm. Usually, algorithms are different from each other, even though their goal is more or less the samor instance, it’sit is known that a group of numbers may be sorted by applying different algorithms. The amount of comparisons done by a single algorithm can differ from others with regards to the same input. Therefore, time complexity of the algorithms can dianwhile, there’s Computer Science, Algorithms and Complexity 4 there is need to evaluate the memory space needed by every algorithm (KABAT, 2013).

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Computing

  A Historical and Technical Perspective

  • Yoshihide Igarashi, Tom Altman, Mariko Funada, Barbara Kamiyama(Authors)
  • 2014(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  255 C H A P T E R 27 The Design of Computer Algorithms As described in Chapter 18, computers were traditionally built to calculate the solution to numerical problems such as the determination of the roots of an algebraic equation, or to process numerical data, e.g., the statistical calculation of national consensus data. However, for the last 40 years or more, a great deal of important work has also been done by computers for nonnumerical problems, such as sorting, searching, word or language processing, and solving combinatorial problems in software development, data communication, and the simulation of various biological, chemical, and physical processes. The design and analysis of computer algorithms have been developed in the context of such applications. 27.1 SORTING AND SEARCHING Sorting a sequence of numeric or alphanumeric items means rearrang-ing them in some specific order. Since a significant portion of data pro-cessing involves sorting, efficient sorting algorithms are of considerable importance for many practical problems [3, 7]. Sorting is one of the first problems for which algorithms were formally analyzed and evaluated. It is considered to be a fundamental problem in the area of algorithmics , mainly because sorting often plays an essential part of many algorithms. For example, sorting significantly facilitates a search for elements in some set or a list. A dictionary is a typical example of a sorted list. Words in a dictionary are usually arranged in an alphabetical order, which allows us to easily locate the word that we are trying to find in the dictionary. 256 ◾ Computing Some sorting methods were in use long before the invention of computers. For example, a card player sorts the cards of his hand so that each card is visible and individually accessible. Suppose that A , 2, 3, 4, 5, 6, 7, 8, 9, 10, J , Q , K are the order of the cards. The following method has been com-monly used among card players.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Cognitive Skills and Their Acquisition

  • John R. Anderson(Author)
  • 2013(Publication Date)
  • Psychology Press

    (Publisher)

  8 The Processes Involved in Designing Software Robin Jeffries, Althea A. Turner, Peter G. Polson

  University of Colorado

  Michael E. Atwood

  Science Applications, Inc., Denver

  Introduction

  The task of design involves a complex set of processes. Starting from a global statement of a problem, a designer must develop a precise plan for a solution that will be realized in some concrete way (e.g., as a building or as a computer program). Potential solutions are constrained by the need to eventually map this plan into a real-world instantiation. For anything more than the most artificial examples, design tasks are too complex to be solved directly. Thus, an important facet of designing is decomposing a problem into more manageable subunits. Design of computer systems, software design, is the particular design task to be focused on in this chapter.

  Software design is the process of translating a set of task requirements (functional specifications) into a structured description of a computer program that will perform the task. There are three major elements of this description. First, the specifications are decomposed into a collection of modules, each of which satisfies part of the problem requirements. This is often referred to as a modular decomposition. Second, the designer must specify the relationships and interactions among the modules. This includes the control structures, which indicate the order in which modules are activated and the conditions under which they are used. Finally, a design includes the data structures involved in the solution. One can think of the original goal-oriented specifications as defining the properties that the solution must have. The design identifies the modules that can satisfy these properties. How these modules are to be implemented is a programming task, which follows the design task.

  This chapter presents a theory of the global processes that experts use to control the development of a software design. After a review of some relevant literature, the theory is described in detail. Thinking aloud protocols collected from both expert and novice designers on a moderately complex problem provide evidence for these theoretical ideas. Finally, we speculate on how such processes might be learned.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  The Social Power of Algorithms

  • David Beer(Author)
  • 2019(Publication Date)
  • Taylor & Francis

    (Publisher)

  From a computational and programming perspective an ‘Algorithm = Logic + Control’; where the logic is the problem domain-specific component and specifies the abstract formulation and expression of a solution (what is to be done) and the control component is the problem-solving strategy and the instructions for processing the logic under different scenarios (how it should be done) (Kowalski, 1979). The efficiency of an algorithm can be enhanced by either refining the logic component or by improving the control over its use, including altering data structures (input) to improve efficiency (Kowalski, 1979). As reasoned logic, the formulation of an algorithm is, in theory at least, independent of programming languages and the machines that execute them; ‘it has an autonomous existence independent of “implementation details”’ (Goffey, 2008, p. 15).

  Some ideas explicitly take the form of an algorithm. Mathematical formulae, for example, are expressed as precise algorithms in the form of equations. In other cases problems have to be abstracted and structured into a set of instructions (pseudo-code) which can then be coded (Goffey, 2008). A computer programme structures lots of relatively simple algorithms together to form large, often complex, recursive decision trees (Neyland, 2015; Steiner, 2012). The methods of guiding and calculating decisions are largely based on Boolean logic (e.g., if this, then that) and the mathematical formulae and equations of calculus, graph theory and probability theory. Coding thus consists of two key translation challenges centred on producing algorithms. The first is translating a task or problem into a structured formula with an appropriate rule set (pseudo-code). The second is translating this pseudo-code into source code that when compiled will perform the task or solve the problem. Both translations can be challenging, requiring the precise definition of what a task/problem is (logic), then breaking that down into a precise set of instructions, factoring in any contingencies such as how the algorithm should perform under different conditions (control). The consequences of mistranslating the problem and/or solution are erroneous outcomes and random uncertainties (Drucker, 2013).

  The processes of translation are often portrayed as technical, benign and commonsensical. This is how algorithms are mostly presented by computer scientists and technology companies: that they are ‘purely formal beings of reason’ (Goffey, 2008, p. 16). Thus, as Seaver (2013) notes, in computer science texts the focus is centred on how to design an algorithm, determine its efficiency and prove its optimality from a purely technical perspective. If there is discussion of the work algorithms do in real-world contexts this concentrates on how algorithms function in practice to perform a specific task. In other words, algorithms are understood ‘to be strictly rational concerns, marrying the certainties of mathematics with the objectivity of technology’ (Seaver, 2013, p. 2). ‘Other knowledge about algorithms – such as their applications, effects, and circulation – is strictly out of frame’ (Seaver, 2013, pp. 1–2). As are the complex set of decision-making processes and practices, and the wider assemblage of systems of thought, finance, politics, legal codes and regulations, materialities and infrastructures, institutions, inter-personal relations, which shape their production (Kitchin, 2014).

  Sign up to read

  Learn more about book