Tutorial Map

1. Introduction
2. Role of Algorithms and Data Structures in Problem Solving
3. Role of Algorithms
4. Role of Data Structures
5. Types of Data Structures
6. Designing Algorithms and measuring their efficiency
7. Identifying Techniques for Designing Algorithms
   1. Divide and Conquer Approach
   2. Greedy Approach
8. Designing Algorithms using Recursion
   1. Tower of Hanoi
9. Determining the Efficiency of an Algorithm
   1. Time/Space Tradeoff
   2. Method for determining Efficiency
   3. Selecting an Efficient Algorithm
   4. Best, Worst, and Average Case Efficiency

Introduction

Computer science is a field of study that deals with solving a variety of problems by using computers. The problem to be solved could be as simple as performing the addition of two numbers, or as complex as designing a robot capable of making decisions in a real-time environment. To solve a given problem by using computer, you need to design an algorithm for it. The nature of an algorithm often depends closely on the nature of the data on which the algorithm works. Therefore, the study of algorithms also involves the study of the data structures that algorithms work on.

This tutorial discusses the role of algorithms and data structures in problem solving through computers. It also discusses some standard techniques that can be used to design algorithms. In addition, it discusses the effect of the selected algorithm on the efficiency of the solution.

Role of Algorithms and Data Structures in Problem Solving

Problem solving is an essential part of every scientific discipline. In today’s world, computers are widely used to solve problems pertaining to various domains, such as banking, commerce, medicine, manufacturing, and transport.

To solve a given problem by using a computer, you need to write a program for it. A program consists of two components, algorithm and data structure.

Many different algorithms can be used to solve the same problem. Similarly, various types of data structures can be used to represent a problem in a computer.

To solve the problem in an efficient manner,you need to select a combination of algorithms and data structures that provide maximum efficiency.

Role of Algorithms

The word algorithm is derived from the name of the persian mathematician Al Khwarizmi.

An algorithms can be defined as a step-by-step procedure for solving a problem. It helps the user arrive at the correct result in a finite number of steps. Consider the following step-by-step procedure to display the first 10 natural numbers:-

1. Set the value of counter to 1
2. Display counter
3. Increment counter by 1
4. If counter <=10, go to step 2

The preceding step-by-step procedure is an algorithm because it produces the correct result in a finite number of steps.

An algorithm has five important properties:-

• Finiteness: An algorithm terminates after a finite number of steps.
• Definiteness: Each step in an algorithm is unambiguous. This means that the action specified by the step cannot be interpreted in multiple ways and can be performed without any confusion.
• Input: An algorithm accepts zero or more inputs.
• Output: An algorithm produces at least one output.
• Effectiveness: An algorithm consists of basic instructions that are realizable. This means that the instructions can be performed by using the given inputs in a finite amount of time.

A problem can be solved by using a computer only if an algorithm can be written for it. In addition, the use of algorithm provides many other benefits:-

• While writing an algorithm, you identify the step-by-step procedure, the major decision points, and the variables necessary to solve the problem. This helps you in the development of the corresponding program.
• Identification of the procedure and the decision points reduces the problem into a series of smaller problems of more manageable size. Therefore, problems that would be difficult or impossible to solve as a whole can be approached as a series of small solvable sub problems.
• With the use of an algorithm, decision making becomes a more rational process. This is because algorithms comprise of sub tasks, where each sub task is atomic in nature and is supported by facts.
• With the use of an algorithm, the same specified steps are used for performing the tasks. This makes the process more consistent and reliable.

Role of Data Structures

Multiple algorithms can be designed to solve a particular problem. However, the algorithm may differ in how efficiently they can solve the problem. In such a situation, an algorithm that provides the maximum efficiency should be used for solving the problem. Efficiency here means that the algorithm should work in minimal time and use minimal memory.

One of the basic techniques for improving the efficiency of algorithms is to structure the data that they operate on in such a way that the resulting operations can be efficiently performed.

The way in which the various data elements are organized in memory with respect to each other is called a data structure.

Data can be organized in many different ways; therefore, you can create as many data structures as you want. However, there are some standard data structures that have proved useful over the years. These include arrays, linked lists, stacks, queues, trees and graphs. We will learn more about these data structures in the subsequent tutorials.

All these data structures are designed to hold a collection of data items. However, the differences lies in the way the data items are arranged with respect to each other and the operations that they allow. Because of the different ways in which the data items are arranged with respect to each other, some data structures prove to be more efficient that others to solve a given problem.

