15 Design and Analysis of Algorithms : Introduction

S. Sridhar

Module 1: Introduction

 

This module 1 focuses on the basics of the algorithm study. The Learning objectives of this module are as follows:

  • Need for Algorithms
  • Role of Algorithms
  • Characteristics of an Algorithms
  • Need for Efficiency
  • Classification of Algorithms

What is computing?

Computers have become integral part of our life. It is difficult to imagine a life without computers. Individuals use computers for variety of reasons such as document preparation, Internet browsing, sending emails, video games, performing numeric calculations, and this list goes on.

 

Industries and governments, on the other hand, use computers much more productivity such as airline reservation, video surveillance, bio-metric recognition, e-governance and e-commerce. Industries use computers for process control and quality testing. These applications improve the efficiency and productivity.

 

The popularity and necessity of computer systems have prompted schools and universities to introduce computer science as an integral part of our modern education.

 

The usage of computers have brought importance for two types of thinking.

1.  Computational Thinking: Computational thinking is the knowledge of using computers to perform our day to day activities. Computational thinking is the need of the hour and a necessary to survive in this world.

2.  Analytical Thinking: Computer science professionals are expected to do know the usage and also are required to provide computer based solutions for problems by writing computer programs for  it. Writing programs requires analytical skills. Algorithmic thinking is a necessary analytical skill that is required for solving problems and writing effective programs. Algorithmic thinking is generic and is not restricted to computer science domain.

What is computer Science?

 

There are many definitions of computer science. An apt definition of computer science is provided by two persons, Norman E Gibbs and Allen B Tucker1. It is proposed as part of the ACM curriculum for liberal art. The proposed definition is given as follows:

 

“Computer science is the study of algorithms or more precisely its formal (or mathematical) properties, hardware and linguistic realizations along with its applications”.

So, one can safely conclude that computer science is the study of algorithms and its manifestations. There are four types of manifestations given by their definition. They are listed as below:

  1. Formal and mathematical Properties of algorithms
  2. Computer Hardware used by algorithms
  3. Linguistic Realizations of algorithms
  4. Applications of Algorithms

1.   Formal and mathematical properties: This includes the study of algorithm correctness, algorithm design and algorithm analysis for understanding the behaviour of algorithms.

2.  Computer Hardware used by Algorithms: These are Hardware realizations that includes the computer hardware which is necessary to run the algorithms in the form of programs.

3.  Linguistic Realizations: These includes the study of programming languages and its design, translators like interpreters, compilers, linkers and loaders.

4.  Applications of Algorithms: This include the study of tools and packages.

 

1 Gibbs, N.E., Tucker, A.B. “A model Curriculum for a Liberal Arts Degree in Computer Science”, Communications of ACM, Vol. 29, No. 3 (1986).

Let us introduces some of the important terminologies.

  1. Algorithm: An algorithm is a set of unambiguous instructions or procedures for solving a given problem to provide correct and expected outputs for all valid and legal input data. Some of the other word words that are used for algorithms in literature are recipe, prescription, process or computational procedure.
  2. Algorithmics: The study of designing, implementing, analyzing algorithms is called Algorithmics.
  3. Input Instance: A valid input from legal set of input data for the algorithm is called an instance of an algorithm. A valid input can be called as an instance of a problem. For example, factorial of a negative number is not possible. So, all valid positive integers {0,1,2,…} can serves input and every legal input is called an instance.

Domain: All possible inputs of a problem are often called domain of the input data. The input should be encoded in a suitable form so that the computers can process.

 

Input Size: The number of binary bits used to represent the given input, say N, is called input size.

The word Algorithm is derived from the name of a Persian mathematician, Abu Ja’fer Mohammed Ibn Musa al Khowarizmi, who lived sometime around 780 – 850 AD. He wrote a book titled “Kitab al Jabr w’al Muqabala” (or Rules of Restoration and Reduction) where he introduced the old Indian-Arabic number systems to Europe. His name was quoted as Algorismus in Latin books and Algorithm is emerged as its corrupted form.

 

Simple Example

 

To illustrate the process of writing an elementary algorithm, let us try to write a procedure for preparing a tea. The input is tea powder, milk etc. The environment of a typical algorithm involves an agent, input, process and output. Here agent is the performer. Agent can be a human or a computer. The agent for preparing the tea is human and output of the procedure is tea. The procedure can be written as a step by step procedure as follows:

  1. Pour tea powder in a cup
  2. Boil the water and pour it into the cup and filter it
  3. Pour milk
  4. Put sugar if necessary
  5. Pour it into a cup.

This kind of procedure can be called an algorithm.

 

Likewise, algorithms can be written for all tasks. The algorithms, thus developed, for all the tasks share some commonalities. The commonalities are called characteristics of an algorithm.

 

The following characteristics of an algorithm are important. They are listed as below:

  1. Input: An algorithm can have zero or more inputs.
  2. Output: An algorithm should produce at least one or more outputs.
  3. Definiteness: By definiteness, it is meant that the instructions should be clear and unambiguous without any confusion. For example, division by zero is not a well-defined instruction.
  4. Uniqueness: The order of the instructions of an algorithm should be well defined as a change in the order of execution leads to wrong result or uncertainty.
  5. Correctness: The algorithm should be correct and yield expected results.
  6. Effectiveness: The algorithm should be traceable.
  7. Finiteness: An algorithm should have finite number of steps and should terminate.

