DEPARTMENT OF PHYSICS AND COMPUTER SCIENCE

SCHOOL OF TECHNOLOGY
NJALA UNIVERSITY
NJALA CAMPUS

DATA STRUCTURE AND ALGORITHM [COMPS 216]

FOR
SECOND YEAR DEGREE STUDENTS
IN
BUSINESS & INFORMATION TECHNOLOGY [BIT]
OR
COMPUTER SCIENCE
Data Structure and Algorithm BIT/CS YR2 Njala University

DATA STRUCTURE AND ALGORITHM

Just as Mathematics is the “Queen and servant of science”, the material covered by
this course is fundamental to all aspects of computer science. Almost all the courses
given in the Computer Science program describe structures and algorithms
specialized towards the application being covered, whether it is databases,
compilation, graphics, operating systems, or whatever. These diverse fields often use
similar data structures, such as lists, hash tables, trees and graphs, and often apply
similar algorithms to perform basic tasks such as table lookup, sorting, searching, or
operations on graphs. It is the purpose of this course to give a broad understanding
of such commonly used data structures and their related algorithms. As a by-
product, you will learn to reason about the correctness and efficiency of programs.

The following lessons introduce the topic of data structures by comparing how data
is actually stored in a computer with the abstract structures that programmers use. To
illustrate this comparison, several basic data structures such as lists, stacks, queues,
arrays, trees, graphs, sets sorting are described

Introduction to Data Structures

Imagine that you are hired by techLinks Systems to organize all of their records into
an automated database system. The first thing you are asked to do is create a database
of names with all the company's management and employees. To start your work, you

make a list of everyone in the company along with their positions.

Name Position

Aaron Manager

Charles VP

George Employee

Jack Employee

Janet VP

2|Page
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

John President

Kim Manager

Larry Manager

Martha Employee

Patricia Employee

Rick Secretary

Sarah VP

Susan Manager

Thomas Employee

Zack Employee

But this list only shows one view of the company. You also want your database to
represent the relationships between management and employees at techLinks
Systems. Although your list contains both name and position, it does not tell you
which managers are responsible for which workers and so on. After thinking about
the problem for a while, you decide that a tree diagram is a much better structure for
showing the work relationships at techLinks Systems.

These two diagrams are examples of different data structures. In one of the data
structures, your data is organized into a list. This is very useful for keeping the names
of the employees in alphabetical order so that we can locate the employee's record
very quickly. However, this structure is not very useful for showing the relationships
between employees. A tree structure is much better suited for this purpose.

3|Page
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
 Data Structure and Algorithm BIT/CS YR2 Njala University

In computer science, data structures are an important way of organizing information

in a computer. Just like the diagrams above illustrate, there are many different data
structures that programmers use to organize data in computers. Some data structures
are similar to the tree diagram because they are good for representing relationships
between data. Other structures are good for ordering data in a particular way like the
list of employees. Each data structure has unique properties that make it well suited
to give a certain view of the data.

COMPUTER MEMORY

To fully understand how a computer can represent large data structures like our tree
diagram, we first need to understand some basic facts about computer memory. Every
piece of data that is stored in a computer is kept in a memory cell with a specific
address. We can think of these memory cells as being a long row of boxes where each
box is labelled with an address. If you have ever used a computer spreadsheet before,
you know that spreadsheets also can hold data. Computer memory is similar to this
with the exception that computer memory labelled boxes is linear.

The computer can store many different types of data in its memory like integers, real
numbers and characters. Once the computer stores data in the memory cells, it can
access the data by using the address of the data cells. For example, consider the
following instructions for adding two integers together.

Instructions Computer Memory

1. Store '1' in cell 2003.

4|Page
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
 Data Structure and Algorithm BIT/CS YR2 Njala University

2. Store '5' in cell 2004.

3. Add cells 2003 and 2004 and store the result

in cell 2006.

Notice how the computer performs operations by referring to the address of the
memory cells. These addresses are a very important component in creating various
data structures in computer memory. For example, suppose we want a data structure
that can store a group of characters as a word. In many computer languages, this data
structure is called a string. If we store the characters for the string 'apple' in the
computer's memory, it might look something like this.

In order for the computer to recognize that 'apple' is a string, it must have some way
of identifying the start and end of the characters stored in memory. This is why the
addresses of the memory cells are important. By using the addresses to refer to a
group of memory cells as a string, the computer can store many strings in a row to
create a list. This is one way that we could create a data structure to represent our list
of employees at techLinks Systems.

But what happens when we try to represent our tree diagram of techLinks Systems?
It doesn't make sense to store the names one after the other because the tree is not
linear. Now we have a problem. We want to represent a nonlinear data structure using
computer memory that is linear. In order to do this, we are going to need some way

5|Page
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

of mapping nonlinear structures like trees or spreadsheet tables onto linear computer
memory. This problem will lead us to the next section.

POINTERS AND INDIRECTION

In our last section, we discovered a problem with representing data structures that are
not linear. We needed some way to map these data structures to the computer's linear
memory. One solution is to use pointers. Pointers are memory locations that are
stored in memory cells. By using a pointer, one memory cell can "point" to another
memory cell by holding a memory address rather than data. Let's see how it works.

In the diagram above, the memory cell at address 2003 contains a pointer, an address
of another cell. In this case, the pointer is pointing to the memory cell 2005 which
contains the letter 'c'. This means that we now have two ways of accessing the letter
'c' as stored data. We can refer to the memory cell which contains 'c' directly or we
can use our pointer to refer to it indirectly. The process of accessing data through
pointers is known as indirection.

We can also create multiple levels of indirection using pointers. The diagram below
shows an example of double indirection. Notice that we must follow two pointers this
time to reach the stored data.

6|Page
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

As you can see, pointers can become very complex and difficult to use with many
levels of indirection. In fact, when used incorrectly, pointers can make data structures
very difficult to understand. Whenever we use pointers in constructing data structures,
we have to consider the trade-off between complexity and flexibility.

The idea of pointers and indirection is not exclusive to computer memory. Pointers
appear in many different aspects of computer use. A good example is hyperlinks in
web pages. This links are really pointers to another web page. Perhaps you have even
experienced "double indirection" when you went to visit a familiar web site and found
the site had moved. Instead of the page you expected, you saw a notice that the web
pages had been moved and a link to the new site. Rather than clicking a single link,
you had to follow two links or two pointers to reach the web page.

LINEAR DATA STRUCTURE

In the previous section, we saw that it is very simple to create data structures that are
organized similar to the way the computer's memory is organized. For example, the
list of employee's from techLinks Systems is a linear data structure. Since the
computer's memory is also linear, it is very easy to see how we can represent this list
with the computer. Any data structure which organizes the data elements one after
the other is a linear data structure. So far we have seen two examples of linear data
structures: the string data structure (a list of characters) and the techLinks Systems list

(a list of strings).

Example String

7|Page
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

Example List

You may have noticed that these two examples of linear data structures resemble each
other. This is because they are both really different kinds of lists. In general, all linear
data structures look like a list. However, this does not mean that all linear data
structures are exactly the same.

Suppose we want to design a list to store the names of the techLinks employees in
the computer. One possible design is to organize the names similar to the example
picture above. Another possible design is to use the pointers we learned about in the
last section. While these two designs provide the same functionality (i.e. a list that can
hold names), the way they are implemented in the computer is much different. This
means that there is an abstract view of a list which is distinct from any particular
computer implementation.

You may have also noticed that the example picture of Name

techLinks Systems employees is not exactly the same Aaron

as the original list. Take another look at the employee Charles

George
list to the right. When we make a list of names, we
Jack
tend to organize this list in a column rather than a row.
Janet
In this case, the conceptual or logical representation of John

a list is a column of names. However, the physical Kim

representation of the list in the computer's memory is Larry

a row of strings. For most data structures, the way that Martha

Patricia
we think about them is far different from the way they
Rick
are implemented in the computer. In other words, the
Sarah
physical representation is much different than the Susan

logical representation, especially in data structures that Thomas

use pointers. Zack

8|Page
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

ORDERED LIST ABSTRACT VIEW

The most common linear data structure is the list. By now you are already pretty
familiar with the idea of a list and at least one way of representing a list in the
computer. Now we are going to look at a particular kind of list: an ordered list. Ordered
lists are very similar to the alphabetical list of employee names for techLinks Systems.
These lists keep items in a specific order such as alphabetical or numerical order.
Whenever an item is added to the list, it is placed in the correct sorted position so
that the entire list is always sorted.

Before we consider how to implement such a list, we need to consider the abstract
view of an ordered list. Since the idea of an abstract view of a list may be a little
confusing, let's think about a more familiar example. Consider the abstract view of a
television. Regardless of who makes a television, we all expect certain basic things like
the ability to change channels and adjust the volume. As long as these operations are
available and the TV displays the shows we want to view, we really don't care about
who made the TV or how they chose to construct it. The circuitry inside the TV set
may be very different from one brand to the next, but the functionality remains the
same. Similarly, when we consider the abstract view of an ordered list, we don't worry
about the details of implementation. We are only concerned with what the list does,
not how it does it.

Suppose we want a list that can hold the following group of sorted numbers: [2 4 6
7]. What are some of the activities that we might want to perform with our list? Well,
since our list is in order, we will need some way of adding numbers to the list in the
proper place, and we will need some way of deleting numbers we don't want from
the list. To represent these operations, we will use the following notation:

AddListItem (List, Item)

9|Page
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

RemoveListItem (List, Item)

