4. Algorithms and Data Structures
This chapter presents fundamental data types that are essential building blocks for a broad variety of applications. We present full implementations, even though some of them are built into Python, so that you can have a clear idea of how they work and why they are important.
The algorithms and data structures that we consider in this chapter introduce a body of knowledge developed over the past several decades that constitutes the basis for the efficient use of computers for a broad variety of applications. As the scope of computing applications continues to expand, so grows the impact of these basic approaches.
- 4.1 Performance outlines a scientific method and powerful theory for understanding the performance and resource consumption of the program that we write.
- 4.2 Sorting and Searching describes two classical algorithms — mergesort and binary search — along with several applications where their efficiency plays a critical role.
- 4.3 Stacks and Queues introduces two closely related data structures for manipulating arbitrary large collections of data.
- 4.4 Symbol Tables considers a quintessential data structure known as the symbol table for storing information, and an efficient implementation known as the binary search tree.
- 4.5 Small World Phenomenon presents a case study to investigate the small world phenomenon — the principle that we are all linked by short chains of acquaintances.
Python Programs in this Chapter
Below is a list of Python programs in this chapter.