U20EST109 - Problem Solving Approach

U20EST109 / PROBLEM SOLVING APPROACH LECTURE NOTES

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

SEMESTER: I YEAR: Jan 2020 – April 2020

Department of Computer science and Engineering Page 1

 U20EST109 - Problem Solving Approach

Syllabus:

U20EST109 PROBLEM SOLVING APPROACH C Hr

(Common to CSE,IT,CCE) 3 45

Course Objectives
 To identify the key concepts of computational thinking and problem solving.
 To know the basics of algorithm and data organization.
 To understand the fundamental algorithms and factoring methods.
 To know the basic concepts of array and problem solving techniques.
 To familiarize the concepts of text processing, pattern searching and recursive
algorithms.

Course Outcomes
After completion of the course, the students will be able to
CO1 - Explain the basic concepts of computational thinking and problem solving. (K2)
CO2 - Explain basic concepts of algorithm and data organization. (K2)
CO3 - Illustrate algorithmic solution to problem solving. (K3)
CO4 - Explain the concepts of array, merging, sorting & searching. (K2)
CO5 - Implement recursive algorithm to solve problems. (K3)

UNIT I INTRODUCTION (9 Hrs)

Computational Thinking - Information and Data - Converting Information into Data – Data
Capacity – Data Types and Encoding – Logic-Solving Problems – Limits of Computation –
Pseudocode and Flow Chart.

UNIT II ALGORITHMIC THINKING & DATA ORGANIZATION (9

Hrs)
Algorithmic Thinking: Algorithms – Software and Programming Languages – Actions. Data
Organization: Name list, Graph Hierarchies – Spread Sheets – Text processing – Patterns –
Pseudocode and Flow Chart.

UNIT III FUNDAMENTAL ALGORITHMS & FACTORING METHODS (9

Hrs)
Fundamental Algorithms: Exchanging – Counting – Summing – Factorial Computation –
Fibonacci Sequence – Reversing the Digit-Base Conversion – Character to number
conversion. Factoring Methods: Finding Square Root – Greatest Common Divisor – Prime
Number – Prime Factor – Pseudocode and Flow Chart.

UNIT IV ARRAY, MERGING, SORTING AND SEARCHING (9 Hrs)

Array Techniques: Introduction – Array order reversal – Array Counting or Histogramming
– Maximum and Minimum of a Set – Removal of Duplicate – Partitioning – Longest
monotone. Sorting and searching: Sorting by Bubble, Selection, Insertion. Searching: Linear,
Binary – Pseudocode and Flow Chart.

UNIT V TEXT PROCESSING, PATTERN SEARCHING & RECURSIVE

Department of Computer science and Engineering Page 2

ALGORITHM (9 Hrs)
Key word Searching – Text Line Adjustment – Linear Pattern Search – Sub Linear Pattern
Search. Recursion: Towers of Hanoi – Sample Generation – Combination Generation –
Permutation Generation – Pseudocode and Flow Chart.

Text Books
1. David Riley and Kenny Hunt, ―Computational Thinking for Modern Problem
Solver‖, Chapman & Hall / CRC Textbooks in Computing, 2014.
2. R. G.Dromey, ―How to solve it by Computer‖, PHI, 2008.
3. Vickers Paul, ―How to Think like a Programmer: Problem Solving for the Bewildered‖,
Cengage Learning EMEA, 2008.

Reference Books
1. V. Anton Spraul, ―Think Like a Programmer: An Introduction to Creative Problem
Solving‖, Cengage
Learning EMEA, 2012.
2. Harold Abelson & Gerald Jay Sussman, ―Structure and Interpretation of
Computer Programs‖, McGraw-Hill Book Company, 1997.
3. Don McAdam, Roger Winn,‖ A Problem-Solving Approach‖, Prentice Hall Canada; 2nd
Edition.
4. Kathryn Rentz, Paula Lentz, ―A Problem-solving Approach ―, McGraw-Hill Education,
2018.
5. Sham Tickoo ―A Problem-solving Approach‖, Delmar / Cengage Learning, 2009.

Web References
1. https://www.edx.org/learn/problem-solving
2. https://www.lynda.com/Business-Skills-tutorials/Problem-Solving-Techniques/553700-
2.html
3. https://www.classcentral.com/course/problem-solving-skills-6687
 UNIT - IV