Suppose you have to write an algorithm that enables printer to service the requests of multiple users on a first-come-first-served (FCFS) basis. In this case, using a data structure that stores and retrieves the requests in the order of their arrival would be much more efficient than a data structure that stores and retrieves the requests in a random order.

In addition to improving the efficiency of an algorithm, the use of appropriate data structures also allows you to overcome some other programming challenges, such as:-

• Simplifying complex problems
• Creating standard, reusable code components

• Creating programs that are easy to understand and maintain

Consider an example where you have to find the maximum value in a set of 50 numbers, In this scenario, you can either use 50 variables or a data structure, such as an array of size 50, to store the numbers. When 50 different variables are used to store the numbers, the algorithm to determine the maximum value among the numbers can be written as:

1. Accept 50 numbers and store them in num1, num2, num3, .. num50
2. Set max = num1
3. If num2 > max then: max = num2
4. If num3 > max then: max = num3:
   .
   .
5. If num50 > max then max = num50
6. Display max

On the other hand, when an array of size 50 is used, the algorithm can be written as:-

1. Set max = num[0]
2. Repeat step3 varying i from 1 to 49
3. If num[i] > max then: max = num[i]
4. Display max

From the preceding two algorithms, it can be seen that the algorithm using an array manipulates memory much more efficiently than the algorithm using 50 variables. Also, the algorithm using an array involves few steps and is therefore, easier to understand and implement as compared to the algorithm that uses 50 variables.

Data structures also enable the creation of reusable code components. Suppose you have created a class to implement a data structure that stores and retrieves requests in the order of their arrival. Once the class is created, the same class can be used in several different applications that need to service the requests of multiple users on a FCFS basis.

This means that a data structure once implemented can be used as a standard component to provide a standard solution to a specific set of problems. The use of standard components helps simplify the maintenance process. This is because the standard components are time tested and therefore, do not need much maintenance.

Types of Data Structures

Data structures can be classified under the following two categories:

• Static: These are data structures whose size is fixed at compile time, and does not grow or shrink at runtime. An example of a static structure is an array. Suppose you declare an array of size 50, but store only 5 elements in it; the memory space allocated for the remaining 45 elements will be wasted. Similarly, if you have declared an array of size 50 but later want to store 20 more elements, you will not be able to store these extra required elements because of the fixed size of an array.
• Dynamic: These are data structures whose size is not fixed at compile time and that can grow and shrink at run time to make efficient use of memory. An example of a dynamic data structure would be a list of items for which memory is not allocated in advance. As and when items are added to the lists, memory is allocated for those elements. Similarly, when items are removed from the list, memory allocated to those elements is de-allocated. Such a list is called a linked list.

Note: Arrays and linked lists are basic data structures that are used to implement other data structures such as stacks, queues, trees and graphs.

An array is always a static data structure, and a linked list is always a dynamic data structure. However, the other data structures can be static or dynamic depending on whether they are implemented using an array or a linked list.

Designing Algorithms and measuring their efficiency

Designing an algorithm for a given problem is a difficult intellectual exercise. This is because there is no systematic method for designing an algorithm. Moreover, there may exist more than one algorithm to solve a problem, Writing an effective algorithm for a new problem or writing a better algorithm for an already existing one is an art as well as science because it requires both creativity and insight.

Identifying Techniques for Designing Algorithms

Although there is no systematic method for designing an algorithm, there are some well-known techniques that have probed to be quite useful in designing algorithms. Two commonly used techniques for designing algorithms are:-

Divide and Conquer Approach

The divide an conquer approach is an algorithm design technique that involves breaking down the problem recursively into sub problems until the sub problems become so small that they can directly be solved. The solutions to the sub problems are then combined to give a solution to the original problem.

Divide and conquer is a powerful approach for solving conceptually difficult problems. It simply requires you to find a way of:-

1. Breaking the problem into sub problems
2. Solving the trivial cases.
3. Combining the solutions of the sub problems to solve the original problem.

Divide and conquer often provides a natural way to design efficient algorithms.

Consider an example where you have to find the minimum value in a list of numbers. The lists is as shown in the figure:-

To find the minimum value, you can divide the list into two halves, as shown in the following figure:-

Again, divide each of the two lists into two halves as shown in the following figure:-

Now, there are only two elements in each list. At this stage, compare the two elements in each lists to find the minimum of the two. The minimum values from each of the four lists is shown in the following figures.

