Author: Lim Wei Liang

Lecturer/Semester Taken: Dr Chong Ket Fah, AY20/21 Special Term 2

Main References:

• Class Lecture Slides & Lab Slides

VisuAlgo - visualising data structures and algorithms through animation

0. Prerequisites

Powers

• $a^x \times a^y = a^{x+y}$
• $a^x \div a^y = a^{x-y}$
• ${(a^x)}^{y} = a^{xy}$
• $(ab)^x = a^x b^x$
• $(\frac{a}{b})^x =\frac{a^x}{b^x}$

Logarithms (inverse of taking power)

• $a^b = y \Leftrightarrow log_ay = b$
• $log_a(a^x) = x$
• $a^{log_a(x)} = x$
• $log_a(m \times n) = log_am + log_an$
• $log_a(m/n) = log_am - log_an$
• $log_a(m^r) = rlog_am$
• Change of Base: $\displaystyle log_ax = \frac{log_bx}{log_ba}$
• $\displaystyle a^{log_cb} = b^{log_ca}$ (derived using above)
• $log_ba = 1/log_ab$
• $log_b(1) = 0$
• $log_bb = 1$

Useful Series

• AP Summation Formula: $\frac{n}{2}(2a + (n-1)d)$ or $\frac{n}{2}(a_1 + a_n)$
• GP Summation Formula: $S_n = \frac{a(1-r^n)}{1-r}$ or $S_n = \frac{a(r^n-1)}{r-1}$
  • GP Infinite Series Formula (for |r| < 1): $S_\infty = \frac{a}{1-r}$
• Harmonic Series: $\displaystyle\sum_{i=1}^{n}{\frac{1}{i}} = 1 + \frac{1}{2} + \frac{1}{3} + ... \ + \frac{1}{n} \approx ln(i+1)$
• Sum of Squares: $\displaystyle\sum_{i=1}^{n}{i^2} = 1 + 4 + 9 + ... \ +n^2 = \frac{n(n+1)(2n+1)}{6}$

Describing Algorithms

• Declare (and if necessary describe) all important data structures and variables at the start
• Be concise
• No need to describe details of data structures/algorithms discussed in class, unless they are modified
• No "black boxes"
• Use the correct terminology
• Be clear in your descriptions

1. Introduction - Analysis of Algorithms