CS 517

1. CS 317
2. CS 517
3. Algorithmic Analysis
- 3.1. Efficiency/Complexity Analysis
- 3.2. Recursive(-like) functions

1. CS 317

Introduction to complexity analysis of algorithms
Emphasis on
- searching
- sorting
- finding spanning trees
- finding shortest paths in graphs
Design techniques such as
- divide & conquer
- dynamic programming
- backtracking
Introduction to problem classification; i.e. NP, intractable, and unsolvable.

2. CS 517

Intensive introduction to computing theory selected core topics from the undergraduate Computer Science curriculum, including

Boolean algebra
digital logic
proof methods
recursion and recurrences
graphs and trees
iterative and recursive algorithms
sorting and searching algorithms
divide-and-conquer algorithms

3. Algorithmic Analysis

nil nil nil

3.1. Efficiency/Complexity Analysis

Time
Space

3.1.1. Input Size

Measured in terms of input size:

Array: number of items
Trees: number of nodes, height of tree
String: number of characters
Polynomials: order of polynomial

3.1.2. Basic Operations

Count the # of basic operations:

+, -, *, /~ are usually considered basic operations with cost 1 (\(c_{op}\))

3.1.3. Order of Growth

In practise we ignore \(c_{op}\) , only consider order of growth

Efficiency Class	Order of Growth
constant	1
logarithmic	\(\log{n}\)
linear	\(n\)
linearithmic	\(n \log {n}\)
exponential	\(2^n\)

Comparing order of growth
\begin{equation} \label{eqn:order-of-growth} \lim_{n \to \infty} \frac{t(n)}{g(n)} \tag{order-of-growth} \end{equation}
- 0 => \(t(n)\) has smalleer order of growth than \(g(n)\)
- \(c\) => Order of growth is equal
- \(\infty\) implies \(t(n)\) has higher order of growth than \(g(n)\)

3.1.4. Asymptotic Notation

Page 20

\(O\) Big-O: Bounded from above

\(t(n) \in O(g(n)) \textrm{ if } t(n) \leq c g(n) \; \forall n \geq n_0\)
\(\Omega\) Big-Omega: Bounded from below

\(t(n) \in \Omega(g(n)) \textrm{ if } t(n) \geq c g(n) \; \forall n \geq n_0\)
\(\Theta\) Big-Theta: Bounded from above and below

\(t(n) \in \Omega(g(n)) \textrm{ if } c_1 g(n) \leq t(n) \leq c_2 g(n) \; \forall n \geq n_0\)
\(o\) Small-O: Bounded from above for all constants c

\(t(n) \in o(g(n)) \textrm{ if } \forall c > 0 \; \exists n_0 : t(n) < c g(n) \; \forall n \geq n_0\)

\begin{equation*}

lim_{n → ∞} \frac {t(n)} {g(n)} = 0 \end{equation*}

\(\omega\) Small-omega: Bounded from below for all constants c

\(t(n) \in \omega(g(n)) \textrm{ if } \forall c > 0 \; \exists n_0 : t(n) > c g(n) \; \forall n \geq n_0\)
\begin{equation*} lim_{n \to \infty} \frac {t(n)} {g(n)} = \infty \end{equation*}

Note that \(t(n) > 0\)

\(f(n) = O(g(n))\)	\(a \leq b\)
\(f(n) = o(g(n))\)	\(a < b\)
\(f(n) = \Theta(g(n))\)	\(a = b\)
\(f(n) = \omega(g(n))\)	\(a > b\)
\(f(n) = \Omega(g(n))\)	\(a \geq b\)

3.1.5. Structure of Input

Slide 2 - Page 3 Efficiency is not only dependent on input size, structure of input mattes too.

Worst case
Best case
Average case
Amortized

Amortized Analysis
Slide 2 - Page 7
- Amortized vs Average: Average analysis is done over the whole range of input. Amortized analysis is done for a sequence of operations.
1. Aggregate Analysis
  
  Show for a sequence of n operations, total time is no worst than T(n), then find the average cost.
2. Accounting Method (?)
3. Potential Method (?)
Average Case
- Use probabilistic analysis
- Usually all inputs are considered equally likely

3.1.6. Useful Tricks

\begin{equation} n! \approx \sqrt{2\pi n} \big(\frac n e \big)^n \end{equation}

3.2. Recursive(-like) functions

Functions whose complexity is defined in terms of itself.

Three methods for solving Recurrence Relations Slide 2 - Page 13

3.2.1. Backward/Forward Substitution

3.2.2. Characteristic Equation

Slide 2 - Page 20

Works only for linear homogeneous recurrence
Bring all terms of recurrence relation to LHS
Write the characteristic equation (convert a_i term to rⁱ terms)
Solve the equation
According to nature of roots, the form of the solution is known

Good for linear homogeneous whose characteristic equation is quadrati

Linear Homogeneous Equations
\(a_n = c_1 a_{n-1} + c_2 a_{n-2} + ... + c_k a_{n-k}\)

(Homogeneous = No constant term. i.e. all terms are constant multiple of \(a_i\) )
- \(a_n = 2 a_{n-} + 1\) (Not homogeneous)
- \(a_n = n \cross a_{n-1}\) (Not a constant coefficient)

3.2.3. Master Theorem

Slide 3 - Page 3
https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)
For analysis of divide-and-conqure algorithms.
Its generalization is Akra-Bazzi Method

\begin{equation*} T(n) = a T(\frac n b) + f(n) \end{equation*}

\(f(n)\) is the time taken to split the problem and recombine the solution
One assumption is that at some \(n \leq \kappa \; ; \kappa > 0\), the solutions doesn't have to recurse i.e \(f(n) = \Theta(1) \; n \leq \kappa\)