Again, compare the first two minimum values to determine their minimum. Also compare the last two minimum values to determine their minimum. The two minimum values thus obtained are shown in the following figure:-

Again, compare the two final minimum values to obtain the overall minimum value, which is 1 in the preceding example.

Designing Algorithms using Recursion

Recursion refers to the technique of defining a process in terms of itself. It is used to solve complex programming problems that are repetitive in nature.

The basic idea behind recursion is to break a problem into smaller versions of itself, and then build up a solution for the entire problem. This may sound similar to the divide and conquer technique. However, recursions not similar to the divide and conquer technique. Divide and conquer is a theoretical concept that may be implemented in a computer program with the help of recursion.

Recursion is implemented in a program by using a recursive procedure or function. A recursive procedure is a function which invokes itself.

Consider a function f(n), which is the sum of the first n natural numbers. This function can be defined in several different ways.

In mathematics, the function will be defined as:-

f(n) = 1 + 2 + 3 + …. + n

However, the same function can be defined in a recursive manner as:-

f(n) = f(n – 1) + n

Where n >1; and f(1) = 1

In this case, the recursive definition of the function f(n) calls the same function, but with its arguments reduced by one. The recursion will end n = 1, in which case f(1) = 1 has been defined.

To understand this concept, consider a factorial function. A factorial function is defined as:-

n! = 1 x 2 x 3 x 4 x .. x n

This same factorial function can be redefined as:-

n! = (n – 1)! x n

Where n > 1; and 0! = 1

This definition of n! is recursive because it refers to itself when it uses (n – 1)!.
The value of n! is explicitly given where n = 0; and the value of n! for arbitrary n is defined in terms of the smaller value of n, which is closer to the base value 0.

If you have to calculate 3! By using recursion. you first define 3! in terms of 2!:-

3! = (3 x 2!)

Now, you will define 2! in terms of 1!:-

3! = (3 x (2 x 1!))

Now, 1! will be defined in terms of 0!:-

3! = (3 x (2 x (1 x 0!)))

As, 0! is defined as 1, the expression becomes:-

3! = (3 x (2 x (1 x 1)))

3! = (3 x (2 x 1 ))

3! = (3 x 2)

3! = 6

This recursive algorithm for determining the factorial of a number n can be written as:-

Algorithm: Factorial(n)

1. If n = 0, then: //Terminating condition
   1. Return (1)
2. Return (n x Factorial(n – 1))

Please note that every recursive algorithm should have a terminating condition. Otherwise, the algorithm will keep on calling itself infinitely.

The main advantage of recursion is that it is useful in writing clear, short, and simple programs. One of the most common and interesting problems that can be solved using recursion is the Tower of Hanoi problem.

Tower of Hanoi

Tower of Hanoi is a classical problem, which consists on n different sized disks and three pins over which these disks can be mounted. All the disks are placed on the first pin with the largest disk at the bottom and the remaining disks in decreasing order of their size as shown in the following figure:-

The objective of the game is to move all disks from the first pin to the third pin in the least number of moves by using the second pin as an intermediary.

To play this game, you need to follow rules:-

• Only one disk can be moved at a time
• A larger disk cannot be placed over a smaller one

Let n be the number of the discs. If n = 3, it will require seven moves to transfer all discs from pin one to pin three, as shown in the table below.

The moves given in the preceding table ar illustrated in the following figures:-

When n = 2, we should move the top disc from pin 1 to pin 2, ,move the top disc from pin 1 to pin 3, and then move the top disc from pin 2 to pin 3.

The solution for n = 1 will be to move the disc from pin 1 to pin 3.

In general, to move n discs from pin 1 to pin 3 using pin 2 as an intermediary, you first need to move the top n – 1 discs from pin 1 to pin 2 using pin 3 as intermediary.

The following algorithm can be used to move the top n discs from the first pin START to final pin FINISH through the temporary pin TEMP:-

Move (n, START, TEMP, FINISH)

1. When n = 1:
   1. MOVE a disc from START to FINISH
   2. Return
2. Move the top n -1 discs from START to TEMP using FINISH as an intermediary [MOVE (n – 1, START, FINISH, TEMP)]
3. Move the top disc from START to FINISH
4. Move the top n – 1 discs from TEMP to FINISH using START as an intermediary [MOVE (n – 1, TEMP, START, FINISH)]

In general, this solution requires 2ⁿ-1 moves for n discs.

Determining the Efficiency of an Algorithm

The greatest difficulty in solving programming problems is not how to solve the problem, but how to solve the problem efficiently. Factors that affect the efficiency of a program include the speed of the machine, the compiler. the operating system, the programming language, and the size of the input. However, in addition to these factors, the way data of a program is organized, and the algorithm used to solve the problem also has a significant impact on the efficiency of a program.

There can be cases, where a number of methods and algorithms can be used to solve a problem. In such a situation, it can be difficult to decide which algorithm to use.

When there are several different ways to organize data and devise algorithms, it becomes important to develop criteria to recommend a choice. Therefore, you need to study the behavior of algorithms under various conditions and compare their efficiency.

The efficiency of an algorithm can be computed by determining the amount of resources it consumes. The primary resources that an algorithm consumes are:

• Time: The CPU time required to execute the algorithm
• Space: The amount of memory used by the algorithm for execution

The lesser resources that an algorithm uses, the more efficient it is.

Time/Space Tradeoff

To solve a given programming problem, many different algorithms may be used. Some of these algorithms may be extremely time-efficient and others extremely space-efficient.

Time/space tradeoff refers to a situation where you can reduce the use of memory at the cost of slower program execution, or reduce the running time at the cost of increased memory usage.

An example of a situation where a time/space tradeoff can be applied is that of data storage. If data is stored in a compressed form, the memory usage is less because data compression reduces the amount of space required. However, it is more time consuming because some additional time is required to run the compression algorithm. Similarly, if data is stored in its uncompressed form, the memory usage is more, but the running time is less.

Memory is generally perceived to be extensible because you can increase the memory of your computer. Time, however, is not extensible. Therefore, time considerations generally override memory considerations.

Method for determining Efficiency

Although, the efficiency of an algorithm depends on how efficiently it uses time and memory space, the scope of this course is limited to determining only the time efficiency of an algorithm.

To measure the time efficiency of an algorithm, you can write a program based on the algorithm, execute it, and measure the time it takes to run. The execution time that you measure in this case would depend on a number of factors such as:-

• Speed of the machine
• Compiler
• Operating System
• Programming language
• Input data

However, to determine how efficiently an algorithm solves a given problem, you would like to determine how the execution time is affected by the nature of the algorithm. Therefore, you need to develop fundamental laws that determine the efficiency of a program in terms of the nature of the underlying algorithm.

To understand how the nature of an algorithm affects the execution, consider a simple example. Suppose assignment, comparison, write, and increment statements take a, b, c, and d time units to execute respectively. Now, consider the following code used to display the elements stored in an array:-

1. Set I = 0 // 1 assignment
2. While(I < n): // n comparisons
   1. Display a[I] // n writes
   2. Increment I by 1 // n increments

The execution time required for the preceding algorithm is given by:-

T = a + b x n + c x n + d x n

T = a + n(b + c + d)

Here, T is the total running time of the algorithm expressed as a linear function of the number of elements (n) in the array. From the preceding expression, it is clear that T is directly proportional to n.

In fact, the total running time T is directly proportional to the number of iterations involved in the algorithm. The number of iterations can be determined by counting the number of comparisons involved in the algorithm.

In the preceding code segment, a total of n comparisons are being made. Therefore, the total running time of the algorithm, T is directly proportional to n.

As T is directly proportional to n, an increase in the value of n will result in a proportional increase in the value of T, as shown in the following figure.

Now, consider the following algorithm:-

1. Set I = 0 // 1 assignment
2. While (I < n): // n comparisons
   1. Set J = 0 // n assignments
   2. While (J < n): // n x n comparisons
      1. Display (a[I][J]) // n x n writes
      2. Increment J by 1 // n x n increments
   3. Increment I by 1 // n increments

If you count the number of comparisons in the preceding code segment, they come out to be (n ² + n), which is a quadratic function of n. Therefore, the total running time is directly proportional to n².

Note: Although the number of comparisons is n² + n, the value of n is very small as compared to the value of n² (especially when n is very large). Therefore, the value of n can be ignored for finding the approximate running time.

As the running time is directly proportional to n², an increase in the value of n will result in a quadratic increase in the running time. This means that if the value of n is doubled, the running time will increase four times. The rate of change of T with an increase in the value of n is depicted in the following figure:-

From the preceding discussion, you can conclude that the running time of a program is a function of n, where n is the size of the input data. The rate at which the running time of an algorithm increases as a result of an increase in the volume of input data is called the order of growth of the algorithm.

