Analysis and Design of Algorithms
By
Manju Choudhary
1
Course Information
Textbook
Introduction to Algorithms 5nd ,Cormen,
Leiserson, Rivest and Stein, The MIT Press, 2001.
Others
Introduction to Design & Analysis Computer Algorithm 3rd, Sara
Baase, Allen Van Gelder, Adison-Wesley, 2000.
Fundamental of Computer Algorithms, Ellis Horowitz, Sartaj
Sahni, Sanguthevar Rajasekaran, 2010.
LMS: Advanced Algorithms by Manju
Enrollment key : csl502
2
Grading Policy
Total Marks: 200
Theory
65%----130 marks
Minor 1: 20 marks (Paper would be of 40 marks)
Minor 2: 20 marks (paper would be of 40 marks)
Internals : 25 marks (includes: online test, assignment, class test)
Major Exam: 65 marks (paper would be of 65 marks)
Practical
35%----- 70 marks
Lab Assessment will be through out the semester.
3
Objective of This Course
Major objective of this course is:
Basic Framework (RAM model)
To design and analyze algorithms
Design fast algorithms
Analysis of designed algorithms
Comparing Algorithms (i.e. their efficiencies)
Techniques for fast algorithms
Greedy , Dynamic, Backtracking, Branch & Bound
NP-Completeness Theory
Approximation theory
4
Approach:
Analytical.
Build a mathematical (computational) model of a computer.
Study properties of algorithms on this model.
REASON about algorithm.
Prove facts about Time taken.
5
Prerequisites:
Following background is necessity of this course:
Programming.
Data structures.
Discrete Mathematics
(Sets, Functions, Vectors, Matrix, Linear Inequalities, Linear
Equations)
6
WhaWhat is Algorithm?t is Algorithm?
A computer algorithm is a detailed set of instructions when
executed sequentially then solve a problem
Market
ITM
Market
Hospital
Playground
Gym
WhaWhat is Algorithm?t is Algorithm?
Market ITM
Hospital
Playground Gym
Algorithm:
1. Go straight.
2. Take left turn.
3. you will reach ITM.
WhaWhat is Algorithm?t is Algorithm?
1. Go straight
ITM
ITM
Market
Hospital
Playground
Gym
WhaWhat is Algorithm?t is Algorithm?
ITM
Market
Market
Hospital
Playground
Gym
aWhat is Algorithm?
2. Take Left turn
wrong
Market ITM
Market
Hospital
Playground
Gym
What is Algorithm?
2. Take left turn
WRONG
ITM
Market
Market
Hospital
Playground
Gym
WhaWhat is Algorithm?t is Algorithm?
2.Take left turn
ITM
Market
Market
Hospital
Playground
Gym
What is Algorithm??
A computer algorithm is a detailed set of instructions
when executed sequentially then solve a problem
WRONG
An Algorithm is a sequence of unambiguous
instructions for solving a problem in a finite amount of
time.
Algorithm:
1. Go straight.
2. Take 3 rd left turn. (no ambiguity)
3. you will reach ITM.
14
Characteristics of good Algorithm
Definiteness of each statement (i.e clarity)
Effectiveness (i.e. doability on a computer)
Termination
An algorithm has zero or more input and single
output
15
Popular Algorithms, Factors of Dependence
Most basic and popular algorithms are
Sorting algorithms
Searching algorithms
Which algorithm is best?
Mainly, it depends upon various factors, for example in
case of sorting
The number of items to be sorted
The extent to which the items are already sorted
Possible restrictions on the item values
The kind of storage device to be used etc.
16
Analysis and Design of Algorithm
17
Design of Algorithm
1. Devising the algorithm (i.e. method)
2. Expressing the Algorithm (middle level language)
3. Validating the Algorithm (i.e. Proof of correctness)
18
What is Algorithm Analysis
?
1. Estimate the time/space required for an algo
rithm.
2. Techniques that drastically reduce the runni
ng time of an algorithm.
pp 19
Importance of Analyze
Algorithm
Need to recognize limitations of various algorithms
for solving a problem.
Need to understand relationship between problem
size and running time.
When is a running program not good enough?
Need to learn how to analyze an algorithm's runni
ng time without coding it.
Need to learn techniques for writing more efficient
code.
20
em?
Correctness
Does the input/output relation match algorithm r
equirement?
Amount of work done ( time complexity)
Basic operations to do task
Amount of space used ( space complexity)
Memory used
Simplicity, clarity
Verification and implementation.
Optimality
Is it impossible to do better?
21
Complexity
The complexity of an algorithm is simply the
amount of work the algorithm performs to co
mplete its task.
Time Complexity
# of operations as a function of input size.
Space Complexity
# of memory words needed by the algorithm.
To compute Time or Space complexity, we
need a common computational model (computer
system with detailed specification).
22
Expression of Algorithm: Pseudocode
Pseudocode is an informal high-level description of
the algorithm.
It is intended for human reading rather than machine
reading.
A program in pseudocode is not an executable program.
Ex.FINDING LARGEST NUMBER
INPUT: unsorted array ‘A[n]’of n numbers
OUTPUT: largest number
----------------------------------------------------------
1 large ← A[j]
2 for j ← 2 to length[A]
3 if large < A[j]
4 large ← A[j] 23
5 end
Computational Model
24
Computational Model
Basic Idea:
It is a mathematical model of a computer.
Mentally execute algorithm on model and
evaluate time taken.
What is the time required on the model for
every operation that an algorithm might
perform.
What should be the input data.
25
Computational Model
Machine-independent algorithm design depends upon
a hypothetical computer called the Computational
model.
In the field of runtime analysis of algorithms, it is
common to specify a computational model in terms
of primitive operations allowed which have unit cost,
or simply unit-cost operations.
Ex:: External Memory Model (EMM), Random
Access Machine (RAM).
26
Computational Model: EMM
In External Memory Model, the primary concern is
the number of disk accesses. Given the rather high
cost of a disk access compared to any CPU
operation, this model actually ignores all other
costs and counts only the number of disk accesses.
27
Computational Model :RAM
A commonly used example is the Random Access
Machine(RAM), which has unit cost for read and write
access to all of its memory cells.
In this course will consider only Random Access Machine
model where every primitive operation (all arithmetic
operations) has unit cost.
28
Computational Model :RAM
Under this model of computation, we are confronted with
a computer where:
Each ``simple'' operation (+, *, -, =, if, call) takes exactly 1
time step.
Loops and subroutines are not considered simple
operations. Instead, they are the composition of many
single-step operations. The time to run through a loop or
execute a subprogram depends upon the number of loop
iterations or the specific nature of the subprogram.
29
Example Of Algorithm
30
Example: What is an Algorithm?
Problem: Input is a sequence of integers stored in an
array.
Output the minimum.
INPUT
OUTPUT
25, 90, 53, 23, 11, 34
Algorithm 11
31
Example Algorithm A
Problem: The input is a sequence of integers stored in array.
Output the minimum.
Algorithm A
32
Example Algorithm B
This algorithm uses two temporary arrays.
1. copy the input a to array t1;
assign n size of input;
2. While n > 1
For i 1 to n /2
t2[ i ] min (t1 [ 2*i ], t1[ 2*i + 1] );
copy array t2 to t1;
n n/2;
33 3. Output t2[1];
Visualize Algorithm B
34 6 5 9 20 8 11 7
Loop 1
6 5 8 7
Loop 2
5 7
Loop 3
5
34
Example Algorithm C
Sort the input in increasing order.
Return the first element of the sorted data.
34 6 5 9 20 8 11 7
Sorting
5 6 7 8 9 11 20 34
35
Example Algorithm D
For each element, test whether it is the minimum.
36
Which algorithm is better?
The algorithms are correct, but
which is the best?
Measure the running time (number
of operations needed).
Measure the amount of memory
used.
Note that the running time of the
algorithms increase as the size of the
input increases.
37
What do we need?
Correctness: Whether the algorithm computes
the correct solution for all instances
Efficiency: Resources needed by the algorithm
1. Time: Number of steps.
2. Space: amount of memory used.
Measurement “model”: Worst case, Average case
and Best case.
38
Time vs. Size of Input
Measurement
parameterized by the size
of the input. Td(n)
4
Tc (n)
The algorihtms A,B,C are
Running time
implemented and run in a
(second)
PC. 2 Tb (n)
Algorithms D is
Ta (n)
implemented and run in a
supercomputer.
0
Let Tk( n ) be the amount 500 1000
of time taken by the Input Size
39Algorithm