Each operation has a name and a list of parameters the operation needs. The
parameter list for the AddListItem operation includes a list (the list we want to add
to) and an item (the item we want to add). The RemoveListItem operation is very
similar except this time we specify the item we want to remove. These operations are
part of the abstract view of an ordered list. They are what we expect from any ordered
list regardless of how it is implemented in the computer.

In this section, we are going to look at two different ways of creating an ordered list
data structure to hold the following list [2 4 6 7]. First, we will create a list using an
array of memory cells. Next, we will create the same list using pointers. Finally,
we will compare these two approaches to see the advantages and disadvantages.

ORDERED LIST: THE IMPLEMENTATION VIEW

Array Implementation

One approach to creating a list is simply to reserve a block of adjacent memory cells
large enough to hold the entire list. Such a block of memory is called an array. Of
course, since we will want to add items to our list, we need to reserve more than just
four memory cells. For now, we will make our array large enough to hold six numbers.

The diagram below shows a graphical representation of our array in memory with the
list numbers.

2 4 6 7
9

Item 200 201 202 203 204 205

10 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

Our list

Operation: Add List Items (OurList, 9)

To add a number to the ordered list we must first locate the correct position in the array for
the number and then insert the new number.

In the diagram, you saw that there were two disadvantages to using an array to
implement an ordered list. First, you saw that the elements in the list must be kept in
sequence, that is, there must not be gaps in the list. If gaps are allowed, the computer
will not be able to determine which items are part of the list and which items are not.
For this reason, the ordered list structures that are implemented with arrays are known
as sequential lists.

The second disadvantage that you saw was that arrays have a fixed size and therefore
limit the number of items the list can contain. Of course we could try to increase the
size of the array, but it may not always be the case that the adjacent memory cells in
the computer are available. They could be in use by some other program. However, it
is quite likely that the computer does have available memory at some other non-
adjacent location. To take advantage of this memory, we need to design our list so
that the list items do not have to be adjacent.

Pointer Implementation

A second approach to creating a list is to link groups of memory cells together using
pointers. Each group of memory cells is called a node. With this implementation every
node contains a data item and a pointer to the next item in the list. You can picture
this structure as a chain of nodes linked together by pointers. As long as we know
where the chain begins, we can follow the links to reach any item in the list. Often
this structure is called a linked list.

11 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

Notice that the last memory cell in our chain contains a symbol called "Null". This
symbol is a special value that tells us we have reached the end of our list. You can
think of this symbol as a pointer that points to nothing. Since we are using pointers
to implement our list, the list operations AddListItem and RemoveListItem will work
differently than they did for sequential lists. The diagram below shows how these
operations work and how they provide a solution for the two problems we had with
arrays.

2 275
4 342 6 103
7 230 8 Null

200 201 275 276 342 343 103 104 230 231

When we were working with arrays we discover two problems. First we have to shift
many items to insert new items in there correct positions, secondly the size of our
array was limited so our list was also limited. The linked list provides solution for this

problem. Let see how it works.

Suppose we want to add number 3 to the ordered list above. To do this we only need to
change the position in our list. First we get an available memory location for the new item.

12 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

Next we set the pointer for 3 to point to 4, the item that should follow 3 in the list. Finally
we change the pointer for 2 to point to the new item we just added.

Now suppose we need to remove the item 7 from the list. To do this we must point the
pointer of the preceding item, 6, to point to the next item, 8. Then we simply delete the 7
from the list.

Notice that with both the add and remove operations. We only needed to make a few
changes to update our linked list. But with an array, we often had to shift many items
to have other items added or removed. Linked list also provide us with flexible list
size. Unlike the array item, linked list items need not be in adjacent memory location,
to lengthen our list we first find another available memory location, store the new
item and then link this new item to our list. As long as we have free memory in the
computer, we can increase the size of our list.

By implementing our list with pointers, we are able to avoid the two disadvantages
we discovered with using sequential lists. However, this does not mean that linked
lists are the perfect solution. Whenever we use indirection in building a data structure,
it becomes much harder to find mistakes. For example, it is very easy to assign the
wrong address to a pointer and "short circuit" our list. In general, sequential lists are
simpler than linked lists but they are also more limited. Linked lists give us a great
amount of flexibility but this comes at the cost of increased complexity.

13 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

STACKS: THE ABSTRACT VIEW

Another common linear data structure is the stack. Just like we did with the ordered
list, we will examine the abstract view of a stack first and then look at a couple of
ways a stack can be implemented. In one way, a stack is very similar to a list except
that a stack is more restricted. The diagram below should give you a good idea of the
abstract view of a stack.

STACK

The columns on the left represent stack data structure. Notice that the stack has only one
operation. The stack data structures only allow items to add from one end. The process of
adding items unto a stack is known as PUSH. In a stack, Items can only be added from the
top of the stack.

Removing an item from the stack, this operation is known as popping items off from the
stack. Notice that items can only be removed from the top of the stack. Just like PUSH
operation, the POP operation is only valid for the top item in the stack.

From the stack, you will notice that items are always removed from the stack opposite the
order they were added. Also notice that the last item added to the stack is always the first
item to be removed from the stack.

14 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

Now that you know how a stack works, you can see that this data structure is really a
restricted list. With the stack, we have restricted the access to one end of the list by
using the pop and push operations. The result of this restriction is that items in the
list pile one on top of the other. To get to the bottom item, we must first remove all
the items above it. This behaviour is sometimes described as "last-in, first-out" or LIFO
since the last item to enter the stack is the first item to leave the stack. With the stack,
the top item is always the last item to enter the stack and it is always the first item to
leave the stack since no other items can be removed until the top item is removed.

Let's take another look at the operations that can be performed on a stack. We will
represent these two operations with the following notation:

PushStackItem (Stack, Item)

Item PopStackItem (Stack)

The PushStackItem operation has two parameters which are a stack and an item. This
operation adds the item to the top of the specified stack. The PopStackItem operation
only takes one parameter which is a stack. However, notice that this operation has the
keyword Item listed to the left. This keyword represents the item that is removed from
the top of the stack when the PopStackItem operation is done. These two operations
are part of the abstract view of a stack. They are what we expect from any stack
regardless of how it is implemented in the computer.

STACKS: THE IMPLEMENTATION VIEW

As we did with the ordered list, we are going to look at two implementations of a
stack. The first implementation uses an array to create the stack data structure, and
the second implementation uses pointers.

Array Implementation

15 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

In order to implement a stack using an array, we need to reserve a block of memory

cells large enough to hold all the items we want to put on the stack. The picture below
shows an array of six memory cells that represent our stack. Notice that we have one
other memory cell called a stack pointer that holds the location of the top of our
stack. As the stack grows and shrinks, this pointer is updated so that it always points
to the top item of the stack.

Notice that our array implementation retains one of the problems we saw with the
array implementation of an ordered list. Since our array is a fixed size, our stack can
only grow to a certain size. Once our stack is full, we will have to use the PopStackItem
operation before we can push any more items onto the stack. To make the size of our
stack more flexible, we can use pointers to implement the stack.

Pointer Implementation

In order to implement a stack using pointers, we need to link nodes (groups of

memory cells) together just like we did for the pointer implementation of a list. Each
node contains a stack item and a pointer to the next node. We also need a special
pointer to keep track of the top of our stack.

16 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

Notice that the stack operations can get a little tricky when we use pointers. To push
an item onto the stack, we need to find a free memory location, set the pointer of the
new location to the top of the stack, and finally set the stack pointer to the new
location. The order of these operations is very important. If we set the stack pointer
to the location of the new memory first, we will lose the location of the top of our
stack. This example shows the same trade-off that we saw earlier with the ordered list
implementations. While the array implementation is simpler, the added complexity of
the pointer implementation gives us a more flexible stack.

17 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

QUEUES: THE ABSTRACT VIEW

The final linear data structure that we will examine is the queue. Like the stack, the
queue is a type of restricted list. However, instead of restricting all the operations to
one end of the list as a stack does, the queue allows items to be added at one end
of the list and removed at the other end. The diagram below should give you a good
idea of the abstract view of a queue.

Head tail

Queue

The row across the top represents the queue data structure. Notice that the queue has two
open ends labelled “Head” and “Tail”. The tail of the queue is where items are added to the
queue. Items are added onto the queue from it tail and this process is called ENQUEUE
operation.

In a queue, Items can only be added to the tail of the queue, not in the middle or from the
head.

Items are removed from the queue by dragging them from the Head of the queue. This
operation is known as DEQUEUE operation. Notice items can only be removed from the HEAD
of the queue. Items at the middle of the queue cannot be removed.

Notice that items are always removed from the queue in the same order they were added.
Also notice that the first items added to the queue is always the first to be removed from the
queue. This restriction placed on a queue causes this structure to be a "first-in, first-out" or
FIFO structure. This idea is similar to customer lines at a grocery store. When customer X is

18 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

ready to check out, he or she enters the tail of the waiting line. When the preceding customers
have paid, then customer X pays and exits the head of the line. The check-out line is really a
queue that enforces a "first come, first serve" policy.

Now let's take another look at the operations that can be performed on a queue. We
will represent these two operations with the following notation:

EnqueueItem (Queue, Item)

Item DequeueItem (Queue)

These two operations are very similar to the operations we learned for the stack data
structure. Although the names are different, the logic of the parameters is the same.
The EnqueueItem operation takes the Item parameter and adds it to the tail of
Queue. The DequeueItem operation removes the head item of Queue and returns
this as Item. Notice that we represent the returned item with a keyword located to
the left of the operation name. These two operations are part of the abstract view of
a queue. Regardless of how we choose to implement our queue on the computer, the
queue must support these two operations.

