Course details

 LTP – 3 0 0 [Three lectures/week]

 Text Book
• INTRODUCTION TO THE DESIGN
AND ANALYSIS OF ALGORITHMS
– ANANY LEVITIN,
PEARSON EDUCATION

A. rights
Copyright © 2007 Pearson Addison-Wesley. All Levitinreserved.
“Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
 Detail of Academic Tasks

 AT1: Test1 Lecture #11(Before MTE)

 AT2: Test2 Lecture #19(Before MTE)

 AT3: Test3 Lecture #33(After MTE)

A. rights
Copyright © 2007 Pearson Addison-Wesley. All Levitinreserved.
“Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Why we need to study this
course ?

A. rights
Copyright © 2007 Pearson Addison-Wesley. All Levitinreserved.
“Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Why are we learning Design and analysis of
algorithms?
 Algorithms are used in almost every program or software
system.
 Once we design an algorithm we need to know how well it
performs on any input.
 In particular we would like to know whether there are
better algorithms for the problem, An answer to this first
demands a way to analyze an algorithm in a machine-
independent way.
 Some Specific design techniques are essential ingredients of
many software applications.

A. rights
Copyright © 2007 Pearson Addison-Wesley. All Levitinreserved.
“Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
The course contents CSE408
 UNIT I - Foundations of algorithm

 UNIT II - String matching algorithms and computational

geometry

 UNIT III - Divide and conquer and ordered statists

 UNIT IV - Dynamic programming and greedy techniques

 UNIT V - Backtracking and approximation algorithms

 UNIT VI - Number-theoretic algorithms and complexity classes

A. rights
Copyright © 2007 Pearson Addison-Wesley. All Levitinreserved.
“Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
UNIT I

Foundations of algorithm
Basic DS
Analysis and growth

A. rights
Copyright © 2007 Pearson Addison-Wesley. All Levitinreserved.
“Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
UNIT II
String matching algorithms and
computational geometry

A. rights
Copyright © 2007 Pearson Addison-Wesley. All Levitinreserved.
“Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
UNIT III

Divide and conquer and ordered statists

A. rights
Copyright © 2007 Pearson Addison-Wesley. All Levitinreserved.
“Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
 UNIT IV

Dynamic programming and greedy technique

Dynamic programming(Knap sack) Greedy technique

A. rights
Copyright © 2007 Pearson Addison-Wesley. All Levitinreserved.
“Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 1
Algorithm

• Instruction:- Set of operations

Problem for Swapping 2 Numbers
Fundamentals of algorithmic
problem solving
•Understanding the problem
•Ascertaining the capabilities of a computational device.
•Choosing between exact and approximate problem solving.
•Deciding an appropriate Data Structure
•Algorithm design techniques.
•Methods of specifying an algorithm.
•Proving an algorithms correctness
•Analyzing an algorithm.
•Coding an algorithm
Step 1- Understanding the problem
• Understand the given problem completely.
• Read the problem description carefully
• Ask doubts about the problem
• Do few examples
• Think about special cases like boundary value
• Know about the already known algorithms for solving that
problem
• Clear about the input to an algorithm.

16
 Step 2- Ascertaining the Capabilities of a
computational device
• Sequential Algorithms: Instructions are executed one after another and
one operation at a time. Algorithms designed to be executed on such
machine are called sequential algorithms
• Parallel Algorithms: Modern computers that can execute instructions in
parallel. Algorithms designed to be executed on such machine are called
parallel algorithms
Step 3- Choosing between exact and
approximate problem solving
• Exact Algorithm: Solving problem exactly
• Approx. Algm. : Solving problem approximately
• Why Approx. Algm.?
• Some problems cannot be solved exactly
• Solving problem exactly can be unacceptably slow because of the
problem complexity.
Step 4- Deciding on appropriate Data
Structures
• A Data structure is defined as a particular scheme of organizing
related data items.
• Decide on the suitable data structure
Step 5- Algorithm Design techniques

 An algorithm design technique is a general approach to solve

problems algorithmically.
 The various design techniques are:
 Brute force
 Divide and conquer
 Greedy approach
 Dynamic programming
 Backtracking
Step 6- Method of specifying an algorithm

• There are 3 methods:

• Natural language
• Easy but ambiguous
• Pseudo code
• Mixture of programming language and natural language
• Flow chart
• It is pictorial representation of the algorithm.
• Here symbols are used.
Step 7- Proving an algorithm’s correctness

 Correctness: Prove that the algo. Yields the required result for
every legitimate input in a finite amount of time.
 A common technique for proving correctness is to use
mathematical induction
 In order to show the alg. Is incorrect, we have to take just one
instance of its input for which the algm. Fails.
 If a algo. is found to be incorrect, then reconsider one or more
those decisions
 For approx. algo. We should show that the error produced by the
algo does not exceed the predefined limit.
Step 8- Analyzing an algorithm
 Analyze the following qualities of the algorithm
 Efficiency:
◦ Time efficiency and Space efficiency
 Simplicity
◦ Simple algorithms mean easy to understand and easy to program.
 Generality
◦ Design an algm. for a problem in more general terms. In some cases, designing
more general algm. Is unnecessary or difficult.
◦ Optimality
 The algorithm should produce optimal results.
Step 9- Coding an algorithm

• Algorithms are designed to be implemented as computer programs.

