# Algorithms

Algorithms
Overview

An algorithm is a finite sequence of precise instructions for performing a computation or for solving a problem.

Algorithm for finding the maximum (largest) value in a finite sequence of integers: Solution Steps:

1. Set the temporary maximum equal to the first integer in the sequence.
2. Compare the next integer in the sequence to the temporary maximum, and if it is larger than the temporary maximum, set the temporary maximum equal to this integer.
3. Repeat the previous step if there are more integers in the sequence.
4. Stop when there are no integers left in the sequence. The temporary maximum at this point is the largest integer in the sequence.

Properties of an Algorithm

1. Input
2. Output
3. Definitiveness
4. Correctness
5. Finiteness
6. Effectiveness
7. Generality
Searching Algorithms

The problem of locating an element in an ordered list occurs in many contexts. For instance, a program that checks the spelling of words searches for them in a dictionary, which is just an ordered list of words. Problems of this kind are called searching problems.

Linear Search

procedure linear search(x: integer, a1, a2, . . . , an: distinct integers)
i := 1
while (in and x != a[i] )
i = i + 1
if in then location := i
else location := 0
return location {location is the subscript of the term that equals x, or is 0 if x is not found}

Binary Search

This algorithm can be used when the list has terms occurring in order of increasing size (for instance: if the terms are numbers, they are listed from smallest to largest; if they are words, they are listed in lexicographic, or alphabetic, order). This second searching algorithm is called the binary search algorithm.

Sorting Algorithms
Bubble Sort

Psuedocode

``` ```

``````
procedure bubblesort(a1, a2, . . . , an: real numbers n ≥ 2)
for ( i := 1 to n-1)
for ( j to n-1)
if a  j > aj+1 then interchange aj and aj+1
{a1, . . . ,a n is in increasing order}
``````
``` ```

Insertion Sort

procedure insertionsort(a1, a2, . . . , an: real numbers n ≥ 2)
for ( j := 2 to n)
i := 1
while a j > ai
i := i+1
m := aj
for k := 0 to ji − 1
ajk := aj k − 1
ai := m
{a1, . . . , an}

Try Sorting Algorithms
Sort Types:
Choose Speed:
Fill the input box with sample values:

Greedy Algorithms

Algorithms that make what seems to be the best choice at each step are called greedy algorithms.
Greedy Change-Making Algorithm

