In this section, we explore the world of programming, algorithms, networks, and infrastructure
Measuring the performance of a parallel system requires different tools and metrics than measuring a single-core processor. This article covers the specialized benchmarks used to evaluate multiprocessor systems, explains how to model scaling behavior as more processors are added, and revisits Amdahl's Law in the context of real-world performance measurement.
Comparing a CPU and a GPU fairly requires a model that accounts for both computational throughput and memory bandwidth limits together. This article introduces the roofline model used to compare real hardware like the Intel Core i7 and NVIDIA Tesla GPU, then shows how matrix multiplication is accelerated across multiple processors as the final practical application of this chapter's parallel concepts.
After covering everything from thread-level parallelism to warehouse-scale computing, it is worth correcting persistent misconceptions about parallel systems that even experienced engineers sometimes hold. This article addresses common fallacies about scaling and parallel hardware, then closes out the parallel processing chapter by tying together the full journey from a single instruction to a building full of cooperating machines.
Before diving into specific algorithms, it is essential to understand what an algorithm actually is, why studying algorithms matters even with fast modern hardware, and how to rigorously analyze an algorithm's efficiency. This comprehensive guide covers the formal definition of an algorithm, walks through insertion sort as a first complete example, and introduces the core techniques for measuring and comparing running time.
Comparing algorithms fairly requires a mathematical language that ignores constant factors and focuses on growth rate as input size becomes large. This comprehensive guide covers the formal definitions of Big-O, Big-Omega, and Big-Theta notation, explains how to prove asymptotic bounds directly from their definitions, and surveys the standard functions and growth rates every algorithm analysis relies on.
Multiplying two matrices is a fundamental operation in computer science, and the naive approach is far from optimal. This comprehensive guide explains the standard cubic-time matrix multiplication algorithm, shows how a straightforward divide-and-conquer approach fails to improve on it, and walks through Strassen's remarkable algorithm that achieves a genuinely faster asymptotic running time.
Every divide-and-conquer algorithm's running time is captured by a recurrence relation, and solving that recurrence is essential to understanding the algorithm's efficiency. This comprehensive guide covers the three standard techniques for solving recurrences: the substitution method for proving a guessed bound, the recursion-tree method for generating a guess, and the master method as a fast shortcut for a common class of recurrences.
Some algorithms make random choices during execution, and analyzing their expected behavior requires a different toolkit than worst-case analysis alone. This comprehensive guide introduces probabilistic analysis through the classic hiring problem, explains indicator random variables as a powerful analytical tool, and shows how randomization can improve an algorithm's expected performance.
The binary heap is one of the most elegant data structures in computer science, enabling both an efficient in-place sorting algorithm and the priority queue abstraction used throughout algorithm design. This comprehensive guide covers heap properties and array representation, the core heapify operation, building a heap from an unordered array, the complete heapsort algorithm, and priority queue operations built on top of heaps.
Quicksort is one of the most widely used sorting algorithms in practice, prized for its excellent average-case performance and in-place operation, despite having a poor theoretical worst case. This comprehensive guide covers the partition-based algorithm in detail, analyzes both its worst-case and expected running time, and explains how randomization transforms it into a reliably efficient algorithm regardless of input order.
Every comparison-based sorting algorithm requires at least Ω(n log n) time in the worst case, but algorithms that avoid comparisons entirely can sort in linear time under the right conditions. This comprehensive guide proves the comparison-sort lower bound using a decision tree argument, then explains three linear-time algorithms — counting sort, radix sort, and bucket sort — along with the specific input assumptions each requires.
Finding the k-th smallest element in an unsorted array does not require the full Θ(n log n) cost of sorting; it can be done in linear time. This comprehensive guide covers the trivial case of finding the minimum or maximum, an elegant randomized selection algorithm with linear expected time, and a more intricate deterministic algorithm that guarantees linear time even in the worst case.
