## CS 473: Topics in Analysis of Algorithms, Fall 2001

## TuTh 11:00-12:15, 204 Transportation Bldg

## Jeff Erickson

## · Project reports · Homeworks · Schedule · Related topics · References · Administrivia ·

## Students were asked to write a report summarizing a few recent algorithms papers. The exact requirements for the project were rather fuzzy -- read two or three algorithms papers on a topic of your choice, all published within the last five years in a theory conference or journal, and convince me that you understood them in 10(±5) pages. I bent the multiple papers and time limit rules for ground-breaking papers or topics far from the lecture topics (but still about "algorithms").

Final project reports

- Peng Cheng: Approximating the permanent
- Matthew Hayward: Quantum computing and Grovers' algorithm
- Igor Kofman: Optimal search and one-way trading algorithms [oral presentation]
- Che-Bin Liu: Word-based RAM priority queues
- Josh Walstrom: Two proposed extensions to competitive analysis
[More coming...]

Homeworks and Solutions

- Homework 1 due September 13 [Solutions]
- Homework 2 due September 27 [Solutions]
- Homework 3 due October 18 [Solutions]
- Homework 4 due November 22 [Solutions]

Schedule

Date Lecture topics Scribe notes I. Dynamic data structures August 23 Introduction, overview, and adminsitrivia

Scapegoat trees [A99], [E01, lecture 6], [GR93]August 28 Splay trees [ST85], [E01, lecture 6] David Bunde's notes August 30 Weight balanced B-trees [AV96]

Lazy global rebuilding [OvL81a], [O83]Viraj Kumar's notes September 4 Multidimensional splitting and merging: setup [GI99] September 6 Multidimensional splitting and merging: analysis [GI99] Josh Walstrom's notes September 11 Dynamic graph connectivity [HLT98] Ajay Ladsaria's notes September 13 Deletion-only minimum spanning trees [HLT98] September 18 Fully dynamic minimum spanning trees [HLT98], [HK97], [HK99] September 20 Sparsification [EGIN97] September 25 Kinetic data structures: setup, search trees [BGH99], [G98] September 27 Kinetic data structures: four kinetic heaps [BGH99], [G98] October 2 Partial persistence: path copying, fat nodes, node copying [DSST89] October 4 Full persistence: node splitting [DSST89] II. Online algorithms [BE98] October 9 ~~Ski~~Video rental [KMMO90],

Lost cow [BCR93]October 11 More lost cows: lower bounds and randomization [BCR93], [KRT90] October 16 List access [AW98]: Optimal offline, MTF, TRANSPOSE, FREQCOUNT, Lower bound October 18 More list access [AW98]: List factoring, TIMESTAMP(0),

BIT [RWS94], COMBINATION [AvSW95]October 23 Deterministic paging: lower bounds,

LFD, LRU, FIFO, CLOCK, FWF [BE98, Chapter 3]October 25 Randomized paging: [BE98, Chapter 4], [ACN00]

RANDOM, MARK, various adversariesOctober 30 Class cancelledNovember 1 November 6 Access graphs: "LRU is better than FIFO" [CN99] November 8 Access graphs: FAR November 13 Zero-sum game theory, Von Neumann minimax/Nash equilibrium via linear programming duality, Loomis's lemma (at most one player needs randomness) November 15 Yao's principle, lower bounds for video rental and paging November 20 Thanksgiving breakNovember 22 November 27 The k-server problem: deterministic lower bound, DOUBLECOVERAGE for the line November 29 The k-server problem: DOUBLECOVERAGE for trees, SLACKCOVERAGE for k=2 in the plane, BALANCE for N=k+1 December 4 The k-server work function algorithm December 6 What I did this semester besides teach December 15 Semester projects due

Related topics we didn't have time for## Advanced data structures:

And people wonder why it's taking Knuth so long to publish Volume 4.

- More of everything we
didcover

- Worst-case-competitive search structures [I01]
- Generic static-to-dynamic transformations [BS80]
- I/O-efficient and cache-oblivious structures (This could easily fill an entire course!) [BDF00]
- Geometric data structures [AE99] (This
wasan entire course three years ago!)- Word-based RAM data structures:

