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.

REF PROGRAM DESCRIPTION DATA

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

REF	PROGRAM	DESCRIPTION	DATA
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