UNIT IV ARRAY, MERGING, SORTING AND SEARCHING (9 Hrs)

Array Techniques: Introduction – Array order reversal – Array Counting or
Histogramming – Maximum and Minimum of a Set – Removal of Duplicate –
Partitioning – Longest monotone. Sorting and searching: Sorting by Bubble,
Selection, Insertion. Searching: Linear, Binary – Pseudocode and Flow Chart.

PART A (2 marks)

1. Define Array.
An array is a data structure that contains a group of elements. Typically these elements are
all of the same data type, such as an integer or string. Arrays are commonly used in computer
programs to organize data so that a related set of values can be easily sorted or searched.
For example, a search engine may use an array to store Web pages found in a search
performed by the user.

2. How to reverse an array.

1. Establish the array a[1… n] of n elements to be reversed.
2. Compute r the number of exchanges needed to reverse the array.
3. While there are still pairs of array elements to be exchanged
(a) exchange the ith element with the [n-i+1]th element.
4. Return the reversed array.

3. Define Histogramming.
 A histogram is a graphical representation of a grouped frequency distribution with
continuous classes.
 It is an area diagram and can be defined as a set of rectangles with bases along with the
intervals between class boundaries and with areas proportional to frequencies in the
corresponding classes.
 In such representations, all the rectangles are adjacent since the base covers the intervals
between class boundaries.
 The heights of rectangles are proportional to corresponding frequencies of similar classes
and for different classes, the heights will be proportional to corresponding frequency
densities.

4. What is called Maximum and minimum in a set?

1. Establish an array a[1….n] of n elements where n>=1.
2. Set temporary maximum max to first array element.
3. While less than n array elements have been considered do
(a) if next element greater than current maximum max then assign it to
max.
 4. Return maximum max for the array of n elements.

5. Define Partitioning. Write an algorithm to perform partition.

 It is defined as spliting the array in two parts: the lower half with objects
matching the condition, the upper half with objects not matching the
condition. This operation is called the partitioning of an array.

Algorithm:
1. Establish the array a[1.. n] and the partitioning value x.
2. Move the two partitions towards each other until a wrongly placed pair
of elements is encountered. Allow for special cases of x being outside the
range of array values.
3. While the two partitions have not met or crossed over do
(a) exchange the wrongly partitioned pair and extend both
partitions inwards by one element;
(b) extend left partition while elements less than or equal to x;
(c) extend the right partition while elements are greater than x.
4. Return the partitioning index p and the partitioned array.

6. What is called LMS (Longest Monotone Subsequence)?

 The longest increasing subsequence problem is to find a subsequence of a given
sequence in which the subsequence's elements are in sorted order, lowest to
highest, and in which the subsequence is as long as possible.
This subsequence is not necessarily contiguous, or unique.
 The Longest Increasing Subsequence (LIS) problem is to find the length of the
longest subsequence of a given sequence such that all elements of the
subsequence are sorted in increasing order.
 For example, the length of LIS for {10, 22, 9, 33, 21, 50, 41, 60, 80} is 6 and
LIS is {10, 22, 33, 50, 60, 80}.

7. Define Sorting. List its types.

 Sorting Algorithms are methods of reorganizing a large number of items into
some specific order such as highest to lowest, or vice-versa, or even in some
alphabetical order.
 These algorithms take an input list, processes it (i.e, performs some operations
on it) and produce the sorted list.
 The most common example we experience every day is sorting clothes or other
items on an e-commerce website either by lowest-price to highest, or list by
popularity, or some other order.

Types of sorting algorithms:

1. Quick sort
2. Bubble sort
3. Merge sort
4. Insertion sort
5. Selection sort
6. Heap sort
7. Radix sort
8. Bucket sort
8. Define Searching and list its types.
 Searching is the process of finding a given value position in a list of values.
 It decides whether a search key is present in the data or not.
 It is the algorithmic process of finding a particular item in a collection of items.
 It can be done on internal data structure or on external data structure.

Types of Searching:
 To search an element in a given array, it can be done in following ways:
1. Sequential Search or Linear search
2. Binary Search

