ADVANCE ANALYSIS OF

ALGORITHM

Irshad Khan
CS & IT
Sarhad University of Science and Information
Technology
IRSHAD KHAN
 Qualification
 PhD (CS) In Progress
 FAST-NUCES Peshawar
 MS (CS)
 FAST-NUCES Peshawar
 MIT
 Gomal University D.I. Khan

 Experience
 Assistant Professor
 Sarhad University of Science and Information Technology
 Lecturer
 Sarhad University of Science and Information Technology
 Lecturer
 IM|Sciences Peshawar
 Lecturer
 CECOS University Peshawar
GRADING POLICY
 Sessional…………………. ………………………20
 Mid Term………….………………………………..30

 Final Term………………………………………….50
LECTURE 1 OUTLINES
 Algorithm
 Basic Data Structure
 Array
 Stack
 Queue
 Linked List
ALGORITHM
• A set of rules for solving a problem in a finite
number of steps

• An algorithm is a procedure for solving a

problem in terms of the actions to be
executed and the order in which those
actions are to be executed. An algorithm is
merely the sequence of steps taken to solve
a problem. The steps are normally
"sequence," "selection, " "iteration," and a
case-type statement.
QUALITIES OF A GOOD ALGORITHM
• Inputs and outputs should be defined precisely.

• Each steps in algorithm should be clear and

unambiguous.

• Algorithm should be most effective among

many different ways to solve a problem.

• An algorithm shouldn't have computer code.

Instead, the algorithm should be written in
such a way that, it can be used in similar
programming languages e.g. (Pseudo Code)
PSEUDO CODE
 Pseudo code is an artificial and informal
language that helps programmers to develop
algorithms.

 Pseudo code is a "text-based" detail

(algorithmic) design tool.

 The rules of Pseudo code are reasonably

straightforward.

 All statements showing "dependency" are to

be indented. These include while, do, for, if,
switch.
PSEUDO CODE (2)
• For looping and selection, The keywords that are to be used include
– Do While...EndDo;
– Do Until...Enddo;
– Case...EndCase;
– If...Endif;
– Call ... with (parameters);
– Call; Return ....;
– Return; When;
– Always use scope terminators for loops and iteration.
• As verbs, use the words Generate, Compute, Process, etc. Words
such as set, reset, increment, compute, calculate, add, sum,
multiply, ... print, display, input, output, edit, test , etc. with careful
indentation tend to foster desirable pseudo code.

If student's grade is greater than or equal to 60

Print "passed"
else
Print "failed"
DATA STRUCTURE
 Array
 Stack

 Queue

 Linked List
ARRAYS
 An array is a list of a finite number of homogeneous data
elements such that
 The elements of the array are referenced respectively by an
index set consisting of "n" consecutive numbers.
 The elements of an array are stored respectively in
successive memory locations.
 The simplest type of data structure is a Linear or one-
dimensional array.
 The number 'n' of elements is known as the length or
size of the array.
 In general the length or the number of data elements of
an array can be obtained from the index set by the
formula
 Length=UB - LB + 1
 Where UB is the largest index, called the upper bound,
and LB is the smallest index , called lower bound.
ARRAY (2)
OPERATIONS ON LINEAR ARRAY
(TRAVERSE)
 Algorithm 1.(Traversing a linear Array)
 This algorithm traverses a linear array LA

with lower bound LB and upper bound UB.

1. Repeat for K = LB to UB:

2. Apply PROCESS to LA[K].

[End of loop.]
3. Exit
 INSERTION IN LINEAR ARRAY
 Algorithm 3.(Inserting into a Linear array) INSERT(LA,
N, K, ITEM)
 Here LA is a linear array with N elements and K is a

positive integer such that K≤N. This algorithm inserts

an element ITEM into the Kth position in LA .

1. [Initialize counter.] Set J=N-1.

2. Repeat Step 3 and 4 while J ≥ K.

3. [Move Jth element downward.] Set LA[J+1] =

LA[J].
4. [Decrease counter.] Set J = J – 1.
[End of Step 2 loop.]
5. [Insert element.] Set LA[K] = ITEM.
6. [Reset N.] Set N = N+1.

7. Exit
DELETION IN LINEAR ARRAY
 Algorithm 4. (Deleting from a linear Array)
DELETE(LA, N, K, ITEM)
 Here LA is a linear array with N elements and K is

a positive integer such that K ≤ N. This

algorithm deletes the Kth element from LA.

1. Set ITEM = LA[K].

2. Repeat for J = K to N-1:

3. [Move J + 1st element upward.] Set LA[J] =

