**Table of Contents**

- IV. COMPUTER NETWORKS
- 13. Distributed Algorithms
- 13.1. 13.1 Message passing systems and algorithms
- 13.2. 13.2 Basic algorithms
- 13.3. 13.3 Ring algorithms
- 13.4. 13.4 Fault-tolerant consensus
- 13.5. 13.5 Logical time, causality, and consistent state
- 13.6. 13.6 Communication services
- 13.7. 13.7 Rumor collection algorithms
- 13.8. 13.8 Mutual exclusion in shared memory

- 14. Network Simulation
- 14.1. 14.1 Types of simulation
- 14.2. 14.2 The need for communications network modelling and simulation
- 14.3. 14.3 Types of communications networks, modelling constructs
- 14.4. 14.4 Performance targets for simulation purposes
- 14.5. 14.5 Traffic characterisation
- 14.6. 14.6 Simulation modelling systems
- 14.7. 14.7 Model Development Life Cycle (MDLC)
- 14.8. 14.8 Modelling of traffic burstiness
- 14.9. 14.9 Appendix A

- 15. Parallel Computations
- 16. Systolic Systems
- 16.1. 16.1 Basic concepts of systolic systems
- 16.1.1. 16.1.1 An introductory example: matrix product
- 16.1.2. 16.1.2 Problem parameters and array parameters
- 16.1.3. 16.1.3 Space coordinates
- 16.1.4. 16.1.4 Serialising generic operators
- 16.1.5. 16.1.5 Assignment-free notation
- 16.1.6. 16.1.6 Elementary operations
- 16.1.7. 16.1.7 Discrete timesteps
- 16.1.8. 16.1.8 External and internal communication
- 16.1.9. 16.1.9 Pipelining

- 16.2. 16.2 Space-time transformation and systolic arrays
- 16.2.1. 16.2.1 Further example: matrix product
- 16.2.2. 16.2.2 The space-time transformation as a global view
- 16.2.3. 16.2.3 Parametric space coordinates
- 16.2.4. 16.2.4 Symbolically deriving the running time
- 16.2.5. 16.2.5 How to unravel the communication topology
- 16.2.6. 16.2.6 Inferring the structure of the cells

- 16.3. 16.3 Input/output schemes
- 16.3.1. 16.3.1 From data structure indices to iteration vectors
- 16.3.2. 16.3.2 Snapshots of data structures
- 16.3.3. 16.3.3 Superposition of input/output schemes
- 16.3.4. 16.3.4 Data rates induced by space-time transformations
- 16.3.5. 16.3.5 Input/output expansion
- 16.3.6. 16.3.6 Coping with stationary variables
- 16.3.7. 16.3.7 Interleaving of calculations

- 16.4. 16.4 Control
- 16.5. 16.5 Linear systolic arrays

- V. DATA BASES
- 17. Memory Management
- 18. Relational Database Design
- 19. Query Rewriting in Relational Databases
- 20. Semi-structured Databases

- VI. APPLICATIONS
- 21. Bioinformatics
- 21.1. 21.1 Algorithms on sequences
- 21.1.1. 21.1.1 Distances of two sequences using linear gap penalty
- 21.1.2. 21.1.2 Dynamic programming with arbitrary gap function
- 21.1.3. 21.1.3 Gotoh algorithm for affine gap penalty
- 21.1.4. 21.1.4 Concave gap penalty
- 21.1.5. 21.1.5 Similarity of two sequences, the Smith-Waterman algorithm
- 21.1.6. 21.1.6 Multiple sequence alignment
- 21.1.7. 21.1.7 Memory-reduction with the Hirschberg algorithm
- 21.1.8. 21.1.8 Memory-reduction with corner-cutting

- 21.2. 21.2 Algorithms on trees
- 21.3. 21.3 Algorithms on stochastic grammars
- 21.4. 21.4 Comparing structures
- 21.5. 21.5 Distance based algorithms for constructing evolutionary trees
- 21.6. 21.6 Miscellaneous topics

- 22. Computer Graphics
- 22.1. 22.1 Fundamentals of analytic geometry
- 22.2. 22.2 Description of point sets with equations
- 22.3. 22.3 Geometry processing and tessellation algorithms
- 22.4. 22.4 Containment algorithms
- 22.5. 22.5 Translation, distortion, geometric transformations
- 22.6. 22.6 Rendering with ray tracing
- 22.7. 22.7 Incremental rendering

- 23. Human-Computer Interaction

- Bibliography

**List of Figures**

