Algorithm in C

7 Key excerpts on "Algorithm in C"

• 

  eBook - ePub

  Computer Fundamentals - 8th Edition

  Concepts, Systems & Applications

  • Pradeep K.Sinha(Author)
  • 2004(Publication Date)
  • BPB Publications

    (Publisher)

  If you know the steps for solving a problem, but while solving it, if you forget to apply some of the steps or you apply the steps in wrong sequence, you get a wrong answer. Similarly, while writing a computer program, if a programmer leaves out some of the instructions or writes the instructions in wrong sequence, the programmer gets a wrong answer when he/she executes the program on a computer. Hence, to produce an effective computer program it is necessary to write every instruction in the correct sequence. However, the instruction sequence (logic) of a computer program may be very complex. Hence, to ensure that the instructions of a program are appropriate for the problem at hand and are in the correct sequence, we must plan the program before writing it.

  ALGORITHM

  What is an Algorithm?

  Planning a program involves defining its logic (the correct sequence of instructions needed to solve the corresponding problem). The term algorithm refers to the logic of a program. It is a step-by-step description of how to arrive at a solution to a given problem. It is a sequence of instructions that when executed in the specified sequence, gives the desired results. In order to qualify as an algorithm, a sequence of instructions must possess the following characteristics:

  1. Each instruction should be precise and unambiguous.
  2. Each instruction should execute in a finite time.
  3. No instruction should repeat infinitely. This ensures that the algorithm terminates ultimately.
  4. After executing the instructions (when the algorithm terminates), the desired results are obtained.

  Sample Algorithms

  To gain insight into algorithms, let us consider some simple examples.

  Example 11.1.

  Fifty students in a class appeared in their final examination. The division column of their mark sheets contains the division (FIRST, SECOND, THIRD, or FAIL) obtained by them. If their mark sheets are available with you, write an algorithm to calculate and print the total number of students who passed in FIRST division.

  Algorithm:

  Step 1: Initialize Total_First_Division and Total_Marksheets_Checked to zero. Step 2: Take the mark sheet of the next student. Step 3: Check the division column of the mark sheet to see if it is FIRST. If no, go to Step 5. Step 4: Add 1 to Total_First_Division. Step 5: Add 1 to Total_Marksheets_Checked. Step 6: Is Total_Marksheets_Checked = 50? If no, go to Step 2. Step 7: Print Total_First_Division. Step 8: Stop.

  Example 11.2.

  There are 100 employees in an organization. The organization wants to distribute annual bonus to the employees based on their performance recorded in their annual appraisal forms. Each employee's appraisal form contains his/her basic salary and grade for his/her performance during the year. Grades are of three categories - ‘A’ for outstanding, ‘B’ for good, and ‘C’ for average performance. Bonus for an employee is 100% of basic salary for outstanding performance, 70% of basic salary for good performance, 40% of basic salary for average performance, and none for all other cases. Write an algorithm to calculate and print the total bonus amount.

  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

  Anyone Can Code

  The Art and Science of Logical Creativity

  • Ali Arya(Author)
  • 2020(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  3 A simple example of an algorithm is addition. When we add two numbers, we add the digits on the right-most column, and if the result is more than 10, we leave the right digit and carry over a one to the next column of digits and add them. This process continues all the way to the last column of digits on the left side. Assembly instruction set for your new furniture is another example of an algorithm although it is less precise than mathematical operations. And so is your method of the piling and folding laundry based on whose clothes or what types they are.

  We will discuss algorithms in Chapter 2 , but for now, let’s just say that they are well-defined sequence of rules and operations that depend on each other, flow logically, and together allow us to solve a problem. This definition is important because it shows the relationship between parts of an algorithm and also its purpose.

  Key Point: Algorithms are the basis of programming and are formed by a well-defined sequence of rules and operations that depend on each other, flow logically, and solve a problem.

  Exhibit I.1 shows a simple algorithm that we can use in a program to calculate a restaurant bill. We usually show algorithms in two common methods:

  EXHIBIT I.1   Simple algorithm. (a) Fixed set of operations, (b) with a rule.

  • Flowchart , a graphical representation with various operations shown with shapes in Exhibit I.1
  • Pseudocode , a plain text that is informal but somewhat structured into a clearly written text where each line corresponds to an operation.

  The text version of the Exhibit I.1a will be something like this:

  1. Add the price of all food items 2. Add tax 3. Ask the tip amount 4. Add tip

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Essential Algorithms

  A Practical Approach to Computer Algorithms Using Python and C#

  • Rod Stephens(Author)
  • 2019(Publication Date)
  • Wiley

    (Publisher)

  CHAPTER 1 Algorithm Basics

  Before you jump into the study of algorithms, you need a little background. To begin with, you need to know that, simply stated, an algorithm is a recipe for getting something done. It defines the steps for performing a task in a certain way.

  That definition seems simple enough, but no one writes algorithms for performing extremely simple tasks. No one writes instructions for how to access the fourth element in an array. It is just assumed that this is part of the definition of an array and that you know how to do it (if you know how to use the programming language in question).

  Normally, people write algorithms only for difficult tasks. Algorithms explain how to find the solution to a complicated algebra problem, how to find the shortest path through a network containing thousands of streets, or how to find the best mix of hundreds of investments to optimize profits.

  This chapter explains some of the basic algorithmic concepts you should understand if you want to get the most out of your study of algorithms.

  It may be tempting to skip this chapter and jump to studying specific algorithms, but you should at least skim this material. Pay close attention to the section “Big O Notation,” because a good understanding of run time performance can mean the difference between an algorithm performing its task in seconds, hours, or not at all.

  Approach

  To get the most out of an algorithm, you must be able to do more than simply follow its steps. You need to understand the following:

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Getting Started with Python

  Understand key data structures and use Python in object-oriented programming

  • Fabrizio Romano, Benjamin Baka, Dusty Phillips(Authors)
  • 2019(Publication Date)
  • Packt Publishing

    (Publisher)

  The study of algorithms is also important because it trains us to think very specifically about certain problems. It can serve to increase our mental and problem solving abilities by helping us isolate the components of a problem and define relationships between these components. In summary, there are four broad reasons for studying algorithms:

  1. They are essential for computer science and intelligent systems.
  2. They are important in many other domains (computational biology, economics, ecology, communications, ecology, physics, and so on).
  3. They play a role in technology innovation.
  4. They improve problem solving and analytical thinking.

  Algorithms, in their simplest form, are just a sequence of actions, a list of instructions. It may just be a linear construct of the form do x , then do y , then do z , then finish. However, to make things more useful we add clauses to the effect of, x then do y , in Python the if-else statements. Here, the future course of action is dependent on some conditions; say the state of a data structure. To this we also add the operation, iteration, the while, and for statements. Expanding our algorithmic literacy further we add recursion. Recursion can often achieve the same result as iteration, however, they are fundamentally different. A recursive function calls itself, applying the same function to progressively smaller inputs. The input of any recursive step is the output of the previous recursive step.

  Essentially, we can say that algorithms are composed of the following four elements:

  • Sequential operations
  • Actions based on the state of a data structure
  • Iteration, repeating an action a number of times
  • Recursion, calling itself on a subset of inputs

  Passage contains an image

  Algorithm design paradigms

  In general, we can discern three broad approaches to algorithm design. They are:

  • Divide and conquer
  • Greedy algorithms
  • Dynamic programming

  As the name suggests, the divide and conquer paradigm involves breaking a problem into smaller sub problems, and then in some way combining the results to obtain a global solution. This is a very common and natural problem solving technique, and is, arguably, the most commonly used approach to algorithm design.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Volume 1: Data structures based on linear relations

  • Xingni Zhou, Zhiyuan Ren, Yanzhuo Ma, Kai Fan, Xiang Ji(Authors)
  • 2020(Publication Date)
  • De Gruyter

    (Publisher)

  1  Introduction

  Main Contents

  • The concept of data structures
  • The basic requirements of algorithm design
  • The methods to analyze algorithm efficiency in terms of time and space complexities

  Learning Purposes

  • Understand the importance of data structure courses
  • Comprehend the concept of data structure
  • Comprehend the steps for algorithm/program design
  • Comprehend the methods for analyzing and evaluating algorithm efficiency

  1.1  Let’s begin with programming

  Everybody who has learned program design would know that programming is the way by which the human brain drives the computer. The famous Swiss computer scientist, the creator of Pascal, Niklaus Wirth proposed a famous equation regarding the concept of programming. He won the highest honor of computer science, Turing Award, with it. The equation only has one line of text:

  A l g o r i t h m + D a t a   S t r u c t u r e s = P r o g r a m

  Nicklaus Wirth published a book in 1976 named Algorithm + Data Structures = Program. It explains the function of data structures in program design. Before starting to program, two issues will have to be solved first: the design of algorithm and the design of data structures. Algorithms are strategies to solve problems, while data structures describe the data model of the information to be processed. A program is then a set of instructions used by the computer to process information based on the strategies.

  The aim of program design is to let the computer help human to finish the complex tasks at hand automatically. The fundamental focus of computer science and technologies is – “what can be automated and efficiently automated?”, “What is the process of transforming the concrete problem to an eventual solution via computers?”, “What is the role played by data structure and algorithms in that?”

  To solve problems via computers, the general steps are shown in Fig. 1.1

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Computer-based Problem Solving Process

  • Teodor Rus(Author)
  • 2015(Publication Date)
  • WSPC

    (Publisher)

  Computer-Based Problem Solving Process (CBPSP) is seen here as an adaptation of the Polya four steps methodology to the computer and consists of a well determined sequence of transformations undergone by the expression of the problem and its solution algorithm. Original form of the algorithm is a natural language expressions in the universe of discourse. This expression is mapped toward a machine language program form that can be executed by the computer. Upon execution completion the sequence of transformations is reversed, thus mapping the machine-language result back into the original universe of discourse. Formally this is an eight steps methodology:

  (1)Formulate the problem, that is, describe the problem as a relationship among data, conditions, and unknowns. Natural language may be used. A mathematical say tells us that if you can formulate it you can solve it!

  (2)Formalize the problem, that is, represent the relationship defining the problem as a well-formed expression of a logic language, which depends upon the problem domain. Arithmetic, geometry, statistics, mathematical logic, actuarial science, accounting, etc., are examples of languages that may be used.

  (3)Develop an algorithm that solves the problem. This means find a sequence of transformations that lead from data to the unknowns while observing the conditions. This sequence can be empirical, i.e., the result of an experimental analysis, or it can be formal (mathematical), i.e., the result of a systematic analysis.

  (4)Program the algorithm. To program an algorithm means to represent it as a well-formed expression of a machine language. Since the machine language is not natural for humans, high-level notations have been designed in order to handle the machine language. These notations evolved as high level programming languages, such as Ada, Algol, Assembly, C, Cobol, Fortran, Lisp, Machine language, Pascal, PL1, etc. [Landin (1966)]. The algorithm’s expression in a high-level programming language is called the (source) program of the algorithm.

  (5)Compile the (source) program. If the language used in Step 4 is different from the machine language then translate the source program expression into a machine language expression. The machine language expression thus obtained is called the target program.

  (6)Initiate program execution

  Sign up to read

  Learn more about book