6DASALGO

Prof. Arcely Napalit | 2077

INTRODUCTION TO ALGORITHM algorithm. For all those problems, where it

is not possible to find the most optimized
Importance of Algorithm solution, an approximation algorithm is
⤷ Algorithmics are a branch of computer science used. Approximate algorithms are the
relevant to most of science, business, and type of algorithms that find the result as
technology. an average outcome of sub outcomes to a
⤷ Algorithms/Algorithmics has come to be problem.
recognized as the cornerstone of computer Example:
science. - For NP-Hard Problems ,
⤷ Computer programs would not exist without approximation algorithms are
algorithms. used - Sorting algorithms are the
⤷ It is useful in developing analytical skills. It is a exact algorithms.
special kind of solution to problems—a procedure c. Serial or Parallel or Distributed
for getting answers in a finite amount of time. Algorithms: In serial algorithms, one
(finite set of instructions) instruction is executed at a time while
⤷ Introduction to Algorithms (Second Edition by parallel algorithms are those in which we
Thomas H. Cormen, Charles E. Leiserson, Ronald divide the problem into subproblems and
L. Rivest, Clifford Stein) execute them on different processors. If
- “an algorithm is any well-defined parallel algorithms are distributed on
computational procedure that takes some different machines, then they are known
value, or set of values, as input and as distributed algorithms.
produces some value, or set of values as 2. Design Method
output.” a. Greedy Method: In the greedy method at
⤷ Various algorithm study techniques include each step, a decision is made to choose
runtime analysis, shortest path, approximate the local optimum, without thinking about
algorithms, random algorithms, compression, and the future consequences.
more. - Local optimum – a solution that is
optimal (either maximal or
Important points of algorithm minimal) within a neighboring set
1. The non ambiguity requirement for each step of of candidate solutions
an algorithm cannot be compromised. Example:
2. The range of inputs for which an algorithm works - Fractional Knapsack, Activity
has to be specified carefully. Selection
3. The same algorithm can be represented in several b. Divide and Conquer: The strategy
different ways. involves dividing the problem into
4. There may exist several algorithms for solving the sub-problem, recursively solving them,
same problem. and then recombining them for the final
answer.
Algorithm Design Techniques Example:
1. Implementation Method - Merge Sort, Quick Sort
a. Recursion or Iteration: recursive algorithm c. Dynamic Programming: Similar to divide
calls itself again and again until a base and conquer, dynamic programming
condition is achieved whereas iterative involves storing results of recursive
algorithms use loops, data structures function calls in a table to avoid redundant
loops to solve any problem. Every computations. The decision to call a
recursive solution can be implemented as function or retrieve values is made
an iterative solution and vice versa. dynamically, reducing overall time
b. Exact or Approximate: Algorithms that are complexity.
capable of finding an optimal solution for
any problem are known as the exact
 Example: - In order for you to know how to write the
