Scribd
Upload
73 views11 pages

Review of Algorithm Analysis

This document provides an overview of algorithm analysis and design. It discusses what an algorithm is, how algorithms are measured for efficiency in terms of time and space complexity, and how to analyze divide-and-conquer algorithms using recurrence relations. Key points covered include the use of asymptotic notations like O(), o(), Θ(), Ω(), and ω() to describe an algorithm's running time, and how divide-and-conquer algorithms can be coded recursively and their running times calculated from recurrence equations.

Uploaded by

Farrukh Abbas
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
73 views11 pages

Review of Algorithm Analysis

This document provides an overview of algorithm analysis and design. It discusses what an algorithm is, how algorithms are measured for efficiency in terms of time and space complexity, and how to analyze divide-and-conquer algorithms using recurrence relations. Key points covered include the use of asymptotic notations like O(), o(), Θ(), Ω(), and ω() to describe an algorithm's running time, and how divide-and-conquer algorithms can be coded recursively and their running times calculated from recurrence equations.

Uploaded by

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

Design and Analysis of Algorithms

Review of algorithm analysis

Haidong Xue (GSU)


Presented By
Dr M A Tahir
Software Engineering Database Data mining

Applications
Network Wireless Network
Algorithms
Software Web programming Security
Data Structure
Signal processing Graphics
Computer

Programming Language AI Robotics

Compiler Principles of Compilers Automata

Machine Operating System


Language
Computer Architecture

Computer Composition
Hardware
Microchip Interfaces

VLSI Design
Knowledge tree
Algorithms

Algorithms for Classic data


Analysis Design
classic problems structure

Shortest Matrix
Sorting …
Asymptotic Probabilisti path multiplication
notations c analysis Heap,
Hashing,
Binary
Divide & Dynamic Search
Greedy
Conquer Programming Tree,
RBT,
O(), ….
o(), Quicksort, … … …
(), … … … Heapsort,
(), Mergesort,
() …

… … … … … … … … … … … … …
Review of algorithm analysis
• What is an algorithm?
• What are we interested in an algorithm?
• How to measure an algorithm?
• How to code divide-and-conquer algorithm?
– Recursion
• How to calculate the running time of divide-
and-conquer algorithm?
– Recurrence equation
What is an algorithm?
• “a sequence of operations” (informal)
• E.g.
– The algorithm to walk
– The algorithm to cook instant noodle
– The algorithm to sort N integers
What is an algorithm?
• Algorithm: walk to a destination
while (have not arrived at the destination)
{
put the back foot in front of the front foot;
}
What is an algorithm?
• Algorithm: cook a cup of instant noodles
1. Pull back lid to the dotted line.
2. Fill the cup to the inside line with boiling water
from a kettle or from the microwave
3. Close lid and let stand for 3 minutes.
4. Stir well and add a pinch of salt and pepper to
taste.
What are we interested in an algorithm?

• Correctness
• Efficiency
– Time complexity – measure the execution time?
– Space complexity
How to measure an algorithm?
• The number of key operations
• The number of space units needed
• What if the input is uncertain?
How to measure an algorithm?
• E.g. Search a book in a box of books
– Key operation: check the title of a book
– Space unit: the space for one book
Asymptotic Notation
• O()
• o()
• ()
• ()
• ()

You might also like