This document outlines the first lecture of an advanced algorithms analysis and design course taught by Dr. Nazir Ahmad Zafar. It introduces key concepts like defining an algorithm, common algorithm design techniques, the problem solving process, and the computational model used for analysis. The lecture covers what an algorithm is, compares different algorithms for the same problem, describes techniques like divide-and-conquer and greedy approaches, explains modeling assumptions made for analysis, and concludes by establishing algorithms as an important technology.
This document outlines the first lecture of an advanced algorithms analysis and design course taught by Dr. Nazir Ahmad Zafar. It introduces key concepts like defining an algorithm, common algorithm design techniques, the problem solving process, and the computational model used for analysis. The lecture covers what an algorithm is, compares different algorithms for the same problem, describes techniques like divide-and-conquer and greedy approaches, explains modeling assumptions made for analysis, and concludes by establishing algorithms as an important technology.
This document outlines the first lecture of an advanced algorithms analysis and design course taught by Dr. Nazir Ahmad Zafar. It introduces key concepts like defining an algorithm, common algorithm design techniques, the problem solving process, and the computational model used for analysis. The lecture covers what an algorithm is, compares different algorithms for the same problem, describes techniques like divide-and-conquer and greedy approaches, explains modeling assumptions made for analysis, and concludes by establishing algorithms as an important technology.
This document outlines the first lecture of an advanced algorithms analysis and design course taught by Dr. Nazir Ahmad Zafar. It introduces key concepts like defining an algorithm, common algorithm design techniques, the problem solving process, and the computational model used for analysis. The lecture covers what an algorithm is, compares different algorithms for the same problem, describes techniques like divide-and-conquer and greedy approaches, explains modeling assumptions made for analysis, and concludes by establishing algorithms as an important technology.
Download as PPT, PDF, TXT or read online from Scribd
Download as ppt, pdf, or txt
You are on page 1/ 20
Advanced Algorithms Analysis
and Design
By
Dr. Nazir Ahmad Zafar
Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
M. Sc. Mathematics: 1989-91 Quaid-i-Azam University, Islamabad M. Phil Mathematics: 1991-93 Quaid-i-Azam University, Islamabad M. Sc. Nuclear Engineering: 1993-94 Quaid-i-Azam University, Islamabad PhD Computer Science: 2000-04 Kyushu University, Japan
Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
Objective of This Course
Major objective of this course is: Design and analysis of modern algorithms Different variants Accuracy Efficiency Comparing efficiencies Motivation thinking new algorithms Advanced designing techniques Real world problems will be taken as examples To create feelings about usefulness of this course Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
Expected Results
On successful completion, students will be able to
Argue and prove correctness of algorithms Derive and solve mathematical models of problems Reasoning when an algorithm calls certain approach Analyze average and worst-case running times Integrating approaches in dynamic and greedy algos. Use of graph theory in problems solving Advanced topics such as Computational geometry, number theory etc. Several other algorithms such as String matching, NP completeness, approximate algorithms etc.
Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
Lecture No 1
Introduction (What, Why and Where Algorithms . . .)
Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
Today Covered In this lecture we will cover the following What is Algorithm? Designing Techniques Model of Computation Algorithms as a technology Algorithms and other technologies Importance of algorithms Difference in Users and Developers Kinds of problems solved by algorithms Conclusion Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
What is Algorithm? A computer algorithm is a detailed step-by-step method for solving a problem by using a computer. An algorithm is a sequence of unambiguous instructions for solving a problem in a finite amount of time. An Algorithm is well defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values as output. More generally, an Algorithm is any well defined computational procedure that takes collection of elements as input and produces a collection of elements as output.
Input
Dr Nazir A. Zafar
Algorithm
output
Advanced Algorithms Analysis and Design
Popular Algorithms, Factors of Dependence
Most basic and popular algorithms are Sorting algorithms Searching algorithms
Which algorithm is best?
Mainly, it depends upon various factors, for example in case of sorting
The number of items to be sorted
The extent to which the items are already sorted Possible restrictions on the item values The kind of storage device to be used etc.
Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
One Problem, Many Algorithms
Problem The statement of the problem specifies, in general terms, the desired input/output relationship. Algorithm The algorithm describes a specific computational procedure for achieving input/output relationship. Example One might need to sort a sequence of numbers into non-decreasing order. Algorithms Various algorithms e.g. merge sort, quick sort, heap sorts etc. Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
Important Designing Techniques
Brute Force Straightforward, naive approach Mostly expensive Divide-and-Conquer Divide into smaller sub-problems Iterative Improvement Improve one change at a time Decrease-and-Conquer Decrease instance size Transform-and-Conquer Modify problem first and then solve it Space and Time Tradeoffs Use more space now to save time later Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
Some of the Important Designing Techniques
Greedy Approach
Locally optimal decisions, can not change once made.
Efficient Easy to implement The solution is expected to be optimal Every problem may not have greedy solution
Dynamic programming
Decompose into sub-problems like divide and conquer
Sub-problems are dependant Record results of smaller sub-problems Re-use it for further occurrence Mostly reduces complexity exponential to polynomial
Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
Problem Solving Phases
Analysis
How does system work?
Breaking a system down to known components How components (processes) relate to each other Breaking a process down to known functions
Synthesis
Building tools Building functions with supporting tools Composing functions to form a process How components should be put together? Final solution
Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
Problem Solving Process
Problem Strategy Algorithm Input Output Steps Analysis Correctness Time & Space Optimality Implementation Verification Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
Model of Computation (Assumptions)
Design assumption Level of abstraction which meets our requirements Neither more nor less e.g. [0, 1] infinite continuous interval
Analysis independent of the variations in
Machine Operating system Programming languages Compiler etc. Low-level details will not be considered Our model will be an abstraction of a standard generic single-processor machine, called a random access machine or RAM. Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
Model of Computation (Assumptions)
A RAM is assumed to be an idealized machine Infinitely large random-access memory Instructions execute sequentially Every instruction is in fact a basic operation on two values in the machines memory which takes unit time. These might be characters or integers. Example of basic operations include Assigning a value to a variable Arithmetic operation (+, - , , /) on integers Performing any comparison e.g. a < b Boolean operations Accessing an element of an array. Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
Model of Computation (Assumptions)
In theoretical analysis, computational complexity Estimated in asymptotic sense, i.e. Estimating for large inputs Big O, Omega, Theta etc. notations are used to compute the complexity Asymptotic notations are used because different implementations of algorithm may differ in efficiency Efficiencies of two given algorithm are related By a constant multiplicative factor Called hidden constant. Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
Drawbacks in Model of Computation
First poor assumption We assumed that each basic operation takes constant time, i.e. model allows Adding Multiplying Comparing etc. two numbers of any length in constant time Addition of two numbers takes a unit time! Not good because numbers may be arbitrarily Addition and multiplication both take unit time! Again very bad assumption Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
Model of Computation not so Bad
Finally what about Our Model? But with all these weaknesses, our model is not so bad because we have to give the Comparison not the absolute analysis of any algorithm. We have to deal with large inputs not with the small size
Model seems to work well describing computational
power of modern nonparallel machines
Can we do Exact Measure of Efficiency ?
Exact, not asymptotic, measure of efficiency can be sometimes computed but it usually requires certain assumptions concerning implementation Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
Summary : Computational Model
Analysis will be performed with respect to this computational model for comparison of algorithms We will give asymptotic analysis not detailed comparison i.e. for large inputs We will use generic uniprocessor random-access machine (RAM) in analysis All memory equally expensive to access No concurrent operations All reasonable instructions take unit time, except, of course, function calls
Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
Conclusion
What, Why and Where Algorithms?
Designing Techniques Problem solving Phases and Procedure Model of computations Major assumptions at design and analysis level Merits and demerits, justification of assumptions taken
We proved that algorithm is a technology
Compared algorithmic technology with others Discussed importance of algorithms In almost all areas of computer science and engineering Algorithms make difference in users and developers Dr Nazir A. Zafar
