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, biometric 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 Tucker[1]. 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:
- Formal and mathematical Properties of algorithms
- Computer Hardware used by algorithms
- Linguistic Realizations of algorithms
- 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.
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
5. Put sugar if necessary
6. 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
2. While (counter <= Number of students)
2.1 Read the student marks of the students
2.2 Compare the marks of the student with 50
2.3 If Student marks is less than 50
Then increment the fail count
2.4 Increment the counter
3. Print fail count
4. 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.
Table 2: Complexity of TSP
| 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
(N-1)! 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:
- S.Sridhar – Design and Analysis of Algorithms, Oxford University Press, 2014.
- Cormen, T.H., C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA 1992.
- 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).
Design and Analysis of Algorithms – Module 1
Component –V – Assessment & Evaluation
Multiple Choice Questions with Answer
| Correct Option | Q-1 | What is a computation problem? |
| A | A problem that can be solved with difficulty. | |
| Correct Option | B | A problem that has formal specification of input / output and the relationship that characterize input and output. |
| C | Solved by a human only. | |
| Feedback for Correct Option | A problem that has formal specification of input and relationship that characterize input and output. | |
| Feedback for Incorrect Option | A- This specifies the hardness and that is not focus. C- Specification is missing aspect and systems are not mentioned. | |
| Correct Option | Q-2 | Which Language is suited to specify algorithms? |
| A | Programming languages | |
| B | Natural Languages | |
| Correct Option | C | Pseudocode |
| Feedback for Correct Option | Combines natural English and Mathematics to specify algorithms. | |
| Feedback for Incorrect Option | A : Makes algorithm implementation language specific B: Natural language instructions are ambiguous |
True & False Statements
| Correct Answer | Q-3 | Computational thinking and Algorithmic thinking are different. |
| Correct Answer | True | |
| False | ||
| Feedback | Computational Thinking refers to usage of computers and algorithmic thinking is for designing algorithms. | |
| Q-4 | Algorithms are different from programs. | |
| Correct Answer | True | |
| False | ||
| Feedback | Algorithm in execution is called a program. | |
| Correct Answer | Q-5 | Giving an opinion is a computational problem |
| True | ||
| Correct Answer | False | |
| Feedback | Giving opinion is a non-computational problem. | |
| Correct Answer | Q-6 | Traveling salesperson is a computationally difficult problem |
| Correct Answer | True | |
| False | ||
| Feedback | Traveling salesperson is a difficult problem for larger instances. |
Fill in the Blanks
| Correct Answer | Q-7 | An algorithm should have ————— number of instructions |
| Option 1 | Infinite | |
| Option 2 | large | |
| Option 3 | Small | |
| Correct Answer | Option 4 | Finite |
| Feedback | An algorithm should have finite number of instructions. | |
| Q-8 | Time complexity refers to ————– time. | |
| Option 1 | Compile time | |
| Option 2 | Calendar time | |
| Correct Answer | Option 3 | Run time |
| Option 4 | None of the above | |
| Feedback | Time complexity refers to execution time. | |
| Q-9 | Definiteness of an algorithm refers to ————— of an instructions. | |
| Option 1 | Confusing instruction | |
| Correct Answer | Option 2 | Clear and Unambiguous |
| Feedback | Definiteness refers to clear and unambiguous nature of the instruction | |
| Correct Answer | Q-10 | Effectiveness of an algorithm refers to ———— of an algorithm. |
| Correct Answer | Option 1 | Traceability |
| Option 2 | Design activity | |
| Option 3 | Testability | |
| Feedback | Abstractionis indeed the process of determining the relevant properties and features of an object while ignoring nonessential details. |
Match the Columns
| Q-11 | Match the Columns |
| Algorist | Opinion about Indian Literature |
| Size | Algorithm is derived from his name |
| Algorithm | A legal input |
| Instance | Measure in logarithm |
| Abu Jaf’er Al Khowarzimi | Performer of an algorithm |
| Non-computational problem | A set by step procedure |
Note:State items in correct order, the LMS will put them in random order
Sequencing
| Q-12 | Please Arrange in ascending order for finding sum of an array |
| Order Number | Answer |
| 1 | Find the size of the array |
| 2 | Check whether the counter is less than size of the array |
| 3 | Initialize sum = 0 |
| 4 | Decide counter = 1 |
| 5 | Print sum |
| 6 | Increment the counter |
| 7 | Add array element to sum to get new sum |