9. Define Bubble sort.

 Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that
repeatedly steps through the list, compares adjacent elements and swaps them if they
are in the wrong order.
 The pass through the list is repeated until the list is sorted. The algorithm, which is
a comparison sort, is named for the way smaller or larger elements "bubble" to the top
of the list.
 This simple algorithm performs poorly in real world use and is used primarily as an
educational tool.
 More efficient algorithms such as quicksort, timsort, or merge sort are used by the
sorting libraries built into popular programming languages such as Python and Java.

10. Define Selection sort.

 Selection sort is an in-place comparison sorting algorithm. It has an O(n2) time
complexity, which makes it inefficient on large lists, and generally performs worse
than the similar insertion sort.
 Selection sort is noted for its simplicity and has performance advantages over more
complicated algorithms in certain situations, particularly where auxiliary memory is
limited.
 The algorithm divides the input list into two parts: a sorted sublist of items which is
built up from left to right at the front (left) of the list and a sublist of the remaining
unsorted items that occupy the rest of the list.
 Initially, the sorted sublist is empty and the unsorted sublist is the entire input list.

11. Define insertion sort.

 Insertion sort is a simple sorting algorithm that builds the final sorted array (or list)
one item at a time. It is much less efficient on large lists than more advanced
algorithms such as quicksort, heapsort, or merge sort.

Advantages:
 Simple implementation
 Efficient
 More efficient
 Adaptive,
 Stable
 In-place;
 Online;
12. Define Linear search.
In computer science, a linear search or sequential search is a method for finding an
element within a list.
It sequentially checks each element of the list until a match is found or the whole list
has been searched.
Class: Search algorithm
Worst-case space complexity: O(1) iterative
Best-case performance: O(1)

13. Define Binary search.

In computer science, binary search, also known as half-interval search, logarithmic
search, or binary chop, is a search algorithm that finds the position of a target value within
a sorted array.
Binary search compares the target value to the middle element of the array.
If they are not equal, the half in which the target cannot lie is eliminated and the
search continues on the remaining half, again taking the middle element to compare to the
target value, and repeating this until the target value is found.
If the search ends with the remaining half being empty, the target is not in the array.

PART B& C
1. Discuss the procedure to reverse an
array. Problem
Rearrange the elements in an array so that they appear in reverse order.

Algorithm development
The problem of reversing the order of an array of numbers appears to be completely
straightforward. Whilst this is essentially true, some care and thought must go into
implementing the algorithm.
We can start the design of this algorithm by careful examination of the elements of an
array before and after it has been reversed; for example,

What we observe from our diagram is that the first element ends up in the last
position. The second element ends up in the second last position and so on. Carrying this
process through we get the following set of exchanges:

In terms of suffixes the exchanges are:

Examining the effects of these exchanges we discover that after step [3] the array is
completely reversed.
The suffix [n- i+ 1] can then be used as our decreasing suffix. With these suffixes we
have

Each exchange (cf. algorithm 2.1) can be achieved by a mechanism of the form

Algorithm description
1. Establish the array a[1… n] of n elements to be reversed.
2. Compute r the number of exchanges needed to reverse the array.
3. While there are still pairs of array elements to be exchanged
(a) exchange the ith element with the [n-i+1]th element.
4. Return the reversed array.

Pascal implementation

Notes on design
1. To reverse an array of n elements [n/2] exchanges are required.
2. There are r= [n/2] pairs of elements in an array of n elements.
3. In practice where array elements need to be accessed in reverse order it is usually
not necessary to actually reverse the order of the array elements.
4. An example makes it easier to establish how many pairs of exchanges are required
in general for both even and odd array sizes.
5. To exchange a pair of array elements the same technique is employed as is used for
exchanging a pair of single variables.
6. There is a simpler algorithm for array reversal that starts out with two indices, i = 0
and j= n+1. With each iteration i is increased and j is decreased for i < j.

Applications
Vector and matrix processing.
2. Write short notes on Array counting or
Histogramming. Problem
Given a set of n students' examination marks (in the range 0 to 100) make a count of
the number of students that obtained each possible mark.

Algorithm development
This problem embodies the same principle as algorithm where we had to make a count
of the number of students that passed an examination. What we are required to do in this case
is obtain the distribution of a set of marks
The counting strategy we could then employ might be as follows:

