Many textbooks start out as informal notes for university courses, refined through repeated offerings.The book under review came out of the author's experiences as a lecturer at an American liberal-arts college, Grinnell, where the first course in computation used Scheme for many years.The first chapter, "Essential Notations", rapidly introduces many features of R7RS Scheme and its libraries, augmented by some primitives written by the author.The next chapter, "The Tool Box", presents or builds a host of abstractions, such as couplers, adapters, and recursion managers (e.g., folds), which are used extensively in the rest of the text.The ambition of this book can be seen in the topic lists for the next two chapters."Data Structures" covers lists, sources (streams without caching, which would necessitate mutation), trees, bushes (rose trees), bags, sets, tables, and buffers (queues), all implemented mostly using pairs and lists (occasionally records)."Sorting" covers insertion sort, selection sort, quicksort, mergesort, binary search trees, treesort, red-black trees (both insertion and deletion), pairing heaps, and order statistics.Considering that the word "Algorithms" is in the title, the book is surprisingly shy about discussing efficiency.Linear time appears briefly; the phrase "proportional to" is used a few times, and "logarithm" only once, in reference to running times.I understand the reluctance; order notation and the proper use of recurrences for analysis of running time are nettles that one hesitates to grasp.They can be avoided in a first course, but only barely, and without them, the motivation for many of these more advanced topics becomes much more difficult.The next chapter, "Combinatorial Constructions", is possibly the most successful, perhaps because it is rich with helper functions and examples, and topics not usually covered: Cartesian products, subsequences and selections (subsets and combinations, but of an ordered list), and finally permutations and partitions, all with ranking and unranking (going from a numerical index to an element of the full answer and vice versa).In the last two chapters, the author's principled insistence on purity and layers of abstraction is at odds with the material."Graphs" presents depth-first and breadth-first traversal, spanning trees, shortest paths (Bellman-Ford, Dijkstra, and Floyd-Warshall), and maximum flow (Ford-Fulkerson)."Sublist Search" is chiefly concerned with Knuth-Morris-Pratt and Boyer-Moore string search.These are topics for which pure functional programming does not have a good story.One should be willing to sacrifice efficiency for

Three pointer based parallel join algorithms are presented and analyzed for environments in which secondary storage is made transparent to the programmer through memory mapping. P.A. Buhr et al. (1992) show that data structures such as B Trees, R Trees and graph data structures can be implemented as efficiently and effectively in this environment as in a traditional environment using explicit I/O. We show how higher order algorithms, in particular parallel join algorithms, behave in a memory mapped environment. A quantitative analytical model has been developed to conduct performance analysis of the parallel join algorithms. The model has been validated by experiments.

Article μDatabase: parallelism in a memory-mapped environment (research summary) Share on Authors: Peter A. Buhr Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1 Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1View Profile , Anil K. Goel Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1 Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1View Profile , Naomi Nishimura Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1 Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1View Profile , Prabhakar Ragde Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1 Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1View Profile Authors Info & Claims SPAA '96: Proceedings of the eighth annual ACM symposium on Parallel Algorithms and ArchitecturesJune 1996 Pages 196–199https://doi.org/10.1145/237502.237547Online:24 June 1996Publication History 0citation143DownloadsMetricsTotal Citations0Total Downloads143Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Shared memory models of parallel computation (e.g., parallel RAMs) that allow simultaneous read/write access are very natural and already widely used for parallel algorithm design. The various models differ from each other in the mechanism by which they resolve write conflicts. To understand the effect of these communication primitives on the power of parallelism, we extensively study the relationship between four such models that appear in the literature, and prove nontrivial separations and simulation results among them.

We consider the problem of element distinctness. Here n synchronized processors, each given an integer input, must decide whether these integers are pairwise distinct, while communicating via an infinitely large shared memory. If simultaneous write access to a memory cell is forbidden, then a lower bound of $\Omega ( \log n )$ on the number of steps easily follows (from S. Cook, C. Dwork, and R. Reischuk, SIAM J. Comput., 15 (1986), pp. 87–97.) When several (different) values can be written simultaneously to any cell, then there is an simple algorithm requiring $O ( 1 )$ steps. We consider the intermediate model, in which simultaneous writes to a single cell are allowed only if all values written are equal. We prove a lower bound of $\Omega ( ( \log n )^{1 /2} )$ steps, improving the previous lower bound of $\Omega ( \log \log \log n )$ steps (F. E. Fich, F. Meyer auf der Heide, and A. Wigderson, Adv. in Comput., 4 (1987), pp. 1–15). The proof uses Ramsey-theoretic and combinatorial arguments. The result implies a separation between the powers of some variants of the PRAM model of parallel computation.

We consider the relative power of concurrentwrite PRAMs when the number of processors (and input variables) is fixed at n, and infinite shared memory is allowed. Several different models (COMMON, ARBITRARY, PRIORITY) have been used for algorithm design in the literature; these models differ in their method of write-conflict resolution. Recent work in separating these models ([FRW1,2,3], [LY]) has relied on further restrictions (limiting the size of memory or the power of processors); the only unrestricted results known concern the element distinctness problem ([FMW], [RSSW]). In this paper we contribute further unrestricted results. We consider the COLLISION model, a natural generalization of the Ethernet ([G]). Our main result is a lower bound of Ω(logloglogn) steps on COLLISION for a problem that can be done in O(1) steps on ARBITRARY. We use this result, together with a reduction performed by means of Ramsey's Theorem, to show that the powers of COMMON and COLLISION are incomparable. We also introduce a new and natural model, TOLERANT, and show that it is strictly less powerful than COLLISION and incomparable with COMMON. The proofs involved use combinatorial arguments, including Turán's Theorem for graphs and the Erdös-Rado intersecting set theorem.

In this paper we compare the power of the two most commonly used concurrent-write models of parallel computation, the COMMON PRAM and the PRIORITY PRAM. These models differ in the way they resolve write conflicts. If several processors want to write into the same shared memory cell at the same time, in the COMMON model they have to write the same value. In the PRIORITY model, they may attempt to write different values; the processor with smallest index succeeds.

Shared-memory models for parallel computation (e.g. parallel RAMs) are very natural and already widely used for parallel algorithm design. The various models differ from each other mainly in the way they restrict simultaneous processor access to a shared memory cell. Understanding the relative power of these models is important for understanding the power of parallel computation.