| |
|
Faculty
Advisors
|
Kanat
Tangwongsan |
Srinath Sridhar |
|
|
|
Dynamic algorithms allow the user to maintain some property while making changes to the input. For example, a minimum spanning tree might be maintained while edges are inserted and deleted from a graph. The hope is that such updates will be much more efficient than executing a minimum spanning tree algorithm from scratch. In a kinetic algorithm the data can change continuously—-e.g., an edge weight might increase over time. There has been significant research in the past twenty years on dynamic and kinetic algorithms for many problems. [1] Furthermore, in recent years there has been a significant increase in the need for these sorts of algorithms in various applications. Examples include maintaining properties of moving sets of points in various simulations, and maintaining various properties of a communication network (e.g., shortest paths and connectivity) as connections are added and deleted.
We are interested in developing efficient implementations of dynamic and kinetic algorithms. This work is partially based on recent results on semi-automatically converting static algorithms to dynamic algorithms by maintaining dependences. This can greatly reduce the cost of coding dynamic algorithms. The REU student will develop a dynamic and kinetic 3d convex hull algorithm based on these ideas. This will be based on using a static incremental 3d convex hull algorithm and inserting the appropriate code to track dependences and propagate changes. The student will experiment with the dynamized version, and develop theory for analyzing the performance of the algorithm. The student will learn about dynamic algorithms, and generally about implementing complex algorithms and experimenting with them. Some background in the ML language would be very helpful.
[1] D. Eppstein, Z. Galil, and G. F. Italiano, Dynamic graph algorithms, In CRC Handbook of Algorithms and Theory of Computation, Chapter 22, CRC Press, 1997.
|
|
CENTER
Carnegie
Mellon 
Aladdin
Preliminary Presentation 
Back
to the REU page