procedure change(c1, c2, . . . , cn: value of denominations where c1 > c2 > . . . , cn : n is a positive integer)
for ( i := 1 to r)
di := 0 {di counts the number of denominations ci used
while nci
di := di + 1 {add a coin of denomination ci }
n := n - ci
di is the number of coins of denominations in ci in change for i = 1, 2, 3

LEMMA 1

If n is a positive integer, then n cents in change using quarters, dimes, nickels, and pennies using the fewest coins possible has at most two dimes, at most one nickel, at most four pennies, and cannot have two dimes and a nickel. The amount of change in dimes, nickels, and pennies cannot exceed 24 cents.

THEOREM 1

The greedy algorithm produces change using the fewest coins possible.

Greedy Algorithm for Scheduling Talks

procedure schedule(s1s2 ≤ . . . , sn: start time of talks
e1e2 ≤ . . . , en : n ending times of talks)
sort talks by finish time and reorder so that e1e2 ≤ . . , en
S := 0
for ( i := 1 to n)
if talk j is compatible with S
S := S &union; {talk j}
return S{ S is the set of talks produced}

The Halting Problem

The Halting Problem is Unsolvable

Test Yourself!
1. What is an algorithm?
1. None of above
2. A function executing a task to solve a problem
3. 1. Finite sequence of precise instructions for performing a computation or for solving a problem.
4. A excerpt of code that can be run induvidually to perform computation
2. Which of these is a property of an algorithm
1. All of them
2. Effectiveness
3. Finiteness
4. Definitiveness
3. The minimum runtime for a linear and binary search algorithm?
1. O(n), O(n)
2. O(n), O(log n)
3. O(log),O(n)
4. O(log n), O(log n)
4. Bubble sort is a type of:
1. Algorithm with highest space complexity
2. Brute-Force algorithm
3. Optimized Algorithm
4. An algorithm that works only on positive numbers
5. Insertion Sort has lower running time as compared to bubble sort?
1. False
2. True
6. Greedy algorithms are also used widely in memory management. Given a list of blocks, in which the sizes are { 100, 150, 180, 200, 300 }, how would a greedy algorithm (grab the smallest block that works first) fit processes with sizes {10, 222, 198, 147, 178 }?
1. process 1: block 1, process 2: block 5, process 3: block 4, process 4: block 3, process 5: block 2
2. process 1: block 5, process 2: block 2, process 3: block 4, process 4: block 3, process 5: block 1
3. process 1: block 1, process 2: block 2, process 3: block 4, process 4: block 3, process 5: block 5
4. process 1: block 1, process 2: block 5, process 3: block 4, process 4: block 2, process 5: block 3
7. An example of set of coin denominations for which the greedy algorithm does not yield an optimal solution for change of 6 is
1. { 1, 3, 3}
2. { 1, 4, 2}
3. { 1, 3, 4 }
8. Binary search only works on sorted array whereas linear search works on sorted as well as unsorted array.
1. False
2. True
9. You need to have complete array into memory for linear search but binary search reduces the in-memory usage.
1. True
2. False

1. c; 2. a; 3. b; 4. b; 5. a; 6. d; 7. c; 8. b; 9. a;

The Growth of Functions
Big-O Notation

DEFINITION

Let f and g be functions from the set of integers or the set of real numbers to the set of real numbers.We say that f(x) is O(g(x)) if there are constants C and k such that |f(x)| ≤ C|g(x)|whenever x > k.
(This is read as "f(x) is big-oh of g(x).")
Example 1 Show that f(x) = 7x2 is O(x3). Take C = 1 and k = 7 as witnesses to establish that 7x2 is O(x3).
When x > 7, 7x2 < x3.
Consequently, we can take C= 1 and k = 7 as witnesses to establish the relationship 7x2 is O(x3).
Alternatively, when x > 1, we have 7x2 < 7x3, so that C = 7 and k = 1 are also witnesses to the relationship 7x2 is O(x3).

Big-O Estimates for Some Important Functions

THEOREM 1

Let f(x) = an xn + an − 1xn − 1 +...+ ax + a, where a0, a1... an − 1, an are real numbers. Let f(x) = anxn + an − 1xn −1 +...+ ax + a, where a0, a1... an − 1, an are real numbers.
Then f(x) is O(xn).
A Display of the Growth of Functions Commonly Used in Big-O Estimates.

The Growth of Combinations of Functions

THEOREM 2

Suppose that f1(x) is O(g1(x)) and that f2(x) is O(g2(x)).
Then (f1 + f2) (x) is O (max(|g1 (x)|, |g2(x)|)).

COROLLARY 1

Suppose that f1(x) and f2(x) are both O(g(x)).
Then (f1 + f2)(x) is O(g(x)).

THEOREM 3

Suppose that f1(x) is O(g1(x)) and f2(x) is O(g2(x)).
Then (f1f2) (x) is O(g1(x)g2(x)).

Big-Omega and Big-Theta Notation

DEFINITION 2

Let f and g be functions from the set of integers or the set of real numbers to the set of real numbers.We say that f(x) is Ω; (g(x) if there are positive constants C and k such that |f(x)| ≥ C|g(x)| whenever x > k.
(This is read as "f(x is big-Omega of g(x.")
Example: Show that f(x) = x3 is Ω(7x2).

• In the above example we have proved the exact opposite.
• Consider the same witness C =1 and k = 7 to establish this relation
• Just by turning in inequality, we can say that f(x) is Ω (7x2) we can say that f(x is Ω(7x2)

DEFINITION 3

Let f and g be functions from the set of integers or the set of real numbers to the set of real numbers.We say that f(x) is θ(g(x)) if f(x) is O(g(x) and f(x) is Ω(g(x)). When f(x)is Θ(g(x)) we say that f is big-Theta of g(x), that f(x) is of order g(x), and that f(x) and g(x) are of the same order.
Example: Show that 3x2+ 8x log x is Θ(x2).

• Because 0 ≤ 8x log x ≤ 8x2, it follows that 3x2 + 8x log x ≤ 11x2 for x > 1.
• Consequently, 3x2 + 8x log x is O(x2).
• Clearly, x2 is O(3x2 + 8x log x). Let f and g be functions from the set of integers or the set of real numbers to the set of real numbers.We say that f(x) is Θ(g(x)) if f(x) is O(g(x)) and f(x) is Ω(g(x)). When f(x) is Θ(g(x)) we say that f is big-Theta of g(x), that f(x) is of order g(x), and that f(x) and g(x) are of the same order.
Example: Show that 3x2 + 8x log x is Θ(x2).
• Because 0 ≤ 8x log x ≤ 8x2, it follows that 3x2 + 8x log x ≤ 11x2 for x > 1.
• Consequently, 3x2 + 8x log x is O(x2).
• Clearly, x2 is O(3x2 + 8x log x).
• Consequently, 3x2 + 8x log x is Θ(x2).

THEOREM 4

Let f(x) = anxn + an-1xn − 1 +...+ a1 + a0, where a0, a1, . . . , an are real numbers with an ≠ 0. an − 1 x n - 1 + . . . + a1x + a0, where a0, a1, . . . , an are real numbers with an 0.
Then f(x) is of order xn.

More on the Growth of Functions

Algorithms class lecture on the growth of functions.

Test Yourself!
1. The Big – O for n! will be:
1. n2
2. nn
3. n3
4. n
2. Which of the following functions is O(x)?
1. f(x) = x2 + 10x + 2
2. f(x) = 10
3. f(x) = xx
3. x2 + 4x + 17 is O(x3) and x3 is not O(x2 + 4x + 17)
1. False
2. True
4. What is the Big-O estimate for f(x) = (x + 1) log(x2 + 1) + 3x2?
1. n2
2. n3
3. nn
4. nn
5. What is the witness for f (n) = 3n log(n!) + (n2 + 3)log n?
1. n>2
2. n>log 2
3. n >3
4. n>=2
6. n < 2n whenever n is a positive integer.
1. False
2. True

1. b; 2. b; 3. a; 4. a; 5. a; 6. b;

Complexity of Algorithms
Time Complexity

An analysis of the time required to solve a problem of a particular size involves the time complexity of the algorithm.The time complexity of an algorithm can be expressed in terms of the number of operations used by the algorithm when the input has a particular size.
In most of the cases we consider the worst-case time complexity of an algorithm. This provides an upper bound on the number of operations an algorithm uses to solve a problem with input of a particular size.

Complexity Analysis of Some Algorithms
Example: Describe the time complexity of an Algorithm for finding the maximum element in a finite set of integers. An analysis of the time required to solve a problem of a particular size involves the time complexity of the algorithm. The time complexity of an algorithm can be expressed in terms of the number of operations used by the algorithm when the input has a particular size.
In most of the cases we consider the worst-case time complexity of an algorithm. This provides an upper bound on the number of operations an algorithm uses to solve a problem with input of a particular size.

Example: Describe the time complexity of an Algorithm for finding the maximum element in a finite set of integers.

• Count the number of comparisons
• There are n comparisons while entering the for loop, one extra when i becomes equal to n
• There are n - 1 comparison in the if loop to check the maximum element
• The total comparison will be n + (n − 1)
2(n − 1) − 1 = 2n − 1 comparisons are made There are n comparisons checking the termination condition of the for loop.
• There are n − 1 comparison in the if statement to check the maximum element.
• The total comparisons will be n + (n − 1) = 2n − 1.
• Hence, the complexity will be Θ(n)
Complexity of Matrix Multiplication

The definition of the product of two matrices can be expressed as an algorithm for computing the product of two matrices. Suppose that C = [cij] is the mn matrix that is the product of the m ✕ k matrix A = [aij] and the kn matrix B = [bij ]. The definition of the product of two matrices can be expressed as an algorithm for computing the product of two matrices. Suppose that C = [cij] is the m ✕ n matrix that is the product of the m ✕ k matrix A = [aij] and the kn matrix B = [bij ].
Pseudocode Matrix Multiplication

Complexity Calculation How many additions of integers and multiplications of integers are used by the matrix multiplication algorithm to multiply two n * n matrices.

• There are a total of n2 elements in the product matrix.
• Each element requires n multiplications and n − 1 additions. How many additions of integers and multiplications of integers are used by the matrix multiplication algorithm to multiply two n * n matrices.
• Hence, the complexity of matrix multiplication is O(n3). Hence, the complexity of matrix multiplication is O(n3).

Algorithm Paradigms is a general approach based on a particular concept that can be used to construct algorithms for solving a variety of problems. Greedy Algorithm, Divide-and-Conquer Algorithm, Brute Force Algorithm, and Probabilistic Algorithm are algorithm paradigms.

Example: Brute Force Algorithms
A brute-force algorithm is solved in the most straightforward manner, without taking advantage of any ideas that can make the algorithm more efficient. Construct a brute-force algorithm for finding the closest pair of points in a set of n points in the plane and provide a worst-case estimate of the number of arithmetic operations.

Pseudocode for Brute-Force Closest Point Algorithm

Complexity of the Algorithm
The algorithm loops through n(n - 1)/2 pairs of points, computes the value (xj - xi)2+ (yj - yi)2and compares it with the minimum, etc. So, the algorithm uses Θ(n2) The algorithm loops through n(n − 1)/2 pairs of points, computes the value (xjxi)2 + (yjyi)2 and compares it with the minimum, etc. So, the algorithm uses Θ(n2) arithmetic and comparison operations.

Understanding the Complexity of Algorithms
Commonly Used Terminology for the Complexity of Algorithms.
Complexity Terminology
Θ(1) Constant Complexity
Θ(log n) Logarithmic Complexity
Θ(n) Linear Complexity
Θ(n log n) Linearithmic complexity
Θ(nb) Polynomial complexity
Θ(bn) where b >1 Exponential Complexity
Θ(n!) Factorial Complexity

Tractable problem: a problem for which there is a worst-case polynomial-time algorithm that solves it
Intractable problem: a problem for which no worst-case polynomial-time algorithm exists for solving it
Solvable problem: a problem that can be solved by an algorithm
Unsolvable problem: a problem that cannot be solved by an algorithm

Test Yourself!
1. Brute for algorithms have
1. High space complexity
2. High time complexity
3. Both high time and space complexity
4. Low time complexity
2. The brute force algorithm for matrix multiplication has
1. Polyarithmatic complexity
2. Polynomial time complexity
3. Linear time complexity
4. Factorial complexity
3. What is the worst case comparisons for Bubble sort?
1. (n)(n)/2
2. n(n+1)/2 -1
3. (n-1)(n-1)/2
4. (n-1)n/2
4. The order in which n>2 matrices are multiplied also determines the cruntime of the algorithm?
1. False
2. True
5. In which order should the matrices A1, A2, and A3—where A1 is 30 × 20, A2 is 20 × 40, and A3 is 40 × 10, all with integer entries—be multiplied to use the least number of multiplications of integers?
1. A1(A2A3)
2. (A1A2)A3
3. (A1 A3) A2
6. What is the least possible multiplication for matrices A1, A2, and A3—where A1 is 30 × 20, A2 is 20 × 40, and A3 is 40 × 10, all with integer entries?
1. 14000
2. 10000
3. 20000
4. 36000