[go: up one dir, main page]
Scribd
Upload
8 views25 pages

1 Lecture 1

The course focuses on the design and analysis of modern algorithms, covering their accuracy, efficiency, and various techniques for solving real-world problems. An algorithm is defined as a finite, step-by-step procedure that transforms input into output, with properties such as generality, finiteness, and efficiency. The document also discusses algorithm analysis, including running time, problem-solving processes, and important designing techniques.

Uploaded by

Explore with GS
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
8 views25 pages

1 Lecture 1

The course focuses on the design and analysis of modern algorithms, covering their accuracy, efficiency, and various techniques for solving real-world problems. An algorithm is defined as a finite, step-by-step procedure that transforms input into output, with properties such as generality, finiteness, and efficiency. The document also discusses algorithm analysis, including running time, problem-solving processes, and important designing techniques.

Uploaded by

Explore with GS
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 25

Advanced Analysis Of

Algorithm

Lecture 1
Dr. Sadia Basar
Objective of this Course
• Design and Analysis of modern algorithms
• Different varients
• Accuracy
• Efficiency
• Comparing efficiencies
• Motivation thinking new algorithms
• Advanced designing techniques
• Real world problems will be taken as examples
What is an 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).
What is an Algorithm?

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.
What is an Algorithm?

Problem

algorithm

input “compute output


r”
Algorithm
• What is an algorithm.
• Problem, problem instance and solution
• Sort list of n numbers in ascending order
• Determine whether x is in list of n numbers
• Algorithm is a general solution which solves
all instances of a problem.
Algorithm

Input Algorithm Output

An algorithm is a step-by-step procedure for


solving a problem in a finite amount of time.
One Problem, Many Algorithms
Problem: Defines the desired input/output
relationship in general terms.
Algorithm: Specifies a computational
procedure to achieve this input/output
relationship.
It means a single problem can have multiple
algorithmic approaches, each with different
efficiencies, complexities, and optimizations.
One Problem, Many Algorithms
Example:
• Sorting a sequence of numbers in non-
decreasing order.
Algorithms:
• Various sorting algorithms can be used, such
as: Merge Sort, Quick Sort, Heap Sort
What properties an algorithm should have ?

• Generality

• Finiteness

• Non-ambiguity

• Efficiency
Generality

• The algorithm applies to all instances of input data


not only for particular instances

Example:
Let’s consider the problem of increasingly sorting a
sequence of values.

For instance:
(2,1,4,3,5) (1,2,3,4,5)
input data result
Generality (cont’d)
Method:
Description:

Step 1: 2 1 4 3 5 - compare the first two


elements:
Step 2: 1 2 4 3 5 if there are not in the desired
order swap them
Step 3: 1 2 4 3 5 - compare the second and the
third element and do the same
…..
Step 4: 1 2 3 4 5
- continue until the last two
elements were compared
The sequence has been ordered
Finiteness

• An algorithm have to terminate, i.e. to stop after a finite


number of steps

Example
Step1: Assign 1 to x;
Step2: Increase x by 2;
Step3: If x=10 then STOP;
else GO TO Step 2

How does this algorithm work ?


Finiteness (cont’d)

How does this algorithm work and what does it produce?


Step1: Assign 1 to x;
Step2: Increase x by 2;
x=1
Step3: If x=10
then STOP; x=3 x=5 x=7 x=9 x=11
else Print x; GO TO Step 2;

The algorithm generates odd numbers but it never stops !


Finiteness (cont’d)

Step1: Assign 1 to x;
Step2: Increase x by 2;
Step3: If x>=10
then STOP;
else Print x; GO TO Step 2
Efficiency
• The need to design efficient algorithms
• What is efficiency?
• Example
• Sequential search Vs. Binary Search
Algorithm Analysis
• How to analyze an algorithm?
• Predicting the resources that the algorithm requires.

• Machine
• Operating system
• Programming languages
• Compiler, etc.

This means that computational models and algorithm analysis should


not depend on specific hardware, software, or programming
environments. Instead, they focus on abstract principles that remain
valid across different implementations.
Algorithm Analysis
• Important thing before analysis

• Model of the machine upon which the algorithms


is executed.

• Random Access Machine (RAM) (Sequential)


• Running Time: No. of primitive operations
or “steps executed”.
Running Time

• Most algorithms transform best case


input objects into output average case
objects. worst case
120
• The running time of an
100
algorithm typically grows with

Running Time
the input size. 80

• Average case time is often 60

difficult to determine. 40

• We focus on the worst case 20


running time. 0
• Easier to analyze 1000 2000 3000 4000
Input Size
• Crucial to applications such as
games, finance and robotics
Limitations of Experiments

• It is necessary to implement the algorithm,


which may be difficult
• Results may not be indicative of the running
time on other inputs not included in the
experiment.
• In order to compare two algorithms, the same
hardware and software environments must be
used
Problem Solving Process

• Problem
• Strategy
• Algorithm
• Input
• Output
• Steps
Problem Solving Process

• Analysis
• Correctness
• Time & Space
• Optimality
• Implementation
• Verification
Algorithm Analysis
• Running Time
• We need a measure that is independent of
computer, programming language and the
programmer.
• Concept of basic operation
• In sorting comparison is a basic operation.
Algorithm Analysis
• What are the constructs / Keywords.
• Time for each construct
• Total Time
• Total time as a function of input size
Important Designing Techniques
• Decrease-and-Conquer
• Reduces the problem size step by step.
• Example: Binary search, where the search space is halved at
each step.
• Transform-and-Conquer
• Modifies the problem to make it easier before solving.
• Example: Changing data representation or preprocessing for
optimization.
• Space and Time Tradeoffs
• Uses additional memory to speed up computations.
• Example: Caching, dynamic programming, or lookup tables.

You might also like