Data structure

Lecture 1
What is meant by data structure ?
- Data structure is any data representation and its
associated operations
- Data structure is a schema for organizing data in the
computer memory
- A data structure is a particular way of sorting and
organization data in a computer so that it can be
used efficiently
- Some of more commonly used data structures
include lists , arrays , stacks , queues, heaps , trees ,
and graphs
The study of such data structure includes the following
three steps :
1-Logical or mathematical description of the structure
2-Implementation of the structure on a computer
3-Quantitative analysis of the structure , which include:
- Determining the amount of memory needed to store
the structure
- The time required to process the structure
- Computer programmers decide which data
structures to use on the nature of the data and the
processes that need to be performed on that data
- When selecting a data structure to solve a problem ,
you should follow these steps :
1-Analyze your problem to determine the basic
operations (insert , delete , traverse ) that must
be supported
2-Quantify the resource constraints for each
operations
3-Select the data structure that best meets these
requirements
- Data structure are classified into two type such as
linear or non-linear
- Linear data structure : a data sturcuter is said to be
linear if its elements form a sequence
- The elements of linear data structure represent by
means of sequential memory locations
- The other way is to have the linear relationship
between the elements represented by means of
pointers of links – EX, array and link list
- Non linear data structure is said to be non linear if its
elements a hierarchical relationship between
elements such as trees and graphs
- All elements assign the memory as random form and
you can fetch data elements through random access
process
The basic operations on data structure are :
1-Traversal : by means of traversal operation, we can
process each element in the list
2-Search : by means of this operation, we can find
the location of the element with a given value or
the record with a given key
3-Insertion : insertion operations is used for adding a
new element to the list
4-Deletion : deletion operation is used to remove an
element from the list
5-Sorting : this operation is used for arranging the
elements in some type of order
6-Merging : by means of merging operation, we can
combine two lists into a single list .
Searching , sorting , and complexity analysis
- Algorithms are one of the basic building blocks of
computer programs
- There are many criteria for assessing the quality of
an algorithm
- The most essential criterion is correctness – namely,
that the algorithm in fact solves the problem it’s
intended to solve
- Readability and ease of maintenance are also
important qualities
- Another important criterion of the quality of
algorithms – (run-time performance )
- When an algorithmic process runs on a real
computer with finite resources , economic thinking
comes into play
- Such a process consumes two resources : processing
time and space or memory
- When run with the same problems or data sets ,a
process that consumes less of these two resources is
of higher quality than a process that consumes
more , and so are the corresponding algorithms
- Most users are happy with any algorithm that loads a
file in less than one second . for such users , any
algorithm that meets this requirement is as good as
any other
- One way to measure the time cost of an algorithm is
to use the computer’s clock to obtain an actual run
time
- This process , called benchmarking , starts by
determining the time for several different data sets
of the same size and then calculates the average
time
- Note that , different hardware platforms have
different processing speeds , so the running times of
an algorithm differ from machine to machine
- Also, the running time of a program varies with the
type of operating system that lies between it and the
hardware
- Another technique used to estimate the efficiency of
an algorithm is to count the instructions executed
with different problem sizes
- These counts provide a good predictor of the
amount of abstract work an algorithm performs , no
matter what platform the algorithm runs on
- Keep in mind , however , that when you count
instructions ,you are counting the instructions in the
high-level code in which the algorithm is written ,
not instructions in the executable machine language
program
You must distinguish between two classes of
instructions:
- Instructions that execute the same number of times
regardless of the problem size
- Instructions whose execution count varies with the
problem size
- The instructions in the second class normally are
found in loops or recursive functions
- In the case of loops, you must take in your
consideration the instructions performed in any
nested loops or , more simply , just the number of
iterations that a nested loop performs
What is searching ?
- Searching is the process of finding a given value
position in a list of values
- It decides whether a search key is present in the data
or not
- There exist two types of searching algorithms : linear
search and binary search
What is sorting ?
- Sorting is a process of ordering a list of elements
from a collection in some kind of order
- Sorting can be done in increasing and decreasing
order
- There exist many algorithms that can be used to sort
any list of elements , such as , bubble sort , insertion
sort , shell sort , heap sort , quick sort
Algorithm complexity
- As you know , an algorithm is a finite set of precise
instructions for performing a computation or for
solving a problem
- Again , the complexity of an algorithm is a function
of describing the efficiency of the algorithm in terms
of the amount of data the algorithm must process
- There are two main complexity measures of the
efficiency of an algorithm : time complexity and
space complexity
- Time complexity is a function describing the amount
of time an algorithm takes in terms of the amount of
input to the algorithm
- Time can mean the number of memory accesses
performed , the number of comparisons between
the integers , the number of times some inner loop is
executed
- Space complexity is a function describing the amount
of memory (space) an algorithm takes in terms of the
amount of input to the algorithm
- The better the time complexity of an algorithm is ,
the faster the algorithm will carry out his work in
practice
Big O Notation
- Big O calculates the worst case time complexity or
the maximum time an algorithm will take to
complete execution
- Big O refers to a way of rating the efficiency of an
algorithm “ O ” stands for “on the order of “, a
reference to the order of complexity of the work of
the algorithm
- An algorithm performs a number of operations