• Use code tuning technique. For eg., replacing costlier multiplication
operation with cheaper addition operation.
Fundamental data structures

• list  graph
• array  tree and binary tree
• linked list  set and dictionary
• string
• stack
• queue
• priority queue/heap

1-25
TYPES OF DATA STRUCTURES
 Linear Data Structures

• Arrays
 Arrays
• A sequence of n items of the same data
 fixed length (need preliminary
type that are stored contiguously in reservation of memory)
computer memory and made accessible  contiguous memory locations
by specifying a value of the array’s index.  direct access
• Linked List  Insert/delete
• A sequence of zero or more nodes each 
containing two kinds of information: Linked Lists
some data and one or more links called  dynamic length
pointers to other nodes of the linked list.  arbitrary memory locations
• Singly linked list (next pointer)  access by following links
• Doubly linked list (next + previous
pointers)
 Insert/delete

a1 a2 … an .
1-27
 Stacks and Queues
• Stacks
• A stack of plates
• insertion/deletion can be done only at the top.
• LIFO
• Two operations (push and pop)
• Queues
• A queue of customers waiting for services
• Insertion/enqueue from the rear and deletion/dequeue from the
front.
• FIFO
• Two operations (enqueue and dequeue)

1-28
Priority Queue and Heap


Priority queues (implemented using heaps)
A data structure for maintaining a set of elements, each associated
with a key/priority, with the following operations
 Finding the element with the highest priority
 Deleting the element with the highest priority
 Inserting a new element
 Scheduling jobs on a shared computer
9
6 8
5 2 3

9 6 8 5 2 3
1-29
Graphs
• Formal definition
• A graph G = <V, E> is defined by a pair of two sets: a finite set
V of items called vertices and a set E of vertex pairs called
edges.
• Undirected and directed graphs (digraphs).
• maximum number of edges in an undirected graph with |V| vertices
• Complete graphs
• A graph with every pair of its vertices connected by an edge
is called complete, K|V|

1-30
Graph Representation
• Adjacency matrix
• n x n boolean matrix if |V| is n.
• The element on the ith row and jth column is 1 if there’s an edge from ith
vertex to the jth vertex; otherwise 0.
• The adjacency matrix of an undirected graph is symmetric.
• Adjacency linked lists
• A collection of linked lists, one for each vertex, that contain all the vertices
adjacent to the list’s vertex.
• Which data structure would you use if the graph is a 100-node star
shape?

0111 2 3 4
0001 4
0001 4
0000
1-31
 Weighted Graphs
• Weighted graphs
• Graphs or digraphs with numbers assigned to the edges.
3
1 2
6 5 7
- A dense graph is a graph in which
3
the
4
number of edges is close to the
maximal number of edges. The9opposite, a graph with only a few edges,
is a sparse graph.
8

1-32
 Graph Properties -- Paths and Connectivity

• Paths
• A path from vertex u to v of a graph G is defined as a sequence of adjacent
(connected by an edge) vertices that starts with u and ends with v.
• Simple paths: All edges of a path are distinct.
• Path lengths: the number of edges, or the number of vertices – 1.
• Connected graphs
• A graph is said to be connected if for every pair of its vertices u and v there is a
path from u to v.
• Connected component
• The maximum connected subgraph of a given graph.

1-33
Graph Properties -- Acyclicity

• Cycle
• A simple path of a positive length that starts and ends a
the same vertex.
• Acyclic graph
• A graph without cycles
• DAG (Directed Acyclic Graph)

1 2

3 4

1-34
Trees
• Trees
• A tree (or free tree) is a connected acyclic graph.
• Forest: a graph that has no cycles but is not necessarily connected.
• Properties of trees
- For every two vertices in a tree there always exists exactly one simple path from
one of these vertices to the other.
• Rooted trees: The above property makes it possible to select an
arbitrary vertex in a free tree and consider it as the root of the so
called rooted tree.
• Levels in a rooted tree.

3
1 3 5
4 1 5
 |E| = |V| - 1 2 4 2
1-35
Rooted Trees (I)
• Ancestors
• For any vertex v in a tree T, all the vertices on the simple path from the
root to that vertex are called ancestors.
• Descendants
• All the vertices for which a vertex v is an ancestor are said to be
descendants of v.
• Parent, child and siblings
• If (u, v) is the last edge of the simple path from the root to vertex v, u is
said to be the parent of v and v is called a child of u.
• Vertices that have the same parent are called siblings.
• Leaves
• A vertex without children is called a leaf.
• Subtree
• A vertex v with all its descendants is called the subtree of T rooted at v.

1-36
 Rooted Trees (II)

• Depth of a vertex
• The length of the simple path from the root to the vertex.
• Height of a tree
• The length of the longest simple path from the root to a leaf.

h=2
3

4 1 5

1-37
Ordered Trees
• Ordered trees
• An ordered tree is a rooted tree in which all the children of each vertex are
ordered.
• Binary trees
• A binary tree is an ordered tree in which every vertex has no more than two
children and each children is designated s either a left child or a right child of its
parent.
• Binary search trees
• Each vertex is assigned a number.
• A number assigned to each parental vertex is larger than all the numbers in its left
subtree and smaller than all the numbers in its right subtree.
• log2n  h  n – 1, where h is the height of a binary tree and n the size.

9 6
6 8 3 9
5 2 3 2 5 8
1-38