[go: up one dir, main page]
Scribd
Upload
6 views12 pages

UNIT I - Session 2

Uploaded by

sakuyuki.owo
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
6 views12 pages

UNIT I - Session 2

Uploaded by

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

UNIT I

INTRODUCTION TO ALGORITHM
DESIGN
Why to design an algorithm?
⚫ General approaches to the construction of efficient
solutions to problems
◦ They provide templates suited for solving a broad range of
diverse problems.

◦ They can be translated into common control and data structures


provided by most high-level languages.

◦ The temporal and spatial requirements of the algorithms which


result can be precisely analyzed.
Algorithm Design Approaches
Based on the architecture

⚫ Top Down Approach


⚫ Bottom up Approach
Top down approach is a method of designing and implementing algorithms that
starts with high-level overview of the problem later breaking into smaller sub-
problems. Ex: Recursive problems like Fibonacci series.

Bottom-up approach works by starting with individual components and building


up to larger system. Ex:
Algorithm Design Techniques
1. Brute Force
◦ To solve a problem based on the problem’s statement
and definitions of the concepts involved.
◦ Easiest approach to apply
◦ Useful for solving small – size instances of a problem.
⚫ Some examples of brute force algorithms are:
◦ Computing an (a > 0, n a nonnegative integer) by
multiplying a*a*…*a
◦ Computing n!
◦ Selection sort, Bubble sort
◦ Sequential search
2. Divide-and-Conquer & Decrease-and-Conquer
Step 1
Split the given instance of the problem into several
smaller sub-instances
Step 2
Independently solve each of the sub-instances
Step 3
Combine the sub-instance solutions.
⚫ With the divide-and-conquer method the size of the
problem instance is reduced by a factor (e.g. half the
input size),
⚫ With the decrease-and-conquer method the size is
reduced by a constant.
Examples of divide-and-conquer algorithms:
⚫ Computing an (a > 0, n a nonnegative integer) by
recursion
⚫ Binary search in a sorted array (recursion)
⚫ Mergesort algorithm, Quicksort algorithm recursion)
⚫ The algorithm for solving the fake coin problem
(recursion)
3. Greedy Algorithms "take what you can get now" strategy

⚫ At each step the choice must be locally optimal

⚫ Works well on optimization problems

⚫ Characteristics

1. Greedy-choice property: A global optimum can be arrived at by selecting a local

optimum.

2. Optimal substructure: An optimal solution to the problem contains an optimal

solution to sub problems.

⚫ Examples:

◦ Minimal spanning tree

◦ Shortest distance in graphs

◦ Greedy algorithm for the Knapsack problem

◦ The coin exchange problem

◦ Huffman trees for optimal encoding


4.Dynamic Programming
⚫ Finds solutions to subproblems and stores them in memory for later use.

⚫ Characteristics

1. Optimal substructure:

Optimal solution to problem consists of optimal solutions to subproblems

2. Overlapping subproblems:

Few subproblems in total, many recurring instances of each

3. Bottom up approach:

Solve bottom-up, building a table of solved subproblems that are used to


solve larger ones.
⚫ Examples:
◦ Fibonacci numbers computed by iteration.
◦ Warshall’s algorithm implemented by iterations
5. Backtracking methods
⚫ The method is used for state-space search problems.
What is State-space search problems
- State-space search problems are problems, where the
problem representation consists of:
◦ initial state
◦ goal state(s)
◦ a set of intermediate states
◦ a set of operators that transform one state into another.
◦ a cost function – evaluates the cost of the operations (optional)
◦ a utility function – evaluates how close is a given state to the goal state (optional)
⚫ The solving process solution is based on the construction of a state-
space tree
⚫ The solution is obtained by searching the tree until a goal state is
found.
⚫ Examples:
◦ DFS problem
◦ Maze problems
6. Branch-and-bound
⚫ Branch and bound is used when we can evaluate each node using
the cost and utility functions.
⚫ At each step we choose the best node to proceed further.
⚫ Branch-and bound algorithms are implemented using a priority
queue.
⚫ The state-space tree is built in a breadth-first manner.
⚫ Example:
8-puzzle problem.
N queens problem
Recollect
⚫ Different design Approaches/ Design
Paradigms
◦ Brute force
Unit 2
◦ Divide and Conquer

◦ Greedy Algorithms

◦ Dynamic Programming
}Unit 3

Unit 4
◦ Backtracking
Unit 5
◦ Branch and Bound

You might also like