An approach we could take is illustrated by the following diagram:

It is at this point that we need to recognize that an array can be usefully employed in
the solution to our problem. We can very easily set up an array with 101 locations, each
location corresponding to a particular mark value. For example,

It is necessary to add one to the previous count in location 57, we will need a
statement of the form:

Since location a[57] must play both the "previous count" and "new count" roles, we
can write

or for the general mark m we can write

Algorithm description
1. Prompt and read in n the number of marks to be processed.
2. Initialize all elements of the counting array a[0. . .100] to zero.
3. While there are still marks to be processed, repeatedly do
(a) read next mark m,
(b) add one to the count in location m in the counting array.
4. Write out the marks frequency count distribution.
Pascal Implementation

Notes on design
1. Essentially n steps are required to generate the frequency histogram for a set of n
marks.
th
2. After i iterations the j element in the a array will contain an integer representing
the number of marks j encountered in the first i marks.
3. The idea of indexing by value is important in many algorithms because of its
efficiency.

Applications
Statistical analyses.

3. Write a procedure to find the minimum and maximum element in an

array. Problem
Find the maximum number in a set of n numbers.

Algorithm development
To start on the algorithm development for this problem let us examine a particular set
of numbers. For example,

After studying this example we can conclude that all numbers need to be examined to
establish the maximum. A second conclusion is that comparison of the relative magnitude of
numbers must be made.
Three situations are possible:
1. the second number can be less than our temporary candidate for the maximum;
2. the second number can be equal to our temporary candidate for the maximum;
 3. the second number can be greater than our temporary candidate for the maximum.

Our initial proposal might therefore be:

Algorithm description
1. Establish an array a[1….n] of n elements where n>=1.
2. Set temporary maximum max to first array element.
3. While less than n array elements have been considered do
(a) if next element greater than current maximum max then assign it to max.
4. Return maximum max for the array of n elements.

Pascal implementation

Notes on design
1. The number of comparisons needed to find the maximum in an array of n elements
is n-1.
2. For all i in the range 1<=i<=n when i elements have been examined the variable
max is greater than or equal to all elements in the range 1 to i.
3. A way of establishing the initializing step is to consider the smallest possible
problem that can be solved by the algorithm.
4. Sometimes algorithms to find the maximum are initialized by setting max = 0.
Setting max initially to any fixed constant is bad programming practice
5. The generalization of this problem involves finding the kth smallest element in an
array.

Applications
Plotting, scaling, sorting.

4. Write an algorithm to remove the duplicate element present in an

array. Problem
Remove all duplicates from an ordered array and contract the array accordingly.

Algorithm development
As a starting point for this design let us focus on a specific example so that we have a
clear idea of exactly what is required.
 After the brief examination of an array we will be able to produce the contracted array
below:

With each comparison, only two situations are possible:

1. a pair of duplicates has been encountered;
2. the two elements are different.
It is fairly obvious that these two situations will always need to be treated differently.
To try to understand this, consider what happens when the four 23s are
encountered. We have:

For example, when the 26 is encountered and recorded as the next unique clement, we have
the configuration below:

Summarizing the basic steps so far in our mechanism we have:

To do this we have two initialization choices:

We may have noticed in exploring the problem that if there are no duplicates in the
array, then the repeated assignment

For this we can use a loop of the form

Algorithm description
1. Establish the array a[1…n] of n elements.
2. Set loop index i to 2 to allow correct termination.
 3. Compare successive pairs of elements until a duplicate is encountered then set
unique element count j.
4. While all pairs have not been examined do
(a) if next pair not duplicates then
(a.1) add one to unique element count j,
(a.2) move later element of pair to array position determined by the
unique element count j.

Pascal Implementation

Notes on design
1. To delete duplicates from an array of n elements (n-1) comparisons are required.
2. At the end of each iteration, the variable j represents the number of unique elements
encountered in examining the first (i-1) pairs of elements.
3. It may be conceptually convenient in this algorithm to think of the original data set
as a source array and the final data set with duplicates removed as the target data set.
4. A specific example is useful in developing the algorithm.
5. Inclusion of the first while-loop prevents unnecessary data movement operations.

