CSCI203 Week 1
Math Revision:
Exponents : x
a * xb = xa + b
| xa
/ xb = xa - b
| (xa
)
b = xa * b
| xn + xn = 2xn
| 2n + 2n = 2n+1
Logarithms: logab = logcb / logca (a,b,c, > 0: a != 1) | logkab = logka + logk
...
CSCI203 Week 1
Math Revision:
Exponents : x
a * xb = xa + b
| xa
/ xb = xa - b
| (xa
)
b = xa * b
| xn + xn = 2xn
| 2n + 2n = 2n+1
Logarithms: logab = logcb / logca (a,b,c, > 0: a != 1) | logkab = logka + logkb (a,b > 0)
Limits: When a function f(n) tends to a limit as n approaches infinity
Series:
- Arithmetic Series (a, a+d, a+2d,…) -> Sn = an + n(n-1)d/2
- Geometric Series (a, ar, ar2
,ar3…) -> sn = a(1-r
n
)/(1-r)
o Convergent when (-1 < r < 1)
Probablility: Pr[A] | pr[~A] | pr[A|B]
Algorithm:
An algorithm is a set of rules for carrying out some calculation or procedure.
They should: be correct, terminate and be efficient
We study algorithms to be able to:
- Understand how they work
- Know when to use them
- Adapt them for different problems
- Create new algorithms that are better than the existing ones
o Better how?
Faster
Less overhead space
More general
Data Structures
Data structures are an organised collection of data.
They represent an abstract data type in an (hopefully) efficient way.
o Efficient how?
Allows for efficient access by the algorithm
Uses a minimum of storage
Algorithmics
Algorithmics is the study of the properties of algorithms such as:
- Correctness
o Difficult to prove that an algorithm is correct
o Easy to prove an algorithm is incorrect
o Can be shown formally or informally
- Efficiency
o Usually a measure of speed (or comparisons)
o Sometimes it is measured in storage space required
o Rarely it is a measure of some other property
- Applicablilty
o What domain the algorithm lies in
o What sub domain the algorithm is efficient in
[Show More]