- 14.1. Estimation of the parameters of the most common distributions.
- 14.2. An example normal distribution.
- 14.3. An example Poisson distribution.
- 14.4. An example exponential distribution.
- 14.5. An example uniform distribution.
- 14.6. An example Pareto distribution.
- 14.7. Exponential distribution of interarrival time with 10 sec on the average.
- 14.8. Probability density function of the Exp (10.0) interarrival time.
- 14.9. Visualisation of anomalies in packet lengths.
- 14.10. Large deviations between delta times.
- 14.11. Histogram of frame lengths.
- 14.12. The three modelling abstraction levels specified by the Project, Node, and Process editors.
- 14.13. Example for graphical representation of scalar data (upper graph) and vector data (lower graph).
- 14.14. Figure 14.14 shows four graphs represented by the Analysis Tool.
- 14.15. Data Exchange Chart.
- 14.16. Summary of Delays.
- 14.17. Diagnosis window.
- 14.18. Statistics window.
- 14.19. Impact of adding more bandwidth on the response time.
- 14.20. Baseline model for further simulation studies.
- 14.21. Comparison of RMON Standards.
- 14.22. The self-similar nature of Internet network traffic.
- 14.23. Traffic traces.
- 14.24. Measured network parameters.
- 14.25. Part of the real network topology where the measurements were taken.
- 14.26. “Message Source” remote client.
- 14.27. Interarrival time and length of messages sent by the remote client.
- 14.28. The Pareto probability distribution for mean 440 bytes and Hurst parameter .
- 14.29. The internal links of the 6Mbps ATM network with variable rate control (VBR).
- 14.30. Parameters of the 6Mbps ATM connection.
- 14.31. The “Destination” subnetwork.
- 14.32. utilisation of the frame relay link in the baseline model.
- 14.33. Baseline message delay between the remote client and the server.
- 14.34. Input buffer level of remote router.
- 14.35. Baseline utilisations of the DS-3 link and Ethernet link in the destination.
- 14.36. Network topology of bursty traffic sources with various Hurst parameters.
- 14.37. Simulated average and peak link utilisation.
- 14.38. Response time and burstiness.
- 14.39. Relation between the number of cells dropped and burstiness.
- 14.40. Utilisation of the frame relay link for fixed size messages.
- 14.41. Utilisation of the frame relay link for Hurst parameter .
- 14.42. Utilisation of the frame relay link for Hurst parameter (many high peaks).
- 14.43. Message delay for fixed size message.
- 14.44. Message delay for (longer response time peaks).
- 14.45. Message delay for (extremely long response time peak).
- 14.46. Settings.
- 14.47. New alert action.
- 14.48. Mailing information.
- 14.49. Settings.
- 14.50. Network topology.
- 15.1. SIMD architecture.
- 15.2. Bus-based SMP architecture.
- 15.3. ccNUMA architecture.
- 15.4. Ideal, typical, and super-linear speedup curves.
- 15.5. Locality optimisation by data transformation.
- 15.6. A simple MPI program.
- 15.7. Structure of an OpenMP program.
- 15.8. Matrix-vector multiply in OpenMP using a parallel loop.
- 15.9. Parallel random access machine.
- 15.10. Types of parallel random access machines.
- 15.11. A chain consisting of six processors.
- 15.12. A square of size .
- 15.13. A 3-dimensional cube of size .
- 15.14. A 4-dimensional hypercube .
- 15.15. A butterfly model.
- 15.16. A ring consisting of 6 processors.
- 15.17. Computation of prefixes of 16 elements using
`Optimal-Prefix`

- 15.18. Input data of array ranking and the the result of the ranking.
- 15.19. Work of algorithm
`Det-Ranking`

- 15.20. Sorting of 16 numbers by algorithm
`Odd-Even-Merge`

- 15.21. A work-optimal merge algorithm
`Optimal-Merge`

- 15.22. Selection of maximal integer number.
- 15.23. Prefix computation on square.
- 16.1. Rectangular systolic array for matrix product. (a) Array structure and input scheme. (b) Cell structure.
- 16.2. Two
*snapshots*for the systolic array from Figure 16.1. - 16.3. Hexagonal systolic array for matrix product. (a) Array structure and principle of the data input/output. (b) Cell structure.
- 16.4. Image of a rectangular domain under projection. Most interior points have been suppressed for clarity. Images of previous vertex points are shaded.
- 16.5. Partitioning of the space coordinates.
- 16.6. Detailed input/output scheme for the systolic array from Figure 16.3(a).
- 16.7. Extended input/output scheme, correcting Figure 16.6.
- 16.8. Interleaved calculation of three matrix products on the systolic array from Figure 16.3.
- 16.9. Resetting registers via global control. (a) Array structure. (b) Cell structure.
- 16.10. Output scheme with delayed output of results.
- 16.11. Combined local/global control. (a) Array structure. (b) Cell structure.
- 16.12. Matrix product on a rectangular systolic array, with output of results and distributed control. (a) Array structure. (b) Cell structure.
- 16.13. Matrix product on a rectangular systolic array, with output of results and distributed control. (a) Array structure. (b) Cell on the upper border.
- 16.14.
*Bubble sort*algorithm on a linear systolic array. (a) Array structure with input/output scheme. (b) Cell structure. - 17.1. Task system , and its optimal schedule.
- 17.2. Scheduling of the task system at list .
- 17.3. Scheduling of the task system using list on processors.
- 17.4. Scheduling of with list on processors.
- 17.5. Scheduling task system on processors.
- 17.6. Task system and its optimal scheduling on two processors.
- 17.7. Optimal list scheduling of task system .
- 17.8. Scheduling belonging to list .
- 17.9. Scheduling belonging to list .
- 17.10. Identical graph of task systems and .
- 17.11. Schedulings and .
- 17.12. Graph of the task system .
- 17.13. Optimal scheduling .
- 17.14. Scheduling .
- 17.15. Precedence graph of task system .
- 17.16. The optimal scheduling (, , ).
- 17.17. The optimal scheduling (, , , , , ).
- 17.18. Summary of the numbers of discs.
- 17.19. Pairwise comparison of algorithms.
- 17.20. Results of the pairwise comparison of algorithms.
- 18.1. Application of
`Join-test(`

`)`

- 19.1. The database CinePest.
- 19.2. The three levels of database architecture.
- 19.3. GMAPs for the university domain.
- 19.4. The graph .
- 19.5. The graph .
- 19.6. A taxonomy of work on answering queries using views.
- 20.1. Edge-labeled graph assigned to a vertex-labeled graph.
- 20.2. An edge-labeled graph and the corresponding vertex-labeled graph.
- 20.3. The graph corresponding to the XML file “forbidden”.
- 20.4. A relational database in the semi-structured model.
- 20.5. The schema of the semi-structured database given in Figure 20.4.
- 21.1. The tree on which we introduce the Felsenstein algorithm. Evolutionary times are denoted with s on the edges of the tree.
- 21.2. A dendrogram.
- 21.3. Connecting leaf to the dendrogram.
- 21.4. Calculating according to the
`Centroid`

- 21.5. Connecting leaf for constructing an additive tree.
- 21.6. Some tree topologies for proving Theorem 21.7.
- 21.7. The configuration of nodes , , and if and follows a cherry motif.
- 21.8. The possible places for node on the tree.
- 21.9. Representation of the signed permutation with an unsigned permutation, and its graph of desire and reality.
- 22.1. Functions defining the sphere, the block, and the torus.
- 22.2. Parametric forms of the sphere, the cylinder, and the cone, where .
- 22.3. Parametric forms of the ellipse, the helix, and the line segment, where .
- 22.4. A Bézier curve defined by four control points and the respective basis functions ().
- 22.5. Construction of B-spline basis functions. A higher order basis function is obtained by blending two consecutive basis functions on the previous level using a linearly increasing and a linearly decreasing weighting, respectively. Here the number of control points is 5, i.e. . Arrows indicate useful interval where we can find number of basis functions that add up to 1. The right side of the figure depicts control points with triangles and curve points corresponding to the knot values by circles.
- 22.6. A B-spline interpolation. Based on points to be interpolated, control points are computed to make the start and end points of the segments equal to the interpolated points.
- 22.7. Iso-parametric curves of surface.
- 22.8. The influence decreases with the distance. Spheres of influence of similar signs increase, of different signs decrease each other.
- 22.9. The operations of constructive solid geometry for a cone of implicit function and for a sphere of implicit function : union (), intersection (), and difference ().
- 22.10. Constructing a complex solid by set operations. The root and the leaf of the CSG tree represents the complex solid, and the primitives, respectively. Other nodes define the set operations (U: union, : difference).
- 22.11. Types of polygons. (a) simple; (b) complex, single connected; (c) multiply connected.
- 22.12. Diagonal and ear of a polygon.
- 22.13. The proof of the existence of a diagonal for simple polygons.
- 22.14. Tessellation of parametric surfaces.
- 22.15. Estimation of the tessellation error.
- 22.16. T vertices and their elimination with forced subdivision.
- 22.17. Construction of a subdivision curve: at each step midpoints are obtained, then the original vertices are moved to the weighted average of neighbouring midpoints and of the original vertex.
- 22.18. One smoothing step of the Catmull-Clark subdivision. First the face points are obtained, then the edge midpoints are moved, and finally the original vertices are refined according to the weighted sum of its neighbouring edge and face points.
- 22.19. Original mesh and its subdivision applying the smoothing step once, twice and three times, respectively.
- 22.20. Generation of the new edge point with butterfly subdivision.
- 22.21. Possible intersections of the per-voxel tri-linear implicit surface and the voxel edges. From the possible 256 cases, these 15 topologically different cases can be identified, from which the others can be obtained by rotations. Grid points where the implicit function has the same sign are depicted by circles.
- 22.22. Polyhedron-point containment test. A convex polyhedron contains a point if the point is on that side of each face plane where the polyhedron is. To test a concave polyhedron, a half line is cast from the point and the number of intersections is counted. If the result is an odd number, then the point is inside, otherwise it is outside.
- 22.23. Point in triangle containment test. The figure shows that case when point is on the left of oriented lines and , and on the right of line , that is, when it is not inside the triangle.
- 22.24. Point in triangle containment test on coordinate plane . Third vertex can be either on the left or on the right side of oriented line , which can always be traced back to the case of being on the left side by exchanging the vertices.
- 22.25. Polyhedron-polyhedron collision detection. Only a part of collision cases can be recognized by testing the containment of the vertices of one object with respect to the other object. Collision can also occur when only edges meet, but vertices do not penetrate to the other object.
- 22.26. Clipping of simple convex polygon results in polygon . The vertices of the resulting polygon are the inner vertices of the original polygon and the intersections of the edges and the boundary plane.
- 22.27. When concave polygons are clipped, the parts that should fall apart are connected by even number of edges.
- 22.28. The 4-bit codes of the points in a plane and the 6-bit codes of the points in space.
- 22.29. The embedded model of the projective plane: the projective plane is embedded into a three-dimensional Euclidean space, and a correspondence is established between points of the projective plane and lines of the embedding three-dimensional Euclidean space by fitting the line to the origin of the three-dimensional space and the given point.
- 22.30. Ray tracing.
- 22.31. Partitioning the virtual world by a uniform grid. The intersections of the ray and the coordinate planes of the grid are at regular distances , , and , respectively.
- 22.32. Encapsulation of the intersection space by the cells of the data structure in a uniform subdivision scheme. The intersection space is a cylinder of radius . The candidate space is the union of those spheres that may overlap a cell intersected by the ray.
- 22.33. A quadtree partitioning the plane, whose three-dimensional version is the octree. The tree is constructed by halving the cells along all coordinate axes until a cell contains “just a few” objects, or the cell sizes gets smaller than a threshold. Objects are registered in the leaves of the tree.
- 22.34. A kd-tree. A cell containing “many” objects are recursively subdivided to two cells with a plane that is perpendicular to one of the coordinate axes.
- 22.35. Notations and cases of algorithm
`Ray-First-Intersection-with-kd-Tree`