- An algorithm usually performs other work

exactly equal to n,n , k
2 n

in the body of a loop , above the loop ,and

below the loop
- An algorithm is said to be of order
O(expression) , or simply of order
expression (where expression is some
function of n , like n and n is the size of
the data ) if there exist numbers p, q and
2

r so that the running time always lies

below between [Link] +q for n>r
- Generally expression is made as simple
and as small as possible

Lecture 2
Algorithm analysis
Again, analysis of algoritm is the process
of analyzing the problem-solving
capability of the algorithm in terms of the
time and size required
We need to define the following :
Worst case : the maximum number of
steps taken on any instance of size n .
-

Best case : the minimum number of steps

taken on any instance of size n .
-

Average case : an average number of

steps taken on any instance of size n .
-

Linear search
Linear search is a very simple algorithm
In this type of search , a sequential search
-

is made over all items one by one

-

Every item is checked and if a match is

found then that particular item is
-

returned , otherwise the search continues

till the end of the data collection
  The pseudocode of this algorithm can be
written as follows:
Procedure linear_search (list,value)
For each item in the list
If match item==value
Return the item’s location
End if
End for
End procedure
 The worst case is if the element is not
found or is found at the end of the
search in which case there are n
comparsions
 The best case is that the thing you are
looking for is in the first slot and so
there is only one comparison . so, we
can say the best case is one O(1)
comparison and the worst case is n
O(n)comparison
Binary search algorithm
- Binary search is the search technique that
works efficiently on sorted lists
- The idea is to use binary search which is a
divide and conquer algorithm
- Binary search first divides a large array
into two smaller subarrays and then
iteratively operate the subarrays
- Instead of working on both subarrays , it
discards one subarray and then iteratively
operate the subarrays
- Instead of working on both subarrays , it
discards one subarray and continues on
the second subarray
- The decision of discarding one subarray is
made in just one comparison . so binary
search reduces the search space to half at
each step
 The steps of binary search algorithm
can be expressed as follows :
A sorted array
N size of array
X  value to be searched
Set left =0 & right =n-1 & mid=-1
While(left<=right)
Mid=(left+right)
If A[mid]<x
Left=mid+1
Else if A[mid]>x
 Right =mid-1
Else
Return mid
End while
If mid=-1
The value not found
Else
The value is found
 The complexity of binary search
algorithm is O(log n)
 The best case of binary search occurs
when the element to be search is in the
middle of the list
 In this case , the element is found in the
first step itself and this involves 1
comparison
 Therefore , best case time complexity of