QUEUES: THE IMPLEMENTATION VIEW

When we looked at the ordered list and stack data structures, we saw two different
ways to implement each one. Although the implementations were different, the data
structure was still the same from the abstract point of view. We could still use the
same operations on the data structures regardless of their implementations. With the
queue, it is also possible to have various implementations that support the operations
EnqueueItem and DequeueItem. However, in this section, we are only going to focus
on one implementation in order to highlight another distinction: the distinction
between the logical representation of a queue and the physical representation of a
queue. Remember that the logical representation is the way that we think of the data

19 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

being stored in the computer. The physical representation is the way the data is
actually organized in the memory cells.

To implement our queue, we will use an array of eight memory cells and two pointers
to keep track of the head and tail of the queue. The diagram below shows a snapshot
of a queue in the computer's memory. The queue currently contains five letter items
with 'L' at the head of the queue and 'O' at the tail of the queue.

Now let's consider how the EnqueueItem and DequeueItem operations might be
implemented. To enqueue letters into the queue, we could advance the tail pointer
one location and add the new letter. To dequeue letters, we could remove the head
letter and increase the head pointer one location. While this approach seems very
straightforward, it has a serious problem. As items are added and removed, our queue
will march straight through the computer's entire memory. We have not limited the
size of our queue.

Perhaps we could limit the size of the queue by not allowing the tail pointer to
advance beyond a certain location. This implementation would stop the queue from
traversing the entire memory, but it would only allow us to fill the queue one time.
Once the head and tail pointers reached the stop location, our queue would no longer
work.

20 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

NONLINEAR DATA STRUCTURES

In the first lesson of this section, we discussed the problem of representing

relationships between employees at techLinks Systems. Since these relationships are
not linear, we could not adequately show the relationships using a linear data structure
like a list or a stack. Instead, we needed something that looks more like a tree.

A tree is just one example of a nonlinear data structure. Two other examples are
multidimensional arrays and graphs. In the next few sections, we will examine these
data structures to see how they are represented using the computer's linear memory.
For each of the data structures we examine, we will look at a simple implementation
for the data structure to see how it can be represented in physical memory. Then we
will compare this physical representation with the logical representation of the data
structure.

MULTIDIMENSIONAL ARRAYS

Let's return to our example of techLinks Systems. After you finish creating a list of the
company's employees, you are asked to make an electronic time sheet that shows the
number of hours that each employee worked during the week. You begin by
associating each data point (hours worked) with two labels: employee's name and day
of the week. To organize the data, you use the following logical representation.

21 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

Mon Tue Wed Thu Fri

Aaron 8 9 3 4 10
Charles 8 8 7 7 5
George 7 6 5 4 7
Jack 6 9 7 6 7
Janet 9 5 7 8 7
John 7 8 9 7 9
Kim 8 4 6 8 7
Larry 2 8 6 7 9
Martha 5 9 8 5 7
Patricia 8 9 8 6 5
Rick 6 9 8 7 6
Sarah 9 9 7 6 9
Susan 4 6 5 4 9
Thomas 1 10 7 8 9
Zack 6 7 9 7 6

Now we have a new data structure called a two-dimensional array. We can see how
the data structure gets its name by comparing it with a typical array. All the arrays we
have seen so far were simply a group of contiguous memory cells. Since computer
memory is linear, the arrays were also linear or one-dimensional. Notice, however, that
each row of the table above looks like a typical, linear array. Our table is really a
collection of one-dimensional arrays with five memory cells. Each memory cell
represents a day of the week, and each array in the table represents an employee.
Just like a one-dimensional array is a collection of memory cells, a two-dimensional
array is a collection of one-dimensional arrays.

You may be wondering how we can represent our two-dimensional array in the
computer's memory. The diagram below shows the answer to this question by
comparing the logical representation (the table) with the physical representation in
memory

22 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

As you saw in the diagram, it is common to refer to array locations by specifying the
row and column numbers after the array name. If we named our table above "Hours"
then we could find the number of hours that Aaron worked on Wednesday at the
following array location: Hours[1, 3].

We can also have higher dimensional arrays that are collections of lower dimensional
arrays. For example, we could organize the time sheet for one month by making a
three-dimensional array. This array would be a collection of four weeks of time sheets
which are two-dimensional arrays.

Then we could find the number of hours that Aaron worked during the second
Wednesday of the month at the following array location: Hours[2, 1, 3]. The '2'
represents the second week of the month, the '1' represents the employee Aaron, and
the '3' represents Wednesday, the third day of the week.

23 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

TREES

Another common nonlinear data structure is the tree. We have already seen an
example of a tree when we looked at the employee hierarchy from techLinks Systems.
Let's take another look at this diagram with some of the important features of trees
highlighted.

In this diagram, we can see that the starting point, or the root node, is circled in blue.
A node is a simple structure that holds data and links to other nodes. In this case, our
root node contains the data string "John" and three links to other nodes. Notice that
the group of nodes circled in red does not have any links. These nodes are at the end
of the branches and they are appropriately called leaves or leaf nodes. In our diagram,
the nodes are connected with solid black lines called arcs or edges. These edges show
the relationships between nodes in the tree. One important relationship is the
parent/child relationship. Parent nodes have at least one edge to a node lower in the
tree. This node is called the child node. Nodes can have more than one child, but
children can only have a single parent. Notice that the root node has no parent, and
the leaf nodes have no children. The final feature to note in our diagram is the subtree.
At each level of the tree, we can see that the tree structure is repeated. For example,
the two nodes representing "Charles" and "Rick" compose a very simple tree with
"Charles" as the root node and "Rick" as a single leaf node.

24 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

Now let's examine one way that trees are implemented in the computer's memory.
We will begin by introducing a simple tree structure called a binary tree. Binary trees
have the restriction that nodes can have no more than two children. With this
restriction, we can easily determine how to represent a single binary node in memory.
Our node will need to reserve memory for data and two pointers.

Using our binary node, we can construct a binary tree. In the data cell of each node,
we will store a letter. The physical representation of our tree might look something
like this:

Although the diagram above represents a tree, it doesn't look much like the tree we
examined from techLinks Systems. Because our tree uses pointers, the physical
representation is much different than the logical representation.

Definition of Trees

A list is a collection of elements where:

25 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

1. Each element (except the first) has exactly 1 predecessor.

2. Each element (except the last) has exactly 1 successor.

Root of a tree: the unique node with no predecessor.

Leaf of a tree: any node with no successor.

Children of a node: its successors.

Parent of a node: its unique predecessor.

Siblings: children of the same parent

Trees are as common and important as lists. And like lists there are many variations -
binary search trees, balanced trees, and heaps are the main ones we will look at.

Recall that a list is a collection of components in which

1. Each component (except one, the first) has exactly 1 predecessor.

2. Each component (except one, the last) has exactly 1 successor.

A tree is very similar: it has property (1) but (2) is slightly relaxed:

(2') each component has some number of successors.

If there is no limit on the number of successors that a node can have, the tree is called
a general tree. If there is a maximum number N of successors for a node, then the
tree is called an N-ary tree. In particular a binary (2-ary) tree is a tree in which each
node has 0, 1, or 2 successors.

The unique node with no predecessor is called the root of the tree. A node with no
successors is called a leaf - there will usually be many leaves in a tree. The successors
of a node are called its children; the unique predecessor of a node is called its parent.
If two nodes have the same parent, they are called brothers or siblings. In a binary
tree the two children are called the left and right.

26 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

Drawing Trees

Here is how we draw a tree:

The root is at the top; below it are its children. An arc connects a node to each of its
children: we sometimes draw arrowheads on the arc, but they are optional because
the direction parent->child is always top->bottom.

Then we continue in the same manner, the children of each node are drawn below
the node.

For example, here is a binary tree:

In general, each child of a node is the root of a tree ``within the big tree''. For example,
B is the root of a little tree (B,D,E), so is C. These inner trees are called subtrees. The
subtrees of a node are the trees whose roots are the children of the node. e.g. the
subtrees of A are the subtrees whose roots are B and C. In a binary tree we refer to
the left subtree and the right subtree.

Path in a Tree

A path is any linear subset of a tree, e.g. A-B-E and C-F are paths. The length of a
path could be counted as either the number of nodes or the number of edges on the
path - in the lectures we will count the nodes; e.g. A-B-E has length 3. But be careful:
there is no agreed definition!

There is a unique path from the root to any node. The depth or level of a node is the
length of this path. When you draw a tree, it is very useful if all the nodes in the same

27 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

level are drawn as a neat horizontal row. The depth or height of a tree is the maximum
depth of the nodes in the tree.

Ordered Trees

A tree is ordered if there is some significance to the order of the subtrees. For example,
consider this tree:

If this is a family tree, there could be no significance to left and right. In this case the
tree is unordered, and we could redraw the tree exchanging subtrees without affecting
the meaning of the tree. On the other hand, there may be some significance to left
and right - maybe the left child is younger than the right... or (as is the case here)
maybe the left child has the name that is earlier in the alphabet. Then, the tree is
ordered and we are not free to move around the subtrees.

For now we will restrict ourselves to ordered trees. Like lists, ordered N-ary trees have
a nice recursive structural definition:

Binary Tree Traversal

Traversing a tree means visiting all the nodes of a tree in order.

There are three different methods of traversing a binary tree:

 pre-order traversal
 in-order traversal
 post-order traversal

In each case, the algorithms for traversal are recursive - they call themselves.

28 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

Pre-order traversal

1. Start at the root node

2. Traverse the left subtree
3. Traverse the right subtree

The nodes of this tree would be visited in the order

:

DBACFEG

In-order traversal

1. Traverse the left subtree

2. Visit the root node
3. Traverse the right subtree

The nodes of this tree would be visited in the order

:

ABCDEFG

Post-order traversal

1. Traverse the left subtree

2. Traverse the right subtree
3. Visit the root node

The nodes of this tree would be visited in the order

:

ACBEGFD

29 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

E.g. let us look at what order the nodes will get processed given this tree:

The preceding diagrams show us the order in which the nodes will get written:

 Pre-Order: A-B-D-C-E-F
 In-Order: B-D-A-E-C-F
 Post-Order: D-B-E-F-C-A

Breadth First Traversal

These three are certainly not the only possible traversal orders. Another very natural traversal
order is ``level by level'' - the root is processed first, all its children are processed next, then
all of their children, etc. down to the bottom level. This is called breadth first traversal. In the
above example, it would process nodes in the order: A-B-C-D-E-F. It is not difficult to write a
breadth-first traversal, but is not quite as simple as the traversal orders just described.

Expression Trees
Algebraic expressions such as

Have an inherent tree-like structure. For example, Figure below is a representation of

the expression in Equation.

The terminal nodes (leaves) of an expression tree are the variables or constants in the
expression (a, b, c, d, and e). The non-terminal nodes of an expression tree are the
operators (+, -, , and ). Notice that the parentheses which appear in Equation do

30 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

not appear in the tree. Nevertheless, the tree representation has captured the intent
of the parentheses since the subtraction is lower in the tree than the multiplication.

Figure: Tree representing the expression a/b+(c-d)e.

The common algebraic operators are either unary or binary. For example, addition,
subtraction, multiplication, and division are all binary operations and negation is a
unary operation. Therefore, the non-terminal nodes of the corresponding expression
trees have either one or two non-empty subtrees. That is, expression trees are usually
binary trees.

31 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

GRAPHS

The last data structure that we will study in this section is the graph. Graphs are similar
to trees except they do not have as many restrictions. In the previous section, we saw
that every tree has a root node, and all the other nodes in the tree are children of
this node. We also saw that nodes can have many children but only one parent. When
we relax these restrictions, we get the graph data structure. The logical representation
of a typical graph might look something like this:

Notice that our graph does not have a root node like the tree data structure did.
Instead, any node can be connected with any other node. Nodes do not have a clear
parent/child relationship like we saw in the tree. Instead nodes are called neighbours
if they are connected by an edge. For example, node A above has three neighbours:
B, C, and D.

It is not hard to imagine how the graph data structure could be useful for representing
data. Perhaps each of the nodes above could represent a city and the edges
connecting the nodes could represent roads. Or we could use a graph to represent a
computer network where the nodes are workstations and the edges are network
connections. Graphs have so many applications in computer science and mathematics

32 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

that several algorithms have been written to perform standard graph operations such
as searching the graph and finding the shortest path between nodes of a graph.

Now that you have a basic idea of the logical representation of graphs, let's take a
look at one way that graphs are commonly represented in computers. The
representation is called an adjacency matrix, and it uses a two-dimensional array to
store information about the graph nodes. The adjacency matrix for our graph is given
below.

A B C D E F
A -- 1 1 1 -- --
B 1 -- 1 -- 1 --
C 1 1 -- -- -- --
D 1 -- -- -- 1 1
E -- 1 -- 1 -- --
F -- -- -- 1 -- --

Notice that the matrix has six rows and six columns labelled with the nodes from the
graph. We mark a '1' in a cell if there exists an edge from the two nodes that index
that cell. For example, since we have an edge between A and B, we mark a '1' in the
cells indexed by A and B. These cells are marked with a dark gray background in the
adjacency matrix. With our adjacency matrix, we can represent every possible edge
that our graph can have.

33 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

ABSTRACT DATA TYPES

The concept of data structures is closely related to another important concept in

computer science called abstract data types. A data type consists of the values it
represents and the operations defined upon it." You are already familiar with some
basic data types such as integers and characters. These data types are found in nearly
all computers, and they have well-defined operations that can be done with them. For
example, the integer data type has operations for addition, subtraction, multiplication,
and division. The computer knows how to perform these arithmetic operations with
any two integers because these operations are part of the integer data type.

We can extend the idea of data types to include more than just the basic data types.
Our definition of data types consists of two parts: 1) values, and 2) operations. Now
suppose we extended our definition so that the first part included data structures. This
extension makes sense because our data structures are really just novel ways of
organizing values. We have already seen several examples of these extended or
abstract data types (ADTs). The examples that we studied are listed below.

Data Structure Operations Abstract View

AddListItem(List, Item)
Ordered List
RemoveListItem(List, Item)

34 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

Item PushStackItem(Stack, Item)

Stack
Item PopStackItem(Stack)

Item EnqueueItem(Queue, Item)

Queue
Item DequeueItem(Queue)

Notice that each of the ADTs above has the two elements required by our definition:
1) a particular data structure, and 2) operations related to the data structure. We call
these data types "abstract" because we have said nothing about how they are
implemented. Instead, we have defined an interface for using the data type which
consists of certain operations. The interface for an ADT remains the same regardless
of how the data structure and operations are implemented. For example, we can use
the stack ADT in a computer program by using the two operations defined in the
stack interface. We do not need to know whether these operations were implemented
using a linked list or an array.

The Concept of Data Type

In mathematics it is customary to classify variables according to certain important

characteristics. Clear distinctions are made between real, complex, and logical
variables or between variables representing individual values, or sets of values, and
so on. This notion of classification is equally if not more important in data
processing. We will adhere to the principle that every constant, variable, expression,
or function is of a certain type. This type essentially characterizes the set of values to

35 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

which a constant belongs, or which can be assumed by a variable or expression, or

which can be generated by a function.

In mathematical texts the type of a variable is usually deducible from the typeface
without consideration of context; this is not feasible in computer programs. Usually
there is one typeface available on computer equipment (i.e., Latin letters). The rule is
therefore widely accepted that the associated type is made explicit in a declaration
of the constant, variable, or function, and that this declaration textually precedes the
application of that constant, variable, or function. This rule is particularly sensible if
one considers the fact that a compiler has to make a choice of representation of the
object within the store of a computer.

Evidently, the amount of storage allocated to a variable will have to be chosen

according to the size of the range of values that the variable may assume. If this
information is known to a compiler, so-called dynamic storage allocation can be
avoided. This is very often the key to an efficient realization of an algorithm. The
primary characteristics of the concept of type that is used throughout this note are:

1. A data type determines the set of values to which a constant belongs, or which
may be assumed by a variable or an expression, or which may be generated by an
operator or a function.

2. The type of a value denoted by a constant, variable, or expression may be derived

from its form or its declaration without the necessity of executing the computational
process.

3. Each operator or function expects arguments of a fixed type and yields a result of
a fixed type. If an operator admits arguments of several types (e.g., + is used for
addition of both integers and real numbers), then the type of the result can be
determined from specific language rules.

Since constituent types may again be structured, entire hierarchies of structures may
be built up, but, obviously, the ultimate components of a structure are atomic.
Therefore, it is necessary that a notation is provided to introduce such primitive,

36 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

unstructured types as well. A straightforward method is that of enumerating the

values that are to constitute the type. For example in a program concerned with
plane geometric figures, we may introduce a primitive type called shape, whose
values may be denoted by the identifiers rectangle, square, ellipse, circle. But apart
from such programmer-defined types, there will have to be some standard,
predefined types. They usually include numbers and logical values. If an ordering
exists among the individual values, then the type is said to be ordered or scalar.

With this tool in hand, it is possible to define primitive types and to build
conglomerates, structured types up to an arbitrary degree of nesting. In practice, it is
not sufficient to have only one general method of combining constituent types into
a structure. With due regard to practical problems of representation and use, a
general-purpose programming language must offer several methods of structuring.
In a mathematical sense, they are equivalent; they differ in the operators available to
select components of these structures.

Variables and data types are introduced in a program in order to be used for
computation. To this end, a set of operators must be available. For each
standard data type a programming language offers a certain set of primitive,
standard operators, and likewise with each structuring method a distinct
operation and notation for selecting a component. The task of composition of
operations is often considered the heart of the art of programming. However, it
will become evident that the appropriate composition of data is equally
fundamental and essential.

The most important basic operators are comparison and assignment, i.e., the test for
equality (and for order in the case of ordered types), and the command to enforce
equality. The fundamental difference between these two operations is emphasized
by the clear distinction in their denotation throughout this text.

Test for equality: x = y (an expression with value TRUE or FALSE)

Assignment to x: x := y (a statement making x equal to y)

37 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

These fundamental operators are defined for most data types, but it should be
noted that their execution may involve a substantial amount of computational effort,
if the data are large and highly structured. For the standard primitive data types, we
postulate not only the availability of assignment and comparison, but also a set of
operators to create (compute) new values. Thus we introduce the standard
operations of arithmetic for numeric types and the elementary operators of
propositional logic for logical values.

Primitive Data Types

A new, primitive type is definable by enumerating the distinct values belonging to it.
Such a type is called an enumeration type. Its definition has the form:

TYPE T = (c1, c2, ... , cn)

T is the new type identifier, and the ci are the new constant identifiers.

Examples

TYPE shape = (rectangle, square, ellipse, circle)

