Python DSA PDF
Python DSA PDF
Rance D. Necaise
Department of Computer Science
College of William and Mary
This book was printed and bound by Hamilton Printing Company. The cover was
printed by Hamilton Printing Company
Copyright ©2011 John Wiley & Sons, Inc. All rights reserved. No part of this
publication may be reproduced, stored in a retrieval system or transmitted in any
form or by any means, electronic, mechanical, photocopying, recording, scanning or
otherwise, except as permitted under Sections 107 or 108 of the 1976 United States
Copyright Act, without either the prior written permission of the Publisher, or
authorization through payment of the appropriate per-copy fee to the Copyright
Clearance Center, Inc. 222 Rosewood Drive, Danvers, MA 01923, website
[Link]. Requests to the Publisher for permission should be addressed
to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken,
NJ 07030-5774, (201)748-6011, fax (201)748-6008, website
[Link]
“Evaluation copies are provided to qualified academics and professionals for review
purposes only, for use in their courses during the next academic year. These copies
are licensed and may not be sold or transferred to a third party. Upon completion
of the review period, please return the evaluation copy to Wiley. Return
instructions and a free of charge return shipping label are available at
[Link]/go/returnlabel. Outside of the United States, please contact your
local representative.”
Necaise, Rance D.
Data structures and algorithms using Python / Rance D. Necaise.
p. cm.
Includes bibliographical references and index.
ISBN 978-0-470-61829-5 (pbk.)
1. Python (Computer program language) 2. Algorithms.
3. Data structures (Computer science) I. Title.
QA76.73.P98N43 2011
005.13'3—dc22 2010039903
10 9 8 7 6 5 4 3 2 1
To my nieces and nephews
Allison, Janey, Kevin, RJ, and Maria
This page intentionally left blank
Contents
Preface xiii
Chapter 2: Arrays 33
2.1 The Array Structure . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.1.1 Why Study Arrays? . . . . . . . . . . . . . . . . . . . . . . . 34
2.1.2 The Array Abstract Data Type . . . . . . . . . . . . . . . . . 34
2.1.3 Implementing the Array . . . . . . . . . . . . . . . . . . . . 36
2.2 The Python List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
v
vi CONTENTS
The standard second course in computer science has traditionally covered the fun-
damental data structures and algorithms, but more recently these topics have been
included in the broader topic of abstract data types. This book is no exception,
with the main focus on the design, use, and implementation of abstract data types.
The importance of designing and using abstract data types for easier modular pro-
gramming is emphasized throughout the text. The traditional data structures are
also presented throughout the text in terms of implementing the various abstract
data types. Multiple implementations using different data structures are used
throughout the text to reinforce the abstraction concept. Common algorithms are
also presented throughout the text as appropriate to provide complete coverage of
the typical data structures course.
Overview
The typical data structures course, which introduces a collection of fundamental
data structures and algorithms, can be taught using any of the different program-
ming languages available today. In recent years, more colleges have begun to adopt
the Python language for introducing students to programming and problem solv-
ing. Python provides several benefits over other languages such as C++ and Java,
the most important of which is that Python has a simple syntax that is easier to
learn. This book expands upon that use of Python by providing a Python-centric
text for the data structures course. The clean syntax and powerful features of the
language are used throughout, but the underlying mechanisms of these features
are fully explored not only to expose the “magic” but also to study their overall
efficiency.
For a number of years, many data structures textbooks have been written to
serve a dual role of introducing data structures and providing an in-depth study
of object-oriented programming (OOP). In some instances, this dual role may
compromise the original purpose of the data structures course by placing more focus
on OOP and less on the abstract data types and their underlying data structures.
To stress the importance of abstract data types, data structures, and algorithms, we
limit the discussion of OOP to the use of base classes for implementing the various
abstract data types. We do not use class inheritance or polymorphism in the main
part of the text but instead provide a basic introduction as an appendix. This
choice was made for several reasons. First, our objective is to provide a “back to
xiii
xiv PREFACE
Prerequisites
This book assumes that the student has completed the standard introduction to
programming and problem-solving course using the Python language. Since the
contents of the first course can differ from college to college and instructor to
instructor, we assume the students are familiar with or can do the following:
❼ Apply the basic data types and constructs, including loops, selection state-
ments, and subprograms (functions)
❼ Design and implement basics classes, including the use of helper methods and
private attributes
reordering of some topics. For example, the chapters on recursion and hashing can
be presented at any time after the discussion of algorithm analysis in Chapter 4.
Chapter 1: Abstract Data Types. Introduces the concept of abstract data types
(ADTs) for both simple types, those containing individual data fields, and the more
complex types, those containing data structures. ADTs are presented in terms
of their definition, use, and implementation. After discussing the importance of
abstraction, we define several ADTs and then show how a well-defined ADT can
be used without knowing how its actually implemented. The focus then turns to
the implementation of the ADTs with an emphasis placed on the importance of
selecting an appropriate data structure. The chapter includes an introduction to
the Python iterator mechanism and provides an example of a user-defined iterator
for use with a container type ADT.
Chapter 2: Arrays. Introduces the student to the array structure, which is im-
portant since Python only provides the list structure and students are unlikely to
have seen the concept of the array as a fixed-sized structure in a first course using
Python. We define an ADT for a one-dimensional array and implement it using a
hardware array provided through a special mechanism of the C-implemented ver-
sion of Python. The two-dimensional array is also introduced and implemented
using a 1-D array of arrays. The array structures will be used throughout the text
in place of the Python’s list when it is the appropriate choice. The implementa-
tion of the list structure provided by Python is presented to show how the various
operations are implemented using a 1-D array. The Matrix ADT is introduced and
includes an implementation using a two-dimensional array that exposes the stu-
dents to an example of an ADT that is best implemented using a structure other
than the list or dictionary.
Chapter 3: Sets and Maps. This chapter reintroduces the students to both
the Set and Map (or dictionary) ADTs with which they are likely to be familiar
from their first programming course using Python. Even though Python provides
these ADTs, they both provide great examples of abstract data types that can be
implemented in many different ways. The chapter also continues the discussion of
arrays from the previous chapter by introducing multi-dimensional arrays (those
of two or more dimensions) along with the concept of physically storing these
using a one-dimensional array in either row-major or column-major order. The
chapter concludes with an example application that can benefit from the use of a
three-dimensional array.
Chapter 8: Queues. Introduces the Queue ADT and includes three different
implementations: Python list, circular array, and linked list. The priority queue
is introduced to provide an opportunity to discuss different structures and data
organization for an efficient implementation. The application of the queue presents
the concept of discrete event computer simulations using an airline ticket counter
as the example.
Chapter 10: Recursion. Introduces the use of recursion to solve various pro-
gramming problems. The properties of creating recursive functions are presented
along with common examples, including factorial, greatest common divisor, and
the Towers of Hanoi. The concept of backtracking is revisited to use recursion for
solving the eight-queens problem.
PREFACE xvii
Chapter 11: Hash Tables. Introduces the concept of hashing and the use of hash
tables for performing fast searches. Different addressing techniques are presented,
including those for both closed and open addressing. Collision resolution techniques
and hash function design are also discussed. The magic behind Python’s dictionary
structure, which uses a hash table, is exposed and its efficiency evaluated.
Chapter 12: Advanced Sorting. Continues the discussion of the sorting problem
by introducing the recursive sorting algorithms—merge sort and quick sort—along
with the radix distribution sort algorithm, all of which can be used to sort se-
quences. Some of the common techniques for sorting linked lists are also presented.
Chapter 13: Binary Trees. Presents the tree structure and the general binary
tree specifically. The construction and use of the binary tree is presented along
with various properties and the various traversal operations. The binary tree is
used to build and evaluate arithmetic expressions and in decoding Morse Code
sequences. The tree-based heap structure is also introduced along with its use in
implementing a priority queue and the heapsort algorithm.
Chapter 14: Search Trees. Continues the discussion from the previous chapter
by using the tree structure to solve the search problem. The basic binary search
tree and the balanced binary search tree (AVL) are both introduced along with
new implementations of the Map ADT. Finally, a brief introduction to the 2-3
multi-way tree is also provided, which shows an alternative to both the binary
search and AVL trees.
Acknowledgments
There are a number of individuals I would like to thank for helping to make this
book possible. First, I must acknowledge two individuals who served as mentors
in the early part of my career. Mary Dayne Gregg (University of Southern Mis-
sissippi), who was the best computer science teacher I have ever known, shared
her love of teaching and provided a great role model in academia. Richard Prosl
(Professor Emeritus, College of William and Mary) served not only as my graduate
advisor but also shared great insight into teaching and helped me to become a good
teacher.
A special thanks to the many students I have taught over the years, especially
those at Washington and Lee University, who during the past five years used draft
versions of the manuscript and provided helpful suggestions. I would also like to
thank some of my colleagues who provided great advice and the encouragement
to complete the project: Sara Sprenkle (Washington and Lee University), Debbie
Noonan (College of William and Mary), and Robert Noonan (College of William
and Mary).
I am also grateful to the following individuals who served as outside review-
ers and provided valuable feedback and helpful suggestions: Esmail Bonakdarian
(Franklin University), David Dubin (University of Illinois at Urbana-Champaign)
Mark E. Fenner (Norwich University), Robert Franks (Central College), Charles J.
Leska (Randolph-Macon College), Fernando Martincic (Wayne State University),
Joseph D. Sloan (Wofford College), David A. Sykes (Wofford College), and Stan
Thomas (Wake Forest University).
Finally, I would like to thank everyone at John Wiley & Sons who helped make
this book possible. I would especially like to thank Beth Golub, Mike Berlin, and
Amy Weintraub, with whom I worked closely throughout the process and who
helped to make this first book an enjoyable experience.
Rance D. Necaise
CHAPTER 1
Abstract Data Types
1.1 Introduction
Data items are represented within a computer as a sequence of binary digits. These
sequences can appear very similar but have different meanings since computers
can store and manipulate different types of data. For example, the binary se-
quence 01001100110010110101110011011100 could be a string of characters, an in-
teger value, or a real value. To distinguish between the different types of data, the
term type is often used to refer to a collection of values and the term data type to
refer to a given type along with a collection of operations for manipulating values
of the given type.
Programming languages commonly provide data types as part of the language
itself. These data types, known as primitives, come in two categories: simple
and complex. The simple data types consist of values that are in the most
basic form and cannot be decomposed into smaller parts. Integer and real types,
for example, consist of single numeric values. The complex data types, on the
other hand, are constructed of multiple components consisting of simple types or
other complex types. In Python, objects, strings, lists, and dictionaries, which can
1
2 CHAPTER 1 Abstract Data Types
contain multiple values, are all examples of complex types. The primitive types
provided by a language may not be sufficient for solving large complex problems.
Thus, most languages allow for the construction of additional data types, known
as user-defined types since they are defined by the programmer and not the
language. Some of these data types can themselves be very complex.
1.1.1 Abstractions
To help manage complex problems and complex data types, computer scientists
typically work with abstractions. An abstraction is a mechanism for separat-
ing the properties of an object and restricting the focus to those relevant in the
current context. The user of the abstraction does not have to understand all of
the details in order to utilize the object, but only those relevant to the current task
or problem.
Two common types of abstractions encountered in computer science are proce-
dural, or functional, abstraction and data abstraction. Procedural abstraction
is the use of a function or method knowing what it does but ignoring how it’s
accomplished. Consider the mathematical square root function which you have
probably used at some point. You know the function will compute the square root
of a given number, but do you know how the square root is computed? Does it
matter if you know how it is computed, or is simply knowing how to correctly use
the function sufficient? Data abstraction is the separation of the properties of a
data type (its values and operations) from the implementation of that data type.
You have used strings in Python many times. But do you know how they are
implemented? That is, do you know how the data is structured internally or how
the various operations are implemented?
Typically, abstractions of complex problems occur in layers, with each higher
layer adding more abstraction than the previous. Consider the problem of repre-
senting integer values on computers and performing arithmetic operations on those
values. Figure 1.1 illustrates the common levels of abstractions used with integer
arithmetic. At the lowest level is the hardware with little to no abstraction since it
includes binary representations of the values and logic circuits for performing the
arithmetic. Hardware designers would deal with integer arithmetic at this level
and be concerned with its correct implementation. A higher level of abstraction
for integer values and arithmetic is provided through assembly language, which in-
volves working with binary values and individual instructions corresponding to the
underlying hardware. Compiler writers and assembly language programmers would
work with integer arithmetic at this level and must ensure the proper selection of
assembly language instructions to compute a given mathematical expression. For
example, suppose we wish to compute x = a + b − 5. At the assembly language
level, this expression must be split into multiple instructions for loading the values
from memory, storing them into registers, and then performing each arithmetic
operation separately, as shown in the following psuedocode:
Software-Implemented
Software-Implemented Higher Level
Big
Big Integers
Integers
High-Level
High-Level Language
Language
Instructions
Instructions
Assembly
Assembly Language
Language
Instructions
Instructions
Hardware
Hardware Lower Level
Implementation
Implementation
One problem with the integer arithmetic provided by most high-level languages
and in computer hardware is that it works with values of a limited size. On 32-bit
architecture computers, for example, signed integer values are limited to the range
−231 . . . (231 − 1). What if we need larger values? In this case, we can provide
long or “big integers” implemented in software to allow values of unlimited size.
This would involve storing the individual digits and implementing functions or
methods for performing the various arithmetic operations. The implementation
of the operations would use the primitive data types and instructions provided by
the high-level language. Software libraries that provide big integer implementations
are available for most common programming languages. Python, however, actually
provides software-implemented big integers as part of the language itself.
implementation, allowing us to focus on the use of the new data type instead of
how it’s implemented. This separation is typically enforced by requiring interac-
tion with the abstract data type through an interface or defined set of operations.
This is known as information hiding . By hiding the implementation details and
requiring ADTs to be accessed through an interface, we can work with an ab-
straction and focus on what functionality the ADT provides instead of how that
functionality is implemented.
Abstract data types can be viewed like black boxes as illustrated in Figure 1.2.
User programs interact with instances of the ADT by invoking one of the several
operations defined by its interface. The set of operations can be grouped into four
categories:
The implementation of the various operations are hidden inside the black box,
the contents of which we do not have to know in order to utilize the ADT. There
are several advantages of working with abstract data types and focusing on the
“what” instead of the “how.”
❼ We can focus on solving the problem at hand instead of getting bogged down
in the implementation details. For example, suppose we need to extract a
collection of values from a file on disk and store them for later use in our
program. If we focus on the implementation details, then we have to worry
about what type of storage structure to use, how it should be used, and
whether it is the most efficient choice.
❼ We can reduce logical errors that can occur from accidental misuse of storage
structures and data types by preventing direct access to the implementation. If
we used a list to store the collection of values in the previous example, there
is the opportunity to accidentally modify its contents in a part of our code
1.1 Introduction 5
where it was not intended. This type of logical error can be difficult to track
down. By using ADTs and requiring access via the interface, we have fewer
access points to debug.
❼ The implementation of the abstract data type can be changed without having
to modify the program code that uses the ADT. There are many times when
we discover the initial implementation of an ADT is not the most efficient or
we need the data organized in a different way. Suppose our initial approach
to the previous problem of storing a collection of values is to simply append
new values to the end of the list. What happens if we later decide the items
should be arranged in a different order than simply appending them to the
end? If we are accessing the list directly, then we will have to modify our code
at every point where values are added and make sure they are not rearranged
in other places. By requiring access via the interface, we can easily “swap out”
the black box with a new implementation with no impact on code segments
that use the ADT.
❼ It’s easier to manage and divide larger programs into smaller modules, al-
lowing different members of a team to work on the separate modules. Large
programming projects are commonly developed by teams of programmers in
which the workload is divided among the members. By working with ADTs
and agreeing on their definition, the team can better ensure the individual
modules will work together when all the pieces are combined. Using our pre-
vious example, if each member of the team directly accessed the list storing
the collection of values, they may inadvertently organize the data in different
ways or modify the list in some unexpected way. When the various modules
are combined, the results may be unpredictable.
There are many common data structures, including arrays, linked lists, stacks,
queues, and trees, to name a few. All data structures store a collection of values,
but differ in how they organize the individual data items and by what operations
can be applied to manage the collection. The choice of a particular data structure
depends on the ADT and the problem at hand. Some data structures are better
suited to particular problems. For example, the queue structure is perfect for
implementing a printer queue, while the B-Tree is the better choice for a database
index. No matter which data structure we use to implement an ADT, by keeping
the implementation separate from the definition, we can use an abstract data type
within our program and later change to a different implementation, as needed,
without having to modify our existing code.
list or vector abstract data type. To avoid confusion, we will use the term list to
refer to the data type provided by Python and use the terms general list or list
structure when referring to the more general list structure as defined earlier.
A date represents a single day in the proleptic Gregorian calendar in which the
first day starts on November 24, 4713 BC.
Date( month, day, year ): Creates a new Date instance initialized to the
given Gregorian date which must be valid. Year 1 BC and earlier are indicated
by negative year components.
day(): Returns the Gregorian day number of this date.
month(): Returns the Gregorian month number of this date.
year(): Returns the Gregorian year of this date.
monthName(): Returns the Gregorian month name of this date.
dayOfWeek(): Returns the day of the week as a number between 0 and 6 with
0 representing Monday and 6 representing Sunday.
numDays( otherDate ): Returns the number of days as a positive integer be-
tween this date and the otherDate.
isLeapYear(): Determines if this date falls in a leap year and returns the
appropriate boolean value.
8 CHAPTER 1 Abstract Data Types
advanceBy( days ): Advances the date by the given number of days. The date
is incremented if days is positive and decremented if days is negative. The
date is capped to November 24, 4714 BC, if necessary.
comparable ( otherDate ): Compares this date to the otherDate to deter-
mine their logical ordering. This comparison can be done using any of the
logical operators <, <=, >, >=, ==, !=.
toString (): Returns a string representing the Gregorian date in the format
mm/dd/yyyy. Implemented as the Python operator that is automatically called
via the str() constructor.
The abstract data types defined in the text will be implemented as Python
classes. When defining an ADT, we specify the ADT operations as method pro-
totypes. The class constructor, which is used to create an instance of the ADT, is
indicated by the name of the class used in the implementation.
Python allows classes to define or overload various operators that can be used
more naturally in a program without having to call a method by name. We define
all ADT operations as named methods, but implement some of them as operators
when appropriate instead of using the named method. The ADT operations that
will be implemented as Python operators are indicated in italicized text and a brief
comment is provided in the ADT definition indicating the corresponding operator.
This approach allows us to focus on the general ADT specification that can be
easily translated to other languages if the need arises but also allows us to take
advantage of Python’s simple syntax in various sample programs.
via the constructor before any operation can be used. Other than the initialization
requirement, an operation may not have any other preconditions. It all depends
on the type of ADT and the respective operation. Likewise, some operations may
not have a postcondition, as is the case for simple access methods, which simply
return a value without modifying the ADT instance itself. Throughout the text,
we do not explicitly state the precondition and postcondition as such, but they are
easily identified from the description of the ADT operations.
When implementing abstract data types, it’s important that we ensure the
proper execution of the various operations by verifying any stated preconditions.
The appropriate mechanism when testing preconditions for abstract data types is
to test the precondition and raise an exception when the precondition fails. You
then allow the user of the ADT to decide how they wish to handle the error, either
catch it or allow the program to abort.
Python, like many other object-oriented programming languages, raises an ex-
ception when an error occurs. An exception is an event that can be triggered
and optionally handled during program execution. When an exception is raised
indicating an error, the program can contain code to catch and gracefully handle
the exception; otherwise, the program will abort. Python also provides the assert
statement, which can be used to raise an AssertionError exception. The assert
statement is used to state what we assume to be true at a given point in the pro-
gram. If the assertion fails, Python automatically raises an AssertionError and
aborts the program, unless the exception is caught.
Throughout the text, we use the assert statement to test the preconditions
when implementing abstract data types. This allows us to focus on the implemen-
tation of the ADTs instead of having to spend time selecting the proper exception
to raise or creating new exceptions for use with our ADTs. For more information
on exceptions and assertions, refer to Appendix C.
Date Representations
There are two common approaches to storing a date in an object. One approach
stores the three components—month, day, and year—as three separate fields. With
this format, it is easy to access the individual components, but it’s difficult to
compare two dates or to compute the number of days between two dates since the
number of days in a month varies from month to month. The second approach
stores the date as an integer value representing the Julian day, which is the number
of days elapsed since the initial date of November 24, 4713 BC (using the Gregorian
calendar notation). Given a Julian day number, we can compute any of the three
Gregorian components and simply subtract the two integer values to determine
1.2 The Date Abstract Data Type 11
which occurs first or how many days separate the two dates. We are going to use
the latter approach as it is very common for storing dates in computer applications
and provides for an easy implementation.
T = (M - 14) / 12
jday = D - 32075 + (1461 * (Y + 4800 + T) / 4) +
(367 * (M - 2 - T * 12) / 12) -
(3 * ((Y + 4900 + T) / 100) / 4)
NOTE
To conserve space, however, classes and methods presented in this book
do not routinely include these comments since the surrounding text provides
a full explanation.
This allows for a more natural use of the objects instead of having to call
specific named methods. It can be tempting to define operators for every
class you create, but you should limit the definition of operator methods for
classes where the specific operator has a meaningful purpose.
1.3 Bags
The Date ADT provided an example of a simple abstract data type. To illustrate
the design and implementation of a complex abstract data type, we define the Bag
ADT. A bag is a simple container like a shopping bag that can be used to store a
collection of items. The bag container restricts access to the individual items by
only defining operations for adding and removing individual items, for determining
if an item is in the bag, and for traversing over the collection of items.
1.3 Bags 15
A bag is a container that stores a collection in which duplicate values are allowed.
The items, each of which is individually stored, have no particular order but they
must be comparable.
Bag(): Creates a bag that is initially empty.
length (): Returns the number of items stored in the bag. Accessed using
the len() function.
contains ( item ): Determines if the given target item is stored in the bag
and returns the appropriate boolean value. Accessed using the in operator.
remove( item ): Removes and returns an occurrence of item from the bag.
An exception is raised if the element is not in the bag.
iterator (): Creates and returns an iterator that can be used to iterate over
the collection of items.
You may have noticed our definition of the Bag ADT does not include an
operation to convert the container to a string. We could include such an operation,
but creating a string for a large collection is time consuming and requires a large
amount of memory. Such an operation can be beneficial when debugging a program
that uses an instance of the Bag ADT. Thus, it’s not uncommon to include the
str operator method for debugging purposes, but it would not typically be used
in production software. We will usually omit the inclusion of a str operator
method in the definition of our abstract data types, except in those cases where it’s
meaningful, but you may want to include one temporarily for debugging purposes.
Examples
Given the abstract definition of the Bag ADT, we can create and use a bag without
knowing how it is actually implemented. Consider the following simple example,
which creates a bag and asks the user to guess one of the values it contains.
16 CHAPTER 1 Abstract Data Types
myBag = Bag()
[Link]( 19 )
[Link]( 74 )
[Link]( 23 )
[Link]( 19 )
[Link]( 12 )
Next, consider the [Link] sample program from the previous section
where we extracted birth dates from the user and determined which ones were
for individuals who were at least 21 years of age. Suppose we want to keep the
collection of birth dates for later use. It wouldn’t make sense to require the user to
re-enter the dates multiple times. Instead, we can store the birth dates in a bag as
they are entered and access them later, as many times as needed. The Bag ADT
is a perfect container for storing objects when the position or order of a specific
item does not matter. The following is a new version of the main routine for our
birth date checking program from Listing 1.1:
def main():
bornBefore = Date( 6, 1, 1988 )
bag = Bag()
# Extract dates from the user and place them in the bag.
date = promptAndExtractDate()
while date is not None :
[Link]( date )
date = promptAndExtractDate()
1. Does the data structure provide for the storage requirements as specified by
the domain of the ADT? Abstract data types are defined to work with a
specific domain of data values. The data structure we choose must be capable
of storing all possible values in that domain, taking into consideration any
restrictions or limitations placed on the individual items.
2. Does the data structure provide the necessary data access and manipulation
functionality to fully implement the ADT? The functionality of an abstract
data type is provided through its defined set of operations. The data structure
must allow for a full and correct implementation of the ADT without having
to violate the abstraction principle by exposing the implementation details to
the user.
3. Does the data structure lend itself to an efficient implementation of the oper-
ations? An important goal in the implementation of an abstract data type is
to provide an efficient solution. Some data structures allow for a more effi-
cient implementation than others, but not every data structure is suitable for
implementing every ADT. Efficiency considerations can help to select the best
structure from among multiple candidates.
There may be multiple data structures suitable for implementing a given ab-
stract data type, but we attempt to select the best possible based on the context
in which the ADT will be used. To accommodate different contexts, language
libraries will commonly provide several implementations of some ADTs, allowing
the programmer to choose the most appropriate. Following this approach, we in-
troduce a number of abstract data types throughout the text and present multiple
implementations as new data structures are introduced.
The efficiency of an implementation is based on complexity analysis, which is
not introduced until later in Chapter 3. Thus, we postpone consideration of the
efficiency of an implementation in selecting a data structure until that time. In
the meantime, we only consider the suitability of a data structure based on the
storage and functional requirements of the abstract data type.
18 CHAPTER 1 Abstract Data Types
We now turn our attention to selecting a data structure for implementing the
Bag ADT. The possible candidates at this point include the list and dictionary
structures. The list can store any type of comparable object, including duplicates.
Each item is stored individually, including duplicates, which means the reference
to each individual object is stored and later accessible when needed. This satisfies
the storage requirements of the Bag ADT, making the list a candidate structure
for its implementation.
The dictionary stores key/value pairs in which the key component must be
comparable and unique. To use the dictionary in implementing the Bag ADT, we
must have a way to store duplicate items as required by the definition of the ab-
stract data type. To accomplish this, each unique item can be stored in the key
part of the key/value pair and a counter can be stored in the value part. The
counter would be used to indicate the number of occurrences of the corresponding
item in the bag. When a duplicate item is added, the counter is incremented; when
a duplicate is removed, the counter is decremented.
Both the list and dictionary structures could be used to implement the Bag
ADT. For the simple version of the bag, however, the list is a better choice since
the dictionary would require twice as much space to store the contents of the bag
in the case where most of the items are unique. The dictionary is an excellent
choice for the implementation of the counting bag variation of the ADT.
Having chosen the list, we must ensure it provides the means to implement the
complete set of bag operations. When implementing an ADT, we must use the
functionality provided by the underlying data structure. Sometimes, an ADT op-
eration is identical to one already provided by the data structure. In this case, the
implementation can be quite simple and may consist of a single call to the corre-
sponding operation of the structure, while in other cases, we have to use multiple
operations provided by the structure. To help verify a correct implementation
of the Bag ADT using the list, we can outline how each bag operation will be
implemented:
From this itemized list, we see that each Bag ADT operation can be imple-
mented using the available functionality of the list. Thus, the list is suitable for
implementing the bag.
1.3 Bags 19
Most of the implementation details follow the specifics discussed in the previous
section. There are some additional details, however. First, the ADT definition
of the remove() operation specifies the precondition that the item must exist
in the bag in order to be removed. Thus, we must first assert that condition
and verify the existence of the item. Second, we need to provide an iteration
mechanism that allows us to iterate over the individual items in the bag. We delay
theItems • 19
19 74
74 23
23 19
19 12
12
Bag 0 1 2 3 4
Figure 1.3: Sample instance of the Bag class implemented using a list.
20 CHAPTER 1 Abstract Data Types
the implementation of this operation until the next section where we discuss the
creation and use of iterators in Python.
A list stores references to objects and technically would be illustrated as shown
in the figure to the right. To conserve space and reduce the clutter that can result
in some figures, however, we illustrate objects in the text as boxes with rounded
edges and show them stored directly Bag 0 1 2 3 4
within the list structure. Variables theItems • • • • • •
will be illustrated as square boxes
with a bullet in the middle and the Bag
name of the variable printed nearby. 19
19 74 74 23
23 1919 1212
Bag
1.4 Iterators
Traversals are very common operations, especially on containers. A traversal iter-
ates over the entire collection, providing access to each individual element. Traver-
sals can be used for a number of operations, including searching for a specific item
or printing an entire collection.
Python’s container types—strings, tuples, lists, and dictionaries—can be tra-
versed using the for loop construct. For our user-defined abstract data types, we
can add methods that perform specific traversal operations when necessary. For
example, if we wanted to save every item contained in a bag to a text file, we could
add a saveElements() method that traverses over the vector and writes each value
to a file. But this would limit the format of the resulting text file to that specified
in the new method. In addition to saving the items, perhaps we would like to
simply print the items to the screen in a specific way. To perform the latter, we
would have to add yet another operation to our ADT.
Not all abstract data types should provide a traversal operation, but it is appro-
priate for most container types. Thus, we need a way to allow generic traversals to
be performed. One way would be to provide the user with access to the underlying
data structure used to implement the ADT. But this would violate the abstraction
principle and defeat the purpose of defining new abstract data types.
Python, like many of today’s object-oriented languages, provides a built-in it-
erator construct that can be used to perform traversals on user-defined ADTs. An
iterator is an object that provides a mechanism for performing generic traversals
through a container without having to expose the underlying implementation. Iter-
ators are used with Python’s for loop construct to provide a traversal mechanism
for both built-in and user-defined containers. Consider the code segment from the
[Link] program in Section 1.3 that uses the for loop to traverse the
collection of dates:
Listing 1.4 The BagIterator class, which is part of the [Link] module.
The next method is called to return the next item in the container. The
method first saves a reference to the current item indicated by the loop variable.
The loop variable is then incremented by one to prepare it for the next invocation
of the next method. If there are no additional items, the method must raise a
StopIteration exception that flags the for loop to terminate. Finally, we must
add an iter method to our Bag class, as shown here:
This method, which is responsible for creating and returning an instance of the
BagIterator class, is automatically called at the beginning of the for loop to
create an iterator object for use with the loop construct.
22 CHAPTER 1 Abstract Data Types
is executed, Python automatically calls the iter method on the bag object
to create an iterator object. Figure 1.4 illustrates the state of the BagIterator
object immediately after being created. Notice the bagItems field of the iterator
object references theItems field of the bag object. This reference was assigned
by the constructor when the BagIterator object was created.
bagVectorcurItem
curItem
•• 0000
_BagIterator
theItems •• 19
19 74
74 23
23 19
19 12
12
Bag 0 1 2 3 4
Figure 1.4: The Bag and BagIterator objects before the first loop iteration.
The for loop then automatically calls the next method on the iterator
object to access the next item in the container. The state of the iterator object
changes with the curItem field having been incremented by one. This process
continues until a StopIteration exception is raised by the next method when
the items have been exhausted as indicated by the curItem. After all of the items
have been processed, the iteration is terminated and execution continues with the
next statement following the loop. The following code segment illustrates how
Python actually performs the iteration when a for loop is used with an instance
of the Bag class:
# Create a BagIterator object for myBag.
iterator = myBag.__iter__()
# Catch the exception and break from the loop when we are done.
except StopIteration:
break
1.5 Application: Student Records 23
LIST OF STUDENTS
Our contact in the Registrar’s office, who assigned the task, has provided some
information about the data. We know each record contains five pieces of infor-
mation for an individual student: (1) the student’s id number represented as an
integer; (2) their first and last names, which are strings; (3) an integer classification
code in the range [1 . . . 4] that indicates if the student is a freshman, sophomore,
junior, or senior; and (4) their current grade point average represented as a floating-
point value. What we have not been told, however, is how the data is stored on
disk. It could be stored in a plain text file, in a binary file, or even in a database.
In addition, if the data is stored in a text or binary file, we will need to know how
the data is formatted in the file, and if it’s in a relational database, we will need
to know the type and the structure of the database.
A student file reader is used to extract student records from external storage. The
five data components of the individual records are extracted and stored in a storage
object specific for this collection of student records.
StudentFileReader( filename ): Creates a student reader instance for ex-
tracting student records from the given file. The type and format of the file
is dependent on the specific implementation.
open(): Opens a connection to the input source and prepares it for extracting
student records. If a connection cannot be opened, an exception is raised.
close(): Closes the connection to the input source. If the connection is not
currently open, an exception is raised.
fetchRecord(): Extracts the next student record from the input source and
returns a reference to a storage object containing the data. None is returned
when there are no additional records to be extracted. An exception is raised
if the connection to the input source was previously closed.
sorted in ascending order based on the student identification number. The actual
report is produced by passing the sorted list to the printReport() function.
Storage Class
When the data for an individual student is extracted from the input file, it will
need to be saved in a storage object that can be added to a list in order to first
sort and then print the records. We could use tuples to store the records, but we
26 CHAPTER 1 Abstract Data Types
avoid the use of tuples when storing structured data since it’s better practice to
use classes with named fields. Thus, we define the StudentRecord class
class StudentRecord :
def __init__( self ):
[Link] = 0
[Link] = None
[Link] = None
[Link] = 0
[Link] = 0.0
to store the data related to an individual student. You may notice there is only a
constructor with no additional methods. This is a complete class as defined and
represents a storage class. The constructor is all that’s needed to define the two
data fields for storing the two component values.
Storage classes should be defined within the same module as the class with
which they will be used. For this application, the StudentRecord class is defined
at the end of the [Link] module. Some storage classes may be intended
for internal use by a specific class and not meant to be accessed from outside the
module. In those cases, the name of the storage class will begin with a single
underscore, which flags it as being private to the module in which it’s defined.
The StudentRecord class, however, has not been defined as being private to the
module since instances of the storage class are not confined to the ADT but in-
stead are returned to the client code by methods of the StudentFileReader class.
The storage class can be imported along with the StudentFileReader class when
needed.
You will note the data fields in the storage class are public (by our notation)
since their names do not begin with an underscore as they have been in other
classes presented earlier. The reason we do not include a restrictive interface for
accessing the data fields is that storage objects are meant to be used exclusively
for storing data and not as an instance of some abstract data type. Given their
limited use, we access the data fields directly as needed.
1.5.2 Implementation
The implementation of the Student File Reader ADT does not require a data
structure since it does not store data but instead extracts data from an external
source. The ADT has to be implemented to extract data based on the format in
which the data is stored. For this example, we are going to extract the data from
Python Tuples. The tuple can be used to store structured data, with
!
CAUTION
a text file in which the records are listed one after the other. The five fields of the
record are each stored on a separate line. The first line contains the id number,
the second and third contain the first and last names, the fourth line contains
the classification code, and the grade point average follows on the fifth line. The
following text block illustrates the format for a file containing two records:
10015
John
Smith
2
3.01
10334
Jane
Roberts
4
3.81
Listing 1.6 provides the implementation of the ADT for extracting the records
from the text file in the given format. The constructor simply initializes an instance
of the class by creating two attributes, one to store the name the text file and the
other to store a reference to the file object after it’s opened. The open() method
is responsible for opening the input file using the name saved in the constructor.
The resulting file object is saved in the inputFile attribute so it can be used in
the other methods. After the records are extracted, the file is closed by calling the
close() method.
Exercises
1.1 Complete the partial implementation of the Date class by implementing the
remaining methods: monthName(), isLeapYear(), numDays(), advanceBy(),
Programming Projects 29
November 2007
Su Mo Tu We Th Fr Sa
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30
1.4 Modify the Date() constructor to make each of the three arguments optional,
with an initial value of zero. When no argument is supplied to the constructor,
the object should be initialized to the current date. Hint: You will need to
use Python’s date() function from the [Link] module.
Programming Projects
1.1 A click counter is a small hand-held device that contains a push button and
a count display. To increment the counter, the button is pushed and the new
count shows in the display. Clicker counters also contain a button that can be
pressed to reset the counter to zero. Design and implement the Counter ADT
that functions as a hand-held clicker.
1.2 A Grab Bag ADT is similar to the Bag ADT with one difference. A grab
bag does not have a remove() operation, but in place of it has a grabItem()
operation, which allows for the random removal of an item from the bag.
Implement the Grab Bag ADT.
30 CHAPTER 1 Abstract Data Types
1.3 A Counting Bag ADT is just like the Bag ADT but includes the numOf(item)
operation, which returns the number of occurrences of the given item in the
bag. Implement the Counting Bag ADT and defend your selection of data
structure.
1.4 The use of the Student File Reader ADT makes it easy to extract student
records from a text file no matter the format used to store the data. Implement
a new version of the ADT to extract the data from a text file in which each
record is stored on a separate line and the individual fields are separated by
commas. For example, the following illustrates the format of a sample file
containing three student records:
1.5 In the chapter, we defined and implemented the Student File Reader ADT for
extracting student records from an external source. We can define and use a
similar ADT for output.
(a) Design a Student File Writer ADT that can be used to display, or store to
an output device, student records contained in a StudentRecord object.
(b) Provide an implementation of your ADT to output the records by display-
ing them to the terminal in a neatly formatted fashion.
(c) Provide an implementation of your ADT to output the records to a text
file using the same format described in the text.
(d) Design and implement a complete program that extracts student records
from a text file, sorts them by either student id or student name, and
displays them to the terminal using your ADT. The choice of sort keys
should be extracted from the user.
1.6 We can use a Time ADT to represent the time of day, for any 24-hour period,
as the number of seconds that have elapsed since midnight. Given the following
list of operations, implement the Time ADT.
Time( hours, minutes, seconds ): Creates a new Time instance and ini-
tializes it with the given time.
hour(): Returns the hour part of the time.
minutes(): Returns the minutes part of the time.
seconds(): Returns the seconds part of the time.
numSeconds( otherTime ): Returns the number of seconds as a positive
integer between this time and the otherTime.
isAM(): Determines if this time is ante meridiem or before midday (at or
before 12 o’clock noon).
Programming Projects 31
1.7 Design and implement a TimeDate ADT that can be used to represent both
a date and time as a single entity.
1.8 A line segment is a straight line bounded by two endpoints. The Line Segment
ADT, whose operations are described below, represents a line segment defined
by points in the two-dimensional Cartesian coordinate system. Use the Point
class from Appendix D and implement the Line Segment ADT.
LineSegment( ptA, ptB ): Creates a new Line Segment instance defined
by the two Point objects.
endPointA(): Returns the first endpoint of the line.
endPointB(): Returns the second endpoint of the line.
length (): Returns the length of the line segment given as the Euclidean
distance between the two endpoints.
toString (): Returns a string representation of the line segment in the
format (Ax, Ay)#(Bx, By).
isVertical(): Is the line segment parallel to the y-axis?
isHorizontal(): Is the line segment parallel to the x-axis?
isParallel( otherLine ): Is this line segment parallel to the otherLine?
isPerpendicular( otherLine ): Is this line segment perpendicular to the
otherLine?
intersects(otherLine ): Does this line segment intersect the otherLine?
bisects( otherLine ): Does this line segment bisect the otherLine?
slope(): Returns the slope of the line segment given as the rise over the
run. If the line segment is vertical, None is returned.
shift( xInc, yInc ): Shifts the line segment by xInc amount along the
x-axis and yInc amount along the y-axis.
midpoint(): Returns the midpoint of the line segment as a Point object.
1.9 A polygon is a closed geometric shape consisting of three or more line segments
that are connected end to end. The endpoints of the line segments are known
as vertices, which can be defined by points in the two-dimensional Cartesian
coordinate system.
32 CHAPTER 1 Abstract Data Types
(a) Define a Polygon ADT to represent a geometric polygon and provide a set
of appropriate operations.
(b) Provide a Python implementation of your Polygon ADT.
1.10 Anyone who is involved in many activities typically uses a calendar to keep
track of the various activities. Colleges commonly maintain several calendars
such as an academic calendar, a school events calendar, and a sporting events
calendar. We have defined an Activities Calendar ADT below that can keep
track of one activity per day over a given range of dates. Select a data structure
and implement the ADT.
ActivitiesCalendar( dateFrom, dateTo ): Creates a new empty activ-
ities calendar initialized to the given range of dates. The date range can
be specified for any non-overlapping period. The only requirements are
that dateFrom must precede dateTo and dateTo cannot overlap the day
and month of dateFrom for the next year.
length (): Returns the number of activities on the calendar.
getActivity( date ): Returns the string that describes the activity for
the given date if an activity exists for the given date; otherwise, None is
returned.
addActivity( date, activity ): Adds the given activity description to
the calendar for the given date. The date must be within the valid date
range for the calendar.
displayMonth( month ): Displays to standard output all activities for the
given month. The display includes the year and name of the month and
the list of activities for the month. The display of each activity includes
the day of the month on which the activity occurs and the description
of the activity.
1.11 Python provides a numeric class for working with floating-point values. But
not all real numbers can be represented precisely on a computer since they are
stored as binary values. In applications where the precision of real numbers
is important, we can use rational numbers or fractions to store exact values.
A fraction, such as 78 , consists of two parts, both of which are integers. The
top value, which can be any integer value, is known as the numerator. The
bottom value, which must be greater than zero, is known as the denominator.
(a) Define a Fraction ADT to represent and store rational numbers. The ADT
should include all of the common mathematical and logical operations. In
addition, your ADT should provide for the conversion between floating-
point values and fractions and the ability to produce a string version of
the fraction.
(b) Provide a Python implementation of your Fraction ADT.
CHAPTER 2
Arrays
The most basic structure for storing and accessing a collection of data is the array.
Arrays can be used to solve a wide range of problems in computer science. Most
programming languages provide this structured data type as a primitive and allow
for the creation of arrays with multiple dimensions. In this chapter, we implement
an array structure for a one-dimensional array and then use it to implement a
two-dimensional array and the related matrix structure.
10
10 51
51 22 18
18 44 31
31 13
13 55 23
23 64
64 29
0 1 2 3 4 5 6 7 8 9 10
33
34 CHAPTER 2 Arrays
But underneath, this results in the allocation of space for up to 200,000 elements,
half of which will go to waste. In this case, an array would be a better choice.
The decision as to whether an array or list should be used is not limited to
the size of the sequence structure. It also depends on how it will be used. The
list provides a large set of operations for managing the items contained in the list.
Some of these include inserting an item at a specific location, searching for an
item, removing an item by value or location, easily extracting a subset of items,
and sorting the items. The array structure, on the other hand, only provides a
limited set of operations for accessing the individual elements comprising the array.
Thus, if the problem at hand requires these types of operations, the list is the better
choice.
quences. We can define the Array ADT to represent a one-dimensional array for
use in Python that works similarly to arrays found in other languages. It will be
used throughout the text when an array structure is required.
getitem ( index ): Returns the value stored in the array at element position
index. The index argument must be within the valid range. Accessed using
the subscript operator.
setitem ( index, value ): Modifies the contents of the array element at po-
sition index to contain value. The index must be within the valid range.
Accessed using the subscript operator.
iterator (): Creates and returns an iterator that can be used to traverse the
elements of the array.
Some computer scientists consider the array a physical structure and not an
abstraction since arrays are implemented at the hardware level. But remember,
there are only three basic operations available with the hardware-implemented
array. As part of our Array ADT, we have provided for these operations but have
also included an iterator and operations for obtaining the size of the array and for
setting every element to a given value. In this case, we have provided a higher level
of abstraction than that provided by the underlying hardware-implemented array.
The following simple program illustrates the creation and use of an array object
based on the Array ADT. Comments are provided to highlight the use of the
operator methods.
# Fill a 1-D array with random values, then print them, one per line.
As a second example, suppose you need to read the contents of a text file and
count the number of letters occurring in the file with the results printed to the
terminal. We know that characters are represented by the ASCII code, which
consists of integer values. The letters of the alphabet, both upper- and lowercase,
are part of what’s known as the printable range of the ASCII code. This includes
the ASCII values in the range [32 . . . 126] along with some of the codes with smaller
values. The latter are known control characters and can include the tab, newline,
and form-feed codes. Since all of the letters will have ASCII values less than 127,
we can create an array of this size and let each element represent a counter for
the corresponding ASCII value. After processing the file, we can traverse over the
elements used as counters for the letters of the alphabet and ignore the others.
The following program provides a solution to this problem using the Array ADT:
# Open the text file for reading and extract each line from the file
# and iterate over each character in the line.
theFile = open( '[Link]', 'r' )
for line in theFile :
for letter in line :
code = ord( letter )
theCounters[code] += 1
# Close the file
[Link]()
# Print the results. The uppercase letters have ASCII values in the
# range 65..90 and the lowercase letters are in the range 97..122.
for i in range( 26 ) :
print( "%c - %4d %c - %4d" % \
(chr(65+i), theCounters[65+i], chr(97+i), theCounters[97+i]) )
syntax for working with the complete functionality available by the underlying
hardware. That syntax, however, can be somewhat cryptic compared to Python,
especially for a Python programmer who may not be familiar with C.
import ctypes
ArrayType = ctypes.py_object * 5
slots = ArrayType()
slots ••
0 1 2 3 4
each of which can store a reference to an object. After the array has been created,
the elements can be accessed using the same integer subscript notation as used
with Python’s own sequence types. For the slots array, the legal range is [0 . . . 4].
The elements of the array have to be initialized before they can be used. If we
attempt to read the contents of an element in the slots array before it has been
initialized
print( slots[0] )
38 CHAPTER 2 Arrays
an exception would be raised in the same way as if we tried to print the value of
a variable sum, that had not previously been assigned a value. Thus, the array
should be initialized immediately after it has been created by assigning a value to
each element using the subscript notation. Any value can be used, but a logical
choice is to assign None to each element:
for i in range( 5 ) :
slots[i] = None
The elements of the array can now be treated like any other variable in Python
that contains a null reference:
slots •• • • • • •
0 1 2 3 4
You may have noticed that we used the literal 5 with the range() function
to indicate the number of elements to be initialized. This was necessary because
a hardware-supported array does not keep track of the array size; it’s up to the
programmer to remember or maintain this value. Likewise, the programmer must
also ensure they do not access an element outside the legal range.
References to any type of Python object can be stored in any element of the
array. For example, the following code segment stores three integers in various
elements of the array:
slots[1] = 12
slots[3] = 54
slots[4] = 37
slots •• • 12
•
12 • 54
•
54 39
•
39
0 1 2 3 4
The operations provided by the array only allow for setting a given element
to a given reference or accessing a reference stored in a given element. To remove
an item from the array, we simply set the corresponding element to None. For
example, suppose we want to remove value 54 from the array
slots[3] = None
slots •• • 12
•
12 • • 39
•
39
0 1 2 3 4
2.1 The Array Structure 39
The size of the array can never change, so removing an item from an array
has no effect on the size of the array or on the items stored in other elements.
The array does not provide any of the list type operations such as appending or
popping items, searching for a specific item, or sorting the items. To use such an
operation with an array, you would have to provide the necessary code yourself.
1 # Implements the Array ADT using array capabilities of the ctypes module.
2 import ctypes
3
4 class Array :
5 # Creates an array with size elements.
6 def __init__( self, size ):
7 assert size > 0, "Array size must be > 0"
8 self._size = size
9 # Create the array structure using the ctypes module.
10 PyArrayType = ctypes.py_object * size
11 self._elements = PyArrayType()
12 # Initialize each element.
13 [Link]( None )
14
15 # Returns the size of the array.
16 def __len__( self ):
17 return self._size
18
19 # Gets the contents of the index element.
20 def __getitem__( self, index ):
21 assert index >= 0 and index < len(self), "Array subscript out of range"
22 return self._elements[ index ]
23
24 # Puts the value in the array element at index position.
25 def __setitem__( self, index, value ):
26 assert index >= 0 and index < len(self), "Array subscript out of range"
27 self._elements[ index ] = value
28
29 # Clears the array by setting each element to the given value.
30 def clear( self, value ):
31 for i in range( len(self) ) :
32 self._elements[i] = value
33
34 # Returns the array's iterator for traversing the elements.
35 def __iter__( self ):
36 return _ArrayIterator( self._elements )
37
38 # An iterator for the Array ADT.
39 class _ArrayIterator :
✭▲✐st✐♥❣ ❈♦♥t✐♥✉❡❞✮
40 CHAPTER 2 Arrays
The constructor, as shown in lines 6–13, handles the creation and initialization
of the array using the technique described earlier. It also defines two data fields
needed for the implementation of the Array ADT: one to store a reference to the
array structure and another to store the number of elements allocated for the
array. The latter is needed since hardware-supported arrays do not keep track of
this value. The initialization of the array is done by calling the clear() method.
The clear() method is used to set each element of the array to a given value,
which it does by iterating over the elements using an index variable. The len
method, which returns the number of elements in the array, simply returns the
value of size that was saved in the constructor. The iter method creates
and returns an instance of the ArrayIterator private iterator class, which is
provided in lines 39–53 of Listing 2.1.
The definition of the Array ADT calls for the implementation of the subscript
operator, which allows for the use of array objects in a manner similar to other
Python collection types. In Python, as in most languages, the subscript notation
can be used to read the contents of an array element or to modify an element. Thus,
there are two different methods that must be defined, as shown in lines 20–27. First,
the getitem operator method takes the array index as an argument and returns
the value of the corresponding element. The precondition must first be verified to
ensure the subscript is within the valid range.
When the subscript notation is used in a program, y = x[i], Python will call
the getitem method, passing the value of i to the index parameter. Since
Python expects the getitem method to return a value, it is your responsibility
to make sure this occurs.
The setitem operator method is used to set or change the contents of a
specific element of the array. It takes two arguments: the array index of the element
being modified and the new value that will be stored in that element. Before the
element is modified, the precondition must be tested to verify the subscript is
within the valid range. Python automatically calls the setitem method when
the subscript notation is used to assign a value to a specific element, x[i] = y.
The index, i, specified in the subscript is passed as the first argument and the
value to be assigned is passed as the second argument, __setitem__(i,y).
2.2 The Python List 41
which results in the list() constructor being called to create a list object and fill
it with the given values. When the list() constructor is called, an array structure
is created to store the items contained in the list. The array is initially created
bigger than needed, leaving capacity for future expansion. The values stored in the
list comprise a subarray in which only a contiguous subset of the array elements
are actually used.
Figure 2.2 illustrates the abstract and physical views of our sample list. In
the physical view, the elements of the array structure used to store the actual
contents of the list are enclosed inside the dashed gray box. The elements with
null references shown outside the dashed gray box are the remaining elements of
the underlying array structure that are still available for use. This notation will be
used throughout the section to illustrate the contents of the list and the underlying
array used to implement it.
abstract view
44 12
12 22 34
34 17
17
0 1 2 3 4
length 55
physical view
capacity 88
array • 44 12
12 22 34
34 17
17 • • •
0 1 2 3 4 5 6 7
Figure 2.2: The abstract and physical views of a list implemented using an array.
42 CHAPTER 2 Arrays
The length of the list, obtained using len(), is the number of items currently
in the subarray and not the size of the underlying array. The size or capacity of
the array used to implement the list must be maintained in order to know when
the array is full. Python does not provide a method to access the capacity value
since that information is not part of the list definition.
[Link]( 50 )
If there is room in the array, the item is stored in the next available slot of the
array and the length field is incremented by one. The result of appending 50 to
pyList is illustrated in Figure 2.3.
pyList
44 12
12 22 34
34 17 50 • •
0 1 2 3 4 5 6 7
What happens when the array becomes full and there are no free elements in
which to add a new list item? For example, consider the following list operations:
[Link]( 18 )
[Link]( 64 )
[Link]( 6 )
After the second statement is executed, the array becomes full and there is no
available space to add more values as illustrated in Figure 2.4.
By definition, a list can contain any number of items and never becomes full.
Thus, when the third statement is executed, the array will have to be expanded to
make room for value 6. From the discussion in the previous section, we know an
array cannot change size once it has been created. To allow for the expansion of
pyList
44 12
12 22 34
34 17
17 50
50 18
18 64
0 1 2 3 4 5 6 7
the list, the following steps have to be performed: (1) a new array is created with
additional capacity, (2) the items from the original array are copied to the new
array, (3) the new larger array is set as the data structure for the list, and (4) the
original smaller array is destroyed. After the array has been expanded, the value
can be appended to the end of the list. In Python, the amount by which the size
of the array is increased is proportional to the current array size. For illustration
purposes, we assume an expansion creates a new array that is double the size of
the original. The result of expanding the array and appending value 6 to the list
is shown in Figure 2.5.
• • • • • • • • • • • • • • • •
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
(2) The values from the original array are copied to the new larger array.
44 12
12 2 34
34 17
17 50
50 18
18 64
64
element-by-element copy
•44 12
•
12 •22 34
•
34 17
•
17 50
•
50 18
• 64
•
64 • • • • • • • •
pyList
•4 •
12
12 •22 •
34
34 •
17
17 •
50
50 •
18
18 •
64
64 • • • • • • • •
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
pyList
•4 •
12
12 •22 •
34
34 •
17
17 •
50
50 •
18
18 •
64
64 •66 • • • • • • •
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Figure 2.5: The steps required to expand the array to provide space for value 6.
44 CHAPTER 2 Arrays
If the list being extended has the capacity to store all of the elements from
the second list, the elements are simply copied, element by element. If there is not
enough capacity for all of the elements, the underlying array has to be expanded as
was done with the append() method. Since Python knows how big the array needs
to be in order to store all of the elements from both lists, it only requires a single
expansion of the destination list, pyListA. The new array will be created larger
than needed to allow more items to be added to the list without first requiring an
immediate expansion of the array. After the new array is created, elements from
the destination list are copied to the new array followed by the elements from the
source list, pyListB, as illustrated in Figure 2.6.
pyListA pyListB
34
34 12
12 • • 44 66 31
31 99 • • • •
0 1 2 3 0 1 2 3 4 5 6 7
pyListA
34
34 12
12 44 66 31
31 99 • •
0 1 2 3 4 5 6 7
we insert the value 79 at index position 3. Since there is already an item at that
position, we must make room for the new item by shifting all of the items down
one position starting with the item at index position 3. After shifting the items,
the value 79 is then inserted at position 3 as illustrated in Figure 2.7. If there are
no free slots for the new item, the list will be expanded in the same fashion as
described earlier.
2.2 The Python List 45
pyList 6 5 4 3 2 1
(a) •4 •
12
12 •22 •
34
34 •
17
17 •
50
50 •
18
18 •
64
64 •66 • • • • • • •
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
79
79
pyList
(b) •4 •
12
12 •22 •
34
34 •
17
17 •
50
50 •
18
18 •
64
64 •6 • • • • • •
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
pyList
(c) •4 •
12
12 •22 79
79 •
34
34 •
17
17 •
50
50 •
18
18 •
64
64 •6 • • • • • •
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Figure 2.7: Inserting an item into a list: (a) the array elements are shifted to the right one
at a time, traversing from right to left; (b) the new value is then inserted into the array at
the given position; (c) the result after inserting the item.
Removing Items
An item can be removed from any position within the list using the pop() method.
Consider the following code segment, which removes both the first and last items
from the sample list:
The first statement removes the first item from the list. After the item is
removed, typically by setting the reference variable to None, the items following it
within the array are shifted down, from left to right, to close the gap. Finally, the
length of the list is decremented to reflect the smaller size. Figure 2.8 on the next
page illustrates the process of removing the first item from the sample list. The
second pop() operation in the example code removes the last item from the list.
Since there are no items following the last one, the only operations required are to
remove the item and decrement the size of the list.
After removing an item from the list, the size of the array may be reduced using
a technique similar to that for expansion. This reduction occurs when the number
of available slots in the internal array falls below a certain threshold. For example,
when more than half of the array elements are empty, the size of the array may be
cut in half.
44
pyList
(a) 12
•
12 •22 •
79
79 •
34
34 •
17
17 •
50
50 •
18
18 •
64
64 6 • • • • • •
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 2 3 4 5 6 7 8 9
(b) 12
•
12 •22 79
79 •
34
34 •
17
17 •
50
50 •
18
18 •
64
64 •6 • • • • • •
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
pyList
(c) •
12
12 •22 •
79
79 34
34 •
17
17 •
50
50 •
18
18 •
64
64 •66 • • • • • • •
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Figure 2.8: Removing an item from a list: (a) a copy of the item is saved; (b) the array
elements are shifted to the left one at a time, traversing left to right; and (c) the size of the
list is decremented by one.
new list. In Python, slicing is performed on a list using the colon operator and
specifying the beginning element index and the number of elements included in the
subset. Consider the following example code segment, which creates a slice from
our sample list:
aSlice = theVector[2:3]
To slice a list, a new list is created with a capacity large enough to store the
entire subset of elements plus additional space for future insertions. The elements
within the specified range are then copied, element by element, to the new list.
The result of creating the sample slice is illustrated in Figure 2.9.
pyList
•
12
12 •22 •
79
79 34
34 •
17
17 •
50
50 •
18
18 •
64
64 • • • • • • • •
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
aSlice
79
79 34
34 3•4
34 •
0 1 2 3
columns
0 1 2 3 4
elements 0
0 1 2 3 4 5
rows
1
Figure 2.10: Sample arrays: (left) a 1-D array viewed as a sequential list and (right) a
2-D array viewed as a rectangular table or grid.
0 1 2
0 90 96 92
7
3 1 85 91 89
90 96 92
2 82 73 84
85 91 89
82 73 84 3 69 82 86
69 82 86
95 88 91 4 95 88 91
78 64 84
5 78 64 84
92 85 89
6 92 85 89
Figure 2.11: Exam grades: (left) stored in a text file; and (right) stored in a 2-D array.
The following code segment shows the implementation needed to extract the
exam grades from the text file and store them into a 2-D array. Notice that we
create the array after extracting the first two values from the file. These values
indicate the number of students and the number of exams that correspond to the
number of rows and columns needed in the array.
2.3 Two-Dimensional Arrays 49
# Extract the first two values which indicate the size of the array.
numExams = int( [Link]() )
numStudents = int( [Link]() )
With the grades extracted from the file and stored in the 2-D array, we can
now process the grades as needed. Suppose we want to compute and display each
student’s exam grade, which we can do with the following code:
0 1 2 3 4 0 1 2 3 4
0 22 15
15 45
45 13 78
78 theRows • 22 15
15 45
45 13
13 78
78
0 •
1 40 12
12 52
52 91 86
86 Array2D
1 • 40
40 12
12 52
52 91
91 86
86
2 59 25
25 33
33 41 66
2 •
59
59 25
25 33
33 41
41 66
(a) (b)
Figure 2.12: A sample 2-D array: (a) the abstract view organized into rows and columns
and (b) the physical storage of the 2-D array using an array of arrays.
Some languages that use the array of arrays approach for implementing a 2-D
array provide access to the individual arrays used to store the row elements. Having
access to the given 1-D array, these languages use the subscript notation x[r][c]
for referencing an individual element. To be consistent in our approach of hiding
the implementation details, we do not provide access to any of the 1-D arrays used
to store the elements of the 2-D array. Thus, our implementation requires the use
of the subscript notation x[r,c].
The implementation of the Array2D abstract data type using an array of arrays
is provided in Listing 2.2. The constructor creates a data field named theRows
to which an Array object is assigned. This is the main array used to store the
references to the other arrays that are created for each row in the 2-D array.
25
26 # Gets the contents of the element at position [i, j]
27 def __getitem__( self, ndxTuple ):
28 assert len(ndxTuple) == 2, "Invalid number of array subscripts."
29 row = ndxTuple[0]
30 col = ndxTuple[1]
31 assert row >= 0 and row < [Link]() \
32 and col >= 0 and col < [Link](), \
33 "Array subscript out of range."
34 the1dArray = self._theRows[row]
35 return the1dArray[col]
36
37 # Sets the contents of the element at position [i,j] to value.
38 def __setitem__( self, ndxTuple, value ):
39 assert len(ndxTuple) == 2, "Invalid number of array subscripts."
40 row = ndxTuple[0]
41 col = ndxTuple[1]
42 assert row >= 0 and row < [Link]() \
43 and col >= 0 and col < [Link](), \
44 "Array subscript out of range."
45 the1dArray = self._theRows[row]
46 the1dArray[col] = value
Basic Operations
Note that the size of the array that is passed as arguments to the constructor is
not saved in data fields. The numRows() method can obtain the number of rows by
checking the length of the main array, which contains an element for each row in the
2-D array. To determine the number of columns in the 2-D array, the numCols()
method can simply check the length of any of the 1-D arrays used to store the
individual rows.
The clear() method can set every element to the given value by calling the
clear() method on each of the 1-D arrays used to store the individual rows. This
is easily done by iterating over the array stored in theRows.
Element Access
Access to individual elements within an 2-D array requires a 2-tuple or two-
component subscript, one for each dimension. In mathematics, the 2-tuple sub-
script is generally notated as xr,c . In modern programming languages, a 2-tuple
subscript is given either as x[r][c] or x[r,c]. In Python, we can use the latter
notation in conjunction with the getitem and setitem subscript operators.
This will allow for a more natural use of the two-dimensional array instead of
having to invoke a named method.
The Python subscript operator method getitem , which is shown in lines
27–35, takes a single index argument as specified in the method definition. This
does not restrict the subscript to a single index value, however. When a multi-
component subscript is specified (i.e., y = x[i,j]), Python automatically stores
52 CHAPTER 2 Arrays
the components in a tuple in the order listed within the brackets and passes the
tuple to the ndxTuple argument of the getitem method.
The contents of the ndxTuple are used to extract the contents of the given
element. After verifying both subscripts are within the valid range, we extract,
from the data field theRows, the reference to the array used to store the given
row. With this reference stored in the local variable the1dArray, we can then
apply the subscript operator to the 1-D array using the column value.
You may notice a second assert statement within the getitem method at
line 28. This is needed because Python does not examine the number of compo-
nents specified in the subscript before passing the tuple to the subscript operator
method. For example, there is nothing to prevent us from incorrectly supplying
three components such as box[i,j,k] instead of two. In fact, Python would have
no way of knowing that we only need two components for the 2-D array subscript.
Thus, we must first check to make sure the subscript tuple passed to the method
contains only two elements.
When making the assertion about the size of the ndxTuple, we assume a tu-
ple is passed to the subscript operator and use the len() function to verify its
length. When a single-component subscript x[0] is supplied to a subscript op-
erator method, as is done with the Array class, the argument is a single integer
value. The len() method can only be used with the collection types and not in-
dividual values. It does generate its own error, however, when used improperly.
Thus, Python’s len() function is used to ensure two components are supplied for
all Array2D objects.
The setitem operator method can be implemented in a similar fashion to
getitem . The major differences are that this method requires a second argu-
ment to receive the value to which an element is set and it modifies the indicated
element with the new value instead of returning a value.
getitem ( row, col ): Returns the value stored in the given matrix element.
Both row and col must be within the valid range.
setitem ( row, col, scalar ): Sets the matrix element at the given row and
col to scalar. The element indices must be within the valid range.
scaleBy( scalar ): Multiplies each element of the matrix by the given scalar
value. The matrix is modified by this operation.
add ( rhsMatrix ): Creates and returns a new matrix that is the result of
adding this matrix to the given rhsMatrix. The size of the two matrices must
be the same.
subtract ( rhsMatrix ): The same as the add() operation but subtracts the
two matrices.
multiply ( rhsMatrix ): Creates and returns a new matrix that is the result
of multiplying this matrix to the given rhsMatrix. The two matrices must be
of appropriate sizes as defined for matrix multiplication.
4 5 1 0 4+1 5+0 5 5
Scaling. A matrix can be uniformly scaled, which modifies each element of the
matrix by the same scale factor. A scale factor of less than 1 has the effect of
reducing the value of each element whereas a scale factor greater than 1 increases
the value of each element. Scaling a matrix by a scale factor of 3 is illustrated here:
6 7 3∗6 3∗7 18 21
3 8 9 = 3 ∗ 8 3 ∗ 9 = 24 27
1 0 3∗1 3∗0 3 0
54 CHAPTER 2 Arrays
Multiplication. Matrix multiplication is only defined for matrices where the num-
ber of columns in the matrix on the lefthand side is equal to the number of rows
in the matrix on the righthand side. The result is a new matrix that contains the
same number of rows as the matrix on the lefthand side and the same number of
columns as the matrix on the righthand side. In other words, given a matrix of size
m × n multiplied by a matrix of size n × p, the resulting matrix is of size m × p. In
multiplying two matrices, each element of the new matrix is the result of summing
the product of a row in the lefthand side matrix by a column in the righthand side
matrix. In the example matrix multiplication illustrated here, the row and column
used to compute entry (0, 0) of the new matrix is shaded in gray.
0 1 " #
6 7 8
2 3 ∗
9 1 0
4 5
(0 ∗ 6 + 1 ∗ 9) (0 ∗ 7 + 1 ∗ 1) (0 ∗ 8 + 1 ∗ 0)
= (2 ∗ 6 + 3 ∗ 9) (2 ∗ 7 + 3 ∗ 1) (2 ∗ 8 + 3 ∗ 0)
(4 ∗ 6 + 5 ∗ 9) (4 ∗ 7 + 5 ∗ 1) (4 ∗ 8 + 5 ∗ 0)
9 1 0
= 39 17 16
69 33 32
Viewing matrix multiplication based on the element subscripts can help you
to better understand the operation. Consider the two matrices from above and
assume they are labeled A and B, respectively.
A0,0 A0,1 " #
B0,0 B0,1 B0,2
A = A1,0 A1,1 B=
B1,0 B1,1 B1,2
A2,0 A2,1
resulting in
(A0,0 ∗ B0,0 + A0,1 ∗ B1,0 ) (A0,0 ∗ B0,1 + A0,1 ∗ B1,1 ) (A0,0 ∗ B0,2 + A0,1 ∗ B1,2 )
C = (A1,0 ∗ B0,0 + A1,1 ∗ B1,0 ) (A1,0 ∗ B0,1 + A1,1 ∗ B1,1 ) (A1,0 ∗ B0,2 + A1,1 ∗ B1,2 )
(A2,0 ∗ B0,0 + A2,1 ∗ B1,0 ) (A2,0 ∗ B0,1 + A2,1 ∗ B1,1 ) (A2,0 ∗ B0,2 + A2,1 ∗ B1,2 )
A Matrix object only requires one data field for storing the 2-D array. After
creating the array, its elements must be set to zero as specified by the definition of
the Matrix ADT. The constructor is provided in lines 6–8.
The numRows() and numCols() methods are straightforward. They need only
return the length of the corresponding dimension of the 2-D array. The element
access methods are also rather simple as they need only call the corresponding
method from the Array2D class. Note that we do not check for valid indices in
these methods even though it is a precondition as defined by the Matrix ADT.
The validation of the precondition is omitted here since we know the corresponding
methods of the Array2D class have the same preconditions and they are verified
by that class. If this were not the case, we would have to validate the indices and
raise an exception directly within the methods of the Matrix class.
The scaling matrix operation, shown in lines 27–30, involves multiplying each
element in the matrix by the given scalar value. The Matrix ADT calls for this
operation to modify the matrix on which it is applied instead of creating a new
matrix resulting from the multiplication. The matrix add operation, on the other
hand, creates and returns a new Matrix object that is the result of adding the
2.5 Application: The Game of Life 57
two given matrices. The first step is to ensure the two matrices are the same
size as required by the rules of matrix addition. After verifying the sizes, a new
Matrix object is created and its elements set by iterating over and summing the
corresponding elements from the two sources. The new matrix resulting from this
operation is then returned. The implementation of the remaining methods, which
is left as an exercise, can be done in a similar fashion.
1. If a cell is alive and has either two or three live neighbors, the cell remains
alive in the next generation. The neighbors are the eight cells immediately
surrounding a cell: vertically, horizontally, and diagonally.
2. A living cell that has no live neighbors or a single live neighbor dies from
isolation in the next generation.
3. A living cell that has four or more live neighbors dies from overpopulation in
the next generation.
4. A dead cell with exactly three live neighbors results in a birth and becomes
alive in the next generation. All other dead cells remain dead in the next
generation.
58 CHAPTER 2 Arrays
The game starts with an initial configuration supplied by the user. Successive
generations are created by applying the set of rules simultaneously to each cell in
the grid. Interesting patterns can develop as the population of organisms undergoes
changes by expanding or eventually dying out. To illustrate the game of Life,
consider the following simple configuration of live organisms:
Applying the rules to this configuration creates the next generation. This results
in two organisms dying (shown below as the light gray boxes) based on rule 2, one
remaining alive based on rule 1, and the generation of a new organism based on
rule 4 (the black box marked with an x).
If we evolve the next generation, the system dies out since both live cells in the
first generation have a single live neighbor.
While some systems may eventually die out, others can evolve into a “stable”
state. Consider the following initial configuration and its first generation. The
result is a stable state since the four live cells each have three neighbors and no
dead cell has exactly three neighbors in order to produce a new live cell.
A life grid is used to represent and store the area in the game of Life that contains
organisms. The grid contains a rectangular grouping of cells of a finite size divided
into rows and columns. The individual cells, which can be alive or dead, are
referenced by row and column indices, both of which start at zero.
LifeGrid( nrows, ncols ): Creates a new game grid consisting of nrows and
ncols. All cells in the grid are set to dead.
configure( coordList ): Configures the grid for evolving the next genera-
tion. The coordList argument is a sequence of 2-tuples with each tuple
representing the coordinates (r, c) of the cells to be set as alive. All remaining
cells are cleared or set to dead.
clearCell( row, col ): Clears the individual cell (row, col) and sets it to
dead. The cell indices must be within the valid range of the grid.
setCell( row, col ): Sets the indicated cell (row, col) to be alive. The cell
indices must be within the valid range of the grid.
numLiveNeighbors( row, col ): Returns the number of live neighbors for the
given cell (row, col). The neighbors of a cell include all of the cells immediately
surrounding it in all directions. For the cells along the border of the grid, the
neighbors that fall outside the grid are assumed to be dead. The cell indices
must be within the valid range of the grid.
We now develop a program for the game of Life using the Life Grid ADT. The
implementation of the program provided in Listing 2.4 on the next page was de-
veloped using a top-down design consisting of several functions. The main routine
creates the game grid and evolves new generations of organisms. It relies on two
additional functions: draw() and evolve().
The draw() routine, the implementation of which is left as an exercise, prints
a text-based representation of the game grid. The evolve() function generates
60 CHAPTER 2 Arrays
a new configuration of organisms based on the rules of the game. A list is used
within evolve() to store the coordinates of live cells in the next generation. After
iterating over all the cells, the grid is reconfigured using this list of coordinates.
This is necessary since the current configuration stored in the game grid cannot be
modified with the next generation until the neighbor count has been computed for
each cell in the current generation.
The program also defines several constant variables. These are used to specify
the grid size, the number of generations to be created, and the set of initial live cells.
Using constant variables allows for easy modifications to any of these parameters
as needed without having to modify other parts of the program. Of course, this
information could be extracted from the user or a text file instead. The results of
executing the [Link] program are illustrated graphically in Figure 2.13.
Figure 2.13: The results of using the [Link] program on a sample grid config-
uration. Configurations after the eighth generation produce a two-phase oscillator, alter-
nating between the configuration of the seventh and eighth generations.
2.5.3 Implementation
The actual game of Life specifies a rectangular grid of infinite size. When develop-
ing a computer solution for such a problem, we are limited to grids of a fixed size.
The game of Life can still be implemented, however, by using a finite size for the
grid. If the system grows too large where it does not fit into the space, it can be
“played” again, with a larger grid.
Before implementing the LifeGrid class, we must decide how the data should
be organized and select an appropriate structure. The most obvious is the use of a
two-dimensional array to represent the grid. Next, we must decide what values to
store in the grid to represent the organisms, both dead and alive. Any pair of values
can be used. We are going to use the value 0 to represent the dead cells and the
62 CHAPTER 2 Arrays
0 1 2 3 4
0 0 0 0 0 0
1 0 0 1 0 0
2 •0 1 1 1 0
3 0 0 0 0 0
4 0 0 0 0 0
Figure 2.14: The game grid representation with live and dead cells: (left) the abstract
view and (right) the physical view using a 2-D array of 0’s and 1’s.
value 1 for the live cells. This choice is based on the ease it creates when counting
the number of neighbors for a given cell. Figure 2.14 illustrates the abstract and
physical views of the game grid.
The LifeGrid class is implemented in Listing 2.5. At the top of the class
definition, before specifying the constructor, two constant variables are initialized
to store the values used to mark the cells within the game grid. These constants are
defined within the class itself and outside of the methods since they are not actual
data fields of a LifeGrid object. By using the named constants, the code is easier to
read and the values used to represent the cell status could easily be changed if we
were so inclined.
The constructor, shown in lines 10–14, creates a 2-D array for the grid using
the Array2D class defined earlier in the chapter. The cells are cleared as the ADT
definition requires by calling the configure() method with an empty coordinate
list. The grid dimension accessor methods are easily implemented using the cor-
responding methods of the Array2D class. The three cell modification routines
are also straightforward. Note that the ADT definition requires the cell indices
specified for the clearCell() and setCell() methods must be valid. Since this
is also the precondition required of the Array2D element access methods, we omit
the direct specification of assertions in these methods. The configure() method,
shown in lines 25–29, clears the grid cells by setting each to a dead organism. It
then iterates through the coordinate list and uses the setCell() method to set
the live cells.
The numLiveNeighbors() method is left as an exercise. Note, however, since
we used the integer values 0 and 1 to represent the state of a cell, counting the
number of live neighbors is as simple as summing the contents of the neighboring
cells. Working with a fixed-size grid introduces the problem of how to deal with the
cells around the border. A border cell will not have all eight neighbors since some
of them lie outside the grid. Different approaches can be taken when a border cell
tually class variables that are unique to the class and not to individual
objects. To reference a class constant variable, use the name of the class in
place of the self keyword (i.e., print( [Link] CELL) ).
2.5 Application: The Game of Life 63
is examined. The most common is to assume any neighboring cell lying outside
the grid contains a dead organism.
1 # Implements the LifeGrid ADT for use with the game of Life.
2 from array import Array2D
3
4 class LifeGrid :
5 # Defines constants to represent the cell states.
6 DEAD_CELL = 0
7 LIVE_CELL = 1
8
9 # Creates the game grid and initializes the cells to dead.
10 def __init__( self, numRows, numCols ):
11 # Allocate the 2-D array for the grid.
12 self._grid = Array2D( numRows, numCols )
13 # Clear the grid and set all cells to dead.
14 [Link]( list() )
15
16 # Returns the number of rows in the grid.
17 def numRows( self ):
18 return self._grid.numRows()
19
20 # Returns the number of columns in the grid.
21 def numCols( self ):
22 return self._grid.numCols()
23
24 # Configures the grid to contain the given live cells.
25 def configure( self, coordList ):
26 # Clear the game grid.
27 for i in range( numRows ):
28 for j in range( numCols ):
29 [Link]( i, j )
30
31 # Set the indicated cells to be alive.
32 for coord in coordList :
33 [Link]( coord[0], coord[1] )
34
35 # Does the indicated cell contain a live organism?
36 def isLiveCell( self, row, col ):
37 return self._grid[row, col] == GameGrid.LIVE_CELL
38
39 # Clears the indicated cell by setting it to dead.
40 def clearCell( self, row, col ):
41 self._grid[row, col] = GameGrid.DEAD_CELL
42
43 # Sets the indicated cell to be alive.
44 def setCell( self, row, col ):
45 self._grid[row, col] = GameGrid.LIVE_CELL
46
47 # Returns the number of live neighbors for the given cell.
48 def numLiveNeighbors( self, row, col ):
49 ......
64 CHAPTER 2 Arrays
Exercises
2.1 Complete the Matrix class by implementing the remaining methods: sub ,
mult , and transpose().
2.4 Modify the [Link] program to prompt the user for the grid size and
the number of generations to evolve.
2.5 Use your program from Exercise 2.4 to experiment with the initial configura-
tions shown in Figure 2.15. Answer the following questions for each configu-
ration using a variety of grid sizes and assuming no more than 10 generations.
2.6 As indicated in the chapter, when a list is created using the replication op-
erator values = [ None ] * 10000 the size of the underlying array used to
implement the list can be up to twice the size actually needed. This extra
space is beneficial to the list itself, but it can be quite wasteful when a list is
used to implement some abstract data types. Consider the implementation of
the Array2D abstract data type as described in the chapter. If we had used
a list of lists to implement the ADT, instead of the array of arrays, a large
amount of extra storage space would be allocated that would never be used.
Calculate the number of elements that will be allocated when using an array
of arrays implementation and a list of lists implementation of the Array2D
abstract data type for each of the following 2-D array sizes:
(a) 75 × 100 (b) 10, 000 × 25 (c) 10, 000 × 10, 000
Programming Projects
2.1 While Python provides the built-in list type for constructing and managing
mutable sequences, many languages do not provide such a structure, at least
not as part of the language itself. To help in further understanding how
Python’s built-in list works, implement the Vector ADT using the Array class
implemented in the chapter. Your implementation should produce a mutable
sequence type that works like Python’s list structure. When the underlying
array needs to be expanded, the new array should double the size of the
original. The operations that can be performed on the ADT are described
below. Assume the size of the underlying array never decreases.
Vector(): Creates a new empty vector with an initial capacity of two
elements.
length (): Returns the number of items contained in the vector.
contains ( item ): Determines if the given item is contained in the vector.
getitem ( ndx ): Returns the item stored in the ndx element of the list.
The value of ndx must be within the valid range.
setitem ( ndx, item ): Sets the element at position ndx to contain the
given item. The value of ndx must be within the valid range, which
includes the first position past the last item.
append( item ): Adds the given item to the end of the list.
insert( ndx, item ): Inserts the given item in the element at position
ndx. The items in the elements at and following the given position are
shifted down to make room for the new item. ndx must be within the
valid range.
remove( ndx ): Removes and returns the item from the element from the
given ndx position. The items in the elements at and following the given
position are shifted up to close the gap created by the removed item. ndx
must be within the valid range.
66 CHAPTER 2 Arrays
indexOf( item ): Returns the index of the vector element containing the
given item. The item must be in the list.
extend( otherVector ): Extends this vector by appending the entire con-
tents of the otherVector to this vector.
subVector( from, to ): Creates and returns a new vector that contains
a subsequence of the items in the vector between and including those
indicated by the given from and to positions. Both the from and to
positions must be within the valid range.
iterator (): Creates and returns an iterator that can be used to traverse
the elements of the vector.
2.2 In a typical Vector ADT, the size of the underlying array decreases after a
sufficient number of items have been removed. Devise a strategy for decreasing
the size of the array as items are removed. Modify your implementation of the
Vector ADT from the previous question to include your reduction strategy.
2.3 A grayscale digital image is a two-dimensional raster image in which the pic-
ture elements, or pixels, store a single value representing a shade of gray that
varies from black to white. In a discrete grayscale image, the shades of gray are
represented by integer values in the range [0 . . . 255], where 0 is black and 255
is white. We can define the Grayscale Image ADT for storing and manipulat-
ing discrete grayscale digital images. Given the description of the operations,
provide a complete implementation of the ADT using a 2-D array.
GrayscaleImage( nrows, ncols ): Creates a new instance that consists
of nrows and ncols of pixels each set to an initial value of 0.
width(): Returns the width of the image.
height(): Returns the height of the image.
clear( value ): Clears the entire image by setting each pixel to the given
intensity value. The intensity value will be clamped to 0 or 255 if it is less
than 0 or greater than 255, respectively.
getitem ( row, col ): Returns the intensity level of the given pixel. The
pixel coordinates must be within the valid range.
setitem ( row, col, value ): Sets the intensity level of the given pixel
to the given value. The pixel coordinates must be within the valid range.
The intensity value is clamped to 0 or 255 if it is outside the valid range.
2.4 Playing board games on a computer is very common. We can use abstraction
to aide in the design of a board game by separating the game logic from the
actual user interaction required to play the game. No matter the type of user
interface provided to play the game (i.e., text based, desktop windowing en-
vironment, or web browser), the underlying logic remains the same. Consider
the game of Reversi, which was invented in 1893 but has a more modern set
of rules dating back to the 1970s. Reversi is played by two players on a game
Programming Projects 67
board divided into 64 squares arranged in 8 rows and 8 columns and a set of
64 chips. Each chip is painted a dark color on one side and a light color on the
other, with each color belonging to one of the two players. The players place
their chips on the board and flip the chips of their opponent with the goal of
having the most chips of their color on the board at the end of the game. The
game starts with a configuration as shown in part (a) of Figure 2.16.
x x x
The players take turns placing chips on the board with their color facing up. A
chip can only be played in a square that is adjacent to a chip of the other player
and that forms a straight line of attack (vertical, horizontal, or diagonal). A
line of attack is formed between two squares containing the player’s own chips
in which there is one or more of the opponent’s chips in between the two. For
example, if player 1 (black) goes first, he has four options as shown in part
(b). Suppose player 1 places a chip in the square marked with an x. After
placing his chip, player 1 flips all of the chips of player 2 (white) that are in
the line of attack. In this case, he flips the chip immediately below the new
chip as shown in part (c). Player 2 then places one of her chips. She has
three options from which to choose as shown by the dark squares in part (c).
If player 2 places her chip in the square marked x, she flips the black chip
below the new chip as shown in part (d). If there are multiple lines of attack
that result from the placement of a chip, then all of the opponent’s chips that
are in all of the lines of attack are flipped. For example, suppose player 1
places a chip in the square marked with an x as shown in part (d). Then he
flips both white chips, the one to the left and the one diagonally down to the
left as shown in part (e). Play alternates between the players until all of the
squares are filled or neither player can move. If one player cannot move but
the other can, play proceeds with the other player. The winner is the player
with the most chips at the end of the game. Given the following description
of the operations, provide a complete implementation for the Reversi Game
Logic ADT.
ReversiGameLogic(): Creates a new instance of the Reversi game logic
with the initial configuration.
whoseTurn(): Returns the player number (1 or 2) for the current player
or 0 if no player can move.
68 CHAPTER 2 Arrays
2.5 Implement a text-based version of the Reversi game using your game logic
ADT from the previous question.
2.6 Define a game logic ADT, similar to that of the Reversi Game Logic ADT, for
the game of checkers.
CHAPTER 3
Sets and Maps
In the previous chapters, we studied several complex abstract data types that
required the use of a data structure for their implementation. In this chapter, we
continue exploring abstract data types with a focus on several common containers.
Two of these are provided by Python as part of the language itself: sets and
dictionaries. Nevertheless, it’s still important to understand how they work and
some of the common ways in which they are implemented.
Your experience in programming will likely not be limited to the Python lan-
guage. At some point in the future, you may use one if not several other common
programming languages. While some of these do provide a wide range of abstract
data types as part of the language itself or included in their standard library, oth-
ers, like C, do not. Thus, it’s important that you know how to implement a set or
dictionary ADT if necessary, when one is not available as part of the language.
Further, both the set and dictionary types provide excellent examples of ab-
stract data types that can be implemented using different data structures. As you
learned in Chapter 1, there may be multiple data structures and ways to organize
the data in those structures that are suitable for implementing an abstract data
type. Thus, it’s not uncommon for language libraries to provide multiple imple-
mentations of an abstract data type, which allows the programmer to choose the
best option for a given problem. Your ability to choose from among these various
implementations will depend not only on your knowledge of the abstract data type
itself, but also on understanding the pros and cons of the various implementations.
3.1 Sets
The Set ADT is a common container used in computer science. But unlike the
Bag ADT introduced in Chapter 1, a set stores unique values and represents the
same structure found in mathematics. It is commonly used when you need to store
a collection of unique values without regard to how they are stored or when you
need to perform various mathematical set operations on collections.
69
70 CHAPTER 3 Sets and Maps
A set is a container that stores a collection of unique values over a given comparable
domain in which the stored values have no particular ordering.
Set(): Creates a new set initialized to the empty set.
length (): Returns the number of elements in the set, also known as the
cardinality. Accessed using the len() function.
add( element ): Modifies the set by adding the given value or element to the
set if the element is not already a member. If the element is not unique, no
action is taken and the operation is skipped.
remove( element ): Removes the given value from the set if the value is con-
tained in the set and raises an exception otherwise.
equals ( setB ): Determines if the set is equal to another set and returns a
boolean value. For two sets, A and B, to be equal, both A and B must contain
the same number of elements and all elements in A must also be elements in
B. If both sets are empty, the sets are equal. Access with == or !=.
isSubsetOf( setB ): Determines if the set is a subset of another set and re-
turns a boolean value. For set A to be a subset of B, all elements in A must
also be elements in B.
union( setB ): Creates and returns a new set that is the union of this set and
setB. The new set created from the union of two sets, A and B, contains all
elements in A plus those elements in B that are not in A. Neither set A nor
set B is modified by this operation.
intersect( setB ): Creates and returns a new set that is the intersection
of this set and setB. The intersection of sets A and B contains only those
elements that are in both A and B. Neither set A nor set B is modified by
this operation.
difference( setB ): Creates and returns a new set that is the difference of
this set and setB. The set difference, A − B, contains only those elements that
are in A but not in B. Neither set A nor set B is modified by this operation.
3.1 Sets 71
iterator (): Creates and returns an iterator that can be used to iterate over
the collection of items.
Example Use
To illustrate the use of the Set ADT, we create and use sets containing the courses
currently being taken by two students. In the following code segment, we create
two sets and add elements to each. The results are illustrated in Figure 3.1.
smith = Set()
[Link]( "CSCI-112" )
[Link]( "MATH-121" )
[Link]( "HIST-340" )
[Link]( "ECON-101" )
roberts = Set()
[Link]( "POL-101" )
[Link]( "ANTH-230" )
[Link]( "CSCI-112" )
[Link]( "ECON-101" )
“CSCI-112” “CSCI-112”
“MATH-121” “POL-101”
“ECON-101” “ECON-101”
“HIST-340” “ANTH-230”
Next, we determine if the two students are taking the exact same courses. If
not, then we want to know if they are taking any of the same courses. We can do
this by computing the intersection between the two sets.
if smith == roberts :
print( "Smith and Roberts are taking the same courses." )
else :
sameCourses = [Link]( roberts )
if [Link]() :
print( "Smith and Roberts are not taking any of "\
+ "the same courses." )
else :
print( "Smith and Roberts are taking some of the "\
+ "same courses:" )
for course in sameCourses :
print( course )
72 CHAPTER 3 Sets and Maps
In this case, the two students are both taking CSCI-112 and ECON-101. Thus,
the results of executing the previous code segment will be
Suppose we want to know which courses Smith is taking that Roberts is not
taking. We can determine this using the set difference operation:
smith roberts
theElements •• theElements ••
• •
Set Set
0 • “CSCI-112”
“CSCI-112” 0 • “POL-101”
“POL-101”
1 • “MATH-121”
“MATH-121” 1 • “ANTH-230”
“ANTH-230”
2 • “HIST-340”
“HIST-340” 2 • “CSCI-112”
“CSCI-112”
3 • “ECON-101”
“ECON-101” 3 • “ECON-101”
“ECON-101”
Adding Elements
As indicated earlier, we must ensure that duplicate values are not added to the set
since the list structure does not handle this for us. When implementing the add
method, shown in lines 16–18, we must first determine if the supplied element is
already in the list or not. If the element is not a duplicate, we can simply append
the value to the end of the list; if the element is a duplicate, we do nothing. The
reason for this is that the definition of the add() operation indicates no action
is taken when an attempt is made to add a duplicate value. This is known as a
noop, which is short for no operation and indicates no action is taken. Noops are
appropriate in some cases, which will be stated implicitly in the definition of an
abstract data type by indicating no action is to be taken when the precondition
fails as we did with the add() operation.
TIP
vantage of the abstraction and avoid “reinventing the wheel” by duplicating
code in several places.
sure the two sets contain the same number of elements; otherwise, they cannot be
equal. It would be inefficient to compare the individual elements since we already
know the two sets cannot be equal. After verifying the size of the lists, we can test
to see if the self set is a subset of setB by calling [Link](setB). This
is a valid test since two equal sets are subsets of each other and we already know
they are of the same size.
To determine if one set is the subset of another, we can iterate over the list
of elements in the self set and make sure each is contained in setB. If just one
element in the self set is not in setB, then it is not a subset. The implementation
of the isSubsetOf() method is shown in lines 33–37.
3.2 Maps
Searching for data items based on unique key values is a very common application
in computer science. An abstract data type that provides this type of search
capability is often referred to as a map or dictionary since it maps a key to
a corresponding value. Consider the problem of a university registrar having to
manage and process large volumes of data related to students. To keep track of the
information or records of data, the registrar assigns a unique student identification
76 CHAPTER 3 Sets and Maps
number to each individual student as illustrated in Figure 3.3. Later, when the
registrar needs to search for a student’s information, the identification number is
used. Using this keyed approach allows access to a specific student record. If
the names were used to identify the records instead, then what happens when
multiple students have the same name? Or, what happens if the name was entered
incorrectly when the record was initially created?
10210
Brown
John
10175
14 East Main St
Smith
Somewhere
John
10142 VA
14 East Main St
Roberts 99155
Somewhere
John
10015 VA
14 East Main St
Smith 99155
Somewhere
John
VA
14 East Main St
99155
Somewhere
VA
99155
In this section, we define our own Map ADT and then provide an implementa-
tion using a list. In later chapters, we will implement and evaluate the map using
a variety of data structures. We use the term map to distinguish our ADT from
the dictionary provided by Python. The Python dictionary is implemented using a
hash table, which requires the key objects to contain the hash method for gen-
erating a hash code. This can limit the type of problems with which a dictionary
can be used. We define our Map ADT with the minimum requirement that the
keys are comparable, which will allow it to be used in a wider range of problems.
It’s not uncommon to provide multiple implementations of an ADT as is done with
many language libraries. We will explore the implementation details of Python’s
dictionary later in Chapter 11 when we discuss hash tables and the design of hash
functions.
A map is a container for storing a collection of data records in which each record
is associated with a unique key. The key components must be comparable.
Map(): Creates a new empty map.
Instead of using two lists to store the key/value entries in the map, we can use
a single list. The individual keys and corresponding values can both be saved in a
single object, with that object then stored in the list. A sample instance illustrating
the data organization required for this approach is shown in Figure 3.4.
Smith
Smith
entryList • John
John
14
14 East
East Main
Main St
St
Map Somewhere
Somewhere Roberts
Roberts
VA
VA Susan
Susan
10015 99155
99155 231
231 Quarry
Quarry Rd
Rd
0 • 10015 ••
Nowhere
Nowhere
TX
TX
1 • 10142
10142 •• 11333
11333
2 • 10210
10210 ••
Brown
Brown
Jessica
Jessica
3 • 10175
10175 •• Smith
Smith 231
231 Quarry
Quarry Rd
Rd
Jane
Jane Plains
Plains
MapEntry 81
81 Jefferson
Jefferson St
St TN
TN
East
East End
End 30101
30101
PA
PA
28541
28541
The implementation of the Map ADT using a single list is provided in List-
ing 3.2. As we indicated earlier in Chapter 1, we want to avoid the use of tuples
when storing structured data since it’s better practice to use classes with named
fields. The MapEntry storage class, defined in lines 56–59, will be used to store the
individual key/value pairs. Note this storage class is defined to be private since it’s
only intended for use by the Map class that provides the single list implementation
of the Map ADT.
17 # new value replaces the current value associated with the key.
18 def add( self, key, value ):
19 ndx = self._findPosition( key )
20 if ndx is not None : # if the key was found
21 self._entryList[ndx].value = value
22 return False
23 else : # otherwise add a new entry
24 entry = _MapEntry( key, value )
25 self._entryList.append( entry )
26 return True
27
28 # Returns the value associated with the key.
29 def valueOf( self, key ):
30 ndx = self._findPosition( key )
31 assert ndx is not None, "Invalid map key."
32 return self._entryList[ndx].value
33
34 # Removes the entry associated with the key.
35 def remove( self, key ):
36 ndx = self._findPosition( key )
37 assert ndx is not None, "Invalid map key."
38 self._entryList.pop( ndx )
39
40 # Returns an iterator for traversing the keys in the map.
41 def __iter__( self ):
42 return _MapIterator( self._entryList )
43
44 # Helper method used to find the index position of a category. If the
45 # key is not found, None is returned.
46 def _findPosition( self, key ):
47 # Iterate through each entry in the list.
48 for i in range( len(self) ) :
49 # Is the key stored in the ith entry?
50 if self._entryList[i].key == key :
51 return i
52 # When not found, return None.
53 return None
54
55 # Storage class for holding the key/value pairs.
56 class _MapEntry :
57 def __init__( self, key, value ):
58 [Link] = key
59 [Link] = value
Many of the methods require a search to determine if the map contains a given
key. In this implementation, the standard in operator cannot be used since the list
contains MapEntry objects and not simply key entries. Instead, we have to search
the list ourselves and examine the key field of each MapEntry object. Likewise, we
routinely have to locate within the list the position containing a specific key/value
entry. Since these operations will be needed in several methods, we can create a
helper method that combines the two searches and use it where needed.
The findPosition() helper method searches the list for the given key. If
the key is found, the index of its location is returned; otherwise, the function
80 CHAPTER 3 Sets and Maps
returns None to indicate the key is not contained in the map. When used by
the other methods, the value returned can be evaluated to determine both the
existence of the key and the location of the corresponding entry if the key is in
the map. By combining the two searches into a single operation, we eliminate the
need to first determine if the map contains the key and then searching again for
its location. Given the helper method, the implementation of the various methods
is straightforward. Implementation of the iterator method is left as an exercise.
les
columns tab 1 2
0 1 2 3 4 0
0 0
rows
1 1
rows
2 2
3 3
0 1 2 3
columns
Figure 3.5: Sample multi-dimensional arrays: (left) a 2-D array viewed as a rectangular
table and (right) a 3-D array viewed as a box of tables.
length( dim ): Returns the length of the given array dimension. The individ-
ual dimensions are numbered starting from 1, where 1 represents the first, or
highest, dimension possible in the array. Thus, in an array with three dimen-
sions, 1 indicates the number of tables in the box, 2 is the number of rows,
and 3 is the number of columns.
clear( value ): Clears the array by setting each element to the given value.
appropriate syntax to make use of a 1-D array. Multi-dimensional arrays are not
handled at the hardware level. Instead, the programming language typically pro-
vides its own mechanism for creating and managing multi-dimensional arrays.
As we saw earlier, a one-dimensional array is composed of a group of sequential
elements stored in successive memory locations. The index used to reference a
particular element is simply the offset from the first element in the array. In most
programming languages, a multi-dimensional array is actually created and stored
in memory as a one-dimensional array. With this organization, a multi-dimensional
array is simply an abstract view of a physical one-dimensional data structure.
Array Storage
A one-dimensional array is commonly used to physically store arrays of higher
dimensions. Consider a two-dimensional array divided into a table of rows and
columns as illustrated in Figure 3.6. How can the individual elements of the table
be stored in the one-dimensional structure while maintaining direct access to the
individual table elements? There are two common approaches. The elements
can be stored in row-major order or column-major order . Most high-level
programming languages use row-major order, with FORTRAN being one of the
few languages that uses column-major ordering to store and manage 2-D arrays.
0 1 2 3 4
0 2 15 45 13 78
1 40 12 52 91 86
2 59 25 33 41 6
In row-major order, the individual rows are stored sequentially, one at a time,
as illustrated in Figure 3.7. The first row of 5 elements are stored in the first 5
sequential elements of the 1-D array, the second row of 5 elements are stored in
the next five sequential elements, and so forth.
In column-major order, the 2-D array is stored sequentially, one entire column
at a time, as illustrated in Figure 3.8. The first column of 3 elements are stored in
the first 3 sequential elements of the 1-D array, followed by the 3 elements of the
second column, and so on.
For larger dimensions, a similar approach can be used. With a three-dimensional
array, the individual tables can be stored contiguously using either row-major or
column-major ordering. As the number of dimensions grow, all elements within
a single instance of each dimension are stored contiguously before the next in-
stance. For example, given a four-dimensional array, which can be thought of as
an array of boxes, all elements of an individual box (3-D array) are stored before
the next box.
3.3 Multi-Dimensional Arrays 83
0 1 2 3 4
Physical storage
0 2 15 45 13 78
of a 2-D array using
row-major order.
1 40 12 52 91 86
2 59 25 33 41 6
•2 •
15 •
45 •
13 •
78 •
40 •
12 •
52 91 86 59 25 33 41 6
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Figure 3.7: Physical storage of a sample 2-D array (top) in a 1-D array using row-major
order (bottom).
Index Computation
Since multi-dimensional arrays are created and managed by instructions in the
programming language, accessing an individual element must also be handled by
the language. When an individual element of a 2-D array is accessed, the compiler
must include additional instructions to calculate the offset of the specific element
within the 1-D array. Given a 2-D array of size m×n and using row-major ordering,
an equation can be derived to compute this offset.
To derive the formula, consider the 2-D array illustrated in Figure 3.7 and
observe the physical storage location within the 1-D array for the first element in
several of the rows. Element (0, 0) maps to position 0 since it is the first element
in both the abstract 2-D and physical 1-D arrays. The first entry of the second
row (1, 0) maps to position n since it follows the first n elements of the first row.
Likewise, element (2, 0) maps to position 2n since it follows the first 2n elements
in the first two rows. We could continue in the same fashion through all of the
rows, but you would soon notice the position for the first element of the ith row is
0 1 2 3 4
Physical storage
of a 2-D array using 0 2 15 45 13 78
column-major order.
1 40 12 52 91 86
2 59 25 33 41 6
•2 •
40 •
59 •
15 •
12 •
25 •
45 •
52 33 13 91 41 78 86 6
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Figure 3.8: Physical storage of a sample 2-D array (top) in a 1-D array using column-
major order (bottom).
84 CHAPTER 3 Sets and Maps
n ∗ i. Since the subscripts start from zero, the ith subscript not only represents a
specific row but also indicates the number of complete rows skipped to reach the
ith row.
Knowing the position of the first element of each row, the position for any
element within a 2-D array can be determined. Given an element (i, j) of a 2-D
array, the storage location of that element in the 1-D array is computed as
The column index, j, is not only the offset within the given row but also the
number of elements that must be skipped in the ith row to reach the jth column.
To see this formula in action, again consider the 2-D array from Figure 3.7 and
assume we want to access element (2, 3). Finding the target element within the
1-D array requires skipping over the first 2 complete rows of elements:
2 15 45 13 78
i
40 12 52 91 86
59 25 33
33 41 6
59
59 25 33 41 6
Plugging the indices into the equation from above results in an index position of
13, which corresponds to the position of element (2, 3) within the 1-D array used
to physically store the 2-D array.
Similar equations can be derived for arrays of higher dimensions. Given a 3-D
array of size d1 × d2 × d3 , the 1-D array offset of element (i1 , i2 , i3 ) stored using
row-major order will be
For each component (i) in the subscript, the equation computes the number of
elements that must be skipped within the corresponding dimension. For example,
the factor (d2 ∗ d3 ) indicates the number of elements in a single table of the cube.
When it’s multiplied by i1 we get the number of complete tables to skip and in turn
the number of elements to skip in order to arrive at the first element of table i1 .
3.3 Multi-Dimensional Arrays 85
i1
d2
d3
where the fj values are the factors representing the number of elements to be
skipped within the corresponding dimension and are computed using
Y
n
fn = 1 and fj = dk ∀0<j<n (3.5)
k=j+1
The size of a multi-dimensional array is fixed at the time it’s created and cannot
change during execution. Likewise, the several fj products used in the equation
above will not change once the size of the array is set. This can be used to our
advantage to reduce the number of multiplications required to compute the element
offsets. Instead of computing the products every time an element is accessed, we
can compute and store the factor values and simply plug them into the equation
when needed.
When using the function, we can pass a variable number of arguments for each
invocation. For example, all of the following are valid function calls:
func( 12 )
func( 5, 8, 2 )
func( 18, -2, 50, 21, 6 )
The asterisk next to the argument name (*args) tells Python to accept any
number of arguments and to combine them into a tuple. The tuple is then passed
to the function and assigned to the formal argument marked with the asterisk.
Note the asterisk is only used in the argument list to indicate that the function
or method can accept any number of arguments. It is not part of the argument
name. The len() operation can be applied to the tuple to determine the number
of actual arguments passed to the function. The individual arguments, which
are elements in the tuple, can be accessed by using the subscript notation or by
iterating the collection.
Constructor
The constructor, which is shown in lines 4–19, defines three data fields: dims
stores the sizes of the individual dimensions; factors stores the factor values
used in the index equation; and elements is used to store the 1-D array used as
the physical storage for the multi-dimensional array.
The constructor is defined to accept a variable-length argument as required in
the ADT definition. The resulting tuple will contain the sizes of the individual
dimensions and is assigned to the dims field. The dimensionality of the array
must be verified at the beginning of the constructor as the MultiArray ADT is
meant for use with arrays of two dimensions or more.
The elements of the multi-dimensional array will be stored in a 1-D array. The
fixed size of the array can be computed as the product of the dimension lengths
by traversing over the tuple containing the variable-length argument. During the
traversal, the precondition requiring all dimension lengths be greater than zero is
also evaluated. The Array class defined earlier in the chapter is used to create the
storage array.
Finally, a 1-D array is created and assigned to the factors field. The size of
the array is equal to the number of dimensions in the multi-dimensional array. This
array will be initialized to the factor values used in Equation 3.4 for computing
the element offsets. The actual computation and initialization is performed by the
computeFactors() helper method, which is left as an exercise. A sample instance
of the MultiArray class is illustrated in Figure 3.9.
dims
• 3 55
factors
• 5 11
elements
• 2 15 45
45 13 78 40
40 12 52 91
91 86 59 25 33 41 6
MultiArray
Figure 3.9: A sample MultiArray object for the 2-D array from Figure 3.6.
numDims() method returns the dimensionality of the array, which can be obtained
from the number of elements in the dims tuple.
Element Access
Access to individual elements within an n-D array requires an n-tuple or multi-
component subscript, one for each dimension. As indicated in Section 2.3.2, when
a multi-component subscript is specified (i.e., y = x[i,j]), Python automatically
stores the components in a tuple in the order listed within the brackets and passes
the tuple to the ndxTuple argument.
The contents of the ndxTuple are passed to the computeIndex() helper method
to compute the index offset within the 1-D storage array. The use of the helper
method reduces the need for duplicate code that otherwise would be required in
both element access methods. The setitem operator method can be imple-
mented in a similar fashion. The major difference is that this method requires a
second argument to receive the value to which an element is set and modifies the
indicated element with the new value instead of returning a value.
: : : : ... : :
where the first line indicates the number of stores; the second line indicates the
number of individual items (both of which are integers); and the remaining lines
contain the sales data. Each line of the sales data consists of four pieces of in-
formation: the store number, the month number, the item number, and the sales
amount for the given item in the given store during the given month. For sim-
plicity, the store and item numbers will consist of consecutive integer values in the
range [1 . . . max], where max is the number of stores or items as extracted from
the first two lines of the file. The month is indicated by an integer in the range
[1 . . . 12] and the sales amount is a floating-point value.
Data Organization
While some reports, like the student report from Chapter 1, are easy to produce
by simply extracting the data and writing it to the report, others require that we
first organize the data in some meaningful way in order to extract the information
needed. That is definitely the case for this problem, where we may need to produce
many different reports from the same collection of data. The ideal structure for
storing the sales data is a 3-D array, as shown in Figure 3.11, in which one dimen-
sion represents the stores, another represents the items sold in the stores, and the
last dimension represents each of the 12 months in the calendar year. The 3-D
array can be viewed as a collection of spreadsheets, as illustrated in Figure 3.12.
res 7
sto...
0
0
:
items
100
0 ... 12
months
.
..
es
3
or
2
st
1
0
0
.
5
..
items
6
10
: : : :
99
0 1 2 3 4 5 6 7 8 9 10 11
months
Each spreadsheet contains the sales for a specific store and is divided into rows and
columns where each row contains the sales for one item and the columns contain
the sales for each month.
Since the store, item, and month numbers are all composed of consecutive
integer values starting from 1, we can easily represent each by a unique index
that is one less than the given number. For example, the data for January will be
stored in column 0, the data for February will be stored in column 1, and so on.
Likewise, the data for item number 1 will be stored in row 0, the data for item
number 2 will be stored in row 1, and so on. We leave the actual extraction of
the data from a text file as an exercise. But for illustration purposes, we assume
this step has been completed resulting in the creation and initialization of the 3-D
array as shown here:
# Compute the total sales of all items for all months in a given store.
def totalSalesByStore( salesData, store ):
# Subtract 1 from the store # since the array indices are 1 less
# than the given store #.
92 CHAPTER 3 Sets and Maps
s = store-1
# Accumulate the total sales for the given store.
total = 0.0
return total
Assuming our view of the data as a collection of spreadsheets, this requires travers-
ing over every element in the spreadsheet containing the data for the given store.
If store equals 1, this is equivalent to processing every element in the spreadsheet
shown at the front of Figure 3.12. Two nested loops are required since we must sum
the values from each row and column contained in the given store spreadsheet.
The number of rows (dimension number 2) and columns (dimension number 3) can
be obtained using the length() array method.
return total
This time, the two nested loops have to iterate over every row of every spread-
sheet for the single column representing the given month. If we use this function
to compute the total sales for the month of January, the elements of the 3-D array
that will be accessed are shown by the shaded area in Figure 3.13(a).
# Compute the total sales of a single item in all stores over all months.
def totalSalesByItem( salesData, item ):
# The item number must be offset by 1.
m = item - 1
return total
The cells of the array that would be accessed when using this function to
compute the total sales for item number 5 are shown by the shaded area in Fig-
ure 3.13(b). Remember, the sales for each item are stored in a specific row of the
array and the index of that row is one less than the item number since the indices
start at 0.
7 7
.
.
..
..
es
3 es 3
or
or
2 2
st
st
1 1
0 0
0 0
1 1
2 2
3 3
4 4
.
.
5 5
..
..
items
items
6 6
7 7
8 8
9 9
10 10
: : : : : : : :
(a) 99 (b) 99
0 1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6 7 8 9 10 11
months months
Figure 3.13: The elements of the 3-D array that must be accessed to compute the total
sales: (a) for the month of January and (b) for item number 5.
# Compute the total sales per month for a given store. A 1-D array is
# returned that contains the totals for each month.
# Iterate over the sales of each item sold during the m month.
for i in range( [Link](2) ):
sum += salesData[s, i, m]
Figure 3.14 illustrates the use of the 1-D array for storing the individual
monthly totals. The shaded area shows the elements of the 3-D array that are
accessed when computing the total sales for the month of April at store number 1.
The monthly total will be stored at index position 3 within the 1-D array since
that is the corresponding column in the 3-D array for the month of April.
store months
0 0 1 2 3 4 5 6 7 8 9 10 11
5
items
10
: : : :
99
totals
0 1 2 3 4 5 6 7 8 9 10 11
Figure 3.14: The elements the 3-D array that must be accessed to compute the monthly
sales for store number 1.
Exercises 95
Exercises
3.1 Complete the Set ADT by implementing intersect() and difference().
It can then be used as shown here to create a set initialized with the given
values:
3.3 Add a new operation to the Set ADT to test for a proper subset. Given two
sets, A and B, A is a proper subset of B, if A is a subset of B and A does not
equal B.
3.4 Add the str() method to the Set implementation to allow a user to print
the contents of the set. The resulting string should look similar to that of a
list, except you are to use curly braces to surround the elements.
3.5 Add Python operator methods to the Set class that can be used to perform
similar operations to those already defined by named methods:
3.6 Add a new operation keyArray() to the Map class that returns an array con-
taining all of the keys stored in the map. The array of keys should be in no
particular ordering.
3.7 Add Python operators to the Map class that can be used to perform similar
operations to those already defined by named methods:
3.8 Design and implement the iterator class SetIterator for use with the Set
ADT implemented using a list.
96 CHAPTER 3 Sets and Maps
3.9 Design and implement the iterator class MapIterator for use with the Map
ADT implemented using a list.
3.10 Develop the index equation that computes the location within a 1-D array for
element (i, j) of a 2-D array stored in column-major order.
3.11 The 2-D array described in Chapter 2 is a simple rectan-
0
gular structure consisting of the same number of elements
1
in each row. Other layouts are possible and sometimes
2
required by problems in computer science. For example,
3
the lower triangular array shown on the right is organized
4
such that the rows are staggered with each successive row
0 1 2 3 4
consisting of one more element than the previous row.
(a) Derive an equation that computes the total number of elements in the
lower triangular table for a table of size m × n.
(b) Derive an index equation that maps an element of the lower triangular
table onto a one-dimensional array stored in row-major order.
Programming Projects
3.1 In this chapter, we implemented the Set ADT using a list. Implement the Set
ADT using a bag created from the Bag class. In your opinion, which is the
better implementation? Explain your answer.
3.2 Define a new class named TriangleArray to implement the lower triangular
table described in Exercise 3.11.
3.3 Given a collection of items stored in a bag, design a linear time algorithm that
determines the number of unique items in the collection.
3.4 Write a function that extracts the sales data from a text file and builds the
3-D array used to produce the various reports in Section 3.4. Assume the data
file has the format as described in the chapter.
3.5 Write a menu-driven program that uses your function from the previous ques-
tion to extract the sales data and can produce any of the following reports:
Algorithms are designed to solve problems, but a given problem can have many
different solutions. How then are we to determine which solution is the most
efficient for a given problem? One approach is to measure the execution time. We
can implement the solution by constructing a computer program, using a given
programming language. We then execute the program and time it using a wall
clock or the computer’s internal clock.
The execution time is dependent on several factors. First, the amount of data
that must be processed directly affects the execution time. As the data set size
increases, so does the execution time. Second, the execution times can vary de-
pending on the type of hardware and the time of day a computer is used. If
we use a multi-process, multi-user system to execute the program, the execution
of other programs on the same machine can directly affect the execution time of
our program. Finally, the choice of programming language and compiler used to
implement an algorithm can also influence the execution time. Some compilers
are better optimizers than others and some languages produce better optimized
code than others. Thus, we need a method to analyze an algorithm’s efficiency
independent of the implementation details.
97
98 CHAPTER 4 Algorithm Analysis
totalSum = 0 # Version 2
for i in range( n ) :
rowSum[i] = 0
for j in range( n ) :
rowSum[i] = rowSum[i] + matrix[i,j]
totalSum = totalSum + rowSum[i]
In this version, the inner loop is again executed n times, but this time, it only
contains one addition operation. That gives a total of n additions for each iteration
of the outer loop, but the outer loop now contains an addition operator of its own.
To calculate the total number of additions for this version, we take the n additions
performed by the inner loop and add one for the addition performed at the bottom
of the outer loop. This gives n + 1 additions for each iteration of the outer loop,
which is performed n times for a total of n2 + n additions.
If we compare the two results, it’s obvious the number of additions in the second
version is less than the first for any n greater than 1. Thus, the second version will
execute faster than the first, but the difference in execution times will not be signif-
icant. The reason is that both algorithms execute on the same order of magnitude,
namely n2 . Thus, as the size of n increases, both algorithms increase at approxi-
mately the same rate (though one is slightly better), as illustrated numerically in
Table 4.1 and graphically in Figure 4.1.
n 2n2 n2 + n
10 200 110
100 20,000 10,100
1000 2,000,000 1,001,000
10000 200,000,000 100,010,000
100000 20,000,000,000 10,000,100,000
104
n2 + n
2n2 n n2
103
102
101
100
Figure 4.1: Graphical comparison of the growth rates from Table 4.1.
Defining Big-O
Assume we have a function T (n) that represents the approximate number of steps
required by an algorithm for an input of size n. For the second version of our
algorithm in the previous section, this would be written as
T2 (n) = n2 + n
Now, suppose there exists a function f (n) defined for the integers n ≥ 0, such that
for some constant c, and some constant m,
T (n) ≤ cf (n)
for all sufficiently large values of n ≥ m. Then, such an algorithm is said to have a
time-complexity of, or executes on the order of, f (n) relative to the number of
operations it requires. In other words, there is a positive integer m and a constant
c (constant of proportionality ) such that for all n ≥ m, T (n) ≤ cf (n). The
100 CHAPTER 4 Algorithm Analysis
function f (n) indicates the rate of growth at which the run time of an algorithm
increases as the input size, n, increases. To specify the time-complexity of an
algorithm, which runs on the order of f (n), we use the notation
O( f (n) )
Consider the two versions of our algorithm from earlier. For version one, the
time was computed to be T1 (n) = 2n2 . If we let c = 2, then
2n2 ≤ 2n2
n2 + n ≤ 2n2
for a result of O(n2 ). In this case, the choice of c comes from the observation that
when n ≥ 1, we have n ≤ n2 and n2 + n ≤ n2 + n2 , which satisfies the equation in
the definition of big-O.
The function f (n) = n2 is not the only choice for satisfying the condition
T (n) ≤ cf (n). We could have said the algorithms had a run time of O(n3 ) or
O(n4 ) since 2n2 ≤ n3 and 2n2 ≤ n4 when n > 1. The objective, however, is
to find a function f (·) that provides the tightest (lowest) upper bound or limit
for the run time of an algorithm. The big-O notation is intended to indicate an
algorithm’s efficiency for large values of n. There is usually little difference in the
execution times of algorithms when n is small.
Constant of Proportionality
The constant of proportionality is only crucial when two algorithms have the same
f (n). It usually makes no difference when comparing algorithms whose growth
rates are of different magnitudes. Suppose we have two algorithms, L1 and L2 ,
with run times equal to n2 and 2n respectively. L1 has a time-complexity of O(n2 )
with c = 1 and L2 has a time of O(n) with c = 2. Even though L1 has a smaller
constant of proportionality, L1 is still slower and, in fact an order of magnitude
slower, for large values of n. Thus, f (n) dominates the expression cf (n) and the run
time performance of the algorithm. The differences between the run times of these
two algorithms is shown numerically in Table 4.2 and graphically in Figure 4.2.
Constructing T(n)
Instead of counting the number of logical comparisons or arithmetic operations, we
evaluate an algorithm by considering every operation. For simplicity, we assume
that each basic operation or statement, at the abstract level, takes the same amount
of time and, thus, each is assumed to cost constant time. The total number of
4.1 Complexity Analysis 101
n n2 2n
10 100 20
100 10,000 200
1000 1,000,000 2,000
10000 100,000,000 20,000
100000 10,000,000,000 200,000
104
n2 2n
n
n2
103
102
101
100
The steps requiring constant time are generally omitted since they eventually
become part of the constant of proportionality. Consider Figure 4.3(a), which
shows a markup of version one of the algorithm from earlier. The basic operations
are marked with a constant time while the loops are marked with the appropriate
total number of iterations. Figure 4.3(b) shows the same algorithm but with the
constant steps omitted since these operations are independent of the data set size.
102 CHAPTER 4 Algorithm Analysis
1 totalSum = 0
1 for i in range( n ) :
1 rowSum[i] = 0
for i in range( n ) :
...
(b) n
n for j in range( n ) :
...
Figure 4.3: Markup for version one of the matrix summing algorithm: (a) shows all oper-
ations marked with the appropriate time and (b) shows only the non-constant time steps.
n2 + log2 n + 3n
n2 + log2 n + 3n ≤ n2 + n2 + n2
n2 + log2 n + 3n ≤ 3n2
Classes of Algorithms
We will work with many different algorithms in this text, but most will have a
time-complexity selected from among a common set of functions, which are listed
in Table 4.3 and illustrated graphically in Figure 4.4.
Algorithms can be classified based on their big-O function. The various classes
are commonly named based upon the dominant term. A logarithmic algorithm is
4.1 Complexity Analysis 103
Table 4.3: Common big-O functions listed from smallest to largest order of magnitude.
108
2n n3 n2
107
106
105 n log2 n
104 n
103
102
log2 n
101
100
any algorithm whose time-complexity is O(loga n). These algorithms are generally
very efficient since loga n will increase more slowly than n. For many problems
encountered in computer science a will typically equal 2 and thus we use the no-
tation log n to imply log2 n. Logarithms of other bases will be explicitly stated.
Polynomial algorithms with an efficiency expressed as a polynomial of the form
am nm + am−1 nm−1 + . . . + a2 n2 + a1 n + a0
104 CHAPTER 4 Algorithm Analysis
is a basic instruction since the time required to assign a reference to the given
variable is independent of the value or type of object specified on the righthand
side of the = sign. The evaluation of arithmetic and logical expressions
y = x
z = x + y * 6
done = x > 0 and x < 100
are basic instructions, again since they require the same number of steps to perform
the given operations regardless of the values of their operands. The subscript
operator, when used with Python’s sequence types (strings, tuples, and lists) is
also a basic instruction.
An assignment statement only requires constant time, but that is the time required
to perform the actual assignment and does not include the time required to execute
any function calls used on the righthand side of the assignment statement.
To determine the run time of the previous statement, we must know the cost of
the function call ex1(n). The time required by a function call is the time it takes
to execute the given function. For example, consider the ex1() function, which
computes the sum of the integer values in the range [0 . . . n):
def ex1( n ):
total = 0
for i in range( n ) :
total += i
return total
4.1 Complexity Analysis 105
NOTE
most problems that do not involve string processing, string operations sel-
dom have an impact on the run time of an algorithm. Thus, in the text, we
assume the string operations, including the use of the print() function, only
require constant time, unless explicitly stated otherwise.
The time required to execute a loop depends on the number of iterations per-
formed and the time needed to execute the loop body during each iteration. In this
case, the loop will be executed n times and the loop body only requires constant
time since it contains a single basic instruction. (Note that the underlying mech-
anism of the for loop and the range() function are both O(1).) We can compute
the time required by the loop as T (n) = n ∗ 1 for a result of O(n).
But what about the other statements in the function? The first line of the
function and the return statement only require constant time. Remember, it’s
common to omit the steps that only require constant time and instead focus on
the critical operations, those that contribute to the overall time. In most instances,
this means we can limit our evaluation to repetition and selection statements and
function and method calls since those have the greatest impact on the overall time
of an algorithm. Since the loop is the only non-constant step, the function ex1()
has a run time of O(n). That means the statement y = ex1(n) from earlier requires
linear time. Next, consider the following function, which includes two for loops:
def ex2( n ):
count = 0
for i in range( n ) :
count += 1
for j in range( n ) :
count += 1
return count
To evaluate the function, we have to determine the time required by each loop.
The two loops each require O(n) time as they are just like the loop in function
ex1() earlier. If we combine the times, it yields T (n) = n + n for a result of O(n).
def ex3( n ):
count = 0
for i in range( n ) :
for j in range( n ) :
count += 1
return count
106 CHAPTER 4 Algorithm Analysis
Both loops will be executed n, but since the inner loop is nested inside the outer
loop, the total time required by the outer loop will be T (n) = n ∗ n, resulting in
a time of O(n2 ) for the ex3() function. Not all nested loops result in a quadratic
time. Consider the following function:
def ex4( n ):
count = 0
for i in range( n ) :
for j in range( 25 ) :
count += 1
return count
which has a time-complexity of O(n). The function contains a nested loop, but
the inner loop executes independent of the size variable n. Since the inner loop
executes a constant number of times, it is a constant time operation. The outer
loop executes n times, resulting in a linear run time. The next example presents a
special case of nested loops:
def ex5( n ):
count = 0
for i in range( n ) :
for j in range( i+1 ) :
count += 1
return count
How many times does the inner loop execute? It depends on the current it-
eration of the outer loop. On the first iteration of the outer loop, the inner loop
will execute one time; on the second iteration, it executes two times; on the third
iteration, it executes three times, and so on until the last iteration when the inner
loop will execute n times. The time required to execute the outer loop will be the
number of times the increment statement count += 1 is executed. Since the inner
loop varies from 1 to n iterations by increments of 1, the total number of times
the increment statement will be executed is equal to the sum of the first n positive
integers:
n(n + 1) n2 + n
T (n) = =
2 2
which results in a quadratic time of O(n2 ).
def ex6( n ):
count = 0
i = n
while i >= 1 :
4.1 Complexity Analysis 107
count += 1
i = i // 2
return count
To determine the run time of this function, we have to determine the number of
loop iterations just like we did with the earlier examples. Since the loop variable is
cut in half each time, this will be less than n. For example, if n equals 16, variable
i will contain the following five values during subsequent iterations (16, 8, 4, 2, 1).
Given a small number, it’s easy to determine the number of loop iterations.
But how do we compute the number of iterations for any given value of n? When
the size of the input is reduced by half in each subsequent iteration, the number
of iterations required to reach a size of one will be equal to
⌊log2 n⌋ + 1
or the largest integer less than log2 n, plus 1. In our example of n = 16, there are
log2 16 + 1, or four iterations. The logarithm to base a of a number n, which is
normally written as y = loga n, is the power to which a must be raised to equal
n, n = ay . Thus, function ex6() requires O(log n) time. Since many problems in
computer science that repeatedly reduce the input size do so by half, it’s not un-
common to use log n to imply log2 n when specifying the run time of an algorithm.
Finally, consider the following definition of function ex7(), which calls ex6()
from within a loop. Since the loop is executed n times and function ex6() requires
logarithmic time, ex7() will have a run time of O(n log n).
def ex7( n ):
count = 0
for i in range( n )
count += ex6( n )
return count
Different Cases
Some algorithms can have run times that are different orders of magnitude for
different sets of inputs of the same size. These algorithms can be evaluated for
their best, worst, and average cases. Algorithms that have different cases can
typically be identified by the inclusion of an event-controlled loop or a conditional
statement. Consider the following example, which traverses a list containing integer
values to find the position of the first negative value. Note that for this problem,
the input is the collection of n values contained in the list.
At first glance, it appears the loop will execute n times, where n is the size of
the list. But notice the return statement inside the loop, which can cause it to
terminate early. If the list does not contain a negative value,
the return statement inside the loop will not be executed and the loop will ter-
minate in the normal fashion from having traversed all n times. In this case, the
function requires O(n) time. This is known as the worst case since the function
must examine every value in the list requiring the most number of steps. Now
consider the case where the list contains a negative value in the first element:
There will only be one iteration of the loop since the test of the condition by the
if statement will be true the first time through and the return statement inside
the loop will be executed. In this case, the findNeg() function only requires O(1)
time. This is known as the best case since the function only has to examine the
first value in the list requiring the least number of steps.
The average case is evaluated for an expected data set or how we expect the
algorithm to perform on average. For the findNeg() function, we would expect the
search to iterate halfway through the list before finding the first negative value,
which on average requires n/2 iterations. The average case is more difficult to
evaluate because it’s not always readily apparent what constitutes the average
case for a particular problem.
In general, we are more interested in the worst case time-complexity of an
algorithm as it provides an upper bound over all possible inputs. In addition, we
can compare the worst case run times of different implementations of an algorithm
to determine which is the most efficient for any input.
Table 4.4: Worst case time-complexities for the more common list operations.
List Traversal
A sequence traversal accesses the individual items, one after the other, in order to
perform some operation on every item. Python provides the built-in iteration for
the list structure, which accesses the items in sequential order starting with the
first item. Consider the following code segment, which iterates over and computes
the sum of the integer values in a list:
sum = 0
for value in valueList :
sum = sum + value
To determine the order of complexity for this simple algorithm, we must first
look at the internal implementation of the traversal. Iteration over the contiguous
elements of a 1-D array, which is used to store the elements of a list, requires a
count-controlled loop with an index variable whose value ranges over the indices
of the subarray. The list iteration above is equivalent to the following:
sum = 0
for i in range( len(valueList) ) :
sum = sum + valueList[i]
Assuming the sequence contains n items, it’s obvious the loop performs n it-
erations. Since all of the operations within the loop only require constant time,
including the element access operation, a complete list traversal requires O(n) time.
Note, this time establishes a minimum required for a complete list traversal. It
can actually be higher if any operations performed during each iteration are worse
than constant time, unlike this example.
List Allocation
Creating a list, like the creation of any object, is considered an operation whose
time-complexity can be analyzed. There are two techniques commonly used to
110 CHAPTER 4 Algorithm Analysis
create a list:
temp = list()
valueList = [ 0 ] * n
The first example creates an empty list, which can be accomplished in constant
time. The second creates a list containing n elements, with each element initialized
to 0. The actual allocation of the n elements can be done in constant time, but
the initialization of the individual elements requires a list traversal. Since there
are n elements and a traversal requires linear time, the allocation of a vector with
n elements requires O(n) time.
Appending to a List
The append() operation adds a new item to the end of the sequence. If the
underlying array used to implement the list has available capacity to add the new
item, the operation has a best case time of O(1) since it only requires a single
element access. In the worst case, there are no available slots and the array has to
be expanded using the steps described in Section 2.2. Creating the new larger array
and destroying the old array can each be done in O(1) time. To copy the contents
of the old array to the new larger array, the items have to be copied element by
element, which requires O(n) time. Combining the times from the three steps
yields a time of T (n) = 1 + 1 + n and a worst case time of O(n).
Extending a List
The extend() operation adds the entire contents of a source list to the end
of the destination list. This operation involves two lists, each of which have
their own collection of items that may be of different lengths. To simplify the
analysis, however, we can assume both lists contain n items. When the destination
list has sufficient capacity to store the new items, the entire contents of the source
list can be copied in O(n) time. But if there is not sufficient capacity, the under-
lying array of the destination list has to be expanded to make room for the new
items. This expansion requires O(n) time since there are currently n items in the
destination list. After the expansion, the n items in the source list are copied to
the expanded array, which also requires O(n) time. Thus, in the worst case the
extend operation requires T (n) = n + n = 2n or O(n) time.
L = list()
for i in range( 1, n+1 ) :
[Link]( i )
Suppose the array is doubled in capacity each time it has to be expanded and
assume the size of the underlying array for an empty list has the capacity for a
single item. We can tally or compute the total running time for this problem by
considering the time required for each individual append operation. This approach
is known as the aggregate method since it computes the total from the individual
operations.
Table 4.5 illustrates the aggregate method when applied to a sequence of 16 ap-
pend operations. si represents the time required to physically store the ith value
when there is an available slot in the array or immediately after the array has been
expanded. Storing an item into an array element is a constant time operation. ei
represents the time required to expand the array when it does not contain available
capacity to store the item. Based on our assumptions related to the size of the
array, an expansion only occurs when i − 1 is a power of 2 and the time incurred
is based on the current size of the array (i − 1). While every append operation
entails a storage cost, relatively few require an expansion cost. Note that as the
size of n increases, the distance between append operations requiring an expansion
also increases.
Based on the tabulated results in Table 4.5, the total time required to perform
a sequence of 16 append operations on an initially empty list is 31, or just under
2n. This results from a total storage cost (si ) of 16 and a total expansion cost
(ei ) of 15. It can be shown that for any n, the sum of the storage and expansion
costs, si + ei , will never be more than T (n) = 2n. Since there are relatively few
expansion operations, the expansion cost can be distributed across the sequence
of operations, resulting in an amortized cost of T (n) = 2n/n or O(1) for the
append operation.
Amortized analysis is the process of computing the time-complexity for a
sequence of operations by computing the average cost over the entire sequence. For
this technique to be applied, the cost per operation must be known and it must
112 CHAPTER 4 Algorithm Analysis
Table 4.5: Using the aggregate method to compute the total run time for a sequence of
16 append operations.
vary in which many of the operations in the sequence contribute little cost and
only a few operations contribute a high cost to the overall time. This is exactly
the case with the append() method. In a long sequence of append operations, only
a few instances require O(n), while many of them are O(1). The amortized cost
can only be used for a long sequence of append operations. If an algorithm used a
single append operation, the cost for that one operation is still O(n) in the worst
case since we do not know if that’s the instance that causes the underlying array
to be expanded.
the evaluation is done by computing an average over all possible inputs and
sometimes requires the use of statistics. Amortized analysis computes an
average cost over a sequence of operations in which many of those opera-
tions are “cheap” and relatively few are “expensive” in terms of contributing
to the overall time.
4.4 Evaluating the Set ADT 113
Table 4.6: Time-complexities for the Set ADT implementation using an unsorted list.
Simple Operations
Evaluating the constructor and length operation is straightforward as they simply
call the corresponding list operation. The contains method, which determines
if an element is contained in the set, uses the in operator to perform a linear
search over the elements stored in the underlying list. The search operation, which
requires O(n) time, will be presented in the next section and we postpone its
analysis until that time. The add() method also requires O(n) time in the worst
case since it uses the in operator to determine if the element is unique and the
append() method to add the unique item to the underlying list, both of which
require linear time in the worst case.
Listing 4.1 A partial listing of the [Link] module from Listing 3.1.
1 class Set :
2 def __init__( self ):
3 self._theElements = list()
4
5 def __len__( self ):
6 return len( self._theElements )
7
8 def __contains__( self, element ):
9 return element in self._theElements
10
11 def add( self, element ):
12 if element not in self :
13 self._theElements.append( element )
14
15 def remove( self, element ):
16 assert element in self, "The element must be in the set."
17 self._theElements.remove( item )
18
19 def __eq__( self, setB ):
20 if len( self ) != len( setB ) :
21 return False
22 else :
23 return [Link]( setB )
24
25 def isSubsetOf( self, setB ):
26 for element in self :
27 if element not in setB :
28 return False
29 return True
30
31 def union( self, setB ):
32 newSet = Set()
33 newSet._theElements.extend( self._theElements )
34 for element in setB :
35 if element not in self :
36 newSet._theElements.append( element )
37 return newSet
given element is a member of set B. Since there are n repetitions of the loop and
each use of the in operator requires O(n) time, the isSubsetOf() method has a
quadratic run time of O(n2 ). The set equality operation is also O(n2 ) since it calls
isSubsetOf() after determining the two sets are of equal size.
· 3 · · 8 · · ·
2 · · 1 · · 5 ·
· · 9 · · 2 · ·
· 7 · · · · · 3
· · · · 4 · · ·
Figure 4.5: A sample sparse matrix with zero elements indicated with dots.
Constructor
The constructor defines three attributes for storing the data related to the sparse
matrix. The elementList field stores MatrixElement objects representing the
non-zero elements. Instances of the storage class contain not only the value for a
specific element but also the row and column indices indicating its location within
the matrix. The numRows and numCols fields are used to store the dimensions of
the matrix. This information cannot be obtained from the element list as was done
with the Array2D used in the implementation of the Matrix ADT in Chapter 2.
Helper Method
Since the element list only contains the non-zero entries, accessing an individual
element is no longer as simple as directly referencing an element of the rectan-
gular grid. Instead, we must search through the list to locate a specific non-zero
element. The helper method findPosition() performs this linear search by iter-
ating through the element list looking for an entry with the given row and column
indices. If found, it returns the list index of the cell containing the element; oth-
erwise, None is returned to indicate the absence of the element.
elementList 0 • 00 11 33 _MatrixElement
• row col value
1 • 11 00 22
numRows
5 2 • 33 77 33
numCols
3 • 00 44 88
8
SparseMatrix 4 • 22 55 22
5 • 11 66 55
6 • 22 22 9
7 • 11 33 11
8 • 44 44 44
9 • 33 11 77
Modifying an Element
The setitem method for the SparseMatrix class is a bit more involved than
that for the Matrix class. The value of an element cannot be directly set as was
done when using the 2-D array. Instead, there are four possible conditions:
1. The element is in the list (and thus non-zero) and the new value is non-zero.
2. The element is in the list, but the new value is zero, turning the element into
a zero element.
3. The element is not currently in the list and the new value is non-zero.
4. The element is not currently in the list, and the new value is zero.
Matrix Scaling
Scaling a matrix requires multiplying each element of the matrix by a given scale
factor. Since the zero elements of the matrix are not affected by the scale factor,
the implementation of this operation for the sparse matrix is as simple as traversing
the list of MatrixElement objects and scaling the corresponding value.
Matrix Addition
In the add() method of the Matrix class implemented in Chapter 2, we iterated
over the 2-D array and added the values, element by element, and stored the
results in the corresponding element of the new matrix. We could use the same
loop structure shown here for the SparseMatrix class:
1. Verify the size of the two matrices to ensure they are the same as required by
matrix addition.
2. Create a new SparseMatrix object with the same number of rows and columns
as the other two.
3. Duplicate the elements of the self matrix and store them in the new matrix.
4. Iterate over the element list of the righthand side matrix (rhsMatrix) to add
the non-zero values to the corresponding elements in the new matrix.
The implementation of the add operation is provided in Listing 4.3. The first
two steps of the add operation are straightforward. The third step of copying the
elements of the self matrix to the new matrix requires a list duplication, which is
handled by the first loop. The second loop handles the fourth step outlined above
by iterating over the list of MatrixElement objects in the rhsMatrix and adding
their values to the corresponding values in the new sparse matrix. Note the use
of the getitem and setitem methods in the second loop. This is necessary
since the two methods properly manage any zero elements that may currently exist
in the newMatrix or that may result after adding corresponding elements.
1 class SparseMatrix :
2 # ...
3 def __add__( self, rhsMatrix ):
4 assert [Link]() == [Link]() and \
5 [Link]() == [Link](), \
6 "Matrix sizes not compatible for the add operation."
7
8 # Create the new matrix.
9 newMatrix = SparseMatrix( [Link](), [Link]() )
10
11 # Duplicate the lhs matrix. The elements are mutable, thus we must
12 # create new objects and not simply copy the references.
13 for element in self._elementList :
14 dupElement = _MatrixElement([Link], [Link], [Link])
15 newMatrix._elementList.append( dupElement )
16
17 # Iterate through each non-zero element of the rhsMatrix.
18 for element in rhsMatrix._elementList :
19 # Get the value of the corresponding element in the new matrix.
20 value = newMatrix[ [Link], [Link] ]
21 value += [Link]
22 # Store the new value back to the new matrix.
23 newMatrix[ [Link], [Link] ] = value
24
25 # Return the new matrix.
26 return newMatrix
120 CHAPTER 4 Algorithm Analysis
❼ The size verification and new matrix creation are constant steps.
❼ To duplicate the entries of the lefthand side sparse matrix requires k time
since append() has an amortized cost of O(1).
❼ The second loop iterates over the element list of the righthand side matrix,
which we have assumed also contains k elements. Since the get and set element
operations used within the loop each require k time in the worst case, the loop
requires 2k ∗ k or 2k 2 time.
Combining this with the time for the previous steps, the add operation is O(k 2 ) in
the worst case. Is this time better than that for the add operation from the Matrix
class implemented as a 2-D array? That depends on the size of k. If there were
no zero elements in either matrix, then k = n2 , which results in a worst case time
of O(n4 ). Remember, however, this implementation is meant to be used with a
sparse matrix in which k ≪ m × n. In addition, the add operation only depends on
the size of the element list, k. Increasing the value of m or n does not increase the
size of k. For the analysis of this algorithm, m and n simply provide a maximum
value for k and are not variables in the equation.
The use of a list as the underlying data structure to store the non-zero elements
of a sparse matrix is a much better implementation than the use of a 2-D array as
it can save significant storage space for large matrices. On the other hand, it intro-
duces element access operations that are more inefficient than when using the 2-D
array. Table 4.7 provides a comparison of the worst case time-complexities for sev-
eral of the operations of the Matrix class using a 2-D array and the SparseMatrix
class using a list. In later chapters, we will further explore the Sparse Matrix ADT
and attempt to improve the time-complexities of the various operations.
Exercises 121
Table 4.7: Comparison of the worst case time-complexities for the Matrix class imple-
mented using a 2-D array and the SparseMatrix class using a list.
Exercises
4.1 Arrange the following expressions from slowest to fastest growth rate.
4.2 Determine the O(·) for each of the following functions, which represent the
number of steps required for some algorithm.
4.4 Determine the O(·) for the following Set operations implemented in Chapter 1:
difference(), intersect(), and remove().
4.5 What is the time-complexity of the proper subset test operation implemented
in Exercise 3.3?
4.6 Prove or show why the worst case time-complexity for the insert() and
remove() list operations is O(n).
122 CHAPTER 4 Algorithm Analysis
4.7 Evaluate each of the following code segments and determine the O(·) for the
best and worst cases. Assume an input size of n.
4.8 The slice operation is used to create a new list that contains a subset of items
from a source list. Implement the slice() function:
def slice( theList, first, last )
which accepts a list and creates a sublist of the values in theList. What is
the worst case time for your implementation and what is the best case time?
4.9 Implement the remaining methods of the SparseMatrix class: transpose(),
getitem , subtract(), and multiply().
4.10 Determine the worst case time-complexities for the SparseMatrix methods
implemented in the previous question.
4.11 Determine the worst case time-complexities for the methods of your
ReversiGameLogic class implemented in Programming Project 2.4.
4.12 Add Python operator methods to the SparseMatrix class that can be used in
place of the named methods for several of the operations.
Programming Projects
4.1 The game of Life is defined for an infinite-sized grid. In Chapter 2, we defined
the Life Grid ADT to use a fixed-size grid in which the user specified the width
and height of the grid. This was sufficient as an illustration of the use of a 2-D
array for the implementation of the game of Life. But a full implementation
should allow for an infinite-sized grid. Implement the Sparse Life Grid ADT
using an approach similar to the one used to implement the sparse matrix.
Programming Projects 123
4.3 Repeat Exercise 2.5 from Chapter 2 but use your new version of the
[Link] program from the previous question.
4.4 The digital grayscale image was introduced in Programming Project 2.3 and an
abstract data type was defined and implemented for storing grayscale images.
A color digital image is also a two-dimensional raster image, but unlike the
grayscale image, the pixels of a color image store data representing colors
instead of a single grayscale value. There are different ways to specify color,
but one of the most common is with the use of the discrete RGB color space.
Individual colors are specified by three intensity values or components within
the range [0 . . . 255], one for each of the three primary colors that represent
the amount of red, green, and blue light that must be added to produce the
given color. We can define the RGBColor class for use in storing a single color
in the discrete RGB color space.
124 CHAPTER 4 Algorithm Analysis
class RGBColor :
def __init__( self, red = 0, green = 0, blue = 0 ):
[Link] = red
[Link] = green
[Link] = blue
Given the description of the operations for the Color Image ADT, implement
the abstract data type using a 2-D array that stores instances of the RGBColor
class. Note when setting the initial color in the constructor or when clearing
the image to a specific color, you can store aliases to one RGBColor object in
each element of the array.
ColorImage( nrows, ncols ): Creates a new instance that consists of
nrows and ncols of pixels each set to black.
width(): Returns the width of the image.
height(): Returns the height of the image.
clear( color ): Clears the entire image by setting each pixel to the given
RGB color.
getitem ( row, col ): Returns the RGB color of the given pixel as an
RGBColor object. The pixel coordinates must be within the valid range.
setitem ( row, col, color ): Set the given pixel to the given RGB color.
The pixel coordinates must be within the valid range.
4.5 Color images can also be stored using three separate color channels in which
the values of each color component is stored in a separate data structure.
Implement a new version of the Color Image ADT using three 1-D arrays to
store the red, green, and blue components of each pixel. Apply the row-major
formula from Section 3.3 to map a specific pixel given by (row, col) to an
entry in the 1-D arrays.
4.6 A color image can be easily converted to a grayscale image by converting each
pixel of the color image, specified by the three components (R, G, B), to a
grayscale value using the formula
gray = round( 0.299 * R + 0.587 * G + 0.114 * B )
When people collect and work with data, they eventually want to search for specific
items within the collection or sort the collection for presentation or easy access.
Searching and sorting are two of the most common applications found in computer
science. In this chapter, we explore these important topics and study some of the
basic algorithms for use with sequence structures. The searching problem will be
discussed many times throughout the text as it can be applied to collections stored
using many different data structures, not just sequences. We will also further
explore the sorting problem in Chapters 12 and 13 with a discussion of more
advanced sorting algorithms.
5.1 Searching
Searching is the process of selecting particular information from a collection of
data based on specific criteria. You are familiar with this concept from your ex-
perience in performing web searches to locate pages containing certain words or
phrases or when looking up a phone number in the telephone book. In this text,
we restrict the term searching to refer to the process of finding a specific item in a
collection of data items.
The search operation can be performed on many different data structures. The
sequence search, which is the focus in this chapter, involves finding an item
within a sequence using a search key to identify the specific item. A key is
a unique value used to identify the data elements of a collection. In collections
containing simple types such as integers or reals, the values themselves are the keys.
For collections of complex types, a specific data component has to be identified as
the key. In some instances, a key may consist of multiple components, which is
also known as a compound key .
125
126 CHAPTER 5 Searching and Sorting
if key in theArray :
print( "The key is in the array." )
else :
print( "The key is not in the array." )
The use of the in operator makes our code simple and easy to read but it
hides the inner workings. Underneath, the in operator is implemented as a linear
search. Consider the unsorted 1-D array of integer values shown in Figure 5.1(a).
To determine if value 31 is in the array, the search begins with the value in the
first element. Since the first element does not contain the target value, the next
element in sequential order is compared to value 31. This process is repeated until
the item is found in the sixth position. What if the item is not in the array? For
example, suppose we want to search for value 8 in the sample array. The search
begins at the first entry as before, but this time every item in the array is compared
to the target value. It cannot be determined that the value is not in the sequence
until the entire array has been traversed, as illustrated in Figure 5.1(b).
start
10
10 51
51 22 18
18 44 31
31 13
13 55 23
23 64
64 29
29
0 1 2 3 4 5 6 7 8 9 10
start
10
10 51
51 22 18
18 44 31
31 13
13 55 23
23 64
64 29
29
0 1 2 3 4 5 6 7 8 9 10
Figure 5.1: Performing a linear search on an unsorted array: (a) the target item is found
and (b) the item is not in the array.
To analyze the sequential search algorithm for the worst case, we must first
determine what conditions constitute the worst case. Remember, the worst case
occurs when the algorithm performs the maximum number of steps. For a sequen-
tial search, that occurs when the target item is not in the sequence and the loop
iterates over the entire sequence. Assuming the sequence contains n items, the
linear search has a worst case time of O(n).
Searching for 8
start
22 44 55 10
10 13
13 18
18 23
23 29
29 31
31 51
51 64
64
0 1 2 3 4 5 6 7 8 9 10
A linear search on a sorted sequence works in the same fashion as that for
the unsorted sequence, with one exception. It’s possible to terminate the search
early when the value is not in the sequence instead of always having to perform a
complete traversal. For example, suppose we want to search for 8 in the array from
Figure 5.2. When the fourth item, which is value 10, is examined, we know value 8
cannot be in the sorted sequence or it would come before 10. The implementation
of a linear search on a sorted sequence is shown in Listing 5.2 on the next page.
The only modification to the earlier version is the inclusion of a test to deter-
mine if the current item within the sequence is larger than the target value. If a
larger value is encountered, the loop terminates and False is returned. With the
modification to the linear search algorithm, we have produced a better version, but
the time-complexity remains the same. The reason is that the worst case occurs
when the value is not in the sequence and is larger than the last element. In this
case, we must still traverse the entire sequence of n items.
128 CHAPTER 5 Searching and Sorting
this task, most people would not begin with the first exam and flip through one at
a time until the requested exam is found, as would be done with a linear search.
Instead, you would probably flip to the middle and determine if the requested exam
comes alphabetically before or after that one. Assuming Jessica’s paper follows al-
phabetically after the middle one, you know it cannot possibly be in the top half of
the stack. Instead, you would probably continue searching in a similar fashion by
splitting the remaining stack of exams in half to determine which portion contains
Jessica’s exam. This is an example of a divide and conquer strategy, which
entails dividing a larger problem into smaller parts and conquering the smaller
part.
Algorithm Description
The binary search algorithm works in a similar fashion to the process described
above and can be applied to a sorted sequence. The algorithm starts by examining
the middle item of the sorted sequence, resulting in one of three possible conditions:
the middle item is the target value, the target value is less than the middle item,
or the target is larger than the middle item. Since the sequence is ordered, we
can eliminate half the values in the list when the target value is not found at the
middle position.
Consider the task of searching for value 10 in the sorted array from Figure 5.2.
We first determine which element contains the middle entry. As illustrated in
Figure 5.3, the middle entry contains 18, which is greater than our target of 10.
Thus, we can discard the upper half of the array from consideration since 10 cannot
possibly be in that part. Having eliminated the upper half, we repeat the process
on the lower half of the array. We then find the middle item of the lower half and
compare its value to the target. Since that entry, which contains 5, is less than the
target, we can eliminate the lower fourth of the array. The process is repeated on
the remaining items. Upon finding value 10 in the middle entry from among those
remaining, the process terminates successfully. If we had not found the target, the
process would continue until either the target value was found or we had eliminated
all values from consideration.
start
22 44 5 10
10 13
13 18
18 23
23 29
29 31
31 51
51 64
64
22 44 55 10
10 13
13 18
18 23
23 29
29 31
31 51
51 64
64
22 44 55 10
10 13 18
18 23
23 29
29 31
31 51
51 64
64
Figure 5.3: Searching for 10 in a sorted array using the binary search.
130 CHAPTER 5 Searching and Sorting
Implementation
The Python implementation of the binary search algorithm is provided in List-
ing 5.4. The variables low and high are used to mark the range of elements in the
sequence currently under consideration. When the search begins, this range is the
entire sequence since the target item can be anywhere within the sequence. The
first step in each iteration is to determine the midpoint of the sequence. If the
sequence contains an even number of elements, the mid point will be chosen such
that the left sequence contains one less item than the right. Figure 5.4 illustrates
the positioning of the low, high, and mid markers as the algorithm progresses.
(a) 2 4 5 10 13
13 18 23 29 31 51 64
64
low high
(b) 2 4 5 10 13 18 23 29 31 51 64
low mid high
(c) 2 4 5 10 13
13 18 23 29 31 51 64
64
low high mid
(d) 2 4 5 10 13 18 23 29
29 31 51 64
low mid high
(e) 2 4 5 10 13 18 23 29 31 51 64
mid low high
(f) 2 4 5 10 13 18 23 29 31 51 64
low high
mid
Figure 5.4: The steps performed by the binary search algorithm in searching for 10: (a)
initial range of items, (b) locating the midpoint, (c) eliminating the upper half, (d) midpoint
of the lower half, (e) eliminating the lower fourth, and (f) finding the target item.
while loop is executed. The worst case occurs when the target value is not in the
sequence, the same as for the linear search. The difference with the binary search
is that not every item in the sequence has to be examined before determining the
target is not in the sequence, even in the worst case. Since the sequence is sorted,
each iteration of the loop can eliminate from consideration half of the remaining
values. As we saw earlier in Section 4.1.2, when the input size is repeatedly re-
duced by half during each iteration of a loop, there will be log n iterations in the
worst case. Thus, the binary search algorithm has a worst case time-complexity of
O(log n), which is more efficient than the linear search.
5.2 Sorting
Sorting is the process of arranging or ordering a collection of items such that each
item and its successor satisfy a prescribed relationship. The items can be simple
values, such as integers and reals, or more complex types, such as student records
or dictionary entries. In either case, the ordering of the items is based on the value
of a sort key . The key is the value itself when sorting simple types or it can be a
specific component or a combination of components when sorting complex types.
We encounter many examples of sorting in everyday life. Consider the listings of
a phone book, the definitions in a dictionary, or the terms in an index, all of which
are organized in alphabetical order to make finding an entry much easier. As we
132 CHAPTER 5 Searching and Sorting
saw earlier in the chapter, the efficiency of some applications can be improved when
working with sorted lists. Another common use of sorting is for the presentation
of data in some organized fashion. For example, we may want to sort a class roster
by student name, sort a list of cities by zip code or population, rank order SAT
scores, or list entries on a bank statement by date.
Sorting is one of the most studied problems in computer science and extensive
research has been done in this area, resulting in many different algorithms. While
Python provides a sort() method for sorting a list, it cannot be used with an
array or other data structures. In addition, exploring the techniques used by some
of the sorting algorithms for improving the efficiency of the sort problem may
provide ideas that can be used with other types of problems. In this section, we
present three basic sorting algorithms, all of which can be applied to data stored
in a mutable sequence such as an array or list.
The algorithm requires multiple passes over the cards, with each pass starting
at the first card and ending one card earlier than on the previous iteration. During
each pass, the cards in the first and second positions are compared. If the first is
larger than the second, the two cards are swapped.
8♣ 5♣ 9♣ 3♣
8 5 9 3
8♣ 5♣ 9♣ 3♣
Next, the cards in positions two and three are compared. If the first one is larger
than the second, they are swapped. Otherwise, we leave them as they were.
5♣ 8♣ 9♣ 3♣
5 8 9 3
5♣ 8♣ 9♣ 3♣
This process continues for each successive pair of cards until the card with the
largest face value is positioned at the end.
5.2 Sorting 133
5♣ 8♣ 9♣ 3♣
5 8 9 3
5♣ 8♣ 9♣ 3♣
5♣ 8♣ 3♣ 9♣
5 8 3 9
5♣ 8♣ 3♣ 9♣
The next two passes over the cards are illustrated below. In the second pass the
card with the second largest face value is positioned in the next-to-last position.
In the third and final pass, the first two cards will be positioned correctly.
5♣ 8♣ 3♣ 9♣
Compare the 8 and 3. Since 8 is larger
than 3, swap the two cards. 5 8 3 9
5♣ 8♣ 3♣ 9♣
5♣ 3♣ 8♣ 9♣
The second largest card (8) is now in its
ordered position. 5 3 8 9
5♣ 3♣ 8♣ 9♣
5♣ 3♣ 8♣ 9♣
(Pass 3) Repeat the process on the first
two cards. Compare the 5 and 3. Since 5 3 8 9
5 is larger than 3, swap the two cards. 5♣ 3♣ 8♣ 9♣
3♣ 5♣ 8♣ 9♣
After swapping the two cards, all of the
cards are now in their proper order, from 3 5 8 9
smallest to largest. 3♣ 5♣ 8♣ 9♣
10 51
51 22 18
18 44 31
31 13 55 23
23 64 29
29
10
10 51
51 22 18
18 44 31
31 13
13 55 23
23 64
64 29
29
10
10 22 51
51 18
18 44 31
31 13
13 55 23
23 64
64 29
29
10
10 22 18
18 51
51 44 31
31 13
13 55 23
23 64
64 29
29
10
10 22 18
18 44 51
51 31
31 13
13 55 23
23 64
64 29
29
10
10 22 18
18 44 31
31 51
51 13
13 55 23
23 64
64 29
29
10
10 22 18
18 44 31
31 13
13 51
51 55 23
23 64
64 29
29
10
10 22 18
18 44 31
31 13
13 55 51
51 23
23 64
64 29
29
10
10 22 18
18 44 31
31 13
13 55 23
23 51
51 64
64 29
29
10
10 22 18
18 44 31
31 13
13 55 23
23 51
51 64
64 29
29
10
10 22 18
18 44 31
31 13
13 55 23
23 51
51 29
29 64
64
Figure 5.5: First complete pass of the bubble sort algorithm, which places 64 in its correct
position. Black boxes represent values being compared; arrows indicate exchanges.
10 22 18
18 44 31
31 13
13 55 23
23 51
51 29 64
64
22 10
10 44 18
18 13
13 55 23
23 31
31 29
29 51
51 64
64
22 44 10
10 13
13 55 18
18 23
23 29
29 31
31 51
51 64
64
22 44 10
10 55 13
13 18
18 23
23 29
29 31
31 51
51 64
64
22 44 55 10
10 13
13 18
18 23
23 29
29 31
31 51
51 64
64
22 44 55 10
10 13
13 18
18 23
23 29
29 31
31 51
51 64
64
22 44 55 10
10 13
13 18
18 23
23 29
29 31
31 51
51 64
64
22 44 55 10
10 13
13 18
18 23
23 29
29 31
31 51
51 64
64
22 44 55 10
10 13
13 18
18 23
23 29
29 31
31 51
51 64
64
22 44 55 10
10 13
13 18
18 23
23 29
29 31
31 51
51 64
64
22 44 55 10
10 13
13 18
18 23
23 29
29 31
31 51
51 64
64
Figure 5.6: Result of applying the bubble sort algorithm to the sample sequence. The
gray boxes show the values that are in order after each outer-loop traversal.
of iterations for the inner loop will be the sum of the first n − 1 integers, which
equals
n(n − 1) 1 1
− n = n2 + n
2 2 2
resulting in a run time of O(n2 ). Bubble sort is considered one of the most in-
efficient sorting algorithms due to the total number of swaps required. Given an
array of keys in reverse order, a swap is performed for every iteration of the inner
loop, which can be costly in practice.
The bubble sort algorithm as implemented in Listing 5.5 always performs n2
iterations of the inner loop. But what if the sequence is already in sorted order?
136 CHAPTER 5 Searching and Sorting
In this case, there would be no need to sort the sequence. But our implementation
still performs all n2 iterations because it has no way of knowing the sequence is
already sorted.
The bubble sort algorithm can be improved by having it terminate early and
not require it to perform all n2 iterations when the sequence is in sorted order.
We can determine the sequence is in sorted order when no swaps are performed
by the if statement within the inner loop. At that point, the function can return
immediately without completing the remaining iterations. If a value is out of sorted
order, then it will either be smaller than its predecessor in the sequence or larger
than its successor at which point the condition of the if statement would be true.
This improvement, which is left as an exercise, introduces a best case that only
requires O(n) time when the initial input sequence is in sorted order.
8♣ 5♣ 9♣ 3♣ 6♣
8 5 9 3 6
8♣ 5♣ 9♣ 3♣ 6♣
Instead of swapping the cards as was done with the bubble sort, we are going
to scan through the cards and select the smallest from among those on the table
and place it in our hand. For our set of cards, we identify the 3 as the smallest:
8♣ 5♣ 9♣ 3♣ 6♣
8 5 9 3 6
8♣ 5♣ 9♣ 3♣ 6♣
We pick up the 3 and place it in our hand, leaving the remaining cards on the
table:
3♣ 8♣ 5♣ 9♣ 6♣
3 8 5 9 6
3♣ 8♣ 5♣ 9♣ 6♣
We repeat the process and identify the 5 as the next smallest face value:
8♣ 5♣ 9♣ 6♣
8 5 9 6
8♣ 5♣ 9♣ 6♣
We pick up the 5 and add it to proper sorted position, which will be on the right
side since there are no cards with a smaller face value left on the table.
5♣
3♣ 5 8♣ 9♣ 6♣
8 9 6
5♣
3
3♣ 8♣ 9♣ 6♣
This process is continued until all of the cards have been picked up and placed
in our hand in the correct sorted order from smallest to largest.
6♣ 8♣ 9♣
3♣ 5 ♣ 6 3 ♣ 5♣ 6♣ 8 3♣ 5♣6♣8♣ 9 3♣ 5♣6♣8♣9♣
6♣
35 3 56 3 568 3 5 6 89
8♣ 9♣
5♣3♣ 6♣5♣3♣ 8♣6♣5♣3♣ 3
9♣8♣6♣5♣ ♣
The process we used to sort the set of five cards is similar to the approach used
by the selection sort algorithm. But when implementing insertion sort in code, the
algorithm maintains both the sorted and unsorted values within the same sequence
structure. The selection sort, which improves on the bubble sort, makes multiple
passes over the sequence, but unlike the bubble sort, it only makes a single swap
after each pass. The implementation of the selection sort algorithm is provided in
Listing 5.6.
The process starts by finding the smallest value in the sequence and swaps it
with the value in the first position of the sequence. The second smallest value
is then found and swapped with the value in the second position. This process
continues positioning each successive value by selecting them from those not yet
sorted and swapping with the values in the respective positions. Figure 5.7 shows
the results after each iteration of the algorithm when applied to the sample array
of integers. The grayed boxes represent those items already placed in their proper
position while the black boxes show the two values that are swapped.
The selection sort, which makes n − 1 passes over the array to reposition n − 1
values, is also O(n2 ). The difference between the selection and bubble sorts is that
the selection sort reduces the number of swaps required to sort the list to O(n).
We pick up the top card from the deck and place it in our hand:
6♣
♣♣
3♣ 859♣
3 8596
695♣
3♣ 8♣
♣♣
our hand the deck
Since this is the first card, there is no decision to be made as to its position.
We again pick up the top card from the deck and compare it to the card already
in our hand and insert it into its proper sorted position:
8♣
596♣
♣♣
3♣ 8
3
8♣
3♣
596
695♣
♣♣
our hand the deck
After placing the 8 into our hand, the process is repeated. This time, we pick
up the 5 and find its position within our hand and insert it in the proper place:
5♣
8♣
3♣ 5 ♣
96♣
3 8 96
5♣
8♣3♣ 69♣
♣
our hand the deck
5.2 Sorting 139
10
10 51
51 2 18 44 31
31 13
13 55 23
23 64
64 29
29
22 51
51 10
10 18 44 31
31 13
13 55 23
23 64
64 29
29
22 44 10
10 18 51 31
31 13
13 55 23
23 64
64 29
29
22 44 55 18
18 51
51 31
31 13
13 10 23
23 64
64 29
29
22 4 55 10
10 51
51 31
31 13
13 18
18 23
23 64
64 29
29
22 44 55 10
10 13
13 31
31 51
51 18
18 23
23 64
64 29
29
22 44 55 10
10 13
13 18
18 51 31
31 23
23 64 29
29
22 44 5 10
10 13
13 18
18 23
23 31
31 51
51 64
64 29
29
22 44 55 10
10 13
13 18
18 23
23 29
29 51
51 64
64 31
31
22 44 55 10
10 13
13 18
18 23
23 29
29 31
31 64
64 51
51
22 44 55 10
10 13
13 18
18 23
23 29
29 31
31 51
51 64
64
Figure 5.7: Result of applying the selection sort algorithm to our sample array. The gray
boxes show the values that have been sorted; the black boxes show the values that are
swapped during each iteration of the algorithm.
140 CHAPTER 5 Searching and Sorting
This process continues, one card at a time, until all of the cards have been removed
from the table and placed into our hand in their proper sorted position.
9♣ 6♣
3♣5♣8♣ 9 3♣5♣ 6
8♣9♣
6♣ 3♣5♣6♣8♣9♣
3 58
5♣3♣
9♣
3 5 893♣ 3 5 689
3♣
8♣ 8♣ 5♣
9♣ 6♣
8♣ 5♣
9♣
pick up the next pick up the
card on top (9) last card (6) the resulting hand
The insertionSort() function starts by assuming the first item is in its proper
position. Next, an iteration is performed over the remaining items so each value
can be inserted into its proper position within the sorted portion of the sequence.
The ordered portion of the sequence is at the front while those yet to be inserted
are at the end. The i loop index variable marks the separation point between the
two parts. The inner loop is used to find the insertion point within the sorted
sequence and at the same time, shifts the items down to make room for the next
item. Thus, the inner loop starts from the end of the sorted subsequence and
5.2 Sorting 141
works its way to the front. After finding the proper position, the item is inserted.
Figure 5.8 illustrates the application of this algorithm on an array of integer values.
The insertion sort is an example of a sorting algorithm in which the best and
worst cases are different. Determining the different cases and the corresponding
run times is left as an exercise.
10
10 51
51 22 18 44 31
31 13
13 55 23
23 64
64 29
29
10
10 51 22 18 44 31
31 13
13 55 23
23 64
64 29
29
22 10
10 51
51 18
18 44 31
31 13
13 55 23
23 64
64 29
29
22 10
10 18
18 51
51 4 31
31 13
13 55 23
23 64
64 29
29
22 44 10
10 18
18 51
51 31
31 13
13 5 23
23 64
64 29
29
22 44 10
10 18
18 31
31 51
51 13 55 23
23 64 29
29
22 44 10
10 13
13 18
18 31
31 51
51 55 23
23 64
64 29
29
22 44 55 10
10 13
13 18
18 31
31 51
51 23
23 64
64 29
29
22 44 55 10
10 13
13 18
18 23
23 31
31 51
51 64
64 29
29
22 4 55 10
10 13
13 18
18 23
23 31
31 51
51 64
64 29
29
22 44 55 10
10 13
13 18
18 23
23 29
29 31
31 51
51 64
64
Figure 5.8: Result of applying the insertion sort algorithm to the sample array. The gray
boxes show values that have been sorted; the black boxes show the next value to be
positioned; and the lighter gray boxes with black text are the sorted values that have to be
shifted to the right to open a spot for the next value.
142 CHAPTER 5 Searching and Sorting
Listing 5.8 Finding the location of a target value using the binary search.
1 # Modified version of the binary search that returns the index within
2 # a sorted sequence indicating where the target should be located.
3 def findSortedPosition( theList, target ):
4 low = 0
5 high = len(theList) - 1
6 while low <= high :
7 mid = (high + low) // 2
8 if theList[mid] == target :
9 return mid # Index of the target.
10 elif target < theList[mid] :
11 high = mid - 1
12 else :
13 low = mid + 1
14
15 return low # Index where the target value should be.
value into the list. The findOrderedPosition() function can also be used with
lists containing duplicate values, but there is no guarantee where the new value
will be placed in relation to the other duplicate values beyond the proper ordering
requirement that they be adjacent.
which creates two lists with the items ordered in ascending order and then calls a
user-defined function to create and return a new list created by merging the other
two. Printing the new merged list produces
Problem Solution
This problem can be solved by simulating the action a person might take to merge
two stacks of exam papers, each of which are in alphabetical order. Start by choos-
ing the exam from the two stacks with the name that comes first in alphabetical
order. Flip it over on the table to start a new stack. Again, choose the exam from
the top of the two stacks that comes next in alphabetical order and flip it over and
place it on top of first one. Repeat this process until one of the two original stacks
is exhausted. The exams in the remaining stack can be flipped over on top of the
new stack as they are already in alphabetical order and alphabetically follow the
144 CHAPTER 5 Searching and Sorting
(a) 22 44 55 10
10 13 18
18 23
23 29
29 31
31 51
51 64
low high
(b) 22 44 55 10
10 13
13 18
18 23
23 29
29 31
31 51
51 64
64
low mid high
(c) 22 44 55 10
10 13 18
18 23
23 29
29 31
31 51
51 64
mid low high
(d) 22 44 55 10
10 13
13 18
18 23
23 29 31
31 51
51 64
64
low mid high
(e) 22 4 55 10
10 13
13 18
18 23
23 29
29 31
31 51
51 64
64
low high mid
(f) 22 44 55 10
10 13
13 18
18 23
23 29
29 31
31 51
51 64
64
low high
mid
(g) 22 44 55 10
10 13
13 18
18 23
23 29
29 31
31 51
51 64
64
mid high
low
(h) 22 44 55 10
10 13
13 18
18 23
23 29
29 31
31 51
51 64
64
mid
high/low
(i) 22 44 55 10 13
13 18
18 23 29
29 31
31 51 64
64
high low
mid
Figure 5.9: Performing a binary search on a sorted list when searching for value 25.
last exam flipped onto the new stack. You now have a single stack of exams in
alphabetical order.
A similar approach can be used to merge two sorted lists. Consider the illus-
tration in Figure 5.10, which demonstrates this process on the sample lists created
in the example code segment from earlier. The items in the original list are not
removed, but instead copied to the new list. Thus, there is no “top” item from
which to select the smallest value as was the case in the example of merging two
stacks of exams. Instead, index variables are used to indicate the “top” or next
value within each list. The implementation of the mergeSortedLists() function
is provided in Listing 5.9.
The process of merging the two lists begins by creating a new empty list and
initializing the two index variables to zero. A loop is used to repeat the process
5.3 Working with Sorted Lists 145
22 8 15
15 23
23 37
37 44 6 15
15 20
20
a b
22 8 15
15 23
23 37
37 44 6 15
15 20
20 22
a b
22 8 15
15 23
23 37
37 44 6 15
15 20
20 22 4
a b
22 8 15
15 23
23 37
37 44 6 15
15 20
20 22 4 66
a b
22 8 15
15 23
23 37
37 44 6 15
15 20
20 22 4 66 88
a b
22 8 15
15 23
23 37
37 44 6 15
15 20
20 22 4 66 88 15
15
a b
22 8 15
15 23
23 37
37 44 6 15
15 20
20 22 4 66 88 15
15 15
15
a b
22 8 15
15 23
23 37
37 44 6 15
15 20
20 22 4 66 88 15
15 15
15 20
20
a b
22 8 15
15 23
23 37
37 44 6 15
15 20
20 22 4 66 88 15
15 15
15 20
20 23
23
a b
22 8 15
15 23
23 37
37 44 6 15
15 20
20 22 4 66 88 15
15 15
15 20
20 23
23 37
37
a b
Figure 5.10: The iterative steps for merging two sorted lists into a new sorted list. a and
b are index variables indicating the next value to be merged from the respective list.
of selecting the next largest value to be added to the new merged list. During the
iteration of the loop, the value at listA[a] is compared to the value listB[b].
The largest of these two values is added or appended to the new list. If the two
values are equal, the value from listB is chosen. As values are copied from the
two original lists to the new merged list, one of the two index variables a or b is
incremented to indicate the next largest value in the corresponding list.
This process is repeated until all of the values have been copied from one of the
two lists, which occurs when a equals the length of listA or b equals the length of
listB. Note that we could have created and initialized the new list with a sufficient
number of elements to store all of the items from both listA and listB. While
that works for this specific problem, we want to create a more general solution that
146 CHAPTER 5 Searching and Sorting
1 # Merges two sorted lists to create and return a new sorted list.
2 def mergeSortedLists( listA, listB ) :
3 # Create the new list and initialize the list markers.
4 newList = list()
5 a = 0
6 b = 0
7
8 # Merge the two lists together until one is empty.
9 while a < len( listA ) and b < len( listB ) :
10 if listA[a] < listB[b] :
11 [Link]( listA[a] )
12 a += 1
13 else :
14 [Link]( listB[b] )
15 b += 1
16
17 # If listA contains more items, append them to newList.
18 while a < len( listA ) :
19 [Link]( listA[a] )
20 a += 1
21
22 # Or if listB contains more items, append them to newList.
23 while b < len( listB ) :
24 [Link]( listB[b] )
25 b += 1
26
27 return newList
we can easily modify for similar problems where the new list may not contain all
of the items from the other two lists.
After the first loop terminates, one of the two lists will be empty and one will
contain at least one additional value. All of the values remaining in that list must
be copied to the new merged list. This is done by the next two while loops, but
only one will be executed depending on which list contains additional values. The
position containing the next value to be copied is denoted by the respective index
variable a or b.
❼ The first loop performs the maximum number of iterations when the selection
of the next value to be copied alternates between the two lists. This results
5.4 The Set ADT Revisited 147
in all values from either listA or listB being copied to the newList and all
but one value from the other for a total of 2n − 1 iterations. Then, one of the
next two loops will execute a single iteration in order to copy the last value
to the newList.
❼ The minimum number of iterations performed by the first loop occurs when
all values from one list are copied to the newList and none from the other. If
the first loop copies the entire contents of listA to the newList, it will require
n iterations followed by n iterations of the third loop to copy the values from
listB. If the first loop copies the entire contents of listB to the newList, it
will require n iterations followed by n iterations of the second loop to copy
the values from listA.
In both cases, the three loops are executed for a combined total of 2n iterations.
Since the statements performed by each of the three loops all require constant time,
merging two lists can be done in O(n) time.
NOTE
nent, the evaluation ends and returns the result. For example, in evaluating
the logical expression a > b and a < c, if a > b is False, then there is no
need to continue the evaluation of the second component since the overall
expression must be False.
Basic Operations
Performing a binary search to locate an element in the sorted list or to find the
position where an element belongs in the sorted list is needed in several methods.
Instead of reimplementing the operation each time, we implement the modified
version of the binary search algorithm from Listing 5.8 in the findPosition()
helper method. The helper method does not detect nor distinguish between unique
and duplicate values. It only returns the index where the element is located within
the list or where it should be placed if it were added to the list. Thus, care must
be taken when implementing the various methods to check for the existence of an
element when necessary.
The contains method is easily implemented using findPosition(). The
index value returned by the helper method indicates the location where the element
should be within the sorted list, but it says nothing about the actual existence of
the element. To determine if the element is in the set, we can compare the element
at the ndx position within the list to the target element. Note the inclusion of
the condition ndx < len(self) within the compound expression. This is needed
since the value returned by findPosition() can be one larger than the number
of items in the list, which occurs when the target should be located at the end
of the list. If this value were directly used in examining the contents of the list
without making sure it was in range, an out-of-range exception could be raised.
The contains method has a worst case time of O(log n) since it uses the binary
search to locate the given element within the sorted list.
To implement the add() method, we must first determine if the element is
unique since a set cannot contain duplicate values. This is done with the use of
the in operator, which automatically calls the contains operator method. If
the element is not already a member of the set, the insert() method is called to
insert the new element in its proper position within the ordered list. Even though
the contains method has a better time-complexity when using a sorted list
and the binary search, the add() operation still requires O(n) time, the proof of
which is left as an exercise.
The remove() method requires that the target element must be a member of
the set. To verify this precondition, an assertion is made using the in operator.
After which, the findPosition() helper method is called to obtain the location
of the element, which can then be used with the pop() list method to remove the
element from the underlying sorted list. Like the add operation, the remove()
method still has a worst case time of O(n), the proof of which is left as an exercise.
150 CHAPTER 5 Searching and Sorting
We can implement the isSubsetOf() method in the same fashion as was done
in the original version that used the unsorted list as shown in lines 29–33 of List-
ing 5.10. To evaluate the efficiency of the method, we again assume both sets
contain n elements. The isSubsetOf() method performs a traversal over the
self set during which the in operator is applied to setB. Since the in operator
requires O(log n) time and it’s called n times, isSubsetOf() has a time-complexity
of O(n log n).
But that implementation would have a time-complexity of O(n log n) since it calls
the isSubsetOf() method. A more efficient implementation of the equals opera-
tion is possible if we compare the elements in the list directly instead of using the
isSubsetOf() method. Remember, for two sets to be equal, they must contain the
exact same elements. Since the lists for both sets are sorted, not only must they
contain the same elements, but those elements must be in corresponding positions
within the two lists for the sets to be equal.
The new implementation of the eq method is provided in Listing 5.11. The
two lists are traversed simultaneously during which corresponding elements are
compared. If a single instance occurs where corresponding elements are not identi-
cal, then the two sets cannot be equal. Otherwise, having traversed the entire list
and finding no mismatched items, the two sets must be equal. The new implemen-
tation only requires O(n) time since it only involves one complete traversal of the
lists. A similar approach can be used to improve the efficiency of the isSubsetOf()
method to only require O(n) time, which is left as an exercise.
1 class Set :
2 # ...
3 def __eq__( self, setB ):
4 if len( self ) != len( setB ) :
5 return False
6 else :
7 for i in range( len(self) ) :
8 if self._theElements[i] != setB._theElements[i] :
9 return False
10 return True
5.4 The Set ADT Revisited 151
1 class Set :
2 # ...
3 def union( self, setB ):
4 newSet = Set()
5 a = 0
6 b = 0
7 # Merge the two lists together until one is empty.
8 while a < len( self ) and b < len( setB ) :
9 valueA = self._theElements[a]
10 valueB = setB._theElements[b]
11 if valueA < valueB :
12 newSet._theElements.append( valueA )
13 a += 1
14 elif valueA > valueB :
15 newSet._theElements.append( valueB )
16 b += 1
17 else : # Only one of the two duplicates are appended.
18 newSet._theElements.append( valueA )
19 a += 1
20 b += 1
21
22 # If listA contains more items, append them to newList.
23 while a < len( self ) :
24 newSet._theElements.append( self._theElements[a] )
25 a += 1
26
27 # Or if listB contains more, append them to newList.
28 while b < len( otherSet ) :
29 newSet._theElements.append( setB._theElements[b] )
30 b += 1
31
32 return newSet
152 CHAPTER 5 Searching and Sorting
Table 5.1: Comparison of the two Set ADT implementations using an unsorted list and
the improved sorted list with binary search and list merging.
Exercises
5.1 Given an unsorted list of n values, what is the time-complexity to find the k t h
smallest value in the worst case? What would be the complexity if the list
were sorted?
5.2 What is the O(·) for the findSortedPosition() function in the worst case?
5.3 Consider the new implementation of the Set class using a sorted list with the
binary search.
(a) Prove or show the worst case time for the add() method is O(n).
(b) What is the best case time for the add() method?
Programming Projects 153
5.4 Determine the worst case time complexity for each method of the Map ADT
implemented in Section 3.2.
5.5 Modify the binary search algorithm to find the position of the first occurrence
of a value that can occur multiple times in the ordered list. Verify your
algorithm is still O(log n).
5.6 Design and implement a function to find all negative values within a given list.
Your function should return a new list containing the negative values. When
does the worst case occur and what is the run time for that case?
5.7 In this chapter, we used a modified version of the mergeSortedLists() func-
tion to develop a linear time union() operation for our Set ADT implemented
using a sorted list. Use a similar approach to implement new linear time ver-
sions of the isSubsetOf(), intersect(), and difference() methods.
5.8 Given the following list of keys (80, 7, 24, 16, 43, 91, 35, 2, 19, 72), show the
contents of the array after each iteration of the outer loop for the indicated
algorithm when sorting in ascending order.
5.9 Given the following list of keys (3, 18, 29, 32, 39, 44, 67, 75), show the contents
of the array after each iteration of the outer loop for the
5.10 Evaluate the insertion sort algorithm to determine the best case and the worst
case time complexities.
Programming Projects
5.1 Implement the Bag ADT from Chapter 1 to use a sorted list and the binary
search algorithm. Evaluate the time complexities for each of the operations.
5.2 Implement a new version of the Map ADT from Section 3.2 to use a sorted
list and the binary search algorithm.
5.3 The implementation of the Sparse Matrix ADT from Chapter 4 can be im-
proved by storing the MatrixElement objects in a sorted list and using the
binary search to locate a specific element. The matrix elements can be sorted
based on the row and column indices using an index function similar to that
used with a 2-D array stored in a MultiArray. Implement a new version of
the Sparse Matrix ADT using a sorted list and the binary search to locate
elements.
5.4 Implement a new version of the Sparse Life Grid ADT from Chapter 4 to use
a sorted list and the binary search to locate the occupied cells.
154 CHAPTER 5 Searching and Sorting
5.5 A colormap is a lookup table or color palette containing a limited set of colors.
Early color graphics cards could only display up to 256 unique colors at one
time. Colormaps were used to specify which 256 colors should be used to
display color images on such a device. Software applications were responsible
for mapping each color in the image that was to be displayed to a color in
the limited color set specified by the colormap. We can define a Colormap
ADT for storing a limited set of colors and for use in mapping one of the
16.7+ million colors possible in the discrete RGB color space to a color in
the colormap. Given the description below of various operations, implement
the Colormap ADT using a 1-D array structure.
ColorMap( k ): Creates a new empty colormap that is capable of storing
up to k colors.
length (): Returns the number of colors currently stored in the colormap.
contains ( color ): Determines if the given color is contained in the col-
ormap.
add( color ): Adds the given color to the colormap. Only one instance of
each color can be added to the colormap. In addition, a color cannot be
added to a full colormap.
remove ( color ): Removes the given color from the colormap. The color
must be contained in the colormap in order to be removed.
map( color ): Maps the given color to an entry in the colormap and
returns that color. A common approach is to map the color to its nearest
neighbor in the colormap. The nearest neighbor of a color is the entry in
the colormap that has the minimum Euclidean distance squared between
the two colors. If there is more than one nearest neighbor in the colormap,
only one is returned. In addition, the colormap must contain at least one
color in order to perform the mapping operation.
iterator (): Creates and returns an iterator object that can be used to
iterate over the colors in the colormap.
5.6 Evaluate the map() method of your implementation of the Colormap ADT
from the previous question to determine the worst case time-complexity.
5.7 Colormaps are used in color quantization, which is the process of reducing the
number of colors in an image while trying to maintain the original appearance
as much as possible. Part of the process recolors an original image using a
reduced set of colors specified in a colormap.
An array is the most basic sequence container used to store and access a collection of
data. It provides easy and direct access to the individual elements and is supported
at the hardware level. But arrays are limited in their functionality. The Python
list, which is also a sequence container, is an abstract sequence type implemented
using an array structure. It extends the functionality of an array by providing a
larger set of operations than the array, and it can automatically adjust in size as
items are added or removed.
The array and Python list can be used to implement many different abstract
data types. They both store data in linear order and provide easy access to their
elements. The binary search can be used with both structures when the items
are stored in sorted order to allow for quick searches. But there are several dis-
advantages in the use of the array and Python list. First, insertion and deletion
operations typically require items to be shifted to make room or close a gap. This
can be time consuming, especially for large sequences. Second, the size of an array
is fixed and cannot change. While the Python list does provide for an expandable
collection, that expansion does not come without a cost. Since the elements of
a Python list are stored in an array, an expansion requires the creation of a new
larger array into which the elements of the original array have to be copied. Fi-
nally, the elements of an array are stored in contiguous bytes of memory, no matter
the size of the array. Each time an array is created, the program must find and
allocate a block of memory large enough to store the entire array. For large arrays,
it can be difficult or impossible for the program to locate a block of memory into
which the array can be stored. This is especially true in the case of a Python list
that grows larger during the execution of a program since each expansion requires
ever larger blocks of memory.
In this chapter, we introduce the linked list data structure, which is a general
purpose structure that can be used to store a collection in linear order. The linked
list improves on the construction and management of an array and Python list
by requiring smaller memory allocations and no element shifts for insertions and
155
156 CHAPTER 6 Linked Structures
deletions. But it does eliminate the constant time direct element access available
with the array and Python list. Thus, it’s not suitable for every data storage
problem. There are several varieties of linked lists. The singly linked list is a linear
structure in which traversals start at the front and progress, one element at a time,
to the end. Other variations include the circularly linked, the doubly linked, and
the circularly doubly linked lists.
6.1 Introduction
Suppose we have a basic class containing a single data field:
class ListNode :
def __init__( self, data ) :
[Link] = data
We can create several instances of this class, each storing data of our choosing. In
the following example, we create three instances, each storing an integer value:
a = ListNode( 11 )
b = ListNode( 52 )
c = ListNode( 18 )
the result of which is the creation of three variables and three objects :
a b c
•• •• ••
11
11 52
52 18
18
class ListNode :
def __init__( self, data ) :
[Link] = data
[Link] = None
The three objects from the previous example would now have a second data field
initialized with a null reference, as illustrated in the following:
a b c
•• •• ••
11
11 • 52
52 • 18
18 •
6.1 Introduction 157
Since the next field can contain a reference to any type of object, we can assign
to it a reference to one of the other ListNode objects. For example, suppose we
assign b to the next field of object a:
[Link] = b
a b c
•• •• ••
11
11 • 52
52 • 18
18 •
[Link] = c
a b c
•• •• ••
11
11 • 52
52 • 18
18 •
We can remove the two external references b and c by assigning None to each,
as shown here:
a b c
•• •• ••
11
11 • 52
52 • 18
18 •
The result is a linked list structure. The two objects previously pointed to by
b and c are still accessible via a. For example, suppose we wanted to print the
values of the three objects. We can access the other two objects through the next
field of the first object:
print( [Link] )
print( [Link] )
print( [Link] )
list. Figure 6.1 provides an example of a linked list consisting of five nodes. The
last node in the list, commonly called the tail node, is indicated by a null link
reference. Most nodes in the list have no name and are simply referenced via the
link field of the preceding node. The first node in the list, however, must be named
or referenced by an external variable as it provides an entry point into the linked
list. This variable is commonly known as the head pointer, or head reference. A
linked list can also be empty, which is indicated when the head reference is null.
head
••
22 • 52
52 • 18
18 • 36
36 • 13
13 •
Figure 6.1: A singly linked list consisting of five nodes and a head reference.
• • • •
entry
•• • • • • • •
• •
• • • •
A linked list is a data structure that can be used to implement any number of
abstract data types. While some languages do provide, as part of their standard
library, a generic List ADT implemented using a linked list, we are going to create
and work with linked lists directly. Some algorithms and abstract data types can
be implemented more efficiently if we have direct access to the individual nodes
within the ADT than would be possible if we created a generic linked list class.
6.2 The Singly Linked List 159
references must be permanent or exist during the lifetime of the linked list
in order to maintain the collection of nodes. Others are only needed on a
temporary basis in order to perform a specific operation. These temporary
external references should be local variables that disappear after the func-
tion or method has completed.
22 • 52
52 • 18
18 • 36
36 • 13
13 •
22 • 52
52 • 18
18 • 36
36 • 13
13 •
22 • 52
52 • 18
18 • 36
36 • 13
13 •
2 • 52
52 • 18
18 • 36
36 • 13
13 •
2 • 52
52 • 18
18 • 36
36 • 13
13 •
(f) The external reference is set to None after printing value 13.
head curNode
•• ••
22 • 52
52 • 18
18 • 36
36 • 13
13 •
Figure 6.3: Traversing a linked list requires the initialization and adjustment of a tempo-
rary external reference variable.
6.2 The Singly Linked List 161
the list has been accessed. The completion of the traversal is determined when
curNode becomes null, as illustrated in Figure 6.3(f). After accessing the last node
in the list, curNode is advanced to the next node, but there being no next node,
curNode is assigned None from the next field of the last node.
A correct implementation of the linked list traversal must also handle the case
where the list is empty. Remember, an empty list is indicated by a null head
reference. If the list were empty, the curNode reference would be set to null in
line 2 of Listing 6.1 and the loop would not execute producing the correct result.
A complete list traversal requires O(n) time since each node must be accessed and
each access only requires constant time.
Note the order of the two conditions in the while loop. It is important that we
test for a null curNode reference before trying to examine the contents of the node.
If the item is not found in the list, curNode will be null when the end of the list
is reached. If we try to evaluate the data field of the null reference, an exception
will be raised, resulting in a run-time error. Remember, a null reference does not
point to an object and thus there are no fields or methods to be referenced.
When implementing the search operation for the linked list, we must make
sure it works with both empty and non-empty lists. In this case, we do not need
a separate test to determine if the list is empty. This is done automatically by
checking the traversal reference variable as the loop condition. If the list were
empty, curNode would be set to None initially and the loop would never be entered.
The linked list search operation requires O(n) in the worst case, which occurs when
the target item is not in the list.
162 CHAPTER 6 Linked Structures
Suppose we want to add the value 96 to our example list shown in Figure 6.4(a).
Adding an item to the front of the list requires several steps. First, we must create
a new node to store the new value and then set its next field to point to the node
currently at the front of the list. We then adjust head to point to the new node
since it is now the first node in the list. These steps are represented as dashed lines
in Figure 6.4(b). Note the order of the new links since it is important we first link
the new node into the list before modifying the head reference. Otherwise, we lose
head
••
22 • 52
52 • 18
18 • 36
36 • 13
13 •
(a)
newNode head
•• ••
2
96
96 • 22 • 52
52 • 18
18 • 36
36 • 13
13 •
1
(b)
head
••
96
96 • 22 • 52
52 • 18
18 • 36
36 • 13
13 •
(c)
Figure 6.4: Prepending a node to the linked list: (a) the original list from Figure 6.1;
(b) link modifications required to prepend the node; and (c) the result after prepending 96.
6.2 The Singly Linked List 163
our external reference to the list and in turn, we lose the list itself. The results,
after linking the new node into the list, are shown in Figure 6.4(c).
When modifying or changing links in a linked list, we must consider the case
when the list is empty. For our implementation, the code works perfectly since the
head reference will be null when the list is empty and the first node inserted needs
the next field set to None.
head curNode
•• ••
96
96 • 22 • 52
52 • 18
18 • 36
36 • 13
13 •
(a)
head curNode
•• ••
2
96
96 • 22 • 52
52 • 18
18 • 36
36 • 13
13 •
1
(b)
Figure 6.5: Deleting a node from a linked list: (a) finding the node to be removed and
assigning an external reference variable and (b) the link modifications required to unlink
and remove a node.
Accessing the node’s successor is very simple using the next link of the node.
But we must also access the node’s predecessor in order to change its link. The
only way we can do this is to position another external reference simultaneously
during the search for the given node, as illustrated in Figure 6.6(a). The result
after removing the node containing value 18 is shown in Figure 6.6(b).
Removing the first node from the list is a special case since the head pointer
references this node. There is no predecessor that has to be relinked, but the head
reference must be adjusted to point to the next node, as illustrated in Figure 6.7.
164 CHAPTER 6 Linked Structures
1
(a)
head
••
96
96 • 22 • 52
52 • 36
36 • 13
13 •
(b)
Figure 6.6: Using a second temporary reference to remove a node from a linked list:
(a) positioning the second temporary reference variable predNode, and (b) the resulting
list after removing 18 from the linked list.
We now step through the code required for deleting a node from a singly linked
list, as illustrated in Listing 6.4. The curNode external reference is initially set to
the first node in the list, the same as is done in the traversal and search operations.
The predNode external reference is set to None since there is no predecessor to the
first node in the list.
A loop is used to position the two temporary external reference variables as
shown in lines 4–6 of Listing 6.4. As the curNode reference is moved along the list
in the body of the loop, the predNode reference follows behind. Thus, predNode
must be assigned to reference the same node as curNode before advancing curNode
to reference the next node.
After positioning the two external references, there are three possible condi-
tions: (1) the item is not in the list; (2) the item is in the first node; or (3) the
item is somewhere else in the list. If the target is not in the list, curNode will be
null, having been assigned None via the link field of the last node. This condition
is evaluated in line 8. To determine if the target is in the first node, we can simply
compare curNode to head and determine if they reference the same node. If they
do, we set head to point to the next node in the list, as shown in lines 9–10.
2
96
96 • 22 • 52
52 • 36
36 • 13
13 •
Figure 6.7: Modifications required to remove the first node of a linked list.
6.3 The Bag ADT Revisited 165
If the target is elsewhere in the list, we simply adjust the link field of the
node referenced by predNode to point to the node following the one referenced by
curNode. This step is performed in the else clause of the condition as shown in
line 12 of Listing 6.4. If the last node is being removed, the same code can be
used because the next field of the node pointed to by predNode will be set to None
since curNode will be null. Removing a node from a linked list requires O(n) time
since the node could be at the end of the list, in which case a complete traversal
is required to locate the node.
size head
44 • 19
19 •• 23 •• 74
74 •• 12 ••
Bag
within the same module. It is specified in lines 51–54 at the bottom of the module,
but it is not intended for use outside the Bag class.
The remove() method implements the removal operation as presented in the
previous section, but with a couple of modifications. The if statement that checked
the status of the curNode variable has been replaced with an assert statement.
This was necessary since the remove operation of the bag has a precondition that
the item must be in the bag in order to be removed. If we make it pass the
assertion, the item counter is decremented to reflect one less item in the bag, the
node containing the item is unlinked from the linked list, and the item is returned
as required by the ADT definition.
Table 6.1: Comparing the Bag ADT implemented using a Python list and a linked list.
168 CHAPTER 6 Linked Structures
of data do not have to be shifted as is required by the Python list. This is especially
true when prepending items. On the other hand, the Python list is a better choice
in those applications where individual elements must be accessed by index. This
can be simulated with a linked list, but it requires a traversal of the list, resulting
in a linear operation whereas the Python list only requires constant time.
Listing 6.6 An iterator for the Bag class implemented using a linked list.
When iterating over a linked list, we need only keep track of the current node
being processed and thus we use a single data field curNode in the iterator. This
reference will be advanced through the linked list as the for loop iterates over the
nodes. As was done with our Python list-based Bag class, the linked list version
must include the iter method (shown in lines 47–48 of Listing 6.5), which
returns an instance of the BagIterator class.
Figure 6.9 illustrates the Bag and BagIterator objects at the beginning of the
for loop. The curNode pointer in the BagIterator object is used just like the
curNode pointer we used when directly performing a linked list traversal earlier
in the chapter. The only difference is that we don’t include a while loop since
Python manages the iteration for us as part of the for loop. Note, the iterator
objects can be used with any singly linked list configuration to traverse the nodes
and return the data contained in each.
6.4 More Ways to Build a Linked List 169
_BagIterator
curNode
•
Bag
size head
44 • 19
19 •• 23
23 •• 74
74 •• 12
12 ••
Figure 6.9: Sample Bag and BagIterator objects at the beginning of the for loop.
head tail
•• ••
28
28 • 19
19 • 45
45 • 13 • 77 •
Figure 6.10: Sample linked list using both head and tail external references.
Appending Nodes
Adding the external tail reference to the linked list requires that we manage both
references as nodes are added and removed. Consider the process of appending a
new node to a non-empty list, as illustrated in Figure 6.11(a). First, a new node
is created to store the value to be appended to the list. Then, the node is linked
170 CHAPTER 6 Linked Structures
28
28 • 19
19 • 45
45 • 13 • 77 • 21
21 ••
1
(a)
head tail
•• ••
28
28 • 19
19 • 45
45 • 13 • 77 • 21
21 ••
(b)
Figure 6.11: Appending a node to a linked list using a tail reference: (a) the links required
to append the node, and (b) the resulting list after appending 21.
into the list following the last node. The next field of the node referenced by tail
is set to point to the new node. The tail reference has to be adjusted to point to
the new node since tail must always point to the last node in the list. The linked
list resulting from appending 21 to the list is illustrated in Figure 6.11(b).
If the list is empty, there is no existing node in which the link field can be
adjusted. Instead, both the head and tail references will be null. In this case, the
new node is appended to the list by simply adjusting both external references to
point to the new node. The code for appending a node to the linked list is provided
in Listing 6.7. It assumes the existence of both the head and tail reference variables.
1 # Given the head and tail pointers, adds an item to a linked list.
2 newNode = ListNode( item )
3 if head is None :
4 head = newNode
5 else :
6 [Link] = newNode
7 tail = newNode
Removing Nodes
Removing a node from a linked list in which both head and tail references are used
requires a simple modification to the code presented earlier in the chapter. Consider
the sample list in Figure 6.12, in which we want to delete the node containing 21.
After unlinking the node to be removed, we must check to see if it was at the end
6.4 More Ways to Build a Linked List 171
1
28 • 19 • 45
45 • 13
13 • 77 • 21
21 ••
Figure 6.12: Deleting the last node in a list using a tail reference.
of the list. If it was, we must adjust the tail reference to point to the same node
as predNode, which is now the last node in the list.
The code for removing an item from a linked list using a tail reference is shown
in Listing 6.8. If the list contains a single node, the head reference will be assigned
None when it is assigned the contents of the node’s next field. The tail reference
will also be set to None when it is set to predNode.
Listing 6.8 Removing a node from a linked list using a tail reference.
1 # Given the head and tail references, removes a target from a linked list.
2 predNode = None
3 curNode = head
4 while curNode is not None and [Link] != target :
5 predNode = curNode
6 curNode = [Link]
7
8 if curNode is not None :
9 if curNode is head :
10 head = [Link]
11 else :
12 [Link] = [Link]
13 if curNode is tail :
14 tail = predNode
head
••
22 • 13
13 • 18
18 • 36
36 • 52
52 •
Linear Search
The linear search for use with the linked list can be modified to take advantage
of the sorted items. The only change required is to add a second condition that
terminates the loop early if we encounter a value larger than the target. The search
routine for a sorted linked list is shown in Listing 6.9.
Inserting Nodes
Adding a new node to an unsorted linked list is simple because we can simply add it
to the front or end of the list since its placement is not important. When adding a
node to a sorted list, however, the correct position for the new value must be found
and the new node linked into the list at that position. The Python implementation
for inserting a value into a sorted linked list is provided in Listing 6.10.
As with the removal operation for the unsorted list, we must position two
temporary external references by traversing through the linked list searching for
the correct position of the new value. The only difference is the loop termination
condition. To insert a new node, we must terminate the loop upon finding the first
value larger than the new value being added.
1 # Given the head pointer, insert a value into a sorted linked list.
2 # Find the insertion point for the new value.
3 predNode = None
4 curNode = head
5 while curNode is not None and value > [Link] :
6 predNode = curNode
7 curNode = [Link]
8
9 # Create the new node for the new value.
10 newNode = ListNode( value )
11 [Link] = curNode
12 # Link the new node into the list.
13 if curNode is head :
14 head = newNode
15 else :
16 [Link] = newNode
6.4 More Ways to Build a Linked List 173
Three cases can occur when inserting a node into a sorted linked list, as illus-
trated in Figure 6.14: the node is inserted in the front, at the end, or somewhere
in the middle. After finding the correct position, a new node is created and its
next field is changed to point to the same node referenced by curNode. This link
is required no matter where in the list the new node is inserted. If the new node
is to be inserted in the front, then the operation is a simple prepend, as was done
with an unsorted linked list, and curNode will be pointing to the first node. When
the new value being added is the largest in the list and the new node is to be added
at the end, curNode will be null and thus the next field will be null as it should
be. When the new node is inserted elsewhere in the list, curNode will be pointing
to the node that will follow the new node.
After linking the new node to the list, we must determine if it is being inserted
at the front of the list, in which case the head reference must be adjusted. We
do this by comparing the curNode reference with the head reference. If they are
aliases, the new node comes first in the linked list and we must adjust the head
newNode head
•• ••
2
-7
-7 •• 2 • 13
13 • 18
18 • 36 • 52
52 •
1
(a)
22 • 13
13 • 18
18 • 36
36 • 52
52 •
2 1 newNode
24
24 •• ••
(b)
head predNode curNode
•• •• ••
22 • 13
13 • 18
18 • 36
36 • 52 •
newNode
•• 69
69 ••
(c)
Figure 6.14: Inserting a new value into a sorted linked list: (a) inserting -7 at the front of
the list; (b) inserting 24 in the middle of the list; (c) inserting 69 at the end of the list.
174 CHAPTER 6 Linked Structures
reference to point to the new node. If the two nodes are not aliases, then the node
is inserted by setting the next field of the node referenced by predNode to point
to the new node. This step is handled by lines 13–16 of Listing 6.10.
listOfRows 0 11 33 44 88
• • •
• col value next
numCols 1 • 00 22 • 11 11 • 66 55 •
8 MatrixElementNode
2 • 22 9 • 55 22 •
SparseMatrix
3 • 11 77 • 77 33 •
4 • 44 44 •
own variable. If the element is already a zero-entry and the new value is zero, no
action is required.
Setting the value of a matrix element requires O(n) time in the worst case,
where n is the number of columns in the matrix. This value is obtained by observing
that the most time-consuming part is the positioning of the two references, curNode
and predNode, which require a complete list traversal in the worst case. Since a
linked list contains a single row, we know it will contain at most n nodes.
45 self._listOfRows[row] = newNode
46 else :
47 [Link] = newnode
48
49 # Scales the matrix by the given scalar.
50 def scaleBy( self, scalar ):
51 for row in range( [Link]() ) :
52 curNode = self._listOfRows[row]
53 while curNode is not None :
54 [Link] *= scalar
55 curNode = [Link]
56
57 # Creates and returns a new matrix that is the transpose of this matrix.
58 def transpose( self ):
59 ......
60
61 # Matrix addition: newMatrix = self + rhsMatrix.
62 def __add__( self, rhsMartrix ) :
63 # Make sure the two matrices have the correct size.
64 assert [Link]() == [Link]() and \
65 [Link]() == [Link](), \
66 "Matrix sizes not compatable for adding."
67
68 # Create a new sparse matrix of the same size.
69 newMatrix = SparseMatrix( [Link](), [Link]() )
70
71 # Add the elements of this matrix to the new matrix.
72 for row in range( [Link]() ) :
73 curNode = self._listOfRows[row]
74 while curNode is not None :
75 newMatrix[row, [Link]] = [Link]
76 curNode = [Link]
77
78 # Add the elements of the rhsMatrix to the new matrix.
79 for row in range( [Link]() ) :
80 curNode = rhsMatrix._listOfRows[row]
81 while curNode is not None :
82 value = newMatrix[row, [Link]]
83 value += [Link]
84 newMatrix[row, [Link]] = value
85 curNode = [Link]
86
87 # Return the new matrix.
88 return newMatrix
89
90 # -- - Matrix subtraction and multiplication ---
91 # def __sub__( self, rhsMatrix ) :
92 # def __mul__( self, rhsMatrix ) :
93
94 # Storage class for creating matrix element nodes.
95 class _MatrixElementNode :
96 def __init__( self, col, value ) :
97 [Link] = col
98 [Link] = value
99 [Link] = None
178 CHAPTER 6 Linked Structures
Matrix Scaling
The scaleBy() method is very similar to the version used in the list implementa-
tion of the original Sparse Matrix ADT from Chapter 4. We need only traverse over
each of the individual linked lists stored in the listOfRows array, during which
we scale the value stored in each node. Remember, this is sufficient as elements
not represented by nodes in the linked lists have zero values and thus would not
be affected by a scaling factor. The matrix scaling operation requires O(k) time
in the worst case since only the k non-zero elements are stored in the structure.
Matrix Addition
The add method for this version of the sparse matrix, which is provided in lines
62–88 of Listing 6.11, also follows the four steps outlined in Section 4.5.1. We first
create a new SparseMatrix object that will contain the new matrix resulting from
the addition. Then, the contents of the self or lefthand-side matrix is copied to
the new matrix, one element at a time. Finally, we traverse over the non-zero
elements of the righthand-side matrix and add the values of its non-zero elements
to the new matrix.
This implementation of the addition operation, which requires O(kn) time in
the worst case, is not the most efficient. Instead of using the getitem and
setitem operations, we can use temporary traversal reference variables with
each matrix to directly access the non-zero values in the two source matrices and
to store the resulting non-zero values in the new matrix. A new implementation
can be devised that only requires O(k) time in the worst case.
Table 6.2: Comparison of the Matrix and Sparse Matrix ADT implementations.
where each ai xi component is called a term. The ai part of the term, which is a
scalar that can be zero, is called the coefficient of the term. The exponent of the
xi part is called the degree of that variable and is limited to whole numbers. For
example,
12x2 − 3x + 7
consists of three terms. The first term, 12x2 , is of degree 2 and has a coefficient
of 12; the second term, −3x, is of degree 1 and has a coefficient of −3; the last
term, while constant, is of degree 0 with a coefficient of 7.
Polynomials can be characterized by degree (i.e., all second-degree polynomi-
als). The degree of a polynomial is the largest single degree of its terms. The
example polynomial above has a degree of 2 since the degree of the first term,
12x2 , has the largest degree.
In this section, we design and implement an abstract data type to represent
polynomials in one variable expressed in expanded form. The discussion begins
with a review of polynomial operations and concludes with a linked list implemen-
tation of our Polynomial ADT.
Addition
Two polynomials of the same variable can be summed by adding the coefficients of
corresponding terms of equal degree. The result is a third polynomial. Consider
the following two polynomials:
5x2 + 3x − 10
2x3 + 4x2 + 3
which we can add to yield a new polynomial:
(5x2 + 3x − 10) + (2x3 + 4x2 + 3) = 2x3 + 9x2 + 3x − 7
Subtraction is performed in a similar fashion but the coefficients are subtracted
instead. Another way to view polynomial addition is to align terms by degree and
add the corresponding coefficients:
5x2 3x −10
+ 2x3 4x2 3
2x3 2
9x 3x −7
Multiplication
The product of two polynomials is also a third polynomial. The new polynomial is
obtained by summing the result from multiplying each term of the first polynomial
by each term of the second. Consider the two polynomials from the previous
example:
(5x2 + 3x − 10)(2x3 + 4x2 + 3)
The second polynomial has to be multiplied by each term of the first polynomial:
5x2 (2x3 + 4x2 + 3) + 3x(2x3 + 4x2 + 3) + −10(2x3 + 4x2 + 3)
We then distribute the terms of the first polynomial to yield three intermediate
polynomials:
(10x5 + 20x4 + 15x2 ) + (6x4 + 12x3 + 9x) + (−20x3 − 40x2 − 30)
Finally, the three polynomials are summed, resulting in
10x5 + 26x4 − 8x3 − 25x2 + 9x − 30
Evaluation
The easiest operation by far is the evaluation of a polynomial. Polynomials can be
evaluated by assigning a value to the variable, commonly called the unknown. By
making the variable known in specifying a value, the expression can be computed,
resulting in a real value. If we assign value 3 to the variable x in the equation
10x5 + 26x4 − 8x3 − 25x2 + 9x − 30
the result will be
10(3)5 + 26(3)4 − 8(3)3 − 25(3)2 + 9(3) − 30 = 4092
6.6 Application: Polynomials 181
containing no terms.
getitem ( degree ): Returns the coefficient for the term of the provided de-
gree. Thus, if the expression of this polynomial is x3 + 4x + 2 and a degree of
1 is provided, this operation returns 4. The coefficient cannot be returned for
an empty polynomial.
evaluate( scalar ): Evaluates the polynomial at the given scalar value and
returns the result. An empty polynomial cannot be evaluated.
subtract ( rhsPoly ): Creates and returns a new Polynomial that is the re-
sult of subtracting this polynomial and the rhsPoly. This operation is not
defined if either polynomial is empty.
multiply ( rhsPoly ): Creates and returns a new Polynomial that is the re-
sult of multiplying this polynomial and the rhsPoly. This operation is not
defined if either polynomial is empty.
Two constructors were specified for this abstract data type. Most object-
oriented languages provide a mechanism to construct an object in various ways. In
Python, we define a single constructor and supply default values for the arguments.
6.6.3 Implementation
To implement the Polynomial ADT, we must determine how best to represent
the individual terms and how to store and manage the collection of terms. In
182 CHAPTER 6 Linked Structures
earlier chapters, we were limited to the use of a list or dictionary. But with the
introduction of the linked list in this chapter, we now have an additional option.
The linked list has the advantage of requiring fewer shifts and no underlying array
management as is required with the Python list. This is especially important when
working with dynamic polynomials.
polyHead
• 2 55 •• 11 3 •• 00 -10
-10 ••
polyTail
•
Polynomial
Finally, we need to decide whether our implementation can benefit from the
use of a tail pointer or if a head pointer alone will suffice. A rule of thumb in
making this decision is whether we will be appending nodes to the list or simply
inserting them in their proper position. If you need to append nodes to a linked
list, you should use a tail pointer. The implementation of some of our polynomial
operations can be improved if we append nodes directly to the end of the linked
list. Thus, we will use and manage a tail pointer in our implementation of the
Polynomial ADT.
6.6 Application: Polynomials 183
Basic Operations
The Polynomial ADT calls for two constructors, one for creating an empty polyno-
mial and the other that can be used to create a polynomial initialized with a single
term supplied as an argument. In Python, we can provide multiple constructors
with the use of default values. The constructor, shown in lines 4–9 of Listing 6.12,
defines two data fields, the head and tail pointers, for use with the linked list im-
plementation. These references are either initialized to None or set to point to the
first node in the list depending on how the constructor was called.
The degree() method is simple to implement as it returns either the degree
of the largest term that is stored in the first node or -1 if the polynomial is not
defined. For our ADT, a polynomial is not defined if it does not contain any terms,
which is indicated in our implementation by an empty list.
The get operation, which we implement using the subscript operator, returns
the coefficient corresponding to a specific term of the polynomial identified by
degree. A linear search of the linked list is required to find the corresponding
term. Since the nodes are sorted by degree, we can terminate the search early
if we encounter a node whose degree is smaller than the target. After the loop
terminates, there are two possible conditions. If there is no non-zero term with the
given degree, then curNode will either be None or pointing to a list node whose
degree is smaller than the target. In this case, we must return a value of 0 since
by definition a zero-term has a coefficient of 0. Otherwise, we simply return the
coefficient of the corresponding term pointed to by curNode.
A polynomial is evaluated by supplying a specific value for the variable used
to represent each term and then summing the terms. The evaluate() method is
easily implemented as a list traversal in which a sum is accumulated, term by term.
The result is a O(n) time operation, where n is the degree of the polynomial.
6.6 Application: Polynomials 185
Appending Terms
We included a tail reference in our linked list implementation for use by several
of the polynomial arithmetic operations in order to perform fast append opera-
tions. While the Polynomial ADT does not define an append operation, we want
to provide a helper method that implements this operation. It will be used by
other methods in the class for creating efficient operations. The appendTerm()
helper method in lines 55–62 of Listing 6.12 accepts the degree and coefficient of
a polynomial term, creates a new node to store the term, and appends the node
to the end of the list. Since we only store the non-zero terms in the linked list, we
must ensure the supplied coefficient is not zero before creating and appending the
new node.
Polynomial Addition
The addition of two polynomials can be performed for our linked list implementa-
tion using a simple brute-force method, as illustrated in the code segment below:
class Polynomial :
# ...
def simple_add( self, rhsPoly ):
newPoly = Polynomial()
if [Link]() > [Link]() :
maxDegree = [Link]()
else
maxDegree = [Link]()
i = maxDegree
while i >= 0 :
value = self[i] + rhsPoly[i]
self._appendTerm( i, value )
i += 1
return newPoly
The new polynomial is created by iterating over the two original polynomials,
term by term, from the largest degree among the two polynomials down to degree 0.
The element access method is used to extract the coefficients of corresponding
terms from each polynomial, which are then added, resulting in a term for the
new polynomial. Since we iterate over the polynomials in decreasing degree order,
we can simply append the new term to the end of the linked list storing the new
polynomial.
This implementation is rather simple, but it’s not very efficient. The element
access method, which is used to obtain the coefficients, requires O(n) time. Assum-
ing the largest degree between the two polynomials is n, the loop will be executed
n times, resulting in quadratic time in the worst case.
The polynomial addition operation can be greatly improved. Upon close ex-
amination it becomes clear this problem is similar to that of merging two sorted
186 CHAPTER 6 Linked Structures
lists. Consider the linked lists in Figure 6.17 representing three polynomials with
the nodes positioned such that corresponding terms are aligned. The top two lists
represent the two polynomials 5x2 + 3x − 10 and 2x3 + 4x2 + 3 while the bottom
list is the polynomial resulting from adding the other two.
listA
• polyHead
• 22 55 •• 11 33 •• 00 -10
-10 ••
polyTail
•
listB
• polyHead
• 33 22 •• 22 44 •• 00 33 ••
polyTail
•
merged
• polyHead
• 33 22 •• 22 99 •• 11 33 •• 00 -7
-7 ••
polyTail
•
Figure 6.17: The top two linked lists store the two polynomials 5x2 + 3x − 10 and
2x3 + 4x2 + 3. The bottom list is the resulting polynomial after adding the two origi-
nal polynomials.
1 class Polynomial :
2 # ...
3 def __add__( self, rhsPoly ):
4 assert [Link]() >= 0 and [Link]() >= 0,
5 "Addition only allowed on non-empty polynomials."
6
7 newPoly = Polynomial()
8 nodeA = self._termList
9 nodeB = rhsPoly._termList
10
11 # Add corresponding terms until one list is empty.
12 while nodeA is not None and nodeB is not None :
13 if [Link] > [Link] :
14 degree = [Link]
15 value = [Link]
16 nodeA = [Link]