Lecture - 1
Design and Analysis of
Algorithms
The “design” pertain to
◦ The description of algorithm at an
abstract level by means of a pseudo
language, and
◦ Proof of correctness that is, the
algorithm solves the given problem
in all cases
The “analysis” deals with
performance evaluation
(complexity analysis)
Algorithm
An algorithm is a set of rules for carrying out
calculation either by hand or on a machine.
An algorithm is a finite step-by-step procedure
to achieve a required result.
An algorithm is a sequence of computational
steps that transform the input into the output.
An algorithm is a sequence of operations
performed on data that have to be organized in
data structures.
An algorithm is an abstraction of a program to
be executed on a physical machine (model of
Computation).
An algorithm is a sequence of computational
steps that transform the input into the output
Algorithm
An algorithm is a sequence of
computational steps that
transform the input into the
output.
Example:
◦ Sorting Problem
◦ Input: A sequence of n numbers
◦ Output: A permutation (reordering)
of the input sequence
Algorithm
Problem
Algorithm
Input Output
Important Problem Types
Sorting
Searching
StringProcessing
Graph Problems
Combinatorial Problems
Geometric Problems
Numerical Problems
Sorting
The sorting problem asks us to
rearrange the items of a given list in
ascending order.
Why would we want a sorted list?
It makes many questions about the list
easier to answer.
It is used as an auxiliary step in several
important algorithms in other areas,
e.g., greedy algorithms, geometric
algorithms.
There is no sorting algorithm that would
be the best solution in all situations.
Searching
The Searching Problem deals
with finding a given value, called
a search key, in a given set.
There is no single algorithm that
fits all situations best.
String Processing
A string is a sequence of characters
from an alphabet.
Strings of particular interest are
◦ Text strings
◦ Bit strings
◦ Gene sequences
String Matching I.e. searching of a
given word in a text get a special
attention from researchers.
Sorting
Two special properties of sorting
algorithms
◦ Stable
◦ In place
A sorting algorithm is called stable it
preserves the relative order of any two
equal elements in its input.
An algorithm is said to be in place if it
dos not require extra memory, except
possibly, for a few memory units.
Graph Problems
A graph is a collection of points called
vertices, some of which are
connected by line segments called
edges.
Graphs can be used for modeling a
wide variety of real-life applications,
like
◦ Transportation and communication
networks
◦ Project Scheduling
◦ Games
Graph Problems
Basic graph algorithms include
◦ Graph traversal algorithms
◦ Shortest path algorithms
◦ Topological sorting for graphs with directed
edges
Some graph problems are
computationally very hard like
◦ Traveling salesperson problem
◦ Graph coloring problem
Combinatorial Problems
These are problems that ask (explicitly
or implicitly) to find a combinatorial
object-such as
◦ A permutation
◦ A combination
◦ Or a subset
That satisfies certain constraints and
has some desired property.
E.g.
◦ Traveling Salesperson problem
◦ Graph Coloring problem
Fundamental Data Structures
Review (Linear Data Structures)
Arrays
◦ Sequence of n items of same data
type
◦ Stored contiguously in computer
memory
◦ Each item is made accessible by
specifying the value of the array’s
index.
Each and every array element
can be accessed in the same
constant amount of time.
Fundamental Data Structures
Review (Linear Data Structures)
Linked List
◦ Sequence of zero or more elements called
nodes.
◦ Each node contains
Some data and
One or more links called pointers to other
nodes of the linked list.
Singly Linked List
◦ a node has a pointer only to its successor
node
Doubly Linked List
◦ a node has a pointer to both its successor
and its predecessor
Fundamental Data Structures
Review (Linear Data Structures)
List
◦ A finite sequence of data items
◦ Implement by using
Arrays or
Linked lists
Special kinds of lists
◦ Stack &
◦ Queue
Fundamental Data Structures
Review (Linear Data Structures)
Stack
◦ Only one end is used both for
insertion and deletion
◦ Operates in LIFO fashion
Queue
◦ One end is used for insertion and
other end is used for deletion
◦ Operates in FIFO fashion
Algorithms Analysis Framework
Introduction
How to analyze an algorithm?
Predicting the resources that the
algorithm requires.
◦ Memory
◦ Communications Bandwidth
◦ Logic gates etc
◦ Computational time
Algorithms Analysis Framework
Introduction
Two parameters of measuring
algorithm’s efficiency
1. Time Efficiency
How fast an algorithm in question
runs
2. Space Efficiency
It deals with the extra space the
algorithm requires
Algorithms Analysis Framework
Introduction
Important thing before
analysis
◦ Model of the machine upon which
the algorithms is executed.
◦ Random Access Machine (RAM)
(Sequential)
