The LEDA Tutorial

The LEDA Tutorial

Joachim Ziegler

<ziegler@mpi-sb.mpg.de>

Version 0.2.0

Copyright © 2004 Joachim Ziegler

23. 12. 2004 14:56:00

Dedication

	The need for speed and newness, which can only be satisfied by consumerism, reflects restlessness, the inner flight from oneself; [...] looking for the next thing to do or the newest gadget to use is only a means of protecting oneself from being close to oneself or to another person.
-- Erich Fromm, To Have Or To Be?

This Tutorium is dedicated to Erich Fromm (1900-1980) from whose books I have learned a lot, for example not permanently to be looking for the next thing to do and for the newest gadget to use to protect myself from being close to myself or to another person. But only sometimes.

Table of Contents

1. What is LEDA?
2. Whom does this tutorial address?
3. How is this tutorial built up?
4. In case of questions, remarks, and errors
5. About the author
6. Acknowledgement

1. On your marks - get set - LEDA!

1.1. Preparations

1.2. Hello LEDA world! - The very first program

1.3. Compiling, linking, and starting LEDA programs

1.3.1. The Unix world
1.3.2. The MS-Windows world

2. Simple data types and simple container types

2.1. Strings (class string)

2.1.1. The LEDA set of rules, handle types, and the categorization of the LEDA types

2.2. Arrays

2.2.1. One-dimensional arrays (class array)
2.2.2. Two-dimensional arrays (class array2)
2.2.3. Time complexity, space complexity, and the O-notation

2.3. Linear lists (class list)

2.3.1. Basic operations on lists
2.3.2. Lists and the item-container-concept
2.3.3. Changing lists and searching in lists
2.3.4. Sorting lists
2.3.5. User-defined type parameters
2.3.6. Copying and comparing item-based types and item types
2.3.7. Further information and tips
2.3.8. Singly linked lists (class slist)

2.4. Stacks

2.4.1. Stacks with an unbounded number of elements (class stack)
2.4.2. Stacks with a bounded number of elements (class b_stack)

2.5. Random numbers (class random_source)

2.5.1. The integer mode
2.5.2. The bit mode

2.6. Random variables

2.6.1. Static random variables (class random_variate)
2.6.2. Dynamic random variables (class dynamic_random_variate)

2.7. Queues

2.7.1. Queues with an unbounded number of elements (class queue)
2.7.2. Queues with a bounded number of elements (class b_queue)

2.8. Sets (class set)

2.8.1. Inserting elements and membership test
2.8.2. Union, intersection, and difference of sets
2.8.3. Linearly ordered types

2.9. Sets of integer numbers

2.9.1. If one knows minimum and maximum in advance (class int_set)
2.9.2. If minimum or maximum are unknown (class d_int_set)

2.10. array, list, stack, queue, set and d_int_set compared

2.11. Useful little somethings

2.11.1. Pairs, triples, and quadruples (classes two_tuple, three_tuple, four_tuple)
2.11.2. Dealing with directories and files
2.11.3. Dates (class date)
2.11.4. Efficient memory management for self-defined types
2.11.5. Some useful functions

2.12. What we did not cover

A. Categorization of the LEDA data types

B. The golden LEDA rules

Bibliography

List of Figures

2.1. An array of characters
2.2. A LEDA array with negative indices
2.3. The method resize() of arrays
2.4. Pascal's triangle
2.5. A two-dimensional array
2.6. The rules of Conway's game of the life
2.7. Tic-Tac-Toe
2.8. Running time analysis of sorting by minimum search
2.9. The asymptotical bounds O and Θ
2.10. A deque
2.11. Inserting and deleting of elements at the beginning and end of a list
2.12. A list with 5 integer numbers
2.13. Iteration in a list with the help of items
2.14. The Josephus problem
2.15. Creating pairings
2.16. A singly linked list
2.17. A stack
2.18. A stack for the evaluation of arithmetic expressions
2.19. A Galton board
2.20. A random walk
2.21. A queue
2.22. Old system at the Saarbrücken Central Station
2.23. New system at the Saarbrücken Central Station
2.24. A set
2.25. The set operations intersection, union, and symmetric difference
2.26. A search tree
2.27. A fractal set
2.28. A set of integer numbers, realized as a bit vector
A.1. Categorization of the LEDA data types

List of Tables

1.1. The LEDA libraries
2.1. array, list, stack, queue, set and d_int_set compared


		Preface