TYPE color = (red, yellow, green)
TYPE sex = (male, female)
TYPE weekday = (Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday)
TYPE currency = (franc, mark, pound, dollar, shilling, Nira, Leone, yen)
TYPE vehicle = (train, bus, automobile, boat, airplane)
TYPE rank = (private, corporal, sergeant, lieutenant, captain, major, colonel, general)

The definition of such types introduces not only a new type identifier, but at the
same time the set of identifiers denoting the values of the new type. These
identifiers may then be used as constants throughout the program, and they
enhance its understandability considerably. If, as an example, we introduce variables
s, d, r, and b.

VAR s: sex
VAR d: weekday

38 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

VAR r: rank

Then the following assignment statements are possible:

s := male
d := Sunday
r := major
b := TRUE

Evidently, they are considerably more informative than their counterparts

s := 1 d := 7 r := 6 b := 2

which are based on the assumption that c, d, r, and b are defined as integers and
that the constants are mapped onto the natural numbers in the order of their
enumeration.

Standard Primitive Types

Standard primitive types are those types that are available on most computers as
built-in features. They include the whole numbers, the logical truth values, and a set
of printable characters. On many computers fractional numbers are also
incorporated, together with the standard arithmetic operations. We denote these
types by the identifiers

INTEGER, REAL, BOOLEAN, CHAR, SET

Integer types

The type INTEGER comprises a subset of the whole numbers whose size may vary
among individual computer systems. If a computer uses n bits to represent an
integer, then the admissible values x must satisfy -2n-1 ≤ x < 2n-1.
It is assumed that all operations on data of this type are exact and correspond to
the ordinary laws of arithmetic, and that the computation will be interrupted in the
case of a result lying outside the representable subset. This event is called overflow.

39 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

The standard operators are the four basic arithmetic operations of addition (+),
subtraction (-), multiplication (*), and division (/).

The type REAL

The type REAL denotes a subset of the real numbers. Whereas arithmetic with
operands of the types INTEGER is assumed to yield exact results, arithmetic on
values of type REAL is permitted to be inaccurate within the limits of round-off
errors caused by computation on a finite number of digits. This is the principal
reason for the explicit distinction between the types INTEGER and REAL, as it is
made in most programming languages.

The standard operators are the four basic arithmetic operations of addition (+),
subtraction (-), multiplication (*), and division (/). It is an essence of data typing that
different types are incompatible under assignment. An exception to this rule is made
for assignment of integer values to real variables, because here the semantics are
unambiguous. After all, integers form a subset of real numbers. However, the inverse
direction is not permissible: Assignment of a real value to an integer variable
requires an operation such as truncation or rounding.

The type BOOLEAN

The two values of the standard type BOOLEAN are denoted by the identifiers TRUE
and FALSE. The Boolean operators are the logical conjunction, disjunction, and
negation whose values are defined in the Table below. The logical conjunction is
denoted by the symbol &, the logical disjunction by OR, and negation by “~”. Note
that comparisons are operations yielding a result of type BOOLEAN. Thus, the result
of a comparison may be assigned to a variable, or it may be used as an operand of
a logical operator in a Boolean expression. For instance, given Boolean variables p
and q and integer variables x = 5, y = 8, z =10, the two assignments

p := x = y
q := (x ≤ y) & (y < z)
yield p = FALSE and q = TRUE.

40 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

p q p&q p OR q ~p

TRUE TRUE TRUE TRUE FALSE

TRUE FALSE TRUE FALSE FALSE

FALSE TRUE TRUE FALSE TRUE

FALSE FALSE FALSE FALSE TRUE

Table 1.1 Boolean Operators.

The type CHAR

The standard type CHAR comprises a set of printable characters. Unfortunately, there
is no generally accepted standard character set used on all computer systems.
Therefore, the use of the predicate "standard" may in this case be almost
misleading; it is to be understood in the sense of "standard on the computer system
on which a certain program is to be executed."

The character set defined by the International Standards Organization (ISO), and
particularly its American version ASCII (American Standard Code for Information
Interchange) is the most widely accepted set. It consists of 95 printable (graphic)
characters and 33 control characters, the latter mainly being used in data
transmission and for the control of printing equipment.

41 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

INTRODUCTION TO ALGORITHMS

Algorithms are especially important to computers because computers are really

general purpose machines for solving problems. But in order for a computer to be
useful, we must give it a problem to solve and a technique for solving the problem.
Through the use of algorithms, we can make computers "intelligent" by
programming them with various algorithms to solve problems. Because of their
speed and accuracy, computers are well-suited for solving tedious problems such as
searching for a name in a large telephone directory or adding a long column of
numbers.

The Definition of an Algorithm

An algorithm is a well – ordered collection of unambiguous and effectively

computable operations that when executed produces a result and halts in a

finite amount of time.

With this definition, we can identify five important characteristics of algorithms.

1. Algorithms are well-ordered.

2. Algorithms have unambiguous operations.
3. Algorithms have effectively computable operations.
4. Algorithms produce a result.
5. Algorithms halt in a finite amount of time.

Algorithms are well-ordered

Since an algorithm is a collection of operations or instructions, we must know the

correct order in which to execute the instructions. If the order is unclear, we may
perform the wrong instruction or we may be uncertain which instruction should be
performed next. This characteristic is especially important for computers. A computer
can only execute an algorithm if it knows the exact order of steps to perform.

42 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

Algorithms have unambiguous operations

Each operation in an algorithm must be sufficiently clear so that it does not need to
be simplified. Given a list of numbers, you can easily order them from largest to
smallest with the simple instruction "Sort these numbers." A computer, however,
needs more detail to sort numbers. It must be told to search for the smallest
number, how to find the smallest number, how to compare numbers together, etc.

The operation "Sort these numbers" is ambiguous to a computer because the

computer has no basic operations for sorting. Basic operations used for writing
algorithms are known as primitive operations or primitives. When an algorithm is
written in computer primitives, then the algorithm is unambiguous and the
computer can execute it.

Algorithms have effectively computable operations

Each operation in an algorithm must be doable, that is, the operation must be
something that is possible to do. Suppose you were given an algorithm for planting
a garden where the first step instructed you to remove all large stones from the soil,
this instruction may not be doable if there is a four ton rock buried just below
ground level. For computers, many mathematical operations such as division by zero
or finding the square root of a negative number are also impossible. These
operations are not effectively computable so they cannot be used in writing
algorithms.

Algorithms produce a result

In our simple definition of an algorithm, we stated that an algorithm is a set of

instructions for solving a problem. Unless an algorithm produces some result, we
can never be certain whether our solution is correct. Have you ever given a
command to a computer and discovered that nothing changed? What was your
response? You probably thought that the computer was malfunctioning because
your command did not produce any type of result. Without some visible change,

43 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

you have no way of determining the effect of your command. The same is true with
algorithms. Only algorithms which produce results can be verified as either right or
wrong.

Algorithms halt in a finite amount of time

Algorithms should be composed of a finite number of operations and they should

complete their execution in a finite amount of time. Suppose we wanted to write an
algorithm to print all the integers greater than 1. Our steps might look something
like this:

1. Print the number 2.

2. Print the number 3.
3. Print the number 4.

While our algorithm seems to be pretty clear, we have two problems. First, the
algorithm must have an infinite number of steps because there are an infinite
number of integers greater than one. Second, the algorithm will run forever trying to
count to infinity. These problems violate our definition that an algorithm must halt
in a finite amount of time. Every algorithm must reach some operation that tells it to
stop.

Specifying Algorithms

When writing algorithms, we have several choices of how we will specify the
operations in our algorithm. One option is to write the algorithm using plain English
although plain English may seem like a good way to write an algorithm, it has some
problems that make it a poor choice. First, plain English is too wordy. When we write
in plain English, we must include many words that contribute to correct grammar or
style but do nothing to help communicate the algorithm. Second, plain English is
too ambiguous. Often an English sentence can be interpreted in many different
ways. Remember that our definition of an algorithm requires that each operation be
unambiguous.

44 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

Another option for writing algorithms is using programming languages. These

languages are collections of primitives (basic operations) that a computer
understands. While programming languages avoid the problems of being wordy and
ambiguous, they have some other disadvantages that make them undesirable for
writing algorithms. Consider the following lines of code from the programming
language java.

int a = 1;
int b = 0;
while (a <= 10)
{
b += a;
a++;
}
[Link] (b);

This algorithm sums the numbers from 1 to 10 and displays the answer on the
computer screen. However, without some special knowledge of the Java
programming language, it would be difficult for you to know what this algorithm
does. Using a programming language to specify algorithms means learning special
syntax and symbols that are not part of Standard English. For example, in the code
above, it is not very obvious what the symbol "++" or the symbol "+=" does. When
we write algorithms, we would rather not worry about the details of a particular
programming language.

What we would really like to do is combine the familiarity of plain English with the
structure and order of programming languages. A good compromise is structured
English. This approach uses English to write operations, but groups operations by

45 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
 Data Structure and Algorithm BIT/CS YR2 Njala University

indenting and numbering lines. An example of this approach is the directions for
changing motor oil illustrated below.

Each operation in the algorithm is written on a separate line so they are easily
distinguished from each other. We can easily see the advantage of this organization
by comparing the structured English algorithm with the plain English algorithm.

How to change your motor oil

