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


function factorial(N){
	if(N==1)
		return 1
	else
		return N*factorial(N-1)
}

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, if & only if . 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 fits under

Example

We have an algorithm whose running time is defined as . Let’s try and pick

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

Formal Definition

is the set of all functions that satisfy: There exist positive constants and such that, for all , then

Example 1

Proof: Choose and set the vertical line

⚠️

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

Example 2

Proof: Choose and set

📌

Saying that time is 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

Proof: Choose and set

📌

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 ()

Function	Common Name
	Constant
	Logarithmic
	Log-squared
	Root-n
	Linear
	n log n
	Quadratic
	Cubic
	Quartic
	Exponential
	Exponential
	Factorial
	ㅤ

or faster time (smaller functions) are considered efficient

or slower time is considered useless

Of course, in the daily computations , even 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 with elements, calculate the pairs that meet the following critieria: and

To calculate the largest number of inversions in an array of N elements:

Solution #1: Brute-force

By using two loops (the 2nd loop is nested)
It takes 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.