LA[J+1].
[End of loop.]
4. [Reset the number N of elements in LA.] Set N =
N-1.
5. Exit.
STACK
 A stack is a special kind of linear list in which
only two operations, insertion and deletion,
can be performed.

 These operations may occur only at its top

end.

 The item in it are stored and retrieved in last

In First Out (LIFO) manner.
STACK (2)
 A stack is a list of elements in which an
element may be inserted or deleted only at
one end, called the top of the stack.
 This means, in particular, that elements are

removed from a stack in the reverse order of

that in which they were inserted into the
stack.
 “Push” is the term used to insert an element

into a stack.
 “Pop” is the term used to delete an element

from a stack.
 These terms are used only with stacks, not

with other data structures.

 STACK
1 AAA
BBB
2
CCC
TOP 3
DDD
TOP 4
EEE
FFF 5
FFF
EEE 6

DDD 7

CCC 8

BBB 9
N–1
AAA
N

AAA BBB CCC DDD EEE FFF …

1 2 3 4 5 6 7 8 9 … N-1 N
TOP
PROPERTIES AND OPERATIONS
 Properties
 Name, TOP, Size
 Operations
QUEUE DATA STRUCTURE
 A queue is a linear data structure, into which
items can only be inserted at one end and
removed from the other.

 In contrast to the stack, which is a LIFO (Last

In First Out) structure, a queue is a FIFO (First
In First Out) structure.
QUEUE STRUCTURE
 CIRCULAR QUEUE
 Problem:
 We cannot insert

further in the given

queue. Although there
are two places at the
start.
 The solution to this

problem lies in
allowing the queue to
wrap around.
QUEUE OPERATIONS
 Primary Operations
 Insertion (Enqueue)
 Deletion (Dequeue)

 Other Operations
 Traverse
 Front
 IsEmpty
 IsFull
ALGORITHM: ENQUEUE / INSERTION
IN CIRCULAR QUEUE USING ARRAY
ALGORITHM: DEQUEUE / DELETION FROM
CIRCULAR QUEUE USING ARRAY
ALGORITHM: TRAVERSE CIRCULAR
QUEUE USING ARRAY
LINKED LIST DATA STRUCTURE
 Link List is a Data Structure in which
elements are explicitly ordered, that is each
item contains within itself the address of
next item.

 Each node of the list has two elements:

 The item being stored in the list and
 A pointer to the next item in the list

 The last node in the list contains a NULL

pointer to indicate that it is the end or tail of
the list.
LINKED LIST (2)
 As items are added to a list, memory for a
node is dynamically allocated. Thus the
number of items that may be added to a list
is limited only by the amount of memory
available.

 Handle of the LL : The variable ( or handle)

which represents the list, is simply a pointer
to the node at the head of the list.
LINKED LIST (3)
 Picture of our list (2, 6, 7, 8, 1) stored as a
linked list:
NODE STRUCTURE
struct node
{
char name[15];
node *next;
};

class Node {
public:
double data; // data
Node* next; // pointer to next
};
OPERATIONS OF LINKED LIST
 Operations of List
 IsEmpty: determine whether or not the list is
empty
 InsertNode: insert a new node at a particular
position
 FindNode: find a node with a given value
 DeleteNode: delete a node with a given value
 DisplayList: print all the nodes in the list
TRAVERSE ALGORITHMS
DELETE ALGORITHM
DELETE CONTINUE…
VARIATIONS OF LINKED LISTS
 Circular linked lists
 The last node points to the first node of the list

A B C

Head
 How do we know when we have finished traversing
the list? (Tip: check if the pointer of the current
node is equal to the head.)
VARIATIONS OF LINKED LISTS
 Doubly linked lists
 Each node points to not only successor but the
predecessor
 There are two NULL: at the first and last nodes in the
list
 Advantage: given a node, it is easy to visit its
predecessor. Convenient to traverse lists backwards

 A B C 

Head Tail
 In a Doubly linked list, each item is allocated space
as it is added to the list. A link is kept with each item
to the next item and previous item in the list.
 Each node of the list has three elements:

The item being stored in the list

A pointer to the next item in the list

A pointer to the previous item in the list

 The last node in the list contains a NULL pointer

(next) to indicate that it is the end or tail of the list
and first node contains NULL pointer for previous
pointer to indicate that it is head of the Link List.
  Figure showing Doubly Link List …..

NULL NULL
A B C D E

Head
HEAD
Tail

Structure corresponding to above will be

struct node
{
char info;
node *next;
node *previous;
};
Struct DLL{ node *Head,*Tail; }
???