Unit 1

Disc 1

LJ 1

Algorithm Techniques

Algorithm: a well-defined sequence of steps used to solve a well-defined problem in finite time

Running time: of an algorithm is the number of instructions it executes when run on a particular instance.

We use Big-Oh to find the upper bound (worst case)

Types of Algorithm Structures:

Recursive
Iterative

Types of Algorithm Solution:

A good solution
Best(s) solution(s)

Algorithms Strategies

Recursion: Divide & Conquer

Reapply algorithm to subproblem

Backtracking: Exhaustive /Brute-force Search approach

Try all possible solutions and pick up the desired one

Note: It is not for optimization (dynamic programming is for that)

It is performed in a depth-first search (DFS) manner

Steps:

Start by trying all possible states and build a State Space Tree to represent them following the DFS order
Apply the Bounding Function to omit the invalid states (based on some condition)
Return the group of valid states

Branch & Bound

It is performed in a breadth-first search (BFS) manner

Branch and bound does not decrease the complexity of a problem, it is simply a reasonable way to organize a search for an optimal solution.

Asymptotic Analysis

Big-Oh Notation (Upper Bounds)

Intuitive Definition

Let n be a size of program’s input

Let T(n) be function e.g. running time

Let f(n) be another function - preferably simple

Then,

T(n) \in O(f(n))

if & only if

T(n) \leq c . F(n)

. So, this has to be true whenever n is big enough for some large constant c

📌

How big is BIG and large is LARGE? Big and Large enough to make

T(n)

fits under

c.f(n)

Example

We have an algorithm whose running time is defined as

T(n) = 10000 + 10n

. Let’s try

f(n) = n

and pick

c=20

We can see that there is always a vertical line (in this example n=1000) where

T(n)

is less than

c.f(n)

Formal Definition

$O(f(n))$ is the set of all functions $T(n)$ that satisfy: There exist positive constants $c$ and $N$ such that, for all $n \ge N$ , then $T(n) \le c.f(n)$

Example 1

100,000n \in O(n)

Proof: Choose

c=100,000

and set the vertical line

N=0

⚠️

Big-Oh notation doesn’t care about (most) constant factors. 👆 This is not applicable for exponent statements like

e^{3n}

and

10^n

Example 2

n \in O(n^3)

Proof: Choose

c=1

and set

N=1

📌

Saying that time is

n \in O(n^3)

doesn’t mean it’s slow! Big-Oh is upper bound, so based on it we can say that an algorithm is fast but NOT an algorithm is slow.

Example 3

n^3 +n^2+n \in O(n^3)

Proof: Choose

c=3

and set

N=1

📌

Big-Oh is usually used to indicate the dominating (fastest-growing) term

Table of Important Big-Oh Sets

Smallest to largest (the small one is a subset of the large one ( $smaller \sub larger$ )

Function	Common Name
$O(1)$	Constant
$O(log n)$	Logarithmic
$O(log^2 n)$	Log-squared
$O(\sqrt n)$	Root-n
$O(n)$	Linear
$O(n.log n)$	n log n
$O(n^2)$	Quadratic
$O(n^3)$	Cubic
$O(n^4)$	Quartic
$O(2^n)$	Exponential
$O(e^n)$	Exponential
$O(n!)$	Factorial
$O(n^n)$	ㅤ

$O(n.log n)$ or faster time (smaller functions) are considered efficient

$O(n^7)$ or slower time is considered useless

Of course, in the daily computations , even $O(n^2)$ is bad

Big-Oh is used to indicate the growth, not number of operations, therefore it is used to indicate:

Worst-case running time
Best-case running time
Memory use

Recursion

A recurrence relation is an equation which is defined in terms of itself

Why to use it:

Many natural functions are easily expressed as recurrences
It is often easy to find a recurrence as the solution of a counting problem. Solving the recurrence can be done for many special cases although it is somewhat of an art.

A recurrence relation consists of:

Base case (a.k.a. initial or boundary condition) that terminates the recursion
General condition that breaks the problem into smaller pieces

Example for solving recurrence relation

https://www.youtube.com/watch?v=u-I-qixs8oY

Divide and Conquer (Recursion)

The time complexity is modeled by recurrence relations

The general steps of this paradigm:

Divide into smaller subproblems

Conquer via recursion calls

Combine solutions of subproblems into one for the original problem: Cleanup work and merge results (e.g. like Merge Sort)

📌

The divide-and-conquer technique can be applied to those problems that exhibit the independence principle:

Each problem instance can be divided into a series of smaller problem instances which are independent of each other.

Merge Sort algorithm is the simplest example that uses this strategy

Problem: Counting Inversions in an Array

Giving an array $A$ with $N$ elements, calculate the pairs $(A[i], A[j])$ that meet the following critieria: $i < j$ and $A[i] > A[j]$

To calculate the largest number of inversions in an array of N elements: $\frac {n(n-1)} {2}$

Solution #1: Brute-force

By using two loops (the 2nd loop is nested)
It takes $O(n^2)$ time

Solution #2: Divide & Conquer

(See Stanford lecture)

Resources

Complexity Analysis

A Gentle Introduction to Algorithm Complexity Analysis

Dionysis "dionyziz" Zindros A lot of programmers that make some of the coolest and most useful software today, such as many of the stuff we see on the Internet or use daily, don't have a theoretical computer science background. They're still pretty awesome and creative programmers and we thank them for what they build.

http://discrete.gr/complexity/

cgi.csc.liv.ac.uk

https://cgi.csc.liv.ac.uk/~ped/teachadmin/algor/algor.html

Lecture 19 Asymptotic Analysis

Uploaded by Ajitesh Upadhyaya on 2014-03-13.

https://youtu.be/X8Ba--V4sGA

lecture 20 algorithm analysis

Uploaded by Ajitesh Upadhyaya on 2014-03-13.

https://www.youtube.com/watch?v=q5BMmfGdWtU

Chapter 3: Algorithm Analysis in A Practical Introduction to Data Structures and Algorithm Analysis by Clifford A.

Chapter 14 Sections 14.1 through 14.2 Analysis Techniques in A Practical Introduction to Data Structures and Algorithm Analysis by Clifford A. Shaffer.