Select Business and Technology Collage

CSC 413:Theory of Algorisms

Data Structures and Algorithms Analysis

By: Samuel M.
Chapters Content

 Introduction
 Dynamic programing
 Graph Theory
 Queue

Data Structures and Algorithms Analysis 2 2 June, 2021

Chapter 1: Introduction
 Algorithms Analysis
 Properties of an algorithm
 Algorithm Analysis Concepts
 Complexity Analysis

 Data Structures
 Classification data structure
 Abstract Data Types
 Simple and advanced searching and sorting algorism

Data Structures and Algorithms Analysis 3 June, 2021

Chapter 2: Dynamic Programing

 Dynamic programing: top-down approach

 Greedy algorithms: bottom-up approach

Chapter 3: Graph Theory

 Elementary graph algorithms

 Breadth First Search (BFS)
 Shortest path
 Minimum spacing tree

Data Structures and Algorithms Analysis 4 June, 2021

Chapter 4: Queue

 Simple and Circular array implementation of:

 Enqueue and Dequeue

 Priority Queue
 Demerging Queues and merging
 LIFO, FIFO…

 Application of Queues

Data Structures and Algorithms Analysis 5 June, 2021

Course Objectives:

 To know and understand the problem types and complexity of algorisms

 Understand the properties of dynamic programing

 Understand the properties of graph and graph algorisms and searching techniques

 To apply import algorism design paradigms and methods of analysis

Data Structures and Algorithms Analysis 6 June, 2021

Assessment

 Class Quiz : 15%

 Assignment : 15 %
 Project : 20%
 Final Exam: 50%
 All assignments must be your own work
 Project/s are possible by group

Data Structures and Algorithms Analysis 7 June, 2021

Introduction

Definition
 Data: Collection of raw facts
 Data structure is systematic way of organizing and accessing data
 Algorithm is a step by step procedure to solve a particular function task
 Program is a series of instructions to carry out a particular task
 

Program = Data structure + Algorithm

Data Structures and Algorithms Analysis 8 June, 2021

What is Algorithm?

 Algorithm is any well-defined procedure that

takes value/set of values, as input and
produces value/s, or set of values, as output.

 It is thus a sequence of computational steps that

.
transform the input into the output.
 These are the ideas behind computer programs
Example:
 There are many algorithms even to solve single
 Directions to some school is an algorithm.
 A recipe for cooking a cake is an algorithm problem

Data Structures and Algorithms Analysis 9 June, 2021

Algorithm Analysis

 Why we need algorithm analysis?

 As computers get faster & problem sizes get bigger,
analysis will become more important
 Writing a working program is not good enough
 The difference b/n good & bad algorithms will get bigger

 What to Analyze ?
 Correctness
 Does the input/output relation match algorithm requirement?

 Amount of work done

 Basic operations to do task finite amount of time

Data Structures and Algorithms Analysis 10 June, 2021

Algorithm Analysis…

 What to Analyze…?
 Amount of space used
 Memory used

 Simplicity, clarity
 Verification and implementation

 Optimality
 Is it impossible to do better?

 Time Complexity
 Amount of computer time it needs to execute the program to get the intended result
 Space Complexity
 Memory requirements based on the problem size

Data Structures and Algorithms Analysis 11 June, 2021

Properties of Algorithm

An algorithm possesses the following properties:

 It must be correct
 It must be composed of a series of concrete steps
 There can be no ambiguity as to which step will be performed next
 It must be composed of a finite number of steps
 It must terminate
 It takes zero or more inputs and results one or more output
 It should be efficient and flexible
 It should use less memory space as much as possible

Data Structures and Algorithms Analysis 12 June, 2021

 Steps in Developing Algorithms

 Devising (Develop) the Algorithm:

 A method for solving a problem in which each step of an
algorithm must be precisely defined with clear statements Pseudo code
(plain text) is used to describe the algorithm
 Less formal language than a programming language

 Validating the Algorithm:

 The proof of correctness of the algorithm
 A human must be able to perform each step using paper & pencil using
input to get the required output in a finite amount of time

Data Structures and Algorithms Analysis 13 June, 2021

 Steps in Developing Algorithms…

 Expressing the algorithm:

 To implement the algorithm in a programming language
 The algorithm used should terminate after a finite number of steps

Data Structures and Algorithms Analysis 14 June, 2021

Efficiency of Algorithm

 Writing efficient programs is what every programmer wants to do

 But what kinds of programs are efficient?
 Which is leads Generalization of programs:

 Algorithms are programs in a general form

 An algorithm is an idea upon which a program is built
 An algorithm should meet three things:
 It should be independent of the programming language in which the idea is realized
 Every programmer having enough knowledge & experience should understand it
 It should be applicable to inputs of all sizes

Data Structures and Algorithms Analysis 15 June, 2021

Efficiency of Algorithm…

 It is measured by the amount of resources it uses, the time and the space
 The time refers to the number of steps the algorithm executes
 Space refers to the number of unit memory storage it requires.

 The input size, denoted by n, is one parameter , used to characterize the

occurrence of the problem
 The way in which the number of steps required by an algorithm varies with the
size of the problem it is solving.

Data Structures and Algorithms Analysis 16 June, 2021

Time Complexity of an Algorithm

 Time Complexity of an algorithm is time(or the number of steps) needed by

a program to complete its task (to execute a particular algorithm)
 The time taken for an algorithm is comprised of two times
 Compilation Time & Run Time

 Compilation time is the time taken to compile an algorithm.

 While compiling it checks for the syntax and semantic errors in the program & links it
with the standard libraries , your program has asked to

 Run Time: It is the time to execute the compiled program

 It is calculated only for executable statements and not for declaration statements
 Usually we consider, one unit for executing one instruction

Data Structures and Algorithms Analysis 17 June, 2021

Asymptotic Notation

 To choose the best algorithm, we need to check efficiency of each algorithm

 The efficiency can be measured by computing time complexity of each algorithm
 Asymptotic notation is a shorthand way to represent the time complexity
 There are three kinds of mathematical notation for this kind of analysis.
i. Big oh (O) Notation -worst case
ii. Omega (Ω) Notation-best case and
iii. Theta (Ө) Notation-average case

Data Structures and Algorithms Analysis 18 June, 2021

Asymptotic Notation…

 Time complexity is a function dependent from the value of n for f(n) and computed
after all instruction performed
 Time complexity of an algorithm is generally classified as three types.
i. Worst case [Big oh (O) notaion]:
 It is the longest time that an algorithm will use over all instances of size n for a given
problem to produce a desired result
ii. Average Case [Theta (Ө notation)]:
 It is the average time( or average space) that the algorithm will use over all instances of size
n for a given problem to produce a desired result
iii. Best Case [Omega (Ω notation)]: It is the shortest time ( or least space ) required to algorithm
for instances to produce a desired results

Data Structures and Algorithms Analysis 19 June, 2021

Asymptotic Notation: example

Time Comp..
g(x)= 5x
t(x)=x2
f(x)=x3

g(x)= Best-Omega (Ω)

t(x)=Average-Theta (Ө)
f(x)=Worst-Big (O)
for x>1

Data Structures and Algorithms Analysis 20 June, 2021

Space Complexity of an Algorithm

 It is the amount of memory consumed by the algorithm (both i/o) until it completes its
execution
 There are three different spaces considered for determining the amount of memory used
by the algorithm.
 Instruction Space: the space in memory occupied by the compiled version of the
program
 We consider this space as a constant space for any value of n.
 The instruction space is independent of the size of the problem

Data Structures and Algorithms Analysis 21 June, 2021

Space Complexity of an Algorithm…

 Data Space: is the space in memory , which used to hold the variables , data
structures, allocated memory and other data elements.
 Environment Space: is the space in memory used on the run time stack for each
function call

Data Structures and Algorithms Analysis 22 June, 2021

Space Complexity of an Algorithm: example

Space Complexity is not as big of an issue as time complexity because it can be reused, whereas time cannot

Data Structures and Algorithms Analysis 23 June, 2021

Asymptotic Notation

Algorism analysis does not give accurate value (time and space)
Conclusion it gives you the estimate values which can be used to study the behavior of
algorism

Data Structures and Algorithms Analysis 24 June, 2021

Thank You!

25
Select Business and Technology Collage
CSC 413:Theory of Algorisms
Data Structures and Algorithms Analysis
Lecturer :3
By: Samuel M.
Introduction: Data Structure (DS)

Definition:

 Data Structure is representation of the logical relationship existing

between individual elements of data

 In other words, it is a way of organizing all data items that considers

not only the elements stored but also their relationship to each other

 DS affects the design of both structural & functional aspects of a

program

Data Structures and Algorithms Analysis 27 June, 2021

Data Structure…

 Algorithm is a set of instruction written to carry out certain

tasks & the DS is the way of organizing the data with their
logical relationship engaged
 To develop a program of an algorithm, we should select an
appropriate data structure for that algorithm
 Therefore algorithm and its associated data structures from a
program

Data Structures and Algorithms Analysis 28 June, 2021

Classification of Data Structure
Data structure

Primitive DS Non-Primitive DS

Integer Float Character Pointer

 Primitive Data Structure Linear List Non-Linear List

 DS that are directly operated up on machine
instruction
 Non-Primitive Data Structure Graph Trees
 DS that are derived directly from primitive
Array Queue
data structure Link List Stack

Data Structures and Algorithms Analysis 29 June, 2021

Primitive Data Structure

 DS that are directly operated upon the machine-level

instructions are known as primitive data structures
Example:
 Integer
 Floating-point number
 Character constants
 String constants
 Pointers etc… are fall in this category

Data Structures and Algorithms Analysis 30 June, 2021

Primitive Data Structure…

 The most commonly used operation on primitive DS are

broadly categorized into:
 Create
 Selection
 Updating
 Destroy or Delete

Data Structures and Algorithms Analysis 31 June, 2021

Non-primitive Data Structure

 DS that are derived from the primitive DS are called Non-primitive DS

 It underline on organizing of a group of similar or various data items

array

Examples Linked list

queue
tree stack graph
Data Structures and Algorithms Analysis 32 June, 2021
Non-primitive Data Structure…

Linear Data structures:

 Are kind of DS that has homogeneous elements
 The DS in which elements are in a sequence and form a lining series
 These easy to implement, since the memory of the computer is also
organized in a linear fashion
Example
 Stack
 Queue
 Linked Lists

Data Structures and Algorithms Analysis 33 June, 2021

Non-primitive Data Structure…

Non-Linear Data structures:

 A Non-Linear Data structures is a data structure in which data item
is connected to several other data items
 Non-Linear data structure may show either a hierarchical
relationship or parent child relationship
 The data elements are not arranged in a sequential structure
 The different non-linear data structures are trees and graphs
Example
 Tree
 Graph

Data Structures and Algorithms Analysis 34 June, 2021

Non-primitive Data Structure…

 The most commonly used operation on non-primitive DS are

broadly categorized into:
 Traversal
 Insertion
 Selection
 Searching
 Sorting
 Merging
 Destroy or Delete

Data Structures and Algorithms Analysis 35 June, 2021

Comparatives

Different between them

 A primitive data structure is generally a basic structure that
is usually built into the language, such as an integer, a float
 A non-primitive data structure is built out of primitive data
structures linked together in meaningful ways, such as a or a
linked-list, binary search tree, AVL Tree, graph etc.

Data Structures and Algorithms Analysis 36 June, 2021

Data Structure

Data Structures and Algorithms Analysis 37 June, 2021

Description of various DS: Arrays

 An array is defined as a set of finite number of homogeneous elements or

same data items
 Array can contain one type of data only, either all integer, all float-point
number or all character
 Simply, declaration of array is as follows:
int arr[10]
 int specifies the data type or type of elements arrays stores.
 “arr” is the name of array

Data Structures and Algorithms Analysis 38 June, 2021

Arrays…

 The number specified inside the square brackets is the number of elements an array
can store, also called sized /length of array
 Following are some of the concepts to be remembered about arrays:
 The individual element of an array can be accessed by specifying name of the
array, following by index or subscript inside square brackets
 The first element of the array has index zero[0]
 The first element & last element will be specified as arr[0] & arr[9] respectively

Data Structures and Algorithms Analysis 39 June, 2021

Arrays…

 The elements of array will always be stored in the consecutive

(continues) memory location
 The number of elements that can be stored in an array, that is the size of
array or its length is given by (Upperbound-lowerbound)+1 equation
Example:
 For the above array (9-0)+1=10 it would be
 0 is the lower bound of array and 9 is the upper bound of array

Data Structures and Algorithms Analysis 40 June, 2021

Arrays…

 Array can always be read or written through loop

 For one-dimensional array it require one loop for reading & other for writing

 Example: Reading an array

for (i=0; i<=9; i++)
scanf(“%d”, &arr[i]);

 For example: Writing an array

for(i=0;i<=9;i++)
printf(“%d”,arr[i]);
Data Structures and Algorithms Analysis 41 June, 2021
Arrays…

 If we are reading or writing two-dimensional array it would require two

loops. And similarly the array of a N dimension would required N loops
 Some common operation performed on array are:
 Creation of an array
 Traversing an array
 Insertion of new element
 Deletion of required element
 Modification of an element
 Merging of arrays
Data Structures and Algorithms Analysis 42 June, 2021
Lists

 A lists (Linear linked list) can be defined as a collection of variable

number of data items
 Lists are the most commonly used non-primitive data structures.
 An element of list must contain at least two fields:
 One for storing data or information and
 other for storing address of next element.

Data Structures and Algorithms Analysis 43 June, 2021

Lists
Technically each such element is referred to as a node, therefore a list can be
defined as a collection of nodes as show bellow:

[Linear Liked List]

Head

AAA BBB CCC

Information field Pointer field44

Data Structures and Algorithms Analysis June, 2021
Lists…

 Types of linked lists:

 Single linked list
 Doubly linked list
 Single circular linked list
 Doubly circular linked list

Data Structures and Algorithms Analysis 45 June, 2021

Stack

 A stack is an ordered collection of elements like arrays, but it has a

special feature that:
 Deletion and insertion of elements can be done only from one end called the top
of the stack (TOP)

 Due to this it is called as last in first out type of data structure (LIFO)
 When an element is inserted into a stack or removed from the stack, its
base remains fixed where the top of stack changes

Data Structures and Algorithms Analysis 46 June, 2021

Stack

 Insertion of element into stack is called PUSH whereas deletion of element

from stack is called POP
 The bellow show figure how the operations take place on a stack:

PUSH POP

[STACK]

Data Structures and Algorithms Analysis 47 June, 2021

Stack

 The stack can be implemented into two ways:

 Using arrays (Static implementation)
 Using pointer (Dynamic implementation)

Data Structures and Algorithms Analysis 48 June, 2021

Queue

 Queue are first in first out type of data structure (i.e. FIFO)
 In a queue new elements are added to the queue from one end called REAR
end & the element are always removed from other end called the FRONT
end
 The people standing in a railway reservation row are an example of queue.

Data Structures and Algorithms Analysis 49 June, 2021

Queue…

Each new person comes and stands at the end of the row and person
getting their reservation confirmed get out of the row from the front end
The bellow show figure how the operations take place on a stack:

10 20 30 40 50
front rear

Data Structures and Algorithms Analysis 50 June, 2021

Queue

 The queue can be implemented into two ways:

 Using arrays (Static implementation)
 Using pointer (Dynamic implementation)

Data Structures and Algorithms Analysis 51 June, 2021

Trees

 A tree can be defined as finite set of data items (nodes).

 Tree is non-linear type of data structure in which data items are arranged or
stored in a sorted sequence.
 Tree represent the hierarchical relationship between various elements.

Data Structures and Algorithms Analysis 52 June, 2021

Trees
In trees:
 There is a special data item at the top of hierarchy called the Root of the tree
 The remaining data items are partitioned into number of mutually exclusive
subset, each of which is itself, a tree which is called the sub tree
 The tree always grows in length towards bottom in data structures, unlike
natural trees which grows upwards

Data Structures and Algorithms Analysis 53 June, 2021

Trees
 The tree structure organizes the data into branches, which related the
information.

A root

B C

D E F G

Data Structures and Algorithms Analysis 54 June, 2021

Graph

 Graph is a mathematical non-linear data structure capable of representing

many kind of physical structures.
 It has found application in Geography, Chemistry and Engineering sciences.
 Definition: A graph G(V,E) is a set of vertices V and a set of edges E.

Data Structures and Algorithms Analysis 55 June, 2021

Graph

 An edge connects a pair of vertices and many have weight such as length,
cost and another measuring instrument for according the graph.
 Vertices on the graph are shown as point or circles and edges are drawn as
arcs or line segment.

Data Structures and Algorithms Analysis 56 June, 2021

Graph

Example of graph:

v2 6 v5 v1 v3
10

v1 8 11
15
9 v2 v4
v3 v4

[a] Directed & Weighted [b] Undirected Graph

Graph

Data Structures and Algorithms Analysis 57 June, 2021

Graph
Types of Graphs:
 Directed graph
 Undirected graph
 Simple graph
 Weighted graph
 Connected graph
 Non-connected graph

Data Structures and Algorithms Analysis 58 June, 2021

Thank You!

59