The order of growth of an algorithm is defined by using the big O notation. The big O notation has been accepted as a fundamental technique for describing the efficiency of an algorithm.

The following table lists some possible orders of growth, and their corresponding big O notations.

If an algorithm has a linear order of growth, the algorithm is said to be of the order O(n). Similarly, if an algorithm has a quadratic order of growth, the algorithm is said to be of the order O(n ²).

Selecting an Efficient Algorithm

Now that you know how the efficiency of a particular algorithm is determined, let us see how this knowledge can be used to select an efficient algorithm.

According to their orders of growth, the big O notations can be arranged in an increasing order as:-

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O (2ⁿ) < O (10ⁿ)

Therefore, if a problem can be solved by using algorithms each of the preceding orders of growth, an algorithm of the order of O(1) will be considered best, and an algorithm of the order O(10ⁿ) will be considered the worst. The goal of algorithm development should be to make algorithms of the smallest possible orders.

The following table depicts the orders of growth for the preceding big O notations.

Big O Notation	Order of growth
O(1)
O(log n)
O(n)
O(n log n)
O(n2)
O(n3)
O(2n)
O(10n)

Now, consider that the assignment, comparisons, write and increment statements take a,b,c and d time units to execute, respectively. Also, suppose all arithmetic operations require e time units to execute. Now, consider the following two algorithms to find the sum of first n natural numbers:-

Algorithm A

1. Set sum = 0 // 1 assignment
2. Set i = 0 // 1 assignment
3. While (i <= n) // n comparisons
   1. Set sum = sum + i // n arithmetic operations, n assignments
   2. Increment i by 1 // n increments
4. Display (sum) // 1 write

Algorithm B

1. Set sum = (n x (n + 1))/2 // 3 arithmetic operations, 1 assignment
2. Display (sum) // 1 write

Both Algorithm A and Algorithm B perform the same task, that is, both determine the sum of the first n natural numbers. Algorithm A adds each number iteratively to a variable sum. However, Algorithm B uses a formula to calculate the sum of the first n natural numbers.

The execution time requires for Algorithm A is given by:-

T = (n + 2) x a + (n x b) + (1 x c) + (n x d) + (n x e)

T = an + 2n + bn + c + dn + en

T = c + n(a + b + d + e + 2)

As T is a linear function of n.

Therefore, the algorithm is of the order O(n).

Now determine the time required to execute algorithm B:-

T = (1 x a) + (1 x c) + (3 x e)

T = a + c + 3e

Unlike Algorithm A, the time taken by Algorithm B is a constant, and does not depend on the value of n. Therefore, the algorithm is of the order O(1).

Because Algorithm A is of the order O(n), the execution time of Algorithm A increases linearly with the value of n. However, Algorithm B is of the order O(1). Therefore, the execution time of Algorithm B is constant. This means that an increase in the value of n does not have any impact on the execution time of the algorithm. Therefore, however large the problem be, Algorithm A solves it in the same amount of time.

Suppose for n = 10, both Algorithm A and B take 10 nanoseconds(ns) to execute. However when n is increased to 100, Algorithm A will take 100 ns to execute, but Algorithm B will take only 10 ns to execute, Similarly, when n is increased to 1000, Algorithm A will take 1000 ns to execute, but Algorithm B will take only 10 ns.

This means that when the problem is very large in size, Algorithm B would prove to be much more efficient than Algorithm A.

Best, Worst, and Average Case Efficiency

Suppose you have a list of names in which you have to search for a particular name. You have designed an algorithm that searches the name in the list of n elements, by comparing the name to be searched with each element in the list sequentially.

The best case in this scenario would be if the first element in the list matches the name to be searched. The efficiency in that case would be expressed as O(1) because only one comparison was made.

Similarly, the worst case in this scenario would be if the complete list is traversed and the element is found at the end of the list or is not found in the list. The efficiency in that case would be expressed as O(n) because n comparisons were made.

Continuing with the same example, the average case efficiency can be obtained by finding the average number of comparisons. Here,

Minimum number of comparisons = 1

Maximum number of comparisons = n

Therefore, average number of comparisons = (n + 1)/2

(n + 1)2 is a linear function of n. Therefore, the average case efficiency will be expressed as O(n).

The worst case efficiency of the preceding search program can be improved by using an alternate search algorithm that provides a better worst case efficiency.

A search algorithm with a better worst case efficiency is binary search that provides an efficiency of O(log n) in the worst case. We will learn more about this algorithm in the subsequent tutorials.