Homework 7
ProfessorRotemOshman
Collaborators
LidiaNehmad MikailKhaishgi JunoCheungahc
9434
Question 1 HuffmanCodes
1 Tree root
letter Frequency code
FCD EABG A 0.06 1010
o B 0.09 1011
F CD EAB G 0.10 010
Se 0.12 on
C D E AB 0.15 100
0 I F 0.16 00
A B G 0.32 11
2 Notall Huffmancodes areuniqueTherecanbemultiplevalidHoffmantreesforthesamesetofsymbolsandfrequencies
therearemultiplenodeswiththesamefrequency
Thisismostcommonwhen
Counterexample
symbol Frequency
A 0.25 wecanpairanytwosymbolwiththelowestfrequencysincetheyreall thesame
0.25 Thepairscanbechosenin differentordersresultingin a validtree
0.25 Theyyieldequallyoptimal prefixfreecodes
0.25
root
AB as a
n i i's
Question
2 MaximizingNumber
ofColors
1 maxoverlapc
foreachpoint letnt representthenumberofintervals in thatcontain t
since Itof
intervals isfinite ciswelldefinedthereis apoint when nt is maximized
Color Requirements
atanypoint where n c thereareexactly aintervalsoverlappingSinceanytwooverlappingintervals
mustbeassigned different
colorsTherefore the C overlappingintervals musthave a
uniquecolor
Atleastadistinctcolorsarenecessary toproperlycolorthesea overlapping intervals
Conclusion
sincethereis apoint where n C theintervalsmustuseatleast acolors
Therefore theminimumnumberofcolors c to
needed properlycolor Xcannot
belessthanc
2 Proof thealgorithmcomputsvalidcoloringandneverusesmore thanccolors
BaseCase 2 0 nocolorsaredefined
FirstInterval a s if isassignedcolor1 itdoesn'toverlapwithanyprevious interval
Thealgorithm is validforthebasecase
Inductive
Hypothesis
Assumethat
forthefirst k intervals a _an thealgorithmassignsvalidcoloringanddoesn'tusemorethan ccolors
Inductive
step
By thegreedyalgorithm are willassignthesmallestavailablecolorthatdoesntconflictwithanyoverlappingintervalalradycolored
nature
Sinceintervalsaresorted
bytheirstartingpointssi anyintervalthatoverlapswith akt musthavestartingpointsi she
BydefinitionC themaxnumberofintervals thatoverlapanysinglepointonthelineTherefore atmosta intervalscanoverlap at
anygiventime atmost a distinctcolorsareneeded
If allpreviouslydefinedcolorsconflictwitharea itwillneverneedmorethane colorstohandleallintervals
overlaps
sincethegreedyalgorithmonlyassigns a colortoarea thecolorremainsvalidNo 2 overlapping share
thesamecolor
Conclusion
BymathematicalInductionthegreedyalgorithmonlyassigns a validcoloringtoeachintervalandnewusesmorethan a colors
1sorting n intervals Onlogn
2GreedyColoring O ct
Tcn Onlogn O n ct