- 22.36. Kd-tree based space partitioning with empty space cutting.
- 22.37. Steps of incremental rendering. (a) Modelling defines objects in their reference state. (b) Shapes are tessellated to prepare for further processing. (c) Modelling transformation places the object in the world coordinate system. (d) Camera transformation translates and rotates the scene to get the eye to be at the origin and to look parallel with axis . (e) Perspective transformation converts projection lines meeting at the origin to parallel lines, that is, it maps the eye position onto an ideal point. (f) Clipping removes those shapes and shape parts, which cannot be projected onto the window. (g) Hidden surface elimination removes those surface parts that are occluded by other shapes. (h) Finally, the visible polygons are projected and their projections are filled with their visible colours.
- 22.38. Parameters of the virtual camera: eye position , target , and vertical direction , from which camera basis vectors are obtained, front and back clipping planes, and vertical field of view (the horizontal field of view is computed from aspect ratio ).
- 22.39. The normalizing transformation sets the field of view to 90 degrees.
- 22.40. The perspective transformation maps the finite frustum of pyramid defined by the front and back clipping planes, and the edges of the window onto an axis aligned, origin centred cube of edge size 2.
- 22.41. Notations of the Bresenham algorithm: is the signed distance between the closest pixel centre and the line segment along axis , which is positive if the line segment is above the pixel centre. is the distance along axis between the pixel centre just above the closest pixel and the line segment.
- 22.42. Polygon fill. Pixels inside the polygon are identified scan line by scan line.
- 22.43. Incremental computation of the intersections between the scan lines and the edges. Coordinate always increases with the reciprocal of the slope of the line.
- 22.44. The structure of the active edge table.
- 22.45. A triangle in the screen coordinate system. Pixels inside the projection of the triangle on plane need to be found. The coordinates of the triangle in these pixels are computed using the equation of the plane of the triangle.
- 22.46. Incremental coordinate computation for a left oriented triangle.
- 22.47. Polygon-window relations: (a) distinct; (b) surrounding ; (c) intersecting; (d) contained.
- 22.48. A BSP-tree. The space is subdivided by the planes of the contained polygons.
- 23.1. shortest paths in a grid-graph, printed in overlap.
- 23.2. The graph for Examples 23.1, 23.2 and 23.6.
- 23.3. for on grids.
- 23.4. Example graph for the LP-penalty method.
- 23.5. An example for a non-unique decomposition in two paths.
- 23.6. for on grids.