Logistics > EXAM > Class notes Data Structures and Algorithms (CS 124) (All)

Class notes Data Structures and Algorithms (CS 124)

Document Content and Description Below

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) | l ... ogkab = 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]

Last updated: 3 years ago

Preview 1 out of 33 pages

Buy Now

Instant download

We Accept: