Workshop in algorithms and data structures, 2005

(0368-3500-33)

 

Lecturer:

 

 

Tel:

8814

E-mail:

T.A.: 

Liam Roditty

E-mail:

liamr@post.tau.ac.il

Tel:

Office 5398

 

General

 

  • The project will be done in groups of 2-3 students.
  • Each group will implement an algorithm, using some basic data structure. A list of suggested topics follows.
  • You can use Leda - a c++ library that contains data structures and algorithms that may be useful for your projects.

                                                 

Requirements

 

  • A specification document should be submitted until 4/5/05.
    It should contain the following:

§         A detailed description of your algorithm and the data structures that you use

§       Environment: programming language, libraries you use, etc.

§         Description of the user interface (inputs, outputs, etc.)

§         A bird’s-eye view on the design of the project: Major procedures, etc.

§         Testing plan: How correctness and efficiency will be proven.

 

·        A significant task will be to make the program easy to check – It should be comprehensible; well-documented; and partitioned into logical components such that each can be tested by itself.

 

·        Project submission: TBD.         

 

 

Slides

 

Dynamic Connectivity

 

Euler Trees

 

Reachability

 

Topics – These are open to student’s suggestions

 

  • Dynamic trees

Implementing dynamic trees (see [14]), and using them for an efficient implementation of one of the following algorithms:

 

  • Dynamic Graphs

Implementing a dynamic algorithm to maintain reachability information in directed graphs:

 

  • Suffix trees and suffix arrays

Implementing suffix trees (see [2,16]) and suffix arrays, and using them for the implementation of one of the following algorithms:

      • Ziv-Lempel [11]
      • Burrows-Wheeler [10]
      • Text indexing with one error [1]

 

  • Heaps that support fast decrease-key and merge

Implementing Fibonacci heaps[17], Thin heaps[18], and the heaps of Hoyer[19]. All three have the same asymptotic efficiency, but the latter two are supposed to have better constants). The task is to compare the constants of the three implementations.

 

 

  • Kinetic heaps

Implementing kinetic heaps (see [8]).

 

 

LEDA

 

  • Leda web site
  • Here are a few examples of some simple programs that use LEDA:
      • my_demo
      • Dijkstra1
      • Dijkstra2
      • Graph file examples (needed for Dijktra1): Graph1, Graph2
      • If you work on the linux machines at the university, you have to define LEDA_ROOT by the command
        “setenv LEDAROOT /usr/local/lib/LEDA-4.4-complete-i386-linux-redhat-7.0-g++-2.96”,
        and you can compile the above programs with this Makefile.

 

Presentations

 

 

Bibliography

 

[1]   A. Amir, G.M. Landau, D. Keselman, M. Lewenstein, N. Lewenstein and M. Rodeh, Text indexing and dictionary matching with one error, Journal of Algorithms, 37:309-325, 2000.

 

[2]   M. Farach-Colton, P. Ferragina, and S. Muthukrishnan, On the sorting-complexity of suffix tree construction, Journal of the ACM 47(6):987-1011, 2000.

 

[3]   A.V. Goldberg and R.E. Tarjan, A new approach to the maximum-flow problem, Journal of the ACM 35(4):921-940, 1988.

 

[4]   A.V. Goldberg and R.E. Tarjan, Finding minimum-cost circulations by canceling negative cycles, Journal of the ACM 36(4):873-886, 1989.

 

[5]   A.V. Goldberg and R.E. Tarjan, Solving minimum-cost flow problems by successive approximation, Proceedings of the 19th annual ACM conference on Theory of computing, p. 7-18, 1987.

 

[6]   J. Holm, K. de Lichtenberg, and M. Thorup, Poly-logarithmic deterministic fully-dynamic graph algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity, Journal of the ACM 48(4):723-760, 2001.

 

[7]   W.L. Hsu and R.M. McConnell, PC trees and circular-ones arrangements, Theoretical computer science, 296(1):99-116, 2003.

 

[8]   H. Kaplan, R.E. Tarjan and K. Tsioutsiouliklis, Faster kinetic heaps and their use in broadcast scheduling, Proc. 12th annual ACM-SIAM Symposium On Discrete Algorithms, 2001, 836-844.

 

[9]   A. Lempel, S. Even and I. Cederbaum, An algorithm for planarity testing of graphs, Theory of graphs: International symposium, Rome, July 1966, P. Rosentiehl, editor, Gordon and Breach, New York, 1967, 215-232.

 

[10]      G. Manzini, The Burrows-Wheeler transform: theory and practice, Proc. 24th Int. Symposium on Mathematical Foundations of Computer Science (MFCS '99), 1999. Springer Verlag LNCS n. 1672, 34-47.

 

[11]      M. Rodeh, V.R. Pratt and S.Even, Linear algorithm for data compression via string matching, Journal of the ACM 28(1):16-24, 1981.

 

[12]      D.J. Rose, R.E. Tarjan and C.S. Lueker, Algorithmic aspects of vertex elimination on graphs, SIAM Journal on Computing, 5(2):266-283, 1976.

 

[13]      D.D. Sleator and R.E. Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, 26:362-391, 1983.

 

[14]      D.D. Sleator and R.E. Tarjan, Self-adjusting binary search trees, Journal of the ACM 32(3):652-686, 1985.

 

[15]      R.E. Tarjan and M. Yannakakis, Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM Journal on Computing, 13(3):566-579, 1984.

 

[16]      E. Ukonnen, Online construction of suffix trees, Algorithmica 14:249-260, 1995.

 

[17]      M. L. Fredman and R. E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. J. Assoc. Comput. Mach., 34:596-615, 1987.

 

[18]      H. Kaplan and R. E. Tarjan, New Heap Data Structures, Technical Report TR-597-99, Princeton University, 1999. Available here.

 

[19]      Peter Hyer. A general technique for implementation of efficient priority queues. Technical Report IMADA-94-33, Odense University, 1994.

 

[20] H. Kaplan and E. Verbin, Efficient Data Structures and a New Randomized Approach for Sorting Signed Permutations by Reversals, CPM ’03. Available here.

[21] EE. Tannier and M.-F. Sagot, Sorting by reversals in subquadratic time. accepted at CPM 2004. Will appear in a volume of Lecture Notes in Computer Science.

[22] A fully dynamic reachability algorithm for directed graphs with an almost linear update time Liam Roditty, Uri Zwick. In Proceedings of 36th ACM Symposium on Theory of Computing (STOC), Chicago, IL, June 2004