binary search is O(1)
Sorting algorithms
- As discussed earlier , sorting is a way of
arranging items in a systematic manner
- Quicksort has historically been the fastest
generic sorting algorithm in practice
- Its average running time is O(nlogn) and
O(n ) worst-case performance
- The classic quicksort algorithm to sort an
2

array S consists of the following four easy

steps :
1- If the number of elements in array s is
0 or 1 , then return
2- Pick any element v in s . this is called
the pivot
3- Partition s-{v}(the remaining elements
in s ) into two disjoint groups :
s1={x⋲ s-{v} | x<=v} ,
and s2={x⋲ s-{v}|x>=v}
4- Return {quicksort(s1) followed by v
followed by quicksort(s2)}
- Quicksort algorithm follows the divide
and conquer approach
- Divide and conquer is a technique of
breaking down the algorithms into
subproblems, then solving the
subproblems, and combining the results
back together to solve the original
problem
- Divide: in divide , first pick a pivot
element . after that , partition or
rearrange the array into two sub-arrays
such that each element in the left sub-
array is less than or equal to the pivot
element and each element in the right
sub-array is larger than the pivot element
- Conquer: recursively, sort two subarrays
with quicksort
 Choosing the pivot :
Picking a good pivot is necessary for the
fast implementation of quicksort . some
of the ways of choosing a pivot are as
follows
- Pivot can be random , ex – select the
random pivot from the given array
- Pivot can either be the rightmost element
of the leftmost element of the given array
- Select median as the pivot element

Lecture 3
Insertion sort
Suppose an array A with N elements
A[0] , A[1] , …., A[N-1] is in memory
 The insertion sort algorithm scans A form
A[0] to A[N-1] , inserting each element
A[K] in its proper position in the
previously sorted sub-array A[0] , A[1] ,
…. , A[N-1] .that is
A[0] by itself is sorted.
➢ A[1] is inserted either before or after
A[0] so that A[0], A[1] is
sorted.
➢ A[2] is inserted into its proper place
compared with A[0] and
A[1], so that A[0], A[1], A[2] is sorted.
➢…
➢ The last element A[N-1] is inserted into
its proper place so that
A[0], A[1], …, A[N-1] is sorted.
- There remains the problem of deciding
how to insert A[k] in its proper place in
the sorted sub-array A[0] , A[1] , ….
- This can be accomplished by comparing
A[k] with A[k-1] , comparing A[k] with
A[k-2] , …. And so on , until first meeting
an element A[j] such that A[j]<= A[k]
  The steps of insertion sort can be
written as follows :
Step 1 : set A[0]= – ∞
Step 2: repeat step 3 to 5 for k=2,3,
….,N
Step 3: set temp=A[k] and ptr=k-1
Step 4: repeat while temp<A[ptr]
(a) Set A[ptr+1]=A[ptr]
(b) Set ptr = ptr-1
End of loop
Step 5: set A[ptr+1] =temp // insert
element in proper place
End of step 2 loop
Step 6: return
 The worst case of insertion sort
algorithm occurs when the array A is in
reverse order and the inner loop must
use the maximum number k-1
comparisons O(n )
Selection sort algorithm
2

The selection sort algorithm used to sort

an array A with N elements works as
follows :
- First find the smallest element in the
array and put it in the first position
- Then find the second smallest element in
the array and put it in the second position
, and so on
 We can the selection sort algorithm as
follows:
SELECTION SORT(arr, n)
Step 1: Repeat Steps 2 and 3 for i = 0 to
n-1
Step 2: CALL SMALLEST(arr, i, n, pos)
Step 3: SWAP arr[i] with arr[pos]
[END OF LOOP]
Step 4: EXIT
SMALLEST (arr, i, n, pos)
Step 1: [INITIALIZE] SET SMALL =
arr[i]
Step 2: [INITIALIZE] SET pos = i
Step 3: Repeat for j = i+1 to n
if (SMALL > arr[j])
SET SMALL = arr[j]
SET pos = j
[END OF if]
[END OF LOOP]
Step 4: RETURN pos
Linked list