Greedy Algorithms

Question 1

Scheduling Problem

Answer 1

Input: One array has start times S[1.n], S[i] and then other array has end times F[1..n], F[i]

Output largest mutually compatible set of activities, maximize it by evaluating

You are maximizing the total amount of activities with out overlapping

Question 2

Scheduling Problem Structure

Answer 2

Can look at this greedy algorithm with the view of dynamic programming in which case we start with two index of schedule.

We define Pi,j to be the set of activies between the end of i and the start of j, these are just indexes stored. With this set we then find the set again between a certain i, j and so on.

Recursion LEMMA:
A[i,j] defines size of optimal solution for Pi,j

for every pi,j not = 0 it is that

A[i,j] = max k in the set Pi,j then A[i,k] + A[k+j] + 1

checking largest fit then the index in between i to k then j to i and also adding the k that you are adding

Dynamic Programming Time complexity for this is O(n^3)

Question 3

Schedule problem greedy

Answer 3

Can make a Local optimal solution that can lead to a global optimal solution

Start by knowing there exist an optimal solution that contains first activity

To prove this , lets have a set of an optimal solution so that means they are not overlapping

the min value of these indexes if k and we know that k is after 1 since 1 not in the set of optimal solution what we could do is just replace k with 1 in the solution now would be
——– —— —— —

So in algo we just store the end time of first and see where they overlap

Question 4

Schedule Algorithm

Answer 4

optscheduling(S[1..n],F[1..n])

ans = 1
last = 1
for i = 2 to n do
if S[i] >= F[last] then
ans = ans + 1
last = i
return ans

Question 5

Schedule Time Complexity

Answer 5

Time complexity clear O(n)
If we sort by finish time it is O(logn)

Question 6

Huffman Coding Background

Answer 6

Compression technique to reduce size of data.

You have a bunch of ASCII 8 bit values we want to turn this into our code to decrease the 8*n bits.

EX: BCCABBDDAECCBBAEDDCC

store array of frequency

only representing 5 letters do we really need 8 bits for each??
We can represent 5 diff letters with 3 bits
Now that replaces the 8 bits. size now 3 * n

how does the retriever know what the new codes mean so how to decipher. also have the codes to decode the message.

HUFFMAN WAY

THE HUFFMAN:
Need a merge pattern to help define the code and decode it easy. We use a Tree

EX:
BCCABBDDAECCBBAEDDCC
char: A B C D E
freq: 3 5 6 4 2

write letter in order of freq

E A D B C

Connect the smallest two with a node then node contains the sum of freq

 O    /     \ E        A   D B C
    
   O
  /   \
O      D    /     \ E        A   B C

   O
  /   \
O      D         O    /     \           /     \ E        A         B        C

       O
    0/      \1
   O           O 
  /   \         /   \
O      D    B      C    /     \          E        A      

After you just label the left tree edge as 0 and the right tree graph as 1 and there is your encodings

keep merging least frequent symbols

Question 7

Huffman Coding Input/Output

Answer 7

Input: Array of frequency

Output: prefix free code that minimizes amount of bits
Sum of F[a] * |C[a]| length of bits

Question 8

Huffman Coding Algorithm Time Complexity

Answer 8

Time complexity from the operation on the priority queue, if a binary heap was used then it would be from O(logn) to O(nlogn)

Question 9

Huffman Coding Algorithm TO Build TREE

Answer 9

using a priority Queue, operations has Insert(), Extractmin(), min()

BuildHUffmanTree(F[1..n]
for i = 1 to n do
L[1] = 0; R[i] = 0;
Q.Insert(F[i],i)
for i = n + 1 to n -1 do
x = Q.ExtractMIN()
y = Q.ExtractMIN()
F[i] = F[x] + F[y]
Q.insert(F[i],i)
L[i] = x; P[x] = i
R[i] = y; P[y] = i
P[2n-1] = 0