KEMBAR78
Overview of Algorithm Design | PDF | Time Complexity | Computational Complexity Theory
Scribd
Upload
57 views9 pages

Overview of Algorithm Design

This document provides an overview of algorithm design and a process for beginners to learn algorithm design. It discusses problem specification, algorithm features, an overall solution strategy, and designing algorithms and data structures together. Key aspects of the design process include specifying inputs, outputs and constraints unambiguously, modeling the problem, developing an initial solution, exploring the solution space, analyzing complexity, finalizing an option, and structuring necessary data. The document demonstrates this process with examples like finding largest/smallest numbers, sorting, Fibonacci numbers, shortest paths, spanning trees, subset sum problems, and the travelling salesperson problem. It also covers time/space complexity, hard problems, approximation, and randomization.

Uploaded by

Saraah Ghori
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
57 views9 pages

Overview of Algorithm Design

This document provides an overview of algorithm design and a process for beginners to learn algorithm design. It discusses problem specification, algorithm features, an overall solution strategy, and designing algorithms and data structures together. Key aspects of the design process include specifying inputs, outputs and constraints unambiguously, modeling the problem, developing an initial solution, exploring the solution space, analyzing complexity, finalizing an option, and structuring necessary data. The document demonstrates this process with examples like finding largest/smallest numbers, sorting, Fibonacci numbers, shortest paths, spanning trees, subset sum problems, and the travelling salesperson problem. It also covers time/space complexity, hard problems, approximation, and randomization.

Uploaded by

Saraah Ghori
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/ 9

Overview of

Algorithm Design
Partha P Chakrabarti
Department of CSE, IIT Kharagpur
T10KT Main Workshop
May 25, 2015

Developing a Process for a


Beginner to Learn Algorithm Design
Problem Specification
Input, Output, Constraints

Algorithm Features
Termination, Functional Correctness, Efficiency,
User Interface / Interaction, Implementation,
Error Handling, Documentation

An Overall Solution Strategy


Initial Solution, Design Space Exploration and
Analysis, Algorithm Finalization, Data
Structuring

Design, Analysis: Algorithm + Data


Structure

Problem Specification
Unambiguously specify the INPUTS, OUTPUTS,
CONDITIONS / CONSTRAINTS.
Make use of logical operations and
mathematical symbols to the extent possible.
Additionally give examples to explain the
specification given where special cases are
properly highlighted)

Finding the smallest of n integers.


Sorting a set of integers.
Finding the median of a set of numbers.
Finding the number of matches of a pattern
in a string.

Modelling Problem
Specification
Modelling, Input, Output, Constraints to
structures
Use of Real-Life like Examples
Finding a route in a map
Crypt-arithmetic Problem
Telephone Line Connection Problem
Time Table Scheduling
Stamp Selection Problem
Pumping Water in a City
Travelling Salesperson
Robbers Dilemma

Mapping to Models
Combinatorial, Matrices, Graphs, Logic, Constraint
Satisfaction / Optimization Framework, ILP

Basic Steps Towards A


Structured Algorithm Design

Initial Solution
Solution Space Creation
Solution Space Explorations
Analysis of Complexity
Finalization of Options
Data Structuring

Detailing the Process

Initial Solution by Recursive Definition


Analysis by Recurrence Relations
Asymptotic Complexity
Opening up the Recursion Space
Traversal of the Recursion Space
Optimal Choice / Balancing the
recursion
Choosing the final solution
Identifying need / sources for
memorization
Data Structuring

Demonstration by
Examples
Finding the largest
of n integers

Largest and Smallest


Largest and second largest
Finding Fibonacci Numbers
Sorting and Searching
(Route Planning) Shortest Path
(Telephone Post Wiring) Spanning Tree (What
about the Telephone Post Placement?)
(Stamp Selection Problem) Sub-Set Sum
(Water Pumping) Max Flow Problem
(Time Table Scheduling) Constraint
Satisfaction
Travelling Salesperson

Efficient Algorithms, Hard


Problems

Time and Space Complexity


Asymptotic Complexity
Use Trick Questions

Adding arbitrarily large numbers


The n = 2*n loop

Space and Recursion


Output sensitive algorithms (Tower of Hanoi)

Polynomial Time Algorithms


Polynomial Space Algorithms
Hard Problems
NP Complete, NP Hard
Exponential Time
Exponential Space

Approximation
Randomization

Thank You

You might also like