- 0-1 Knapsack, subset-sum algorithm efficiently you have to know
problem exactly what each line of code is going to
3. Other Classifications accomplish when the program is
a. Randomized Algorithms: Algorithms that executed.
make random choices for faster solutions - Write the code to execute quickly but can
are known as randomized algorithms also handle the input data that it will
randomized algorithms. receive.
Example: 4. Experiment
- Randomized Quick Sort . - Once it is designed and coded, go back
b. Classification by complexity: Algorithms and experiment with different variables in
that are classified on the basis of time the algorithm.
taken to get a solution of any problem for - Try and enter data that will make it fail or
input size. This analysis is known as time try and re-write the code to work it out
complexity analysis. most efficiently.
Example: - Experimentation is really just another step
- Some algorithms take O(n), while of analyzing the algorithm.
some take exponential time.
COMPLEXITY ANALYSIS
ANALYZING AND CODING AN ALGORITHM Criteria/Characteristics of Algorithms
4 Stages of Algorithm Analysis and Design ⤷ All algo must satisfy the ff criteria/characteristics:
1. Design 1. Input: zero or more quantities are extremely
- Identify the problem and thoroughly supplied
understand it. 2. Output: at least one quantity is produced
- Consult everybody who has an interest in 3. Definiteness: each instruction is clear and
the problem. unambiguous
- After obtaining the input, break down the 4. Finiteness: for all input cases it terminates after
problem into stages and calculate the finite number of steps
outcome at each step so that the next 5. Effectiveness: every instruction must be very
step can occur. Then, you will create a basic so that it can be carried out, in principle, by
flowchart and/or use pseudocode to a person by using only pencil and paper.
address the specific challenges of
managing the flow of operations within the Four Research areas of study in algorithms
code. 1. Design of algorithms - algorithmic strategies
2. Analyze 2. Validation of algorithms - proof techniques
- After creating the basic framework, it’s 3. Analysis of algorithms - computing time and
time to start analyzing how efficient the storage requirements for an algorithm
code is in solving the problem. 4. Testing of programs - software testing, test cases
- This is a step that some programmers like design and debugging.
to attack after they have coded the
algorithm and run it through the compiler. Problems - Algorithm Specification
Others prefer to examine it prior to writing - The process of translating a solution of a problem
the code and analyze results based on into an algorithm. This can be done in 3 ways:
their expectations from the design stage. 1. Steps or instructions can be written by
- Evaluate algorithm efficiency by analyzing using a natural language like English, to
its time and space complexity with varying ensure that the resulting instructions are
data structure sizes. The problem here is definite.
determining the point of maximum 2. Flowchart - Graphic representation can
efficiency and acceptable results for the also be used for specifications however,
project. they work well only if the algorithm is
3. Implement simple and simple.
- Writing and coding the algorithm is the 3. Pseudo code - most preferred option to
next step in the process. specify an algorithm
Complexity Cases ⤷ Frequency count - is the number of times
a. Space Complexity: the amount of memory it an instruction is executed in the execution
needs to run to completion. of a program.
⤷ S(P) = c + Sp (instance characteristics)
- c — space for (instructions, Example for Space & Time Complexity
simple variables, fixed size) public int sumArray(int[] array) {
- Sp — variable part depends upon int size = 0; (line 1)
problem instance characteristics int sum = 0; (line 2)
⤷ Bytes size in Java data types
for(int i = 0; i < size; i++){
Primitive Type Bytes required sum += array[i]; (line 3)
for Java
return sum; (line 4)
Primitive
}
boolean
1 int avg = sum/size; (line 5)
byte return avg; (line 6)
}
char
2
short ⤷ Space Complexity
- int = 4 * 4 bytes (size, sum, i, avg)
int - int[ ] = n * 4 bytes (array)
4 - Aux = 4 bytes
float - S(P) = 4n + 16 bytes
- Total S(P) = 4n + 20 bytes
long
8
double ⤷ Time Complexity
- for loop = n
- lines = 6
b. Time Complexity: the amount of computer time it
- 6 * n = 6n
needs to run the completion.
- Big O(6n)
⤷ T(P) = compile time + run time (execution
- Big O(n)
time)
- compile time — constant or same
Three types of analysis that we perform on a particular
program is executed many time
- run time of a program (tp) — algorithm.
depends upon instances of the - Best Case: In which we analyze the performance
characteristics. of an algorithm for the input, for which the
- Total Computation Time = time algorithm takes less time or space.
required to execute the instruction - Worst Case: In which we analyze the performance
* number of times the instruction of an algorithm for the input, for which the
is executed algorithm takes a long time or space.
Example: - Average Case: In which we analyze the
- Frequency count performance of an algorithm for the input, for
⤷ Time required to execute the instruction which the algorithm takes time or space that lies
depends upon: between best and worst case.
- speed of processor
- instruction set of the machine Time-complexity can be expressed using the three terms
learning called Asymptotic Notations.
- time required (processor cycles) 1. Big-O Notation (Ο) – specifically describes the
to execute an instruction worst case scenario.
- compiler used to translate high 2. Omega Notation (Ω) – specifically describes the
level instructions to machine best case scenario.
language 3. Theta Notation (θ) – This notation represents the
average complexity of an algorithm.
Note: But most times, we will use the Big O notation
because it will give us an upper limit of the execution time. General Rule for Big O
1. Ignore constants:
Common Big O functions and how to identify them - 5n = O(n)
2. Certain terms dominates others
Big O(1) Constant time Declaration,
algorithms or assignment, - O(1) < O(log n)
operations are mathematical - O(log n) < O(n)
considered to have a operations - O(n) < O(n log n)
constant time A statement - O(n log n) < O(n2)
complexity when that can only - O(n2) < O(2n)
they are not execute once - O(2n) < O(n!)
dependent on the
3. Constants do not matter in Big O notation.
size of the input
data, and the time - O(3n) = O(n)
required to run the - O(20) = O(1)
same every single - O(4n2) = O(n2)
time. 4. Smaller terms does not matter in Big O notation
- O(n + 5) = O(n)
Big O(n) Linear time A single
- O(20n + 20) = O(n)
complexity can be looping
identified by the fact statement - O(n2+ 40n + 30) = O(n2)
that the number of -
operations increases 5. Big O notation short hands
linearly with the size - Arithmetic operations are constant
of the input. - Variable assignment is constant
- Accessing elements in an array
Big O (n2) Quadratic time, An inner and
- Loop, the complexity depends on the loop
Algorithms or outer looping
operations that have statement. times of what ever happen inside
quadratic time are
identified as having HUFFMAN CODING
to perform linear
⤷ Huffman coding/encoding is an algorithm for doing
time operations for
each value in an data compression and it forms the basic idea
input, not just for the behind file compression.
input itself. ⤷ It can be used for finding solutions to the given
problem statement.
Big O(log n) Logarithmic Time ⤷ Developed by David Huffman in 1951, this
occurs when at each technique is the basis for all data compression
subsequent step in
the algorithm, the and encoding schemes
time is decreased at ⤷ It is a famous algorithm used for lossless data
a magnitude encoding
inversely ⤷ It follows a Greedy approach, since it deals with
proportional to N. generating minimum length prefix-free binary
this generally codes
happens in Binary
Search Algo.
Two Types of Encoding
Big O(n log Linearithmic Time Quick, heap ⤷ Fixed-length encoding (FLC): Every character is
n) Complexity. One merge assigned a binary code using same number of
example of an algo bits. Thus, a string like “aabacdad” can require 64
that runs with this bits (8 bytes) for storage or transmission,
time complexity
assuming that each character uses 8 bits.
Big O(2n) Exponential Time ⤷ Variable Length encoding (VLC): this scheme
Complexity uses a variable number of bits for encoding the
characters depending on their frequency in the
Big O(2!) Factorial Time given text.
Complexity
 HUFFMAN TREE
