Skip to main content

Introduction

Summary

keywords

TODO

HW

Exercise*

Next time

Greedy

Used when step by step choosing the local optimum reaches the global optimum

  • It will need an appropriate data structure
  • graph algorithms are also by nature, a greedy algorithm

Fractional Knapsack Problem​

  • maximize the profit with fraction-able objects.
  • no need of DP. The only idea you need is as follows.

highest $profit/weight$

take the maximum prof/weight object as many as possible, and take the next maximum prof/weight object as many as possible.

Create a heap with the prof/weight ratio. Why not sorting? the smaller things we do not use.

make a key to track back the object from the ratio..?

Scheduling unit-time tasks with deadlines​

Select the highest earning first.

Create a heap with the earning. For each day, pick the next highest earning. Check it the deadlines meet the time slot.

DO not iterate from the first time slot. Put the task in the time slot closest to the deadline.

Optimal Merge Pattern​

This will be used in Huffman Coding. similar to Rope connecting problem

  • the cost of merging depends on the sizes of items.
  • merge small things first. This strategy leads to the smallest cost.

for every iteration, double check if the sum of smallest items lead to the smallest item.

Huffman Coding.​

compression technique.

Say we want to send 20-character string.

  1. No encoding Without encoding, it takes 8 bits per character. 160 bits in total.

  2. Fixed size coding. make an optimal encoding map($85+35$), and send the map along with the data($3*20$)? smaller(115 bits) than no encoding(160 bits), but 배보다 배꼽이 더 커.

  3. variable size coding.