SELECT COLLEGE
DEPARTMENT OF COMPUTER SCIENCE
Analysis of Algorithms CoSc 3092 E32
Chapter 1
Introduction
2
Course Outline
Chapter-1:
◼ Introduction to Design and Analysis of Algorithms
➢ What is problem and algorithm?
➢ Characteristics of an Algorithm and etc…
➢ How to analyze an Algorithm
➢ Asymptotic notations
Chapter-2:
◼ Design and analysis of Divide and Conquer
Algorithms
➢ Divide, Conquer and Combine
➢ Sorting Algorithms (Quick sort, Merge sort and Binary search)
3
Course Outline…
◼ Chapter-3:
◼ The Greedy Algorithms Method -
➢ Elements of Greedy Strategy
➢ Graph Minimum Spanning Tree (MST)
➢ Shortest Paths
➢ Huffman Codes
Chapter-4:
◼ Dynamic Programming
➢ Elements of Dynamic Programming
➢ Shortest Path - Dijkstra Algorithm
➢ Knapsack
➢ Depth First Search
4
Objective of the Course
◼ Understand foundations of algorithms and as well as
design and analysis of various algorithms
◼ Make use of skills to understand mathematical notations
in algorithms and their simple mathematical proofs
◼ How to analyze, validate/verify algorithms
5
Evaluation Criteria
▪ Class Test/Assignment : 20%
▪ Group Project : 30 %
▪ Final Exam: 50%
▪ Student with class absence more than 15% will
not seat for final exam
6
Feedback
▪ Your feedback from previous course
▪ -Ve feedbacks are encouraged
7
What is a problem?
◼ Definition
◼ A mapping/relation between a set of input instances
(domain) and an output set (range)
◼ Problem Specification
◼ Specify what a typical input instance is
◼ Specify what the output should be in terms of the
input instance
8
Types of Problems
There are typical problems that requires different solution
Example:
▪ Search: find X in the input satisfying property Y
▪ Structuring: Transform input X to satisfy property Y
▪ Construction: Build X satisfying Y
▪ Optimization: Find the best X satisfying property Y
▪ Decision: Does X satisfy Y?
▪ Adaptive: Maintain property Y over time.
9
Example of insertion sort
Example: Sorting
Input: A sequence of N numbers a1…an
Output: the permutation (reordering) of the input sequence
such that a1 a2 … an .
◼ Practice 1: write sorting steps of the following nemubers
Input: 8 2 4 9 3 6
Output: 2 3 4 6 8 9
8 2 4 9 3 6
L1.10
Example of insertion sort
8 2 4 9 3 6
L1.11
Example of insertion sort
8 2 4 9 3 6
2 8 4 9 3 6
L1.12
Example of insertion sort
8 2 4 9 3 6
2 8 4 9 3 6
L1.13
Example of insertion sort
8 2 4 9 3 6
2 8 4 9 3 6
2 4 8 9 3 6
L1.14
Example of insertion sort
8 2 4 9 3 6
2 8 4 9 3 6
2 4 8 9 3 6
L1.15
Example of insertion sort
8 2 4 9 3 6
2 8 4 9 3 6
2 4 8 9 3 6
2 4 8 9 3 6
L1.16
Example of insertion sort
8 2 4 9 3 6
2 8 4 9 3 6
2 4 8 9 3 6
2 4 8 9 3 6
L1.17
Example of insertion sort
8 2 4 9 3 6
2 8 4 9 3 6
2 4 8 9 3 6
2 4 8 9 3 6
2 3 4 8 9 6
L1.18
Example of insertion sort
8 2 4 9 3 6
2 8 4 9 3 6
2 4 8 9 3 6
2 4 8 9 3 6
2 3 4 8 9 6
L1.19
Example of insertion sort
8 2 4 9 3 6
2 8 4 9 3 6
2 4 8 9 3 6
2 4 8 9 3 6
2 3 4 8 9 6
2 3 4 6 8 9 done
L1.20
Design and Analysis of Algorithms
▪ An algorithm is a sequence of unambiguous
instructions for solving a problem, i.e., for obtaining a
required output for any legitimate input in a finite
amount of time.
▪ Finite, sequenced set of steps to complete one task
Example: Making tea, step for phone calling, coding instructions
▪ Mapping is algorithm and actual construction is
program
▪ For better construction better mapping is important
21
Algorithm vs Program
Difference between Algorithm and Program are:
No Algorithm Program
1 Algorithm is finite Program need not to be finite
2 It is written using It is written using a specific
natural language or programming language
algorithmic language
3 It is design phase Programing is implementation
phase
4 Analyzed Tested
• Analysis: predict the cost of an algorithm in terms of
resources and performance
• Design: design algorithms which minimize the cost
22
What is an algorithm & problem solving ?
Problem
Algorithm
“computer” Output
Input
▪ Algorithms are the ideas behind computer programs
▪ Used to solve a general, specified problem.
23
Fundamentals of Algorithm & Problem Solving
24
Problem Solving Techniques
1. Understand the problem or Review the Specifications.
2. Plan the logic
3. a) (Informal Design)
i. List major tasks
ii. List subtasks, sub-subtasks & so on
b) (Formal Design)
i. Create formal design from task lists
ii. Desk check design
4. Writing an algorithm
5. Flowcharting
6. Coding
7. Translate the program into machine language
9. Test the program
i. If necessary debug the program
10. Documentation
11. Put the program into production. If necessary maintain the program.
25
Properties of algorithms
There are two desired properties of algorithms
◼ Correctness and Efficiency
◼ Does the input/output relation match algorithm requirement?
◼ Always provides correct output when presented with legal input
Example: Classical Multiplication and a la russe algorithm
26
Properties of algorithms
▪ All algorithms are produces the correct answer
▪ Are all efficient?
27
Properties of algorithms
Example: 2
Find the possible Algorithm: Nearest neighbor
28
Properties of algorithms
Example: 3
Find the possible Algorithm: Nearest neighbor
29
Properties of algorithms
Which algorithm is better?
30
Properties of algorithms
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.
31
Running Time
◼ Most algorithms transform input objects best case
average case
into output objects.
worst case
120
100
◼ The running time of an algorithm
Running Time
80
typically grows with the input size. 60
40
◼ Average case time is often difficult to 20
determine. 0
1000 2000 3000 4000
Input Size
◼ We focus on the worst case running time.
◼ Easier to analyze
◼ Crucial to applications such as games, finance
and robotics
32
Basic Issues Related to Algorithms
◼ How to design algorithms
◼ How to express algorithms
◼ Proving correctness
◼ Efficiency (or complexity) analysis
◼ Theoretical analysis
◼ Empirical analysis
◼ Optimality
33
Algorithm Design Strategies
◼ Brute force ◼ Greedy approach
◼ Divide and conquer ◼ Dynamic programming
◼ Decrease and conquer ◼ Backtracking and branch-
◼ Transform and conquer and-bound
◼ Space and time tradeoffs
How good is the algorithm?
◼ Correctness
◼ Time efficiency
◼ Space efficiency
Thank You
End of Chapter-One