Applications
Data compression and text processing problems.
5. Develop an algorithm to perform Partitioning of an array.
Problem
Given a randomly ordered array, of n elements, partition the elements into two subsets
such that elements <=x are in one subset and elements >x are in the other subset.

Algorithm development
Given the random data set below, we are asked to partition it into two subsets, one
containing elements <=17 and the other containing elements >17.

Clearly we need to be able to separate the two subsets. To do this, we could put those
elements >17 at the top end (the high suffix end) of the array and those <=17 at the bottom of
the array. One straightforward way of making this transfer is to sort the array into ascending
order. When we do this we get the configuration below.

For our example the configuration below:

let us re-examine and compare the original random set and the "unordered" solution to
the problem.

For example, the 28 could be placed where the 12 is and the 12 could be placed in the
28's original position. This idea can be extended and so we end up with the steps illustrated
below.

That is,

Similarly the 26 could be exchanged with the 6. What this exploration is starting to
suggest is that we can move in from both ends. When we do this we are actually "growing"
both the left and right partitions towards the middle.
That is
 If we continue this "pincer" process, the two partitions will eventually meet and when
they do we will have the desired partition for our complete data set. Working completely
through our example above, we get:

With these exchanges we end up with the partitioned set below:

It can be seen that this approach enables us to partition the data by making just one
pass rather than two passes through the array. We might therefore propose the following basic
partitioning mechanism:

This can be accomplished by a loop of the form:

Movement inwards from the right can proceed until we encounter an element smaller
than or equal to x; for this we can use a decreasing loop:

As soon as both loops have terminated we have detected an element at position i, that
must be moved to the right partition, and an element at j, that must be moved to the left
partition.

At this point the ith and jth elements can be exchanged. For the exchange we can use
the standard technique:

After the exchange we can start the "moving inwards" process again at positions (i+1)
and (j-1).
There are several possible configurations that can apply when the two partitions are
about to meet.
 There is a problem here because i, and j cross over before the last exchange is made.
This will lead to incorrect partitioning of the array. We will come back to this problem again
when we have looked at the other cases.

As in case 2, there are problems in case 4 as i and j can cross over before the last
exchange is made.

Algorithm description
1. Establish the array a[1.. n] and the partitioning value x.
2. Move the two partitions towards each other until a wrongly placed pair of elements
is encountered. Allow for special cases of x being outside the range of array values.
3. While the two partitions have not met or crossed over do
(a) exchange the wrongly partitioned pair and extend both partitions inwards
by one element;
(b) extend left partition while elements less than or equal to x;
(c) extend the right partition while elements are greater than x.
4. Return the partitioning index p and the partitioned array.
Pascal implementation

Notes on design
1. To partition an array into two subsets at most (n +2) comparisons of the form
a[i]<=x and a[j]>x must be made.
2. After each iteration the first (i-1) elements in the array are <=x and the last (n-j)
elements are >x.
3. In designing an algorithm, do not do more than is required. Sorted partitions are not
needed to solve the problem.
4. In the final design the problem is solved by only moving data when it is absolutely
necessary.
5. The final design is superior to the second design because it achieves the partitioning
more efficiently without knowledge of the partition location.
6. The idea of working inwards from both ends of the array gives the algorithm
balance.
7. If there are a lot of duplicates, some unnecessary exchanges are made.

Applications
Sorting, statistical classification.
6. Write a procedure to find the Longest Monotone
Sequence. Problem
Given a set of n distinct numbers, find the length of the longest monotone increasing
subsequence.

Algorithm development
A monotone increasing subsequence is a subset of numbers which are strictly
increasing from left to right. This definition does not require that the num-bers be adjacent in
the original set or that the longest sequence is unique. For example in the set below:

the sequence 1, 2, 4, 7, 11, 14, is a monotone increasing subsequence. The task at hand
is to find the longest such subsequence for a given sequence of integers.
Our subsequence is again:

In deriving this subsequence we notice that there are many other monotone increasing
subsequences present in the data:

To start with we will write down the lengths of the first five longest subsequences by
inspection and then we will try to work out a suitable mechanism.

Applying this observation to the longest sequence ending at position 6, we determine

that this sequence must be:

For example, we have:

