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.

Python Programs in this Chapter

Below is a list of Python programs in this chapter.

4.1.1 threesum.py 3-sum problem 8ints.txt  1kints.txt  2kints.txt  4kints.txt  8kints.txt  16kints.txt  32kints.txt  64kints.txt  128kints.txt  
4.1.2 doublingtest.py validating a doubling hypothesis
4.1.3 timeops.py timing operators and functions
4.1.4 bigarray.py discovering memory capacity
4.2.1 questions.py binary search (20 questions)
4.2.2 bisection.py binary search (inverting a function)
4.2.3 binarysearch.py binary search (sorted array) emails.txt  white.txt  
4.2.4 insertion.py insertion sort tiny.txt  tomsawyer.txt  
4.2.5 timesort.py doubling test for sorting functions
4.2.6 merge.py mergesort tiny.txt  tomsawyer.txt  
4.2.7 frequencycount.py frequency counts leipzig100k.txt  leipzig200k.txt  leipzig1m.txt  
4.3.1 arraystack.py stack (resizing array implementation) tobe.txt  
4.3.2 linkedstack.py stack (linked list implementation) tobe.txt  
4.3.3 evaluate.py expression evaluation expression1.txt  expression2.txt  
4.3.4 linkedqueue.py queue (linked list implementation) tobe.txt  
4.3.5 mm1queue.py M/M/1 queue simulation
4.3.6 loadbalance.py load balancing simulation
4.4.1 lookup.py dictionary lookup amino.csv  djia.csv  elements.csv  ip.csv  ip-by-country.csv  morse.csv  phone-na.csv  
4.4.2 index.py indexing mobydick.txt  tale.txt  
4.4.3 hashst.py hash symbol table data type
4.4.4 bst.py BST symbol table data type
4.5.1 graph.py graph data type tinygraph.txt  
4.5.2 invert.py using a graph to invert an index tinygraph.txt  movies.txt  
4.5.3 separation.py shortest-paths client routes.txt  movies.txt  
4.5.4 pathfinder.py shortest-paths client
4.5.5 smallworld.py small-world test tinygraph.txt  
4.5.6 performer.py performer-performer graph tinymovies.txt  moviesg.txt