Plain English Structured English
First, place the oil pan underneath the oil plug 1. Place the oil pan underneath the oil
of your car. Next, unscrew the oil plug and plug of your car.
drain the oil. Now, replace the oil plug. Once 2. Unscrew the oil plug.
the old oil is drained, remove the oil cap from 3. Drain oil.
the engine and pour in 4 quarts of oil. Finally, 4. Replace the oil plug.
replace the oil cap on the engine. 5. Remove the oil cap from the engine.
6. Pour in 4 quarts of oil.
7. Replace the oil cap.

For the remainder of this study, we will write our algorithms using the structured
English approach.

46 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

SORTING ALGORITHMS

Now that we have a definite way of writing our algorithms, let's look at some
algorithms for solving the problem of sorting. Sorting is a very common problem
handled by computers. For example, most graphical email programs allow users to
sort their email messages in several ways: date received, subject line, sender, priority,
etc. Each time you reorder your email messages, the computer uses a sorting
algorithm to sort them. Since computers can compare a large number of items
quickly, they are quite good at sorting.

Sorting is generally understood to be the process of rearranging a given set of

objects in a specific order. The purpose of sorting is to facilitate the later search for
members of the sorted set. As such it is an almost universally performed,
fundamental activity. Objects are sorted in telephone books, in income tax files, in
tables of contents, in libraries, in dictionaries, in warehouses, and almost everywhere
that stored objects have to be searched and retrieved. Even small children are
taught to put their things "in order", and they are confronted with some sort of

sorting long before they learn anything about arithmetic.

Hence, sorting is a relevant and essential activity, particularly in data processing.

What else would be easier to sort than data! Nevertheless, our primary interest in
sorting is devoted to the even more fundamental techniques used in the
construction of algorithms. There are not many techniques that do not occur
somewhere in connection with sorting algorithms. In particular, sorting is an ideal
subject to demonstrate a great diversity of algorithms, all having the same purpose,
many of them being optimal in some sense, and most of them having advantages
over others. It is therefore an ideal subject to demonstrate the necessity of
performance analysis of algorithms. The example of sorting is moreover well suited
for showing how a very significant gain in performance may be obtained by the

47 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

development of sophisticated algorithms when obvious methods are readily

available.

Our list of numbers will be stored in an array of memory cells like the diagram
below.

One important quality of a good algorithm is that it solves a class of problems and
not just one particular problem. A good sorting algorithm should provide a solution
to the problem of sorting for many types of items. Imagine if you were trying to
design an email program that allowed users to sort their messages by date received,
subject line, and sender. Would you want to write a new algorithm for each different
sort, or would you prefer to write a single algorithm that handled all three? Of
course you would prefer the latter approach, so when you designed your algorithm,
you would design it to solve a class of problems (e.g. sorting) rather than an
individual problem (e.g. sorting emails by date).

BASIC OPERATIONS

The sorting algorithms we will learn in the next few lessons share two basic
operations in common. These operations are the comparison operation and the
swap operation. We will look at each one in more detail before we examine our
sorting algorithms.

The Comparison Operation

The comparison operation is simply a way of determining which item in a list should
come first. If we are sorting a list of numbers from smallest to largest, the
comparison operation tells us to place the number with the least value first. If we
are sorting a list of letters alphabetically, the comparison operation tells us to place

48 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

'a' before 'b', 'b' before 'c', and so on. We will see that a sorting algorithm must
usually perform many comparisons in order to correctly sort a list.

The Swap Operation

The swap operation is one way we move items as we are sorting. By swapping small
items with large ones, we can place all the items in the correct order. When we use
computers for sorting, the swap operation can be a little tricky because of the way
computers copy data from one memory location to another. Using the example
below, see if you can correctly determine the algorithm for the swap operation

5 4

Cell A Cell B

Use the mouse to swipe the content of the cells what problem do you discover?
How do you solve this problem?

The best things to do

Let's take one more look at the swap algorithm we wrote:

1. Copy the contents of cell A to temp.

2. Copy the contents of cell B to cell A.
3. Copy the contents of temp to cell B.

Notice that this operation requires three copies. It is important to remember that
the swap operation is really a combination of copy operations. In our next lesson,
we will learn a sorting algorithm called the Simple Sort that uses just the copy
operation rather than the swap operation.

49 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

THE SIMPLE SORT

Simple Sort can be used by a computer. Let's see what this algorithm looks like and
how it can be used to sort numbers in a computer.

Simple Sort Algorithm

1. Get a list of unsorted numbers

2. Repeat steps 3 through 6 until the unsorted list is empty
3. Compare the unsorted numbers
4. Select the smallest unsorted number
5. Move this number to the sorted list
6. Store a maximum value in the place of the smallest number
7. Stop

For our algorithm to work, we must replace our original number with a special
marker so it will not be considered again. The steps below illustrate how the Simple
Sort algorithm works on a computer.

1. First, we give the computer a list of unsorted numbers. These numbers are
stored in a group of contiguous memory cells called an array. Each memory
cell of the array holds a single number.

2. As the computer sorts these numbers, it will repeatedly compare them to find
the smallest number. This is similar to the comparisons made when sorting
our hand of cards. Each time we compared two cards and kept the smaller of

50 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

the two. Then we compared this card to the remaining cards until we found a
smaller one or checked all the cards. The computer uses the same process
only with numbers rather than cards.

3. Once the smallest number is found, the computer will copy this number to a
new array of memory cells and replace the old number with a special number
called MAX. MAX is the largest number a single memory cell can hold. None
of the remaining numbers can be larger than MAX, so this number is a good
choice for marking memory cells that have already been sorted.

Unsorted Array

Sorted Array

4. Next, the computer begins searching for the smallest number in the unsorted
list. Although it is easy for us to scan the numbers and select the 2 as
smallest, the computer must compare all the memory cells in the unsorted
array to be certain which number is smallest. This means the computer must
perform six comparisons: (7 < 8), (7 > 5), (5 > 2), (2 < 4), (2 < 6), and finally
(2 < 3) Once the comparisons are done, the computer copies 2 to the sorted
array and replaces the original 2 with MAX.

Unsorted Array

Sorted Array

51 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

5. Now the computer begins searching for the smallest number again. Six more
comparisons are required to determine that 3 is smallest: (7 < 8), (7 > 5),
(5 < MAX), (5 > 4), (4 < 6), and finally (4 > 3). Now we can see the
importance of replacing 2 with MAX in our previous step. If we had not made
this change, then 2 would have been selected as the smallest number again.
After copying 3 to the sorted array, the computer also replaces the original
with MAX.

Unsorted Array

Sorted Array

6. With six more comparisons, the computer selects 4 as the smallest number,
copies it to the sorted array, and replaces the original with MAX.

Unsorted Array

Sorted Array

7. The numbers 5, 6, 7, and 8 are also selected in turn by six comparisons, a

copy, and a replacement of the original. Once all the memory cells in the
unsorted array have been considered, the sorted array contains our original
numbers in sorted order.

Unsorted Array

52 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

Sorted Array

THE INSERTION SORT

Now let's look at how the Insertion Sort algorithm would work inside a computer.
Below is our modified algorithm for sorting a list of numbers.

Insertion Sort Algorithm

1. Get a list of unsorted numbers

2. Set a marker for the sorted section after the first number in the list
3. Repeat steps 4 through 6 until the unsorted section is empty
4. Select the first unsorted number
5. Swap this number to the left until it arrives at the correct sorted position
6. Advance the marker to the right one position
7. Stop

The steps below illustrate how the Insertion Sort algorithm works on a computer.

1. First, we give the computer a list of unsorted numbers and store them in an
array of memory cells

53 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

2. To begin the sort, the computer divides the sorted and unsorted sections of
the list by placing a marker after the first number. To sort the numbers, it will
repeatedly compare the first unsorted number with the numbers in the sorted
section. If the unsorted number is smaller than its sorted neighbour, the
computer will swap them.

3. The first number in the unsorted section is 8, so the computer compares it

with the number to the left. Since 8 is greater than 7, these numbers do not
need to be swapped and the computer simply advances the marker one
position. Notice that only one comparison was needed to sort the 8.

4. Now the first number in the unsorted section is 5. 5 is less than 8, so the
computer swaps these numbers.

5. 5 is also less than 7, so the computer swaps these numbers as well.

54 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

6. Now 5 is in the correct order, so the computer advances the marker one
position. This time two comparisons and two swaps were needed to sort the
number.

7. Now the first number in the unsorted section is 2. 2 is less than 8, 7, and 5,
so after three comparisons and three swaps, 2 arrives at the correct sorted
position, and the computer advances the sort marker.

8. Now the first number in the unsorted section is 4. 4 is less than 8, 7, and 5
but it is not less than 2. This time the computer performs four comparisons
and three swaps to put the 4 in the correct order. Only three swaps were
needed since the 2 and the 4 did not need to be switched. After these
comparisons and swaps, the computer advances the sort marker.

9. Now 6 is the first number in the unsorted section. After three comparisons
and two swaps, the computer places the 6 in the correct position between 5
and 7. Notice that the computer did not need to compare the 6 with the 2 or
the 4 since it already knows these numbers are less than 5. Once the
computer finds a number in the sorted section less than 6, it knows it has
found the correct position for 6 and it can advance the sort marker.

55 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

10. The final unsorted number is 3. To find the correct position for 3, the
computer must compare it with every number in the unsorted section.
However, only five swaps are required since the first number (2) is less than 3.
After moving 3 to the correct position and advancing the sort marker, the
Insertion Sort is complete since the unsorted section is empty.

THE SELECTION SORT

Let’s see how the computer would perform this sort with numbers. Below is our
modified algorithm for sorting a list of numbers.

Selection Sort Algorithm

1. Get a list of unsorted numbers

