Design and Analysis of Algorithms
Revised 05/02/03
Comp 271
Mordecai Golin
Department of Computer Science, HKUST
Information about the Lecturer
Dr. Mordecai Golin
Office: 3559
Email: [email protected]
http://www.cs.ust.hk/˜golin
Office hours: Just drop by or send email for ap-
pointment.
1
Textbook and Lecture Notes
Textbook: Cormen, Leiserson, Rivest, Stein:
“Introduction to Algorithms”, 2.ed. MIT Press 2001.
Lecture Slides: Available on course webpage
http://www.cs.ust.hk/course/comp271
References: Recommendations
1. Dave Mount: Lecture Notes
Available on course web page
2. Jon Bentley: Programming Pearls (2nd ed). Addison-Wesley,
2000.
3. Michael R. Garey & David S. Johnson: Computers and in-
tractability : a guide to the theory of NP-completeness. W.
H. Freeman, 1979.
4. Robert Sedgewick: Algorithms in C++ (3rd ed) Volumes 1
and 2. Addison-Wesley, 1998.
2
About COMP 271
A continuation of COMP 171, with advanced topics
and techniques. Main topics are:
1. Design paradigms: divide-and-conquer, greedy
algorithms, dynamic programming.
2. Analysis of algorithms (goes hand in hand with
design).
3. Graph Algorithms.
4. Complexity classes (P, NP, NP-complete).
Prerequisite: Discrete Math. and COMP 171
3
We assume that you know
Sorting: Quicksort, Insertion Sort, Mergesort, Radix Sort
(with analysis). Lower Bounds on Sorting.
Big
notation and simple analysis of algorithms
Heaps
Graphs and Digraphs. Breadth & Depth first search and
their running times. Topological Sort.
Balanced Binary Search Trees (dictionaries)
Hashing
4
Tentative Syllabus
Introduction & Review
Maximum Contiguous Subarray:
case study in algorithm design
Divide-and-Conquer Algorithms: Mergesort, Polynomial Mul-
tiplication, Randomized Selection
Graphs:
– Review: Notation, Depth/Breadth First Search
– Cycle Finding & Topological Sort
– Minimum Spanning Trees: Kruskal’s and Prim’s algo-
rithms
– Dijkstra’s shortest path algorithm
Dynamic Programming: Knapsack, Chain Matrix Multipli-
cation, Longest Common Subsequence, All Pairs Shortest
Path
Greedy algorithms: Activity Selection, Huffman Coding
Complexity Classes: Nondeterminism, the classes P and
NP, NP-complete problems, polynomial reductions
5
Other Information
Lecture and tutorial schedule, TAs.
No Tutorials this week.
Tutorials start on February 14, 2003.
Question banks: To help you review
Assignments: 4, each worth 5% of grade
Midterm: worth 35% of grade
Final exam (comprehensive): worth 45% of grade.
Final Grade. Will be curved based on class per-
formance. Guaranteed Grades:
Average of
Average of
Average of
Average of
6
Classroom Etiquette
No pagers and cell phones – switch off in class-
room.
Latecomers should enter QUIETLY.
No loud talking during lectures.
But please ask questions and provide feedback.
7
Lecture 1: Introduction
Computational Problems and Algorithms
Definition: A computational problem is a specifica-
tion of the desired input-output relationship.
Definition: An instance of a problem is all the inputs
needed to compute a solution to the problem.
Definition: An algorithm is a well defined computa-
tional procedure that transforms inputs into outputs,
achieving the desired input-output relationship.
Definition: A correct algorithm halts with the correct
output for every input instance. We can then say that
the algorithm solves the problem.
8
Example of Problems and Instances
Computational Problem: Sorting
Input: Sequence of numbers .
Output: Permutation (reordering)
such that .
Instance of Problem:
9
Example of Algorithm: Insertion Sort
In-Place Sort: uses only a fixed amount of storage
beyond that needed for the data.
Pseudocode: is an array of numbers
for to length( )
key = ;
;
and
while (
key)
;
;
key;
Pause: How does it work?
10
Insertion Sort: an Incremental Approach
To sort a given array of length , at the th step it
sorts the array of the first items by making use of the
sorted array of the first items in the th
Step.
Example: Sort with Insertion Sort.
Step 1:
Step 2:
Step 3:
Step 4:
11
Analyzing Algorithms
Predict resource utilization
1. Memory (space complexity)
2. Running time (time complexity)
Remark: Really depends on the model of computa-
tion (sequential or parallel). We usually assume se-
quential.
12
Analyzing Algorithms – Continued
Running time: the number of primitive operations
used to solve the problem.
Primitive operations: e.g., addition, multiplication,
comparisons.
Running time: depends on problem instance, often
we find an upper bound: F(input size)
Input size: rigorous definition given later.
1. Sorting: number of items to be sorted
2. Multiplication: number of bits, number of digits.
3. Graphs: number of vertices and edges.
13
Three Cases of Analysis
Best Case: constraints on the input, other than size,
resulting in the fastest possible running time.
Worst Case: constraints on the input, other than size,
resulting in the slowest possible running time.
Example. In the worst case Quicksort runs in
time on an input of keys.
Average Case: average running time over every pos-
sible type of input (usually involve probabilities of dif-
ferent types of input).
Example. In the average case Quicksort runs in
time on an input of keys. All inputs of keys are
considered equally likely.
Remark: All cases are relative to the algorithm under
consideration.
14
Three Analyses of Insertion Sorting
Best Case: .
The number of comparisons needed is equal to
Worst Case: .
The number of comparisons needed is equal to
Average Case: assuming that each of the
instances are equally likely.
15
Big Oh
: is an asymptotically upper
bound for .
and
such that
for all
Remark: “ ” means that
Examples:
(1) .
(2) .
(3) .
(4) .
(5)
16
Big Omega
: is an asymptotically lower
bound for .
and
such that
for all
Examples:
(1) .
(2) .
(3) .
(3) Does imply ?
(4) Does imply ?
17
Big Theta
: is an asymptotically tight
bound for .
and
such that
for all
Examples:
(1)
(2)
18
Note that if
then
and
In the other direction, if
and
then
and
19
Some thoughts on Algorithm Design
Algorithm Design, as taught in this class, is mainly
about designing algorithms that have small big
running times.
“All other things being equal”, algo-
rithms will run more quickly than ones and
algorithms will beat ones.
Being able to do good algorithm design lets you
identify the hard parts of your problem and deal
with them effectively.
Too often, programmers try to solve problems us-
ing brute force techniques and end up with slow
complicated code! A few hours of abstract thought
devoted to algorithm design could have speeded
up the solution substantially and simplified it.
20
Note: After algorithm design one can continue on to
Algorithm tuning which would further concentrate on
improving algorithms by cutting cut down on the con-
stants in the big bounds. This needs a good un-
derstanding of both algorithm design principles and
efficient use of data structures. In this course we will
not go further into algorithm tuning. For a good intro-
duction, see chapter 9 in Programming Pearls, 2nd ed
by Jon Bentley.
21