Algorithm for creating Huffman Tree a e A1 b
- Step 1: Create a leaf node for each character and
build a min heap using all the nodes (The Frequency 4 4 5 7
frequency value is used to compare two nodes in ˃ A2(8) = a + e/ 4 + 4
min heap)
- Step 2: Repeat Steps 3 to 5 while heap has more
A1 b A2
than one node
- Step 3: Extract two nodes, say x and y, with Frequency 5 7 8
minimum frequency from the heap
˃ A3(12) = A1 + b/ 56 + 7
- Step 4: Create a new internal node z with x as its
left child and y as its right child. Also
frequency(z)= frequency(x)+frequency(y) A2 A3
- Step 5: Add z to min heap
- Step 6: Last node in the heap is the root of Frequency 8 12
Huffman tree ˃ A4(20) = A2 + A3/ 8 + 132

Definition of Terms Tree

- fixed-length code ⤷ Should start with the last node
- Each codeword has the same length. ⤷ Right node = 1
- always uniquely decipherable ⤷ Left node = 0
- These do not always give the best
compression so we prefer to use variable
length codes.
-
- variable-length code
- Each codeword may have different
lengths.
- Prefix Code
- A code is called a prefix (free) code if no
codeword is a prefix of another one.

Table
a b c d e
⤷ Go back to table
Frequency (20) 4 7 3 2 4
NO PRIORITY QUEUE
FLC (3 bits) 000 001 010 011 100
a b c d e
VLC 00 11 101 100 01
Frequency (20) 4 7 3 2 4
4(2) + 7(2) + 3(3) + 2(3) + 4(2) = 45
˃ A1(11) = a + b/ 4 + 7
˃ 4+7+3+2+4 = 20 * 3 bits = 60
˃ 45/60 = 0.75 or 75
100 – 75 = 25 A1 c d e
Savings = 25%
Frequency (20) 11 3 2 4
Arrange ˃ A2(14) = A1 + c / 11 + 3
⤷ Arrange in ascending order
d c a e b A2 d e