2. Set a marker for the unsorted section at the front of the list
3. Repeat steps 4 - 6 until one number remains in the unsorted section
4. Compare all unsorted numbers in order to select the smallest one
5. Swap this number with the first number in the unsorted section
6. Advance the marker to the right one position
7. Stop

56 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

The steps below illustrate how the Selection Sort algorithm works on a computer.

1. First, we give the computer a list of unsorted numbers and store them in an
array of memory cells.

2. To begin the sort, the computer divides the sorted and unsorted sections of
the list by placing a marker before the first number. To sort the numbers, the
computer will repeatedly search the unsorted section for the smallest number,
swap this number with the first number in the unsorted section, and update
the sort marker.

3. To find the smallest number in the unsorted section, the computer must make
six comparisons: (7 < 8), (7 > 5), (5 > 2), (2 < 4), (2 < 6), and (2 > 3). After
these comparisons, the computer knows that 2 is the smallest number, so it
swaps this number with 7, the first number in the unsorted section, and
advances the sort marker.

4. Now five more comparisons are needed to find the smallest number in the
unsorted section: (8 > 5), (5 < 7), (5 > 4), (4 < 6), and (4 > 3). After these
comparisons, the computer swaps 3, the smallest number in the unsorted
section, with 8, the first number in the unsorted section, and advances the
sort marker.

57 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

5. This time four comparisons are needed to determine that 4 is the smallest
number in the unsorted section: (5 < 7), (5 > 4), (4 < 6), and (4 < 8). After
these comparisons, the computer swaps 4 with 5 and then advances the sort
marker.

6. After three more comparisons, the computer identifies 5 as the smallest

unsorted number: (7 > 5), (5 < 6), and (5 < 8). Then the computer swaps 5
with 7 and advances the sort marker.

7. This time only two comparisons are needed to determine that 6 is the
smallest number: (7 > 6) and (6 < 8). After these two comparisons, the
computer swaps 6 with 7 and then advances the sort marker.

8. Now we only need a single comparison to find the right position for 7:
(7 < 8). Since 7 is the smallest number and it is also the first number in the
unsorted section, the computer does not need to swap this number. It only
needs to advance the sort marker. Now there is only one number in the

58 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

unsorted section, so the list of numbers is sorted and the Selection Sort
algorithm is complete.

Problems and algorithms

In this section, we introduce the concept of algorithms and discuss the issues of
fundamental analysis of algorithms. An algorithm is a clearly specified set of simple
instructions to be followed to solve a problem. In other words, it is a step-by-step
procedure for taking any instance of a problem and producing a correct answer for
that instance.

Example 1.1 Finding the minimum:

Problem Given a non-empty set of numbers, what is the minimum element of the
set?

Instance:

What is the minimum element of (2, 5, 8, 3) entered on a single line from the
keyboard?

Algorithm 1.1 is a solution for solving the problem of finding the minimum of a set
of data that are input from the keyboard. The algorithm should give a correct
answer for any set of data.

Algorithm 1.1 Minimum key

INPUT: nothing
OUTPUT: the minimum

59 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

1: read min;
2: while not eoln do
3: read x
4: if x < min then
5: min ← x
6: end if
7: end while
8: print min;

Implementation

Algorithm 1.1 can be implemented to a Java method and run on a computer:

import [Link];
int min() {
Scanner input = new Scanner( [Link] );
[Link]("x=? (999 to end) ");
int x = [Link]();
int min = x;
while (x!=999) {
[Link]("x=? (999 to end) ");
x = [Link]();
if (x < min) {
min = x;
}
}
return min;
}

Pseudo-code for algorithm description

Using a natural language such as plain English to describe an algorithm is not

impossible. However, one quickly realizes that any human language is too rich to be
concise or precise enough for the task. A common practice is to use so-called
pseudo-code to describe algorithms. The syntax of any pseudo-code is similar to
that of a high-level computer language such as Java. It is therefore much more

60 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

convenient for an algorithm in pseudo-code to be translated into a computer

program in some higher language than from a human language.

Thus once an algorithm for a problem is properly developed, it is a relatively easy

matter to implement or translate it into a program in some computer language. In
this course, instead of giving a formal definition of the pseudo-code, we just borrow
conventional syntax in Java, or the like. We encourage you to separate the algorithm
design and implementation in the first and second stages respectively. During the
first stage, i.e. the algorithm design stage we ignore the implementation details and
focus on problem-solving techniques and algorithmic issues.

Efficiency

In this module, our goal is not only to develop a working algorithm, but also an
efficient algorithm for a given problem. The speed of hardware computation of basic
operations has been improved dramatically, but efficiency matters more than ever
today. This is because our ambition for computer applications has grown with
computer power. Many areas demand a great increase in speed of computation.
Examples include the simulation of continuous systems, high resolution graphics,
and the interpretation of physical data, medical applications, and information
systems.

On the other hand (and more importantly), an algorithm may be so inefficient that,
even with computation speed vastly increased, it would not be possible to obtain a
result within a useful period of time. The time that many algorithms take to execute
is a non-linear function of the input size. This can reduce their ability to benefit from
the increase in speed when the input size is large.

Example 1.2 A particular sorting algorithm takes n2 comparisons to sort n numbers.

Suppose that computing speed increases by a factor of 100. In the time that it was
required to take to execute the n2comparisons, it is now possible to do 100n2 =
(10n)2 comparisons. Unfortunately, with 100 times speed-up, only 10 times as many
numbers can be sorted as before.

61 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

Measures of performance

Naturally, the efficiency of an algorithm is estimated by its performance. The

performance of an algorithm can be measured by the time and the space required
in order to fulfil a task. The time and space requirement of an algorithm is called the
computational complexity of the algorithm. The greater the amount of the time and
space required, the more complex is the algorithm.

The time complexity of an algorithm is, loosely speaking, an imaginary execution

time of the algorithm. The execution time can be measured by the number of some
characteristic operations performed by the algorithm in order to transform the input
data to the results. Note that we do not measure the time complexity by the
running time of a program. This means that we do not use the common time units
such as second, minute and hour. The unit of the time complexity, strictly speaking,
should be the number of execution steps, although we often do not use any unit.

An algorithm consists of a set of ordered instructions and the time complexity, that
is, the number of execution steps in an algorithm, is irrelevant to the real time. Note
our main interest here is in an algorithm instead of a program. A program is an
implementation of an algorithm. The execution time of a program depends on the
implementation including not only the operating system but also the speed of the
computer itself.

The same program may run faster on a computer with a faster CPU, but the same
algorithm should perform the same number of algorithmic steps to accomplishment
a task. Normally we are concerned with the time complexity rather than space
complexity of an algorithm. The reasons are that firstly it becomes easier and
cheaper to obtain space. Secondly techniques to achieve space efficiency by
spending more time are available.

Observation

62 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

The complexity of an algorithm normally depends on the size of input. The number
of operations may depend on a particular input.

Solution

For different sets of input data, we analyse the performance of an algorithm in the
worst case or in the average case. For different algorithms, we focus on the growth
rate of the time taken by the algorithms as the input size increases. The time
complexity of an algorithm can be expressed by a function of input size: T (n). We
are normally interested in the behaviour of T (n) as n grows large.

ALGORITHM ANALYSIS

Analysis of algorithms is the theoretical study of computer program performance

and resource usage. This section of the course is concerned with the design and
analysis of “good” algorithms and data structures. Intuitively speaking, an algorithm
is a step-by-step procedure (a “procedure”) for performing a task, and a data
structure is a systematic way of organizing data and making it accessible in certain
ways. It turns out that the two tasks — designing algorithms and designing data
structures — are intimately linked; usually, a good algorithm builds upon
appropriate data structures. There are examples of intricate data structures that have
been designed with the sole purpose of making a particular algorithm more
efficient.

With the measures of performance introduced earlier, it is possible to conduct an

analysis and estimate the cost of an algorithm. Many reasons can be given to
explain why we need algorithm analysis. One main reason is that there are usually
several algorithmic ideas for a problem, and we would like to eliminate the
inefficient algorithms early. By early, we mean that we would like to compute or
estimate the computational complexity of any two algorithms before actually
implementing (coding) them into programs.

63 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

Secondly, algorithms may behave differently for different input sizes, and we would
like to estimate their computational complexity for large inputs. For some problems
we simply have not found an efficient algorithm yet, but we may find those
algorithms feasible and useful for input within some limited range.

Furthermore, the ability to do an analysis usually provides insight into designing

efficient algorithms. The analysis also could pinpoint the bottlenecks which should
be taken care of during coding. In what follows, we shall introduce some
fundamental methods for algorithm analysis. Before moving on, we have to first
agree a model of ‘normal’ computer.

But what makes an algorithm good? This is the question we are going to discuss in
this section.

Evaluating Algorithms

What makes an algorithm good? The three most important criteria are correctness,
efficiency, and simplicity.

Correctness is clearly the most important criterion for evaluating an algorithm. If the
algorithm is not doing what it is supposed to do, it is worthless. Unfortunately, it is
not always easy to establish the correctness of an algorithm; it may actually require
complicated mathematical proofs to do this.

The focus of the section will be on efficiency. We would like our algorithms to make
efficient use of the computer’s resources. In particular, we would like them to run as
fast as possible using as little memory as possible. To keep things simple, we will
concentrate on the runtime of the algorithms and will only occasionally look at the
space (i.e., amount of memory) they need.

The third important criterion is simplicity. We would like our algorithms to be easy
to understand and easy to implement. Unfortunately, there often (but not always) is
a trade-off between efficiency and simplicity: More efficient algorithms tend to be
more complicated. It depends on the particular task which of the two criteria is more