Additionally, the algorithm should be simple (i.e., Ease of implementation, generality (An algorithm should be generic and not specific).

 

What is a program? A computer program is an algorithm in action. Algorithm thus acts as a blueprints that are used for constructing a house. In short, Program is an expression of that idea in a programming language.

 

What are the problems for which algorithms can be written?

 

Algorithms are feasible for computational problems. A computational problem is characterized by two factors – 1. The formalization of all legal  inputs and  expected outputs of a given  problem  2.  The characterization of the relationship between problem output and input. Non-computational problems are problems that cannot be solved by the computer system. For example, emotions and opinions. For example, it is not feasible to write a program for, say, offering opinion on Indian Literature.

 

Only computational problems can be solved by computers. One encounters many types of computational problems in the domain of computer science. Some of the problems are listed below:

  1. Structuring Problems: In structuring problems, the input is restructured based on certain conditions or properties. For example, Sorting is an example of a structuring problem.
  2. Search Problems: Search problem involves searching for a target in a list of all possibilities. Puzzles are good examples of search problems where the target or goal is searched in a huge list of feasible solutions.
  3. Construction Problems: These are the problems that involve the construction of solutions based on the constraints that are associated with the given problem.
  4. Decision problems: Decision problems are Yes/No type of problems where the algorithm output is restricted to answering Yes or No.
  5. Optimization Problems: Optimization problems are very important set of problems that are often encountered in computer science domain. The problems like finding shortest path or least cost solutions are optimization  problems.  These  problems  have  objective  function  and  a  set  of  constraints.  The solution is finding a solution that maximize or minimize the objective function while satisfying the constraints.

Let us discuss about the ways of writing a simple algorithm. Let us assume that there is a class (say, a tuition centre) where the following set of students are studying. The course marks are given as shown in Table 1. The students are expected to get 50 marks to pass. Given this table, find how many failures are there?

 

Table 1 Students Course Mark

Register Number Student Name Course Marks
1 Raghav 80
2 Preeti 30
3. John 83
4. Jones 23
5. Joseph 90

This can be done manually by checking each mark with 50. If the mark is less that 50, then the fail count can be incremented. Finally, when the list is over, the fail count is printed.

The informal algorithm is given as follows:

  1. Let counter = 1, Number of Students = 5
  2. Fail count = 0
  3. While (counter <= Number of students)
    1. 1 Read the student marks of the students
    2. 2 Compare the marks of the student with 50
    3. 3 If Student marks is less than 5 Then increment the fail count
    4. 4 Increment the counter
  4. Print fail count
  1. Exit

The above algorithm is a simple algorithm. But in reality, efficient algorithms are preferred. What is an efficient algorithm? An efficient algorithm is one that uses computer resources optimally. Why? Computer resources are limited.

Let us take a simple example of traveling salesperson problem (TSP). Informally, travelling salesperson is one starts in a city visits all other cities only once and returns back to the original city where he had started. This problem can be modeled as a graph.. A graph is a set of nodes and edges that interconnect the nodes. In this case, the cities are the nodes and edges are the path that connects the cities. Edges are undirected in this case. Alternatively, it is possible to move from a particular city to any other city or vice versa.

 

A brute force technique can be used for solving this problem.

  1. TSP problem involving only one city, there is no path!
  2. For two cities, there is only one path (A-B).
  3. For three cities, A, B, and C, the two paths are A – B – C and A – C – B, assuming A is the origin from where the traveling salesperson started.
  4. For four cities, A,B, C and D, the paths are { A –D- B-C-A, A-D-C-B-A, A-B-C-D-A, A-B-D- C-A, A-C-D-B-A and A-C-D-B-A}.

This is shown in Table 2.

Number of Cities Number of routes
1 0  (As there is no route)
2 1
3 2
4 6

Thus it can be noted that every addition of a city increases the path exponentially. Table 2 shows the number of possible routes. It can be seen that for N cities, the number of paths are

  • )! Thus, for 51 cities, the paths are (51-1)! = 50!

50! is

 

Thus, one can imagine that for larger values of N ( Say all the cities of India or China), the number of paths are very large and even if a computer takes a second for exploring a route, the algorithm would run for many months. This shows that efficiency of algorithms is very important and thus designing such algorithms are very important.

 

In short, one can conclude as part of this module 1 that

  • Computer Science core is algorithm study
  • Algorithmic thinking is necessary to solve problems
  • Algorithms is the blueprint of how to solve problems
  • Efficiency is a necessity for algorithms

References:

  1. S.Sridhar – Design and Analysis of Algorithms, Oxford University Press, 2014.
  2. Cormen, T.H., C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA 1992.
  3. Gibbs, N.E., Tucker, A.B. “A model Curriculum for a Liberal Arts Degree in Computer Science”, Communications of ACM, Vol. 29, No. 3 (1986).