Design And Analysis of Algorithms
Introduction (The Role of Algorithms)
The hardware, the speed of the processor, the compiler, and the programming language are all
important factors in determining the performance of a program. However, the algorithm that you
use is the most important factor. This is because the algorithm determines how the hardware will
be used and how fast the program will run.
Asymptotic Complexity (Part 1)
In algorithm analysis, we count the number of steps or operations as a function of input size.
Different operations take different time or different number of cycles on the processor. The relation
between operations and time is not always straightforward, so operations may not necessarily take
the same time. The synthetic complexity that we use in analyzing algorithms tells you how many
times an algorithm takes as long as it would if all operations took the same amount of time.
Loading something from l1 cache into the CPU or CPU registers can take two or three cycles,
while loading from main memory can take depends on the processor and on memory. Asymptotic
notation is an approximation, but it gives you a very good idea about an algorithm and allows you
to compare different algorithms. Now what's the rationale behind deleting lower order terms?
Because there are too small compared to the higher order terms, as n increases the difference
between lower order term and higher order term becomes bigger.
An on average an operation takes ten cycles, so this processor will execute 10 power 8 operations
per second. For an o of n squared, how big should the input be in order for the program to get
executed within one second? 10 power 4.
The algorithm, the choice of the algorithm, is the major factor that affects performance. In fact, we
will be doing an assignment in which you will implement multiple algorithms. The formula that
we will be using is number of operations in this case is going to be 2 power 50 and the speed of
the processor is 10 power 8. To power 50 equals 2 power 20 times 2 power 30 divided by 10 power
8. 1 mega is two power 20 which is approximately 10 power 6 and 1 giga is about 10 power 9. The
time in hours is equal to 10 power 7 divided by you know 3600.
Finding an efficient algorithm for solving a problem is not a luxury. It is not just you know to
speed up the program a little bit sometimes. Sometimes if you do not have an efficient enough
algorithm, it will not complete within your lifetime. If you are trying to run an exponential
algorithm with an input size of a hundred right in then this is not going to complete in your lifetime
so if you run it on a computer that is a million times faster it will still be a billion years right. A
subset will include or exclude an element so for each element if you have you know 1, 2, 3 all the
way to n each element has two possibilities you either take it or not in the subset. The algorithm
will have to be exponential so why 2 power n can you have an argument why the total number of
subsets is 2 powers. This is a problem that looks innocent but it's an NP-complete problem and so
to solve this, you write a program that looks at all possible subsets and if n equals a hundred then
your program will take billions of years to run. Ok, so now let's look more closely at an example
, that is look at the familiar start our algorithm analysis with a familiar example to start our
algorithm analysis:
Two is currently stored in a temporary location. After shifting five, we have checked all elements
to the left of the separator. The two will be inserted to the right of the separator, resulting in the
array: 5 4 4 6 1 2.
Insertion sort takes an array and size n and follows a set of steps to insert elements: Loop through
i from 1 to n-1. Determine the element that needs to be inserted. Compare the element to the
elements on its left, shifting them right if necessary. Insert the element in its appropriate position.
Note that indentation in the pseudocode is significant. Lack of braces may cause confusion for the
compiler but is done for program readability.
There is a more compact way of writing this code. Instead of using the break statement, we can
check if the value of a at j is greater than 10 in the loop condition. It can be written as:
for i = 1 to n - 1
temp = a[i]
for j = i - 1 to 0 and a[j] > 10
a [j + 1] = a[j]
a [j + 1] = temp
In algorithm analysis, we can compute the lower and upper bounds for the running time of an
algorithm. The lower bound using the omega notation is the running time that the actual running
time will be greater than or equal to omega(n). The upper bound, using the big O notation, is O(n²).
Thus, the actual running time falls between omega(n) and O(n²). It should be noted that the big O
notation denotes the upper bound of the running time. When we say that the running time is O(n²),
it means that the running time is bounded by n². We use the theta notation to calculate the precise
asymptotically precise running time.
To compute a sum, we need to establish a mathematical relation between i and the number of
executions of the inner loop. When i equals 1, we do one shift. When i equals 2, we do two shifts.
What is the maximum value of i if n minus one equal i? This is equivalent to asking what the value
of the arithmetic series is.
Asymptotic Complexity (Part 2)
Algorithm analysis involves counting operations. Whether an algorithm is considered lucky or
unlucky is relative and can vary depending on other algorithms. For example, for quicksort, if the
input is sorted and there is no randomization of the pivot, the worst-case running time of the
algorithm will be t(n) = O(n^2).
Big O represents an upper bound and can be thought of as less than or equal to. Some parts of the
algorithm do not require precise analysis. If the algorithm can be divided into three sections that
are executed sequentially, analyzing one section may be enough. For instance, if section A is
analyzed and found to be Θ(n^2), the other two sections do not need to be analyzed if it can be
said that one is Ω(n^2) and the other is O(n^2).
Introduction (The Role of Algorithms)
The hardware, the speed of the processor, the compiler, and the programming language are all
important factors in determining the performance of a program. However, the algorithm that you
use is the most important factor. This is because the algorithm determines how the hardware will
be used and how fast the program will run.
Asymptotic Complexity (Part 1)
In algorithm analysis, we count the number of steps or operations as a function of input size.
Different operations take different time or different number of cycles on the processor. The relation
between operations and time is not always straightforward, so operations may not necessarily take
the same time. The synthetic complexity that we use in analyzing algorithms tells you how many
times an algorithm takes as long as it would if all operations took the same amount of time.
Loading something from l1 cache into the CPU or CPU registers can take two or three cycles,
while loading from main memory can take depends on the processor and on memory. Asymptotic
notation is an approximation, but it gives you a very good idea about an algorithm and allows you
to compare different algorithms. Now what's the rationale behind deleting lower order terms?
Because there are too small compared to the higher order terms, as n increases the difference
between lower order term and higher order term becomes bigger.
An on average an operation takes ten cycles, so this processor will execute 10 power 8 operations
per second. For an o of n squared, how big should the input be in order for the program to get
executed within one second? 10 power 4.
The algorithm, the choice of the algorithm, is the major factor that affects performance. In fact, we
will be doing an assignment in which you will implement multiple algorithms. The formula that
we will be using is number of operations in this case is going to be 2 power 50 and the speed of
the processor is 10 power 8. To power 50 equals 2 power 20 times 2 power 30 divided by 10 power
8. 1 mega is two power 20 which is approximately 10 power 6 and 1 giga is about 10 power 9. The
time in hours is equal to 10 power 7 divided by you know 3600.
Finding an efficient algorithm for solving a problem is not a luxury. It is not just you know to
speed up the program a little bit sometimes. Sometimes if you do not have an efficient enough
algorithm, it will not complete within your lifetime. If you are trying to run an exponential
algorithm with an input size of a hundred right in then this is not going to complete in your lifetime
so if you run it on a computer that is a million times faster it will still be a billion years right. A
subset will include or exclude an element so for each element if you have you know 1, 2, 3 all the
way to n each element has two possibilities you either take it or not in the subset. The algorithm
will have to be exponential so why 2 power n can you have an argument why the total number of
subsets is 2 powers. This is a problem that looks innocent but it's an NP-complete problem and so
to solve this, you write a program that looks at all possible subsets and if n equals a hundred then
your program will take billions of years to run. Ok, so now let's look more closely at an example
, that is look at the familiar start our algorithm analysis with a familiar example to start our
algorithm analysis:
Two is currently stored in a temporary location. After shifting five, we have checked all elements
to the left of the separator. The two will be inserted to the right of the separator, resulting in the
array: 5 4 4 6 1 2.
Insertion sort takes an array and size n and follows a set of steps to insert elements: Loop through
i from 1 to n-1. Determine the element that needs to be inserted. Compare the element to the
elements on its left, shifting them right if necessary. Insert the element in its appropriate position.
Note that indentation in the pseudocode is significant. Lack of braces may cause confusion for the
compiler but is done for program readability.
There is a more compact way of writing this code. Instead of using the break statement, we can
check if the value of a at j is greater than 10 in the loop condition. It can be written as:
for i = 1 to n - 1
temp = a[i]
for j = i - 1 to 0 and a[j] > 10
a [j + 1] = a[j]
a [j + 1] = temp
In algorithm analysis, we can compute the lower and upper bounds for the running time of an
algorithm. The lower bound using the omega notation is the running time that the actual running
time will be greater than or equal to omega(n). The upper bound, using the big O notation, is O(n²).
Thus, the actual running time falls between omega(n) and O(n²). It should be noted that the big O
notation denotes the upper bound of the running time. When we say that the running time is O(n²),
it means that the running time is bounded by n². We use the theta notation to calculate the precise
asymptotically precise running time.
To compute a sum, we need to establish a mathematical relation between i and the number of
executions of the inner loop. When i equals 1, we do one shift. When i equals 2, we do two shifts.
What is the maximum value of i if n minus one equal i? This is equivalent to asking what the value
of the arithmetic series is.
Asymptotic Complexity (Part 2)
Algorithm analysis involves counting operations. Whether an algorithm is considered lucky or
unlucky is relative and can vary depending on other algorithms. For example, for quicksort, if the
input is sorted and there is no randomization of the pivot, the worst-case running time of the
algorithm will be t(n) = O(n^2).
Big O represents an upper bound and can be thought of as less than or equal to. Some parts of the
algorithm do not require precise analysis. If the algorithm can be divided into three sections that
are executed sequentially, analyzing one section may be enough. For instance, if section A is
analyzed and found to be Θ(n^2), the other two sections do not need to be analyzed if it can be
said that one is Ω(n^2) and the other is O(n^2).
