WEBPAGE FOR CMSC 651

Fall 2006

Syllabus: syll.ps,syll.pdf

HW is recommended to be in LaTeX. Here is a guide to math in latex: latex.ps,latex.pdf

If you want to download the latex code which produced math.ps and math.pdf its here: latex.tex

FINAL: Friday Dec 15, 1:30-3:30, same room as class

HANDOUTS

Amortized Data Structures: amort.ps, amort.pdf

MY NOTES ON Combinatorial Arguments: comb.ps, comb.pdf

MY NOTES ON Dijistras Algorithm with constant bound on weights: dij.const.ps, Dij.const.pdf

SAMIR'S NOTES on MST: mst.ps, mst.pdf

MY NOTES on MST: yaomst.ps, yaomst.pdf

SAMIR'S NOTES ON FLOWS (includes example where Ford-Fulkerson does not halt) flow1.ps, flow1.pdf

CORRECTIONS TO NOTES: 651bugs.ps, 651bugs.pdf,

MORE CORRECTIONS TO NOTES: 651bugs2.ps, 651bugs2.pdf,

MY NOTES on UNION-FIND, LOGSTAR stuff logstar.ps, logstar.pdf,

SAMIR'S NOTES on matching. samirmatch.ps, samirmatch.pdf

SAMIR'S NOTES ON LINEAR PROGRAMMING

linprog.ps, linprog.pdf

lpdual1.ps, lpdual1.pdf

lpdual2.ps, lpdual2.pdf

MY NOTES ON TURNING A NONCONST ALG TO A CONST ONE: const.ps, const.pdf

PAPER: Faster Algorithms for Shortest Path Problems dijcjacm.pdf

PAPER: A Potential-Based Amortized Analysis of the Union-Find Data Structure unionfindeasyanal.pdf

PAPERS ON MST:

1. A Randomized Linear-Time algorithm to find MST, by Karger-Klein-Tarjan KKT.pdf
2. Backward Analysis of the Karger-Kleein-Tarjan algorithm for MST, by Chan KKTsimpler.pdf
3. A simpler linear time algorithm for MST verification, by King Kingmsv.ps

PAPER ON SUBSEQ THING BEING NONCONSTRUCTTIVE subseq.ps

HOMEWORKS

HOMEWORK 1: hw01.ps,hw01.pdf

HOMEWORK 2: hw02.ps,hw02.pdf

HOMEWORK 3: hw03.ps,hw03.pdf

HOMEWORK 4: hw04.ps,hw04.pdf

MIDTERM: mid.ps, mid.pdf

MIDTERMMAKEUP-UNION-FIND: UFD.ps, UFD.pdf

MIDTERMMAKEUP-DIJ-C: RH.ps, RH.pdf

HOMEWORK 5: hw05.ps,hw05.pdf

HOMEWORK 6: hw06.ps,hw06.pdf

HOMEWORK 7: hw07.ps,hw07.pdf

HOMEWORK 8: hw08.ps,hw08.pdf