Design and Analysis of
Algorithms
Lecture # 1
Muhammad Nasir
Department of Computer Science
COMSATS University Islamabad,
Lahore Campus
[email protected]
About the Course
Purpose: A brief introduction to Design and
Analysis of Algorithms
Lab or Programming Course: No
Math Course: No
Textbook: Introduction to Algorithms,
second edition by Thomas H. Cormen
Pre-requisites
• Discrete Structures
• Data Structures
Course Evaluation
Assignments
Quizzes
Term Projects / Reports
S1 exam
S2 exam
Final exam
Class Expectations
Come to lectures on time and participate
Keep up with reading material
Complete assignments, projects, etc on time
Submit clean, organized, and to the point reports
Attendance Key to Success
Pay attention to lectures and keep extra notes
Ask questions
Effort
Do homework on your own. It’s ok to ask others but make
your own effort.
Consistency
Keep up with reading, and homework.
Plagiarism Policy
According to this policy, a student's submitted
work must be the student's own. In this course,
this policy will be applied to all work submitted for
grade including exams, quizzes, homework, and
projects.
Algorithm
The word Algorithm comes from the name of the
muslim author Abu Ja’far Mohammad ibn Musa
al-Khowarizmi.
Introduction
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.
Introduction
Algorithm:
Most basic and popular algorithms are
sorting algorithms & Searching algorithms
Introduction
Algorithms and Programming:
• good understanding of algorithms is essential for a
good programming
• Unlike a program, an algorithm is a mathematical
entity, which is independent of a specific
programming language, machine, or compiler.
• Algorithm design is all about the mathematical
theory behind the design of good programs
Introduction
Algorithms and Data Structures
• Efficient Algorithms require efficient Data Structures
and vice versa
Why Study Data Structures and Algorithms?
• For good algorithm design
• To be really complete algorithm designer, it is
important to be aware of programming and machine
issues as well
• They have various applications like databases,
operating system, computer graphics , compilers and
computer networks etc.
• a good understanding of algorithm design is a
central element to a good understanding of
computer science and good programming.
Course Outline
Course will consist of four major sections:
• The first is on the mathematical tools necessary for the
analysis of algorithms. This will focus on asymptotic,
summations, recurrences.
• The second element will deal with one particularly
important algorithmic problem: sorting a list of
numbers. We will show a number of different strategies
for sorting, and use this problem as a case-study in
different techniques for designing and analyzing
algorithms.
Course Outline
• The third one will deal with a collection of various
algorithmic problems and solution techniques. Dynamic
programming, greedy algorithms, graphs etc.
• Finally, a very brief introduction to the theory of NP-
completeness. NP-complete problem are those for
which no efficient algorithms are known, but no one
knows for sure whether efficient solutions might exist.
Criterion for Analyzing Algorithms
• To design good algorithms, we must agree on
the criterion for measuring the algorithms
• The emphasis is on the design of efficient
algorithms
Criterion for Analyzing Algorithms
• Computational resources required an algorithm
• Running time
• Memory/space required
• An algorithm which requires less amount of
running time and memory space will be called
an efficient algorithm
Model of Computation
• Our analysis will be independent of the
variations in:
• Machine hardware
• Operating system
• Compiler
• Programming language etc
• Algorithms need to understood by the people
not machines
Model of Computation
• Ideally this model should be a reasonable
abstraction of a standard generic single-
processor machine
• We will call this machine as Random Access
Machine
Random Access Machine (RAM)
• A Random Access Machine (RAM) is an
ideal machine with
• Infinite large memory
• Executes one instruction at a time (no parallelism)
• Each instruction performs some basic operations on
two values in memory
Basic RAM operations
• Basic operations include
• Assigning a value to a variable
• Performing basic arithmetic operation (+, -, *, /) on
any size of integer values
• Accessing an element of an Array
like array[100]
An Important Assumption
• Each basic operation takes same constant time
to execute
• There is no difference between performing
addition or multiplication on any size of the
values
Running Time Analysis Criteria
• Worst case analysis
Maximum running time over all (legal) inputs of size n
• Average case analysis
average running time over all inputs of size n
• Best case analysis
Running time over the best case input of size n
• We always look for the worst case
running time