A basic structure we can use for an array a[1 .. n] is:

Algorithm description:
1. Establish the data set a[1..n] of n elements.
2. Set initial conditions for subsequence terminating in the first position.
3. For the remaining (n-1) positions in the array do
(a) if current element less than maximum in the longest previous set then
(a.1) locate position and value of maximum among the
predecessors;
(a.2) update position and length of maximum if required; else update
length, position of maximum and the maximum length so far.
4. Return length of longest monotone increasing subsequence.

Pascal implementation
Notes on design
1. In the worst case (for a sequence in descending order) the algorithm will examine
data elements in n(n-1)+n= 1/2(n+1) times.
2. After the ith step in the outer loop the longest subsequences terminating with the
first i elements will have been determined.
3. In the development of this algorithm small specific examples play an important
role.
4. The idea of breaking a large problem down into a set of smaller simpler problems is
a valuable strategy in designing algorithms.
5. In this design we have seen how it is always important to try to make the best use of
a given piece of information
6. Because it is more efficient to reference a single variable than an indexed variable,
the current term a[i] (which is referenced frequently) has been assigned to a single
variable current.
7. With an additional n storage elements, it is possible to implement a more efficient
algorithm for this problem by linking together all elements with sequences of the same
length.

Applications
Studying random sequences, file comparison.

7. Write an algorithm to perform Bubble sort or Sort by

exchange. Problem
Given a randomly ordered set of n numbers sort them into non-descending order using
an exchange method.

Algorithm development
Almost all sorting methods rely on exchanging data to achieve the desired ordering.
The method we will now consider relies heavily on an exchange mechanism. Suppose we start
out with the following random data set:

This leads to the configuration below:

With this new change we get the configuration

After applying this idea to all adjacent pairs in our current data set we get the
configuration below:

Combining these observations with our earlier mechanism for comparing and
exchanging adjacent pairs the overall structure of our algorithm becomes:

Adjacent pairs can be compared using a test of the form

It is not hard to imagine, because of the nature of this sorting algorithm, that for many
data sets the array will be completely ordered well before i

Algorithm description
1. Establish the array a[1.. n] of n elements.
2. While the array is still not sorted do
(a) set the order indicator sorted to true;
 (b) for all adjacent pairs of elements in the unsorted part of the array do
(b.1) if current adjacent pair not in non-descending order then
(1.a) exchange the elements of the pair,
(1.b) set sorted to false.
3. Return the sorted array.

Pascal Implementation

Notes on design
1. The relevant parameters for analyzing this algorithm are the number of comparisons
and number of exchanges made.
2. A weakness of this algorithm is that it relies more heavily on exchanges than most
other sorting methods.
3. Examination of the intermediate configurations for the sample data set suggests that
the algorithm lacks balance and symmetry.

Applications
Only for sorting data in which a small percentage of elements are out of order.
8. Write an algorithm to perform Selection
sort. Problem
Given a randomly ordered set of n integers, sort them into non-descending order using
the selection sort.

Algorithm development
An important idea in sorting of data is to use a selection method to achieve the desired
ordering. In its simplest form at each stage in the ordering process, the next smallest value
must be found and placed in order. Consider the unsorted array:

What we are attempting to do is to develop a mechanism that converts the unsorted

array to the ordered configuration below:

Comparing the sorted and unsorted arrays we see that one way to start off the sorting
process would be to perform the following two steps:
1. Find the smallest element in the unsorted array;
2. Place the smallest element in position a[1].

The following construct can be used to find the smallest element:

Then the assignment below can be used to put the minimum in position

Performing these two steps on the unsorted array we get:

This step can be added to our previous code:

 The 20 and the 3 can then be swapped using the following statements (note the 3 is
saved in the temporary variable min) which will need to be placed outside the loop for finding
the minimum.

The steps we need are therefore:

That is,

Before actually considering the details of the implementation see Fig. 5.3, where the
complete sort for our example is shown.
Algorithm description
l . Establish the array a[1.. n] of n elements.
2. While there are still elements in the unsorted part of the array do
(a) find the minimum min and its location p in the unsorted part of the array a[i
.. n];
(b) exchange the minimum min in the unsorted part of the array with the first
element a[i] in the unsorted array.