- van Emde Boas trees
- Fusion trees
- O(log log n) priority queues
- O(sqrt{log n}) search trees
- Text data structures: tries, suffix trees, and DAWGs
- Parametric/kinetic minimum spanning trees [AEGH98]
- Confluent persistence
- Lower bounds (pointer machine, cell probe, RAM, semigroup)
## Pointers to free electronic papers were mined from ResearchIndex and authors' personal web pages. Papers from the ACM Digital Library and most journals require a subscription, and thus may be inaccessible from outside the uiuc.edu domain; I will only link to these if no free version is available. *Stars indicate authors who (as far as I know) were graduate students when their papers were first published. [No pressure!]

References## General

- [CLRS01]
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, second edition. MIT Press / McGraw-Hill, 2001.
- [E01]
- Jeff Erickson. CS 373: Combinatorial Algorithms, Spring 2001 lecture notes.
Peer into the deep dark dusty cobwebs of the instructor's mind!- [MR95]
- Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1995.
## Dynamic Data Structures

- [A99]
- Arne Anderson*. General balanced trees. J. Algorithms 30:1-28, 1999.
- [AEGH98]
- Pankaj K. Agarwal, David Eppstein, Leonidas J. Guibas, and Monika R. Henzinger. Parametric and kinetic minimum spanning trees. Proc. 39th IEEE Symp. Found. Comput. Sci., 596-605, 1998. [David's FOCS slides]
- [AE99]
- Pankaj K. Agarwal and Jeff Erickson. Geometric range seraching and its relatives. Advances in Discrete and Computational Geometry (Bernard Chazelle, Jacob E. Goodman, and Richard Pollack, editors), 1-56, 1999. Contemporary Mathematics 223, AMS Press.
- [AV96]
- Lars Arge* and Jeffrey S. Vitter. Optimal dynamic interval management in external memory. Proc. 37th IEEE Symp. Found. Comput. Sci., 560-569, 1996.
- [BDF00]
- Michael A. Bender, Erik D. Demaine*, and Martin Farach-Colton. Cache-oblivious B-trees. Proc. 41st IEEE Symp. Found. Comput. Sci. 399-409, 2000.
- [BGH99]
- Julien Basch*, Leonidas J. Guibas, and John Hershberger. Data structure for mobile data J. Algorithms 31(1):1-28, 1999.
- [BS80]
- Jon L. Bentley and James B. Saxe*. Decomposable searching problems: 1. Static-to-dynamic transformations. J. Algorithms 1:301-358, 1980.
- [BJ00]
- Gerth S. Brodal and Riko Jacob*. Dynamic planar convex hull with optimal query time and O(log
n·log logn) update time. Proc. 7th Scandinavian Workshop on Algorithm Theory 57-70, 2000. Lecture Notes in Computer Science 1851, Springer-Verlag.- [C01]
- Timothy M. Chan. Dynamic planar convex hull operations in near-logarithmic amortized time. J. ACM 48:1-12, 2001.
- [DSST89]
- James R. Driscoll*, Neil Sarnak*, Daniel D. Sleator, and Robert E. Tarjan. Making data structures persistent. Journal of Computer and System Sciences 38:86-124, 1989. Extended abstract in Proc. 18th Ann. ACM Symp. Theory Comput., 109-121, 1986. [ACM Digital Library]
- [EGIN97]
- David Eppstein*, Zvi Galil, Giuseppe F. Italiano, and Amnon Nissenzweig. Sparsification: A technique for speeding up dynamic graph algorithms. J. ACM 44(5):669-696, 1997. [ACM Digital Library]
- [GR93]
- Igal Galperin* and Ronald L. Rivest. Scapegoat trees. 4th ACM-SIAM Symposium on Discrete Algorithms, 165-174, 1993. [ACM Digital Library]
- [GI99]
- Roberto Grossi* and Giuseppe F. Italiano. Efficient splitting and merging for order decomposable problems. Information and Computation 154(1):1-33, 1999.
- [G98]
- Leonidas J. Guibas. Kinetic data structures: A state of the art report. Robotics: The Algorithmic Perspective [Proc. 3rd WAFR], 191-209, 1998. A. K. Peters.
- [HK97]
- Monika R. Henzinger and Valerie King. Maintaining minimum spanning trees in dynamic graphs. Proc. 24th ICALP, 594-604, 1997.
- [HK99]
- Monika R. Henzinger and Valerie King. Randomized dynamic graph algorithms with polylogarithmic time per operation. J. ACM 46(4):502-516, 1999.
- [HLT98]
- Jacob Holm*, Kristian de Lichtenberg*, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. Proc. 13th Ann. ACM Symp. Theory Comput., 79-89, 1998. [ACM Digital Library]. Full version: Technical reports DIKU-TR-97/17 and DIKU-TR-97/26, University of Copenhagen, September 1997.
- [I01]
- John Iacono. Alternatives to splay trees with O(log
n) worst-case access times. 12th ACM-SIAM Symposium on Discrete Algorithms, 516-522, 2001. [ACM Digital Library]- [O83]
- Mark H. Overmars. The Design of Dynamic Data Structures. Lecture Notes in Computer Science 156, Spring-Verlag, 1983.
- [OvL81]
- Mark H. Overmars* and Jan van Leeuwen. Maintenance of configurations in the plane. J. Computer and System Sciences 23:166-204, 1981.
- [OvL81a]
- Mark H. Overmars* and Jan van Leeuwen. Worst-case optimal insertion and deletion methods for decomposable searching problems. Information Processing Letters 12(4):168-173, 1981.
- [ST85]
- Daniel D. Sleator* and Robert E. Tarjan. Self-adjusting binary search trees. J. ACM 32:652-686, 1985. [HTML demo and C code] [nice Java demo] [ACM digital library]
- [WDGP00]
- Pacific Institute Workshop on Dynamic Graph Problems, June 5-9, 2000. The web site includes slides from talks by Stephen Alstrup, David Eppstein, Faith Fich, and Robert Tarjan.
## Online Algorithms

- [ACN00]
- Dimitris Achlioptas*, Marek Chrobak, and John Noga*. Competitive analysis of randomized paging algorithms Theoretical Computer Science 234:203-218, 2000.
- [AvSW95]
- Susanne Albers, Bernhard von Stengel, and Ralph Werchner. A combined BIT and TIMESTAMP algorithm for the list update problem. Inform. Proc. Letters 56:135-139, 1995.
- [AW98]
- Susanne Albers and Jeffery Westbrook. Self-organizing data structures. Online Algorithms: The State of the Art, (Amos Fiat and Gerhard Woeginger, editors), pages 31-51. Lecture Notes in Computer Science 1442, Springer-Verlag, 1998.
- [BE98]
Allan Borodin and Ran El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998.[The canonical textbook for online algorithms.]- [BCR93]
- Ricardo A. Baeza-Yates, Joseph C. Culberson, and Gregory J. E. Rawlins. Searching in the plane. Information and Computation 106(2):234-252, 1993.
- [CN99]
- Marek Chrobak and John Noga*. LRU is better than FIFO. Algorithmica 23:180-185, 1999.
- [KMMO94]
- Anna R. Karlin, Mark S. Manasse, Lyle A. McGeoch, Susan S. Owicki. Competitive randomized algorithms for nonuniform problems. Algorithmica 11(6):542-571, 1994. [SODA 1990 version from ACM Digital Library]
- [KRT96]
- Ming-Yang Kao, John H. Reif, and Stephen R. Tate. Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem. Information and Computation 133(1):62-80, 1996.

Administrivia

Instructor:Jeff Erickson (jeffe@cs.uiuc.edu)Office Hours:TuTh 3:00-4:00, Green Street Coffee HouseCourse Newsgroup:uiuc.class.cs473

Course Topics:I originally indented to cover some approximation algorithms and inapproximability results as well, but that was far too ambitious. Maybe next time!

Dynamic data structures:search structures, graph properties, persistence, ...Online algorithms and competitive analysis:list access, paging, load balancing, ...

Coursework:- There were four written homeworks, a semester project, and no exams.

Prerequisites:- CS 373 or an equivalent undergraduate algorithms course. Mathematically and/or algorithmically mature undergradutes were welcome to enroll with my permission.

Reading:- There was no required textbook for this class. The books by Borodin and El-Yaniv [BE98] and Motwani and Raghavan [MR95] were useful references for the more advanced material, and everyone already had CLR(S) [CLRS01] for the more basic stuff. Much of the lecture material came from recent preprints, conference papers, and journal papers. I provided pointers to electronic copies of these papers here whenever possible.

Jeff Erickson (jeffe@cs.uiuc.edu) 22 Dec 2001