Frequency 2 3 4 4 7 Frequency (20) 14 2 4

˃ A1(5) = d + c/ 2 + 3 ˃ A3(16) = A2 + d/ 14 + 2
 - An optimal solution of the problem would
A3 e
be a feasible solution which gives the
Frequency (20) 16 4 maximum profit.
˃ A4(20) = A3 + e/ 16 + 4
Greedy Algorithm
- Adopted to determine how the next job is selected
Tree
for an optimal solution.
1. Step 1: Sort all the given jobs in
decreasing order of their profit.
2. Step 2: Check the value of the maximum
deadline.
- Draw a Gantt chart where
maximum time on Gantt chart is
the value of the maximum
deadline.
3. Step 3: Pick up the jobs one by one.
- Put the job on the Gantt chart as
far as possible from 0 ensuring
that the job gets completed before
a = 0000 4(4) its deadline.
b = 0001 7(4)
c = 001 3(3) Example
d = 01 2(2)
e=1 4(1) Jobs J1 J2 J3 J4 J5 J6

Deadlines 5 3 3 2 4 2
⤷ Total = 61
61/60 = 1.02 or 102 Profits 300 250 275 400 220 100
100 – 102 = –2
⤷ Savings = –2%
Step 1: Sort in Descending order (profit)

JOB SCHEDULING WITH DEADLINES Jobs J4 J1 J3 J2 J5 J6

- It is the sequencing of jobs on a single processor Deadlines 2 5 3 3 4 2
with deadline constraints.
- You are given a set of jobs. Profits 400 300 275 250 220 100
- Each job has a defined deadline and
some profit associated with it. Step 2: Draw Gantt Chart with units n = 5 (0 – 5)
- The profit of a job is given only when that 0 1 2 3 4 5
job is completed within its deadline.
- Only one processor is available for
processing all the jobs.
- The processor takes one unit of time to Step 3: Take each job one by one in the order they appear
complete a job in Step 1. We place the job on Gantt chart as far as
- The problem states, “How can the total profit be possible from 0
maximized if only one job can be completed at a 0 1 2 3 4 5
time?”
J2 J4 J3 J5 J1
- Solution:
- A feasible solution would be a subset of
jobs where each job of the subset gets Answer the following questions:
completed within its deadline. 1. Write the optimal schedule that gives maximum
- Value of the feasible solution would be the profit.
sum of profit of all the jobs contained in a. J2, J4, J3, J5, J1
the subset. 2. Are all the jobs completed in the optimal
schedule?
 a. Jobs are not completed in optimal
schedule, J6 could not be completed
within its deadline.
3. What is the maximum earned profit?
a. Maximum earned profit =
220+400+275+250+300 = 1445 units