Next:
Contents
Up:
MX4002 Home Page
Contents
Index
Algorithms
MX4028
Ian Craw and John Pulham
Contents
List of Figures
List of Tables
Foreword
Course Numbers
These Notes
The Web Version
The MX4028 Mailing List
Background Reading
Introduction
Algorithms; Computer languages
Programming
An Implementation of the Euclidean Algorithm
Recursion
Algorithm Types
An Algorithm -- Hatching Polygons
The Problem
General Method
Hatching Convex Polygons
The Analysis of an Algorithm
Timing
A More Precise Analysis
Computing detours:
A
n
k
Approximating
H
n
Conclusion
Questions 1 (Hints and solutions start on page
.)
Sorting
Complications
Two Simple Sorting Algorithms
Minimum Element Sort
Insertion Sort
Proof of Algorithm
A More Precise Analysis of Insertion Sort
A better sort: Quicksort
Timing the algorithm
Merge Sort
Merge Algorithm
Merge Sort
Timing the Algorithm
Timings for Various Sorting Algorithms
Optimal Sorting
Optimal Merging
Some Example Sort Implementations
Questions 2 (Hints and solutions start on page
.)
Abstract Data Types
Introduction
The ADT Stack
The ADT Queue
The ADT Array
The ADT List
The ADT Priority Queue
Trees
The ADT tree
Traversals
Binary Trees
Huffman Codes
Heapsort
Questions 3 (Hints and solutions start on page
.)
Grammers and Parsing
Formal Languages
Formal Grammars
First Example
Second Example
Arithmetic Expressions
AE Grammer
Postfix Expressions
Postfix Grammer
Converting Infix to Postfix
FBIE Grammer
Evaluating a Postfix Expression
Questions 4 (Hints and solutions start on page
.)
Random Numbers
What is a Random Number?
Generating Random Numbers
Applications of Random Numbers
Generating Random Reals
Generating Random Integers
Choosing `with probability
p
'
Random Shuffles
Random Samples
Questions 5 (Hints and solutions start on page
.)
The Fast Fourier Transform
Multiplying Polynomials
Fourier Series
The Fourier Matrix
Products
Properties of the Fourier Transform
The Fast Fourier Transform.
Timing the FFT
Convolution as Filtering
An application to Image Processing
Gaussian Blur
The Laplace Operator
Questions 6 (Hints and solutions start on page
.)
Appendices
Big O
Solutions to Exercises
Solutions for Questions 1 (page
).
Solutions for Questions 2 (page
).
Solutions for Questions 3 (page
).
Solutions for Questions 4 (page
).
Solutions for Questions 5 (page
).
Solutions for Questions 6 (page
).
Bibliography
Index
About this document ...
Ian Craw 2001-04-27
![[*]](file:/maths/faces/local/lib/latex2html-2K.1beta/icons/crossref.gif){kind=icon}
.)
.)
.)
.)
.)
).
).
).
).
).
).