Computer Science and Software Engineering, 2008
CITS3210 Algorithms
Lecture Notes
Notes by CSSE, Comics by xkcd.com
1
, Overview
Computer Science and Software Engineering, 2011
1. Introduction
(a) What are Algorithms?
(b) Design of Algorithms.
(c) Types of Algorithms.
CITS3210 Algorithms
2. Complexity
Introduction
(a) Growth rates.
(b) Asymptotic analysis, O and Θ.
(c) Average case analysis.
(d) Recurrence relations.
3. Sorting
(a) Insertion Sort.
(b) Merge Sort.
(c) QuickSort.
Notes by CSSE, Comics by xkcd.com
1 2
What will we be studying?
We will study a collection of algorithms,
What you should already know? examining their design, analysis and sometimes
even implementation. The topics we will cover
will be taken from the following list:
This unit will require the following basic
knowledge:
1. Specifying and implementing algorithms.
1. Java Programming: classes, control 2. Basic complexity analysis.
structures, recursion, testing, etc
3. Sorting Algorithms.
2. Data Structures: stacks, queues, lists,
trees, etc. 4. Graph algorithms.
5. Network flow algorithms.
3. Complexity: definition of “big O”, Θ
notation, amortized analysis etc.
6. Computational Geometry.
4. Some maths: proof methods, such as proof 7. String algorithms.
by induction, some understanding of
continuous functions
8. Greedy/Dynamic algorithms.
9. Optimization Algorithms.
3 4
, What are the outcomes of this unit?
At the end of the unit you will:
1. be able to identify and abstract
What are algorithms?
computational problems.
An algorithm is a well-defined finite set of rules
2. know important algorithmic techniques and
that specifies a sequential series of elementary
a range of useful algorithms.
operations to be applied to some data called
the input, producing after a finite amount of
3. be able to implement algorithms as a time some data called the output.
solution to any solvable problem.
An algorithm solves some computational
4. be able to analyse the complexity and problem.
correctness of algorithms.
Algorithms (along with data structures) are the
5. be able to design correct and efficient fundamental “building blocks” from which
algorithms. programs are constructed. Only by fully
understanding them is it possible to write very
The course will proceed by covering a number effective programs.
of algorithms; as they are covered, the general
algorithmic technique involved will be
highlighted, and the role of appropriate data
structures, and efficient implementation
considered.
5 6
Design and Analysis
An algorithmic solution to a computational
problem will usually involve designing an Design and Analysis
algorithm, and then analysing its performance.
In designing and analysing an algorithm we
Design A good algorithm designer must have a should consider the following questions:
thorough background knowledge of algorithmic
techniques, but especially substantial creativity
and imagination. Often the most obvious way 1. What is the problem we have to solve?
of doing something is inefficient, and a better
solution will require thinking “out of the box”.
2. Does a solution exist?
In this respect, algorithm design is as much an
art as a science.
3. Can we find a solution (algorithm), and is
Analysis A good algorithm analyst must be there more than one solution?
able to carefully estimate or calculate the
resources (time, space or other) that the
4. Is the algorithm correct?
algorithm will use when running. This requires
logic, care and often some mathematical ability.
5. How efficient is the algorithm?
The aim of this course is to give you sufficient
background to understand and appreciate the
issues involved in the design and analysis of
algorithms.
7 8
, The naive solution
The naive solution is to simply write a recursive
The importance of design method that directly models the problem.
By far the most important thing in a program static int fib(int n) {
is the design of the algorithm. It is far more
significant than the language the program is return (n<3 ? 1 : fib(n-1) + fib(n-2));
written in, or the clock speed of the computer.
}
To demonstrate this, we consider the problem
of computing the Fibonacci numbers. Is this a good algorithm/program in terms of
resource usage?
The Fibonacci sequence is the sequence of
integers starting Timing it on a (2005) iMac gives the following
results (the time is in seconds and is for a loop
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, . . . calculating Fn 10000 times).
which is formally defined by
Value Time Value Time
F1 = F2 = 1 and Fn = Fn−1 + Fn−2. F20 1.65 F24 9.946
F21 2.51 F25 15.95
F22 3.94 F26 25.68
Let us devise an algorithm to compute Fn. F23 6.29 F27 41.40
How long will it take to compute F30, F40 or
F50?
9 10
Theoretical results
Each method call to fib() does roughly the
Experimental results
same amount of work (just two comparisons
and one addition), so we will have a very rough
Make a plot of the times taken.
estimate of the time taken if we count how
many method calls are made.
40.0
Exercise: Show the number of method calls
made to fib() is 2Fn − 1.
30.0
20.0
10.0
22 24 26
11 12
CITS3210 Algorithms
Lecture Notes
Notes by CSSE, Comics by xkcd.com
1
, Overview
Computer Science and Software Engineering, 2011
1. Introduction
(a) What are Algorithms?
(b) Design of Algorithms.
(c) Types of Algorithms.
CITS3210 Algorithms
2. Complexity
Introduction
(a) Growth rates.
(b) Asymptotic analysis, O and Θ.
(c) Average case analysis.
(d) Recurrence relations.
3. Sorting
(a) Insertion Sort.
(b) Merge Sort.
(c) QuickSort.
Notes by CSSE, Comics by xkcd.com
1 2
What will we be studying?
We will study a collection of algorithms,
What you should already know? examining their design, analysis and sometimes
even implementation. The topics we will cover
will be taken from the following list:
This unit will require the following basic
knowledge:
1. Specifying and implementing algorithms.
1. Java Programming: classes, control 2. Basic complexity analysis.
structures, recursion, testing, etc
3. Sorting Algorithms.
2. Data Structures: stacks, queues, lists,
trees, etc. 4. Graph algorithms.
5. Network flow algorithms.
3. Complexity: definition of “big O”, Θ
notation, amortized analysis etc.
6. Computational Geometry.
4. Some maths: proof methods, such as proof 7. String algorithms.
by induction, some understanding of
continuous functions
8. Greedy/Dynamic algorithms.
9. Optimization Algorithms.
3 4
, What are the outcomes of this unit?
At the end of the unit you will:
1. be able to identify and abstract
What are algorithms?
computational problems.
An algorithm is a well-defined finite set of rules
2. know important algorithmic techniques and
that specifies a sequential series of elementary
a range of useful algorithms.
operations to be applied to some data called
the input, producing after a finite amount of
3. be able to implement algorithms as a time some data called the output.
solution to any solvable problem.
An algorithm solves some computational
4. be able to analyse the complexity and problem.
correctness of algorithms.
Algorithms (along with data structures) are the
5. be able to design correct and efficient fundamental “building blocks” from which
algorithms. programs are constructed. Only by fully
understanding them is it possible to write very
The course will proceed by covering a number effective programs.
of algorithms; as they are covered, the general
algorithmic technique involved will be
highlighted, and the role of appropriate data
structures, and efficient implementation
considered.
5 6
Design and Analysis
An algorithmic solution to a computational
problem will usually involve designing an Design and Analysis
algorithm, and then analysing its performance.
In designing and analysing an algorithm we
Design A good algorithm designer must have a should consider the following questions:
thorough background knowledge of algorithmic
techniques, but especially substantial creativity
and imagination. Often the most obvious way 1. What is the problem we have to solve?
of doing something is inefficient, and a better
solution will require thinking “out of the box”.
2. Does a solution exist?
In this respect, algorithm design is as much an
art as a science.
3. Can we find a solution (algorithm), and is
Analysis A good algorithm analyst must be there more than one solution?
able to carefully estimate or calculate the
resources (time, space or other) that the
4. Is the algorithm correct?
algorithm will use when running. This requires
logic, care and often some mathematical ability.
5. How efficient is the algorithm?
The aim of this course is to give you sufficient
background to understand and appreciate the
issues involved in the design and analysis of
algorithms.
7 8
, The naive solution
The naive solution is to simply write a recursive
The importance of design method that directly models the problem.
By far the most important thing in a program static int fib(int n) {
is the design of the algorithm. It is far more
significant than the language the program is return (n<3 ? 1 : fib(n-1) + fib(n-2));
written in, or the clock speed of the computer.
}
To demonstrate this, we consider the problem
of computing the Fibonacci numbers. Is this a good algorithm/program in terms of
resource usage?
The Fibonacci sequence is the sequence of
integers starting Timing it on a (2005) iMac gives the following
results (the time is in seconds and is for a loop
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, . . . calculating Fn 10000 times).
which is formally defined by
Value Time Value Time
F1 = F2 = 1 and Fn = Fn−1 + Fn−2. F20 1.65 F24 9.946
F21 2.51 F25 15.95
F22 3.94 F26 25.68
Let us devise an algorithm to compute Fn. F23 6.29 F27 41.40
How long will it take to compute F30, F40 or
F50?
9 10
Theoretical results
Each method call to fib() does roughly the
Experimental results
same amount of work (just two comparisons
and one addition), so we will have a very rough
Make a plot of the times taken.
estimate of the time taken if we count how
many method calls are made.
40.0
Exercise: Show the number of method calls
made to fib() is 2Fn − 1.
30.0
20.0
10.0
22 24 26
11 12