Pascal implementation

Notes on design
1. In analyzing the selection sort algorithm there are three parameters that are
important: the number of comparisons made, the number of exchanges made, and the
number of times the minimum is updated.
2. After the ith step of the outer loop the first i values a[1 . .i] have been placed in non-
descending order (i.e. a[1]<=a[2]<=….<=a[i] ).
3. Of the simple sorting algorithms the selection sort is one of the best because it
keeps to a minimum the number of exchanges made.
 4. In this design we saw how a complete algorithm is built by first designing an
algorithm to solve the simplest problem.
5. The number of comparisons required by the selection sort can be reduced by
considering elements in pairs and finding the minimum and maximum at the same
time.
6. There are more sophisticated and efficient ways of carrying out the selection
process. We will examine some of these later.

Applications
Sorting only small amounts of data—much more efficient methods are used for large
data sets.

9. Develop an algorithm to perform Insertion sort.

Problem
Given a randomly ordered set of n numbers sort them into non-descending order using
an insertion method.

Algorithm development
Central to this algorithm is the idea of building up the complete solution by inserting
an element from the unordered part into the current partially ordered solution, extending it by
one element.
This mechanism is suggestive of a selection sort where we selected the smallest
element in the unordered part and placed it on the end of the sorted part. We have:

A simple, systematic, and alternative way we could choose the next item to be inserted is to
always pick the first element in the unordered part (i.e. x in our example).

At this stage the outline for our insertion sort algorithm is:

Starting with j := i the following steps will allow us to move backwards through the
array and accomplish the task.
 One way around the problem would be to include a check on the j suffix using

To test our design, Fig. 5.6 shows this mechanism applied to a specific examples.

Algorithm description
1. Establish the array a[1.. n] of n elements.
2. Find the minimum and put it in place to act as sentinel.
3. While there are still elements to be inserted in the ordered part do
(a) select next element x to be inserted;
(b) while x is less than preceding element do
(b.1) move preceding element up one position,
(b.2) extend search back one element further;
(c) insert x at current position.
Pascal implementation

Notes on design
1. In analyzing the insertion sort two parameters are important. They are the number
of comparisons (i.e. x<a[j-1]) made and secondly the number of array elements that
need to be moved or shifted.
2. The condition remaining invariant in the outer loop is that after the ith iteration the
first i values in the array have been placed in non-descending order (i.e.
a[1]<=a[2]<=….<=a[i]).
3. The insertion sort is usually regarded as the best of the n2 algorithms for sorting
small random data sets.
4. The design for this algorithm has been arrived at by first working out the
mechanism for insertion in an array of size n= 2.

Applications
Where there are relatively small data sets. It is sometimes used for this purpose in the
more advanced quicksort algorithm.
10. Explain in detail about Linear search.
Searching for an element in an array is an extremely common task. As with
sorting, the right choice of algorithms can make a big difference.
You must simply look through all elements until you have found a match or until
you reach the end. This is called a linear or sequential search.
How long does a linear search take? If we assume that the element v is present in
the array a, then the average search visits n/2 elements, where n is the length of the array.
If it is not present, then all n elements must be inspected to verify the absence.
Either way, a linear search is an O(n) algorithm.
Here is a class that performs linear searches through an array a of integers. When
searching for a value, the search method returns the first index of the match, or -1 if the
value does not occur in a.

Example:
Consider the array of integer in Table 1. Walk through the linear search algorithm on
this array searching the following keys: 20, 42, 102, 4.

Analysis
As the name suggests, the complexity of linear search is linear.
1. Input: the collection of elements A
2. Input size: n as there are n elements
3. Elementary Operation: the comparison to the key in line 2
4. Best case: we immediately find the element, O(1) comparisons
5. Worst case: we don't find it, or we find it at the last elements, n
comparisons, O(n)
6. Average case (details omitted): an expected number of comparisons of n/2
Є O(n)
 U20EST109 - Problem Solving Approach

Pseudocode
procedure linear_search (list, value)

for each item in the list

if match item ==
value
return the item's location
end if
end for

end procedure