64 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

important. If a program is used only once or few times, the cost of implementing a
very efficient, but also very complicated algorithm may exceed the cost of running a
simple, but inefficient algorithm. On the other hand, if a program will be used very
often, the cost of running an inefficient algorithm over and over again may by far
exceed the cost of implementing an efficient complicated algorithm. It is up to the
programmer to decide which way to go in any particular situation.

Counting steps

Given two algorithms A1 and A2, which one is more efficient? In other words, which
one has lower computational complexity? To answer this question, one way is to
simply count the execution steps of each algorithm and compare the numbers of
the steps of the two.

Example

Problem: Compute ∑𝑛𝑘=1 k, where n is an integer.

Algorithm 1.2 Sum1(n)

INPUT: n
OUTPUT: sum
1: sum ← 0
2: for k ← 1, k ≤ n, k ← k + 1 do
3: sum ← sum+ k
4: end for
5: print sum
From the fact
we have
𝑛(𝑛−1)
∑𝑛𝑘=1 k =
2

Algorithm 1.3 Sum2(n)

INPUT: n
OUTPUT: sum
1: print n(n + 1)/2

65 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

Implementation

These algorithms can be implemented to the following Java methods:

int sum1( int n ) {

int sum = 0;
for (int k=1; k<=n; k++) {
sum = sum + k;
}
return sum;
}
int sum2( int n ) {
int sum;
return (n*(n+1)/2);
}

We look at the time complexity by counting the steps taken in execution. Let any
assignment, arithmetic computation +,-,*,/, read, print be all counted as one step. So
for Algorithm 1.2, it takes 1 + n × 1 + 1 = n + 2 steps; and for Algorithm 1.3, it
takes 1 + 1 + 1 = 3 steps to execute. Obviously, Algorithm 1.3 is more efficient in
terms of execution time.

How about the space efficiency? Let a simple variable require one unit of storage.
Algorithm 1.2 needs three units since it involves three variables sum, k and n, and
Algorithm 1.3 only needs two units since it involves only two variables n and sum.
We can therefore conclude that Algorithm 1.3 is more efficient in terms of storage,
too.

In fact, Algorithm 1.3 has an important advantage, that is, it takes constant time to
execute no matter how large n is. This means that it takes the same amount of time
to run no matter how many such numbers need to be added up. We have done an
analysis. Had we, however, to undertake all the counting every time to analyse an

66 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

algorithm, the task would be tedious and quickly become infeasible. We need some
easier approach.

Asymptotic behaviour

We are often interested in the rate of growth of the time required for an algorithm
when the input size gets larger. So the lower order terms of the time complexity T
(n) could be ignored, where n is a positive integer. In other words, we only need to
master the asymptotic behaviour of T (n). Here the term asymptotic means
approximate in a specific way.

Big O notations

In general, the asymptotic behaviour of functions can be described by so-called

“big-O” notations, often consisting of four members O(), (), _() and o(). They are
called “big-oh”, “omega”, “theta” and “small-oh” respectively.
The worst and average cases

The behaviour of an algorithm usually depends not only on the size of the input, but
also on the input itself. Look at Algorithm 1.4 which determines whether integer x is
an element of array Y [0..n − 1], where n is a non-negative integer.

Example

Algorithm 1.4 boolean foundFirstX(int x, int Y[])

1: i ← 0
2: boolean found ← false
3: while (notfound) && (i < length(Y )) do
4: found ← (x = Y [i])
5: i ← i + 1
6: end while
7: return found

67 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

The time complexity of foundFirstX(x,Y) depends on the value of x and on the

contents of the array Y . For example, if Y [0] = x, that is, the first element in array Y
equals to x, then the while loop (step 3–6 in the algorithm) will only be executed
once, and the number of execution steps is only 1 + 1 + 1 × (1 + 1 + 1 + 1) + 1 =
7, including step 1, step 2, 1 × (step 3, 4, 5, 6), and step 7. If x equals the kth
element of Y , the number of execution steps becomes 1 + 1 + k × (1 + 1 + 1 + 1)
+ 1 = 3 + 4k, where k ≤ length(Y ), including step 1, step 2, k × (step 3, 4, 5, 6), and
step 7. Each of these different situations is called a case. In each case, the algorithm
gives a different performance.

We therefore need to consider the behavior of the algorithm for two special cases,
namely the worst case and the average case.

In terms of time complexity, the worst case is the situation where the algorithm
would take the longest time. The average case is the case where the average
behavior is estimated after every instance of the problem has been taken into
consideration. We define two functions of n, the input size, for the two cases
respectively.

In general, an algorithm may accept k different instances of size n.

Let Ti(n) be the time complexity of the algorithm when given the ith instance, for 1
≤ i ≤ k. Let pi be the probability that this instance occurs. Then the time complexity
for The worst case:

W(n) = max
1≤i≤k
Ti(n)
The average case:

A(n) =
Xk
i=1
piTi(n)

68 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

The worst case analysis could help to provide an estimate for a time limit for a
particular implementation of an algorithm. It is particularly useful in real time
applications. The average case analysis is more meaningful in providing an overall
picture because it computes the number of steps performed for each possible input
instance of size n and then takes the (probability-weighted) average.

RECURSIVE ALGORITHM

A recursive algorithm calls itself which usually passes the return value as a
parameter to the algorithm again. This parameter is the input while the return value

is the output.

The Nature of Recursion

Problems that lend themselves to a recursive solution have the following

characteristics:

 One or more simple cases of the problem (called stopping cases) have a
simple, non-recursive solution.
 For the other cases, there is a process (using recursion) for substituting one or
more reduced cases of the problem that are closer to a stopping case.
 Eventually the problem can be reduced to stopping cases only, all of which
are relatively easy to solve.

The recursive algorithms that we write will generally consist of an if statement with
the form shown below:
if (the stopping case is reached)
{
Solve it
}

69 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

else
{
Reduce the problem using recursion
}
Let's assume that for a particular problem of size N, we can split this problem into
one involving a problem of size 1, which we can solve (a stopping case), and a
problem of size N - 1, which we can split further. If we split the problem N times, we
will end up with N problems of size 1, all of which we can solve.

Recursive Multiplication

Consider how we might solve the problem of multiplying 6 by 3, assuming that we

know the addition tables but not the multiplication tables. The problem of
multiplying 6 by 3 can be split into the two problems:

Problem 1. Multiply 6 by 2.

Problem 2. Add 6 to the result of problem 1.

Because we know the addition tables, we can solve problem 2 but not problem 1.
However, problem 1 is simpler than the original problem. We can split it into the
two problems 1.1 and 1.2, leaving us three problems to solve, two of which are
additions.

Problem 1. Multiply 6 by 2.

Problem 1.1 Multiply 6 by 1.

Problem 1.2 Add 6 to the result.

Problem 2. Add 6 to the result of problem 1.

70 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

Even though we don't know the multiplication tables, we are familiar with the simple
rule that, for any M, M x 1 is M. By solving problem 1.1 (the answer is 6) and
problem 1.2, we get the solution to problem 1 (the answer is 12). Solving problem 2
gives us the final answer, 18.

Factorial

A classical simple example of recursion is the definition of the factorial of a positive

integer N. Written N! and read “N factorial,” this is easily understood as the product
1 x 2 x . . . x N. Thus, 3! = 6, 4! = 24, 5! = 120, and so on. But we can write a
definition without any “dot-dot-dot” as follows:

To find N!:

1. If N = 1 then N! = 1;
2. Otherwise N! = N x (N - 1)!

We have defined the “!” operation in terms of “!”. Notice that the definition is not
circular, because the “!” is applied to a smaller and smaller number each time until it
is applied to 1. Here is the definition applied to calculate 5!.

Recursive Calculation of 5!

5! = 5 x 4!
= 5 x (4 x 3!)
= 5 x (4 x (3 x 2!))
= 5 x (4 x (3 x (2 x 1!)))
= 5 x (4 x (3 x (2 x 1)))
= 5 x (4 x (3 x 2))
= 5 x (4 x 6)
= 5 x 24
= 120

71 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

Try the definition on some other numbers to make sure you understand how the
recursion works. You will discover that N! gets very large very quickly: Even an
innocent-looking calculation, such as 10!, produces a rather large number
(3,628,800). In fact, if you were to write a program to calculate N! and run it on a
computer using 16 bits to represent an integer, your program could not calculate
factorials larger than 7!, because 8! > 32767. On a computer with a 32-bit integer
representation, your program would fail to compute 14!.

Here is the recursive method that does all of this:

public static int factorial(int n) {

if (n == 1) //terminating case

return 1;

int iRet = n * factorial(n-1); //recursive call to itself

return iRet;

This is a more elegant solution than our procedural method. Two key points in this
recursive method are the terminating case and the recursive call. The recursive call
occurs when the method calls itself.

The method above will wait for the recursive call to return before continuing. The
recursive call will also make another recursive call and wait for that to finish... and so
on. The methods are stacking until one method finally returns with a value. That's
where the terminating case comes in. The terminating case stops the function from
making any further calls to itself. The problem is divided to the point where we are

72 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.
Data Structure and Algorithm BIT/CS YR2 Njala University

computing 1!. Since that answer is trivial, there are no more recursive calls and it
returns immediately. This triggers all of the previous recursive calls to return, one-
by-one, and in order.

73 | P a g e
A. Kallon Lecture Notes First Semester - 2014 / 2015 AY.