Lec‐01 Analysis of Algorithms
Umar Manzoor 1
Course Title: Analysis of Algorithms (Sec A & B) Prerequisite: Data Structures, Operating System
Yahoo Group: http://groups.yahoo.com/group/analysisofalgo/
Name: Umar Manzoor Email:
[email protected] Office: N‐111‐A Telephone Extension: 205 Office Hours: Tuesday 12.30 – 2.00 Wednesday 12.30 – 2.00
Never miss a class Start working on projects/assignments from first day. Come prepared in the class Read book (s) Remain attentive during the class Remain interactive and show Class Participation
All people involved in any kind of cheating in any exam will get zero in that exam
Habitual cheaters will get zero in all assignments/projects. This may lead to a course failure.
Cheating punishment may become more strict
There will be 4‐5 programming assignments, related to the topics being studied in course
Will require reasonable amount of programming effort
Also carry decent weight.
7
A project will be assigned to each group This involves studying a particular problem, analyzing its solution, implementing solution, running simulations and inferring results, Also required is in depth complexity analysis of solution used. A list of topic will be given in probably second week.
8
•
Introduction to Algorithms, by Cormen, Leiserson and Rivest. Pub MIT Press 1990 • Get the latest edition if possible •
Another book for reference • Data Structures and Algorithms, by Aho, Hopcroft
and Ullman, Pub Addision Wesley, 1983
9
10
Sessional exams
25%
Final exam
40%
Semester Project
20%
Quizzes
10%
Programming Assignments
15%
Lets start the course!
11
What are algorithms? Why is the study of algorithms worthwhile? What is the role of algorithms relative to other technologies used in computers?
12
An algorithm is any well‐defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output.
So it is a sequence of computational steps that transform the input into the output.
A tool for solving a well‐specified computational problem. 13
Input: A sequence of n numbers
Output: A permutation (re‐ordering) of the input sequence such that b1
14
An algorithm is said to be correct if , for every input instance, it halts with the correct output. An incorrect algorithm
might not halt at all on some input instances, or It might halt with an answer other than desired
one.
Can incorrect algorithm be useful? 15
Sorting/searching are by no mean the only computational problem for which algorithms have been developed. Otherwise we wouldn’t have the whole course on this topic Practical application of algorithms are ubiquitous and include the following examples
16
The human Genome project Internet world Electronic commerce Manufacturing and other commercial settings Shortest path Matrices multiplication order DNA sequence matching
17
There are many candidate solution, most of which are not what we want, finding one that we do want can present quite a challenge.
There are practical applications (its not just mathematical exercises to develop algorithms.)
18
The theoretical study of computer‐program performance and resource usage. What’s more important than performance?
• Modularity • Correctness • Maintainability • Functionality • Robustness • User‐friendliness • Programmer time • Simplicity • Extensibility • Reliability
19
Algorithms help us to understand scalability. Performance often draws the line between what is feasible and what is impossible. Algorithmic mathematics provides a language for talking about program behavior. Performance is the currency of computing. The lessons of program performance generalize to other computing resources. Speed is fun! 20
A data structure is a way to store and organize data in order to facilitate access and modifications. No single data structure works well for all purposes Need to know the strengths and limitations of several of them.
21
Cant get a “cookbook” for algorithms? Many problems you will encounter don’t have any published algorithm. So need to learn “techniques” of algorithms design and analysis So you develop algorithms in your own, show that they give correct answer and understand their efficiency. We will learn several such techniques in later part of this course.
22
Is an algorithm a technology like hardware, etc? Total system performance depends on choosing “efficient” algorithms as much as choosing fast hardware.
23
Hardware with high clock rates, pipelining and superscalar architecture. Easy to use, intuitive graphical user interface (GUI’s) Object oriented systems. Local‐area and wide‐area networking.
Are algorithms as important as above technologies? 24
Algorithms are at the core of most technologies used in contemporary computers Efficient algorithm can be used to solve larger problems than ever before.
25
Program Efficiency and Complexity Analysis. CHP‐2,3 Cormen.
A quick review! Come prepared with lectures from DS course
26