In computer science, when we analyze problems in this way, we do not like to need
to worry about the constant multiples. The reason for it is that for really really large values
of n multiplying it by 1/2 does not change the value that much.
We use an order notation that only indicates the highest power of n in the number of
operations performed.
The notation is called Big-O notation, and we write O(n) to indicate that the number
of operations performed is proportional to n (that may mean exactly n, or n/2, or 10n, or
2n
+ 15 - it does not matter which, because for large values of n, those are all similar.

Using that notation the table above would look as follows:

11. Write short notes on Binary

Search. Problem
Given an element x and a set of data that is in strictly ascending numerical order find
whether or not x is present in the set.

Algorithm development
It is easy to see that in all cases the value in the set that we are seeking is either in the
first half of the list or the second half of the list (it may also be the middle value in the set).
For example,

Department of Computer science and Engineering Page 32

Department of Computer science and Engineering Page 33
 U20EST109 - Problem Solving Approach

Suppose it is established that the value we are seeking is in the second half of the list
(e.g. somewhere between the (n/2)th value and the nth value).

The halving strategy that we have been considering is one of the most widely used
methods in computing science. It is commonly known as the divide-and-conquer strategy.
The corresponding searching method we are starting to develop is known as the binary search
algorithm.
At this stage we have the general strategy: repeatedly

Let us now consider a specific example in order to try to find the details of the
algorithm needed for implementation.

To get the middle value of an array of size n we can try:

for n= 15 this yields middle = 7 which is not strictly the middle. If we add 1 before carrying
out the division we get

This gives a[middle] = a[8] = 39. Since the value we are seeking (i.e. 44) is greater
than 39 it must be somewhere in the range a[9] ... a[15]. That is, a[9] becomes the lower
limit of where 44 could be. That is, lower := middle+ 1. We then have:

Tests on several other values confirm that this method of calculating the middle works
in the general case, e.g.

Accordingly the upper limit becomes one less than the middle value, i.e.

We then have:

Department of Computer science and Engineering Page 34

 The procedure progresses as before until we get the configuration below:

At this stage we find that 43 is less than the middle value and we have:

This leads to the situation where lower = upper = middle (i.e. they are all 9).

The next comparison of 43 with a[middle] = a[9] tells us the value we are seeking is
above the middle value. We therefore get

Since all unsuccessful searches eventually pass through the stage when upper=
lower= middle (because of the way in which middle is calculated) we can use the condition

At this stage we have the following algorithm.

1. Establish ordered array size n and the value sought x.
2. Establish the ordered data set a[1.. n].
3. Set upper and lower limits.
4. Repeatedly
(a) calculate middle position of remaining array;
(b) if value sought is greater than middle value
then adjust lower limit to one greater than middle,
else adjust upper limit to one less than middle
until value sought is found or lower becomes greater than upper.
5. Set found accordingly.
The Pascal implementation is

In other words, if x is present in the array, we want the following condition to hold
after each iteration:

Our starting configuration will be:

Beginning with:

we can make the following conditional test in an effort to bring upper and lower closer
together:

If this condition is true then x must be in the range a[middle +1 . . upper] if it is

present in the array. It follows that with this condition true, we can make the assignment:

On the other hand if this condition is not true (i.e. therefore x<=a[middle]) x must be
in the range a[lower … middle] if it is present in the array. The variable upper can therefore
be reassigned as:

These two situations suggest that the termination condition:

is probably the most appropriate if x is present.

The truncation caused by the integer division, i.e.

ensures that the middle value is always less than the current upper value (except when upper
= lower). For example,
Algorithm description
1. Establish the array a[l.. n], and the value sought x.
2. Assign the upper and lower variables to the array limits.
3. While lower<upper do
(a) compute the middle position of remaining array segment to be searched,
(b) if the value sought is greater than current middle value then
(b. 1) adjust lower limit accordingly
else
(b'. 1) adjust upper limit accordingly.
4. If the array element at lower position is equal to the value sought then
(a) return found
else
(a') return not found.

Pascal implementation

Notes on design
1. The binary search algorithm in general offers a much more efficient alternative
than the linear search algorithm.
2. With each iteration, if x is present in the array, lower will be increased and upper
will be decreased in such a way that the condition:

remains true. Termination will occur when lower = upper and hence if x is present we
will have

3. There have been many implementations of the binary search algorithm