SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:PROF.

AJAY PASHANKAR
SYLLABUS

UNIT I

Algorithm analysis

Problem, size of problem (symbol n); runtime resources time T(n), space S(n); worst case,
best case, average case. Measuring running time as a function of n with the wall clock
(using function time() of module time); advantages and disadvantages.

7 standard functions: constant c, log n, n, n log n, n2, n3, exponential cn or 2n; growth
of these functions as n grows: for constants c1 and c2, compare c1 * f1(n) with c2 * f2(n)
(for functions f1 and f2 from the set of these 7 functions); conclude that one function grows
faster than another independent of the values of the constants.

Operation count, unit steps (constant time): arithmetic operation (or expression
evaluation or assignment), comparison (with Boolean operators <, ==, >) function call
and/or function return, element access (for compound types); can even treat a single loop
iteration as a constant-time unit step.

Asymptotic analysis: upper bounds with A (at most) and O notation; lower bounds with Ω

Problem-solving methods: greedy method, divide-and-conquer, dynamic programming

(briefly, during all 3 units)

Abstract data types (with associated operations and applications) Define the ADTs as
Python classes, and their operations as class methods.

(i) stacks: operations push(), pop(), is_empty(); stacktop(), len() implementation using
lists; applications: reverse a sequence, match parentheses in an expression (or html tags);
evaluate a postfix expression.

Unit II

(ii) queues: operations enqueue() and dequeue(), i.e., enter() and exit(), is_empty(),
first(), last()); implementation using Python lists; applications: simulation of a single-
window queue (uniform, Gaussian and other distributions are available in the Python
module random).

(iii) Singly, doubly and circularly linked lists, with head and optional tail; implementation of
list nodes as Python objects; operations: insertion and deletion at the front and the rear of
the list, search for a value in a list, delete a value in a list; applications: simulate stack and
queue, maintain a set of data in sorted order. Linear search in linked lists.

(iv) trees and binary trees, definitions and properties; insertion and deletion of a tree node

Unit III

(v) trees and binary trees, implementation of binary trees in lists and in linked structures;
applications: preorder, inorder and postorder traversals of binary trees; binary search trees;
breadth-first and depth-first tree traversals.

Page 1 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR
(vi) graphs: directed and undirected graphs; implementation using adjacency matrix and
adjacency list; graph traversal algorithms: depth first and breadth first traversals,
application: shortest paths

(vii) map ADT, Python classes dictionary and set; applications.

Textbook(s):

1) Data Structures and Algorithms in Python, Goodrich, Tamassia, Goldwasser,

2016 J. Wiley
2) Data Structures and Algorithms Using Python - Rance D. Necaise, College of
William and Mary, 2016, J. Wiley

Reference(s)
1) Data Structure and Algorithmic Thinking with Python- Narasimha Karumanchi,
2015, Careermonk Publications
2) Fundamentals of Python: Data Structures, Kenneth Lambert, Delmar Cengage
Learning

SR. NO CHAPTER NAME PAGE NUMBER

1 ALGORITHM ANALYSIS 3-7

2 STANDARD FUNCTIONS 8-15

3 ASYMPTOTIC ANALYSIS: 16-32

4 ABSTRACT DATA TYPES(ADT) 33-52

Page 2 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR
CHAPTER 1: ALGORITHM ANALYSIS

TOPIC COVERED: Problem, size of problem (symbol n); runtime resources time T(n), space
S(n); worst case, best case, average case. Measuring running time as a function of n with
the wall clock (using function time() of module time); advantages and disadvantages.

Experimental Studies

If an algorithm has been implemented, we can study its running time by executing
it on various test inputs and recording the time spent during each execution.
A simple approach for doing this in Python is by using the time function of the time module.
This function reports the number of seconds, or fractions thereof, that have elapsed since a
benchmark time known as the epoch. The choice of the epoch is not significant to our goal,
as we can determine the elapsed time by recording the time just before the algorithm and
the time just after the algorithm, and computing their difference, as follows:
from time import time
start time = time( ) # record the starting time
run algorithm
end time = time( ) # record the ending time
elapsed = end time − start time # compute the elapsed time
We will demonstrate use of this approach, in Chapter 5, to gather experimental data on the
efficiency of Python’s list class. An elapsed time measured in this fashion is a decent
reflection of the algorithm efficiency, but it is by no means perfect.
The time function measures relative to what is known as the “wall clock.” Because many
processes share use of a computer’s central processing unit (or CPU), the elapsed time
will depend on what other processes are running on the computer when the test is
performed. A fairer metric is the number of CPU cycles that are used by the algorithm. This
can be determined using the clock function of the time module, but even this measure
might not be consistent if repeating the identical algorithm on the identical input, and its
granularity will depend upon the computer system. Python includes a more advanced
module, named timeit, to help automate such evaluations with repetition to account for
such variance among trials.
Because we are interested in the general dependence of running time on the size and
structure of the input, we should perform independent experiments on many different test
inputs of various sizes. We can then visualize the results by plotting the performance of
each run of the algorithm as a point with x-coordinate equal to the input size, n, and y-
coordinate equal to the running time, t. Figure 3.1 displays such hypothetical data. This
visualization may provide some intuition regarding the relationship between problem size
and execution time for the algorithm. This may lead to a statistical analysis that seeks to fit
the best function of the input size to the experimental data. To be meaningful, this analysis
requires that we choose good sample inputs and test enough of them to be able to make
sound statistical claims about the algorithm’s running time.

Page 3 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR

Figure 3.1: Results of an experimental study on the running time of an algorithm.

A dot with coordinates (n, t) indicates that on an input of size n, the running time

of the algorithm was measured as t milliseconds (ms).

Challenges of Experimental Analysis

While experimental studies of running times are valuable, especially when finetuning

production-quality code, there are three major limitations to their use for algorithm
analysis:

• Experimental running times of two algorithms are difficult to directly compare unless
the experiments are performed in the same hardware and software environments.
• Experiments can be done only on a limited set of test inputs; hence, they leave out
the running times of inputs not included in the experiment (and these inputs may be
important).
• An algorithm must be fully implemented in order to execute it to study its running
time experimentally.

This last requirement is the most serious drawback to the use of experimental studies.

At early stages of design, when considering a choice of data structures or algorithms, it

would be foolish to spend a significant amount of time implementing an approach that could
easily be deemed inferior by a higher-level analysis.

Page 4 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR
Moving Beyond Experimental Analysis

Our goal is to develop an approach to analyzing the efficiency of algorithms that:

1. Allows us to evaluate the relative efficiency of any two algorithms in a way

that is independent of the hardware and software environment.
2. Is performed by studying a high-level description of the algorithm without
need for implementation.
3. Takes into account all possible inputs.

Counting Primitive Operations

To analyze the running time of an algorithm without performing experiments, we

perform an analysis directly on a high-level description of the algorithm (either in

the form of an actual code fragment, or language-independent pseudo-code). We

define a set of primitive operations such as the following:

• Assigning an identifier to an object

• Determining the object associated with an identifier
• Performing an arithmetic operation (for example, adding two numbers)
• Comparing two numbers
• Accessing a single element of a Python list by index
• Calling a function (excluding operations executed within the function)
• Returning from a function.

Formally, a primitive operation corresponds to a low-level instruction with an execution

time that is constant. Ideally, this might be the type of basic operation that is

executed by the hardware, although many of our primitive operations may be translated

to a small number of instructions. Instead of trying to determine the specific

execution time of each primitive operation, we will simply count how many primitive

operations are executed, and use this number t as a measure of the running

time of the algorithm.

This operation count will correlate to an actual running time in a specific computer,

for each primitive operation corresponds to a constant number of instructions,

and there are only a fixed number of primitive operations. The implicit assumption

in this approach is that the running times of different primitive operations will be

fairly similar. Thus, the number, t, of primitive operations an algorithm performs

will be proportional to the actual running time of that algorithm.

Measuring Operations as a Function of Input Size

Page 5 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR
To capture the order of growth of an algorithm’s running time, we will associate,

with each algorithm, a function f (n) that characterizes the number of primitive

operations that are performed as a function of the input size n. Section 3.2 will introduce

the seven most common functions that arise, and Section 3.3 will introduce

a mathematical framework for comparing functions to each other.

Focusing on the Worst-Case Input

An algorithm may run faster on some inputs than it does on others of the same size.

Thus, we may wish to express the running time of an algorithm as the function of

the input size obtained by taking the average over all possible inputs of the same

size. Unfortunately, such an average-case analysis is typically quite challenging.

It requires us to define a probability distribution on the set of inputs, which is often

a difficult task. Figure 3.2 schematically shows how, depending on the input distribution,

the running time of an algorithm can be anywhere between the worst-case

time and the best-case time. For example, what if inputs are really only of types

“A” or “D”?

An average-case analysis usually requires that we calculate expected running

times based on a given input distribution, which usually involves sophisticated

probability theory. Therefore, for the remainder of this book, unless we specify

otherwise, we will characterize running times in terms of the worst case, as a function

of the input size, n, of the algorithm.

Worst-case analysis is much easier than average-case analysis, as it requires

only the ability to identify the worst-case input, which is often simple. Also, this

approach typically leads to better algorithms. Making the standard of success for an

algorithm to perform well in the worst case necessarily requires that it will do well

on every input. That is, designing for the worst case leads to stronger algorithmic

“muscles,” much like a track star who always practices by running up an incline.

Page 6 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR

Page 7 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR
CHAPTER 2: STANDARD FUNCTIONS:

The Seven Functions Used in This Book

In this section, we briefly discuss the seven most important functions used in the

analysis of algorithms. We will use only these seven simple functions for almost

all the analysis we do in this book. In fact, a section that uses a function other

than one of these seven will be marked with a star (_) to indicate that it is optional.

In addition to these seven fundamental functions, Appendix B contains a list of

other useful mathematical facts that apply in the analysis of data structures and

algorithms.

The Constant Function

The simplest function we can think of is the constant function. This is the function,

f (n) = c,

for some fixed constant c, such as c = 5, c = 27, or c = 210. That is, for any

argument n, the constant function f (n) assigns the value c. In other words, it does

not matter what the value of n is; f (n) will always be equal to the constant value c.

Because we are most interested in integer functions, the most fundamental constant

function is g(n) = 1, and this is the typical constant function we use in this

book. Note that any other constant function, f (n) = c, can be written as a constant

c times g(n). That is, f (n) = cg(n) in this case.

As simple as it is, the constant function is useful in algorithm analysis, because

it characterizes the number of steps needed to do a basic operation on a computer,

like adding two numbers, assigning a value to some variable, or comparing two

numbers.

The Logarithm Function

One of the interesting and sometimes even surprising aspects of the analysis of

data structures and algorithms is the ubiquitous presence of the logarithm function,

f (n) = logb n, for some constant b > 1. This function is defined as follows:

x = logb n if and only if bx = n.

By definition, logb 1 = 0. The value b is known as the base of the logarithm.

Page 8 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR
The most common base for the logarithm function in computer science is 2,

as computers store integers in binary, and because a common operation in many

algorithms is to repeatedly divide an input in half. In fact, this base is so common

that we will typically omit it from the notation when it is 2. That is, for us,

log n = log2 n.

We note that most handheld calculators have a button marked LOG, but this is
typically for calculating the logarithm base-10, not base-two.
Computing the logarithm function exactly for any integer n involves the use
of calculus, but we can use an approximation that is good enough for our purposes
without calculus. In particular, we can easily compute the smallest integer
greater than or equal to logb n (its so-called ceiling, logb n_). For positive integer,
n, this value is equal to the number of times we can divide n by b before we get
a number less than or equal to 1. For example, the evaluation of log3 27_ is 3,
because ((27/3)/3)/3 = 1. Likewise, log4 64_ is 3, because ((64/4)/4)/4 = 1,
and log2 12_ is 4, because (((12/2)/2)/2)/2 = 0.75 ≤ 1.
The following proposition describes several important identities that involve
logarithms for any base greater than 1.
Proposition 3.1 (Logarithm Rules): Given real numbers a > 0, b > 1, c > 0
and d > 1, we have:
1. logb(ac) = logb a+logb c
2. logb(a/c) = logb a−logb c
3. logb(ac) = clogb a
4. logb a = logd a/logd b
5. blogd a = alogd b
By convention, the unparenthesized notation lognc denotes the value log(nc).
We use a notational shorthand, logc n, to denote the quantity, (log n)c, in which the
result of the logarithm is raised to a power.
The above identities can be derived from converse rules for exponentiation that
we will present on page 121. We illustrate these identities with a few examples.
Example 3.2: We demonstrate below some interesting applications of the logarithm
rules from Proposition 3.1 (using the usual convention that the base of a
logarithm is 2 if it is omitted).
• log(2n) = log2+logn = 1+logn, by rule 1
• log(n/2) = log n−log2 = logn−1, by rule 2
• log n3 = 3logn, by rule 3
• log 2n = nlog 2 = n · 1 = n, by rule 3
• log4 n = (log n)/log 4 = (log n)/2, by rule 4
• 2log n = nlog 2 = n1 = n, by rule 5.
As a practical matter, we note that rule 4 gives us a way to compute the base-two
logarithm on a calculator that has a base-10 logarithm button, LOG, for
log2 n = LOG n/LOG 2.

The Linear Function

Another simple yet important function is the linear function,
f (n) = n.
That is, given an input value n, the linear function f assigns the value n itself.
This function arises in algorithm analysis any time we have to do a single basic
operation for each of n elements. For example, comparing a number x to each
element of a sequence of size n will require n comparisons. The linear function
also represents the best running time we can hope to achieve for any algorithm that
processes each of n objects that are not already in the computer’s memory, because

Page 9 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR
reading in the n objects already requires n operations.

The N-Log-N Function

The next function we discuss in this section is the n-log-n function,
f (n) = nlog n,
that is, the function that assigns to an input n the value of n times the logarithm
base-two of n. This function grows a little more rapidly than the linear function and
a lot less rapidly than the quadratic function; therefore, we would greatly prefer an
algorithm with a running time that is proportional to nlog n, than one with quadratic
running time. We will see several important algorithms that exhibit a running time
proportional to the n-log-n function. For example, the fastest possible algorithms
for sorting n arbitrary values require time proportional to nlog n.

The Quadratic Function

Another function that appears often in algorithm analysis is the quadratic function,
f (n) = n2.
That is, given an input value n, the function f assigns the product of n with itself
(in other words, “n squared”).
The main reason why the quadratic function appears in the analysis of algorithms
is that there are many algorithms that have nested loops, where the inner
loop performs a linear number of operations and the outer loop is performed a
linear number of times. Thus, in such cases, the algorithm performs n · n = n2
operations.

Nested Loops and the Quadratic Function

The quadratic function can also arise in the context of nested loops where the first
iteration of a loop uses one operation, the second uses two operations, the third uses
three operations, and so on. That is, the number of operations is
1+2+3+· · ·+(n−2)+(n−1)+n.
In other words, this is the total number of operations that will be performed by the
nested loop if the number of operations performed inside the loop increases by one
with each iteration of the outer loop. This quantity also has an interesting history.
In 1787, a German schoolteacher decided to keep his 9- and 10-year-old pupils
occupied by adding up the integers from 1 to 100. But almost immediately one
of the children claimed to have the answer! The teacher was suspicious, for the
student had only the answer on his slate. But the answer, 5050, was correct and the
student, Carl Gauss, grew up to be one of the greatest mathematicians of his time.
We presume that young Gauss used the following identity.

Page 10 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR

Figure 3.3: Visual justifications of Proposition 3.3. Both illustrations visualize the

identity in terms of the total area covered by n unit-width rectangles with heights

1,2, . . . ,n. In (a), the rectangles are shown to cover a big triangle of area n2/2
(base

n and height n) plus n small triangles of area 1/2 each (base 1 and height 1). In

(b), which applies only when n is even, the rectangles are shown to cover a big

rectangle of base n/2 and height n+1.

The lesson to be learned from Proposition 3.3 is that if we perform an algorithm

with nested loops such that the operations in the inner loop increase by one each

time, then the total number of operations is quadratic in the number of times, n,

we perform the outer loop. To be fair, the number of operations is n2/2 + n/2,

and so this is just over half the number of operations than an algorithm that uses n

operations each time the inner loop is performed. But the order of growth is still

quadratic in n.

The Cubic Function and Other Polynomials

Page 11 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR
Continuing our discussion of functions that are powers of the input, we consider

the cubic function,

f (n) = n3,

which assigns to an input value n the product of n with itself three times. This
function

appears less frequently in the context of algorithm analysis than the constant,

linear, and quadratic functions previously mentioned, but it does appear from time

to time.

Polynomials

Most of the functions we have listed so far can each be viewed as being part of a

larger class of functions, the polynomials. A polynomial function has the form,

f (n) = a0+a1n+a2n2+a3n3 +· · ·+adnd,

where a0,a1, . . . ,ad are constants, called the coefficients of the polynomial, and

ad _= 0. Integer d, which indicates the highest power in the polynomial, is called

the degree of the polynomial.

For example, the following functions are all polynomials:

• f (n) = 2+5n+n2

• f (n) = 1+n3

• f (n) = 1

• f (n) = n

• f (n) = n2

Therefore, we could argue that this book presents just four important functions
used

in algorithm analysis, but we will stick to saying that there are seven, since the
constant,

linear, and quadratic functions are too important to be lumped in with other

polynomials. Running times that are polynomials with small degree are generally

better than polynomial running times with larger degree.

Page 12 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR
Summations

A notation that appears again and again in the analysis of data structures and
algorithms

is the summation, which is defined as follows:

i=a

f (i) = f (a)+ f (a+1)+ f (a+2)+· · ·+ f (b),

where a and b are integers and a ≤ b. Summations arise in data structure and
algorithm

analysis because the running times of loops naturally give rise to summations.

Using a summation, we can rewrite the formula of Proposition 3.3 as

i=1

i=

n(n+1)

Likewise, we can write a polynomial f (n) of degree d with coefficients a0, . . . ,ad
as

f (n) =

i=0

aini.

Thus, the summation notation gives us a shorthand way of expressing sums of

increasing

terms that have a regular structure.

Page 13 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR
The Exponential Function

Another function used in the analysis of algorithms is the exponential function,

f (n) = bn,

where b is a positive constant, called the base, and the argument n is the
exponent.

That is, function f (n) assigns to the input argument n the value obtained by
multiplying

the base b by itself n times. As was the case with the logarithm function,

the most common base for the exponential function in algorithm analysis is b = 2.

For example, an integer word containing n bits can represent all the nonnegative

integers less than 2n. If we have a loop that starts by performing one operation

and then doubles the number of operations performed with each iteration, then the

number of operations performed in the nth iteration is 2n.

We sometimes have other exponents besides n, however; hence, it is useful

for us to know a few handy rules for working with exponents. In particular, the

following exponent rules are quite helpful.

3.2.1 Comparing Growth Rates

To sum up, Table 3.1 shows, in order, each of the seven common functions used in

algorithm analysis.

Ideally, we would like data structure operations to run in times proportional

to the constant or logarithm function, and we would like our algorithms to run in

linear or n-log-n time. Algorithms with quadratic or cubic running times are less

practical, and algorithms with exponential running times are infeasible for all but

the smallest sized inputs. Plots of the seven functions are shown in Figure 3.4.

Page 14 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR

The Ceiling and Floor Functions

One additional comment concerning the functions above is in order. When

discussing logarithms, we noted that the value is generally not an integer, yet the
running time of an algorithm is usually expressed by means of an integer quantity,

such as the number of operations performed. Thus, the analysis of an algorithm

may sometimes involve the use of the floor function and ceiling function, which
are defined respectively as follows:

Page 15 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR

CHAPTER 3: ASYMPTOTIC ANALYSIS:

In algorithm analysis, we focus on the growth rate of the running time as a function
of the input size n, taking a “big-picture” approach. For example, it is often enough
just to know that the running time of an algorithm grows proportionally to n.
We analyze algorithms using a mathematical notation for functions that disregards
constant factors. Namely, we characterize the running times of algorithms
by using functions that map the size of the input, n, to values that correspond to
the main factor that determines the growth rate in terms of n. This approach reflects
that each basic step in a pseudo-code description or a high-level language
implementation may correspond to a small number of primitive operations. Thus,
we can perform an analysis of an algorithm by estimating the number of primitive
operations executed up to a constant factor, rather than getting bogged down in
language-specific or hardware-specific analysis of the exact number of operations
that execute on the computer.
As a tangible example, we revisit the goal of finding the largest element of a
Python list; we first used this example when introducing for loops on page 21 of
Section 1.4.2. Code Fragment 3.1 presents a function named find max for this task.

This is a classic example of an algorithm with a running time that grows proportional to n,
as the loop executes once for each data element, with some fixed number of primitive
operations executing for each pass. In the remainder of this section, we provide a
framework to formalize this claim.

Big-O Notation

Instead of counting the precise number of operations or steps, computer scientists are more
interested in classifying an algorithm based on the order of magnitude as applied to
execution time or space requirements. This classification approximates the actual number of
required steps for execution or the actual storage requirements in terms of variable-sized
data sets. The term big-O, which is de-rived from the expression \on the order of," is used
to specify an algorithm's classification.

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

Page 16 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR

Now, suppose there exists a function f(n) defined for the integers n _ 0, such that

for some constant c, and some constant m,

for all sufficiently large values of . 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 The 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

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

for a result of O(n2). For version two, we computed a time of T2(n) = n2 + n.

Again, if we let c = 2, then

for a result of O(n2). In this case, the choice of c comes from the observation that

, which satisfies the equation in

the definition of big-O.

Page 17 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR

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

Page 18 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR

operations required by an algorithm can be computed as a sum of the times required

to perform each step:

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.

Page 19 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR

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.

Page 20 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR
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

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

Page 21 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR
computer science a will typically equal 2 and thus we use the notation 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

are characterized by a time-complexity of O(nm) since the dominant term is the highest
power of n. The most common polynomial algorithms are linear (m = 1), quadratic (m = 2),
and cubic (m = 3). An algorithm whose efficiency is characterized by a dominant term in the
form an is called exponential. Exponential algorithms are among the worst algorithms in
terms of time-complexity.

The “Big-Oh” Notation(Extra part refer its required)

Let f (n) and g(n) be functions mapping positive integers to positive real numbers.

We say that f (n) is O(g(n)) if there is a real constant c > 0 and an integer constant

n0 ≥ 1 such that

f (n) ≤ cg(n), for n ≥ n0.

This definition is often referred to as the “big-Oh” notation, for it is sometimes pronounced

as “ f (n) is big-Oh of g(n).” Figure 3.5 illustrates the general definition.

Example 3.6: The function 8n+5 is O(n).

Justification: By the big-Oh definition, we need to find a real constant c>0 and

an integer constant n0 ≥ 1 such that 8n+5 ≤ cn for every integer n ≥ n0. It is easy

to see that a possible choice is c = 9 and n0 = 5. Indeed, this is one of infinitely

many choices available because there is a trade-off between c and n0. For example,

Page 22 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR
we could rely on constants c = 13 and n0 = 1.

The big-Oh notation allows us to say that a function f (n) is “less than or equal

to” another function g(n) up to a constant factor and in the asymptotic sense as n

grows toward infinity. This ability comes from the fact that the definition uses “≤”

to compare f (n) to a g(n) times a constant, c, for the asymptotic cases when n≥n0.

However, it is considered poor taste to say “ f (n) ≤ O(g(n)),” since the big-Oh

already denotes the “less-than-or-equal-to” concept. Likewise, although common,

it is not fully correct to say “ f (n) = O(g(n)),” with the usual understanding of the

“=” relation, because there is no way to make sense of the symmetric statement,

“O(g(n)) = f (n).” It is best to say, “ f (n) is O(g(n)).”

Alternatively, we can say “ f (n) is order of g(n).” For the more mathematically inclined, it
is also correct to say, “ f (n) ∈ O(g(n)),” for the big-Oh notation, technically speaking,
denotes a whole collection of functions. In this book, we will stick to presenting big-Oh
statements as “ f (n) is O(g(n)).” Even with this interpretation, there is considerable
freedom in how we can use arithmetic operations with the big- Oh notation, and with this
freedom comes a certain amount of responsibility.

Characterizing Running Times Using the Big-Oh Notation

The big-Oh notation is used widely to characterize running times and space bounds in terms
of some parameter n, which varies from problem to problem, but is always defined as a
chosen measure of the “size” of the problem. For example, if we are interested in finding
the largest element in a sequence, as with the find max algorithm, we should let n denote
the number of elements in that collection. Using the big-Oh notation, we can write the
following mathematically precise statement on the running time of algorithm find max (Code
Fragment 3.1) for any computer.

Proposition 3.7: The algorithm, find max, for computing the maximum element of a list of n
numbers, runs in O(n) time.

Justification: The initialization before the loop begins requires only a constant number of
primitive operations. Each iteration of the loop also requires only a constant number of
primitive operations, and the loop executes n times. Therefore, we account for the number
of primitive operations being c_ +c__ · n for appropriate constants c_ and c__ that reflect,
respectively, the work performed during initialization and the loop body. Because each
primitive operation runs in constant time, we have that the running time of algorithm find
max on an input of size n is at most a constant times n; that is, we conclude that the
running time of algorithm find max is O(n).

Some Properties of the Big-Oh Notation

The big-Oh notation allows us to ignore constant factors and lower-order terms and focus on
the main components of a function that affect its growth.

Page 23 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR
Example 3.8: 5n4 +3n3+2n2 +4n+1 is O(n4).

Justification: Note that 5n4+3n3+2n2+4n+1≤ (5+3+2+4+1)n4 = cn4, for c = 15, when n

≥ n0 = 1.

In fact, we can characterize the growth rate of any polynomial function.

Proposition 3.9: If f (n) is a polynomial of degree d, that is,

Justification: Note that, for n ≥ 1, we have 1 ≤ n ≤ n2 ≤ · · · ≤ nd; hence,

We show that f (n) is O(nd) by defining c = |a0|+|a1|+· · ·+|ad| and n0 = 1.

Complexity Analysis

To determine the efficiency of an algorithm, we can examine the solution itself and

measure those aspects of the algorithm that most critically affect its execution time.

For example, we can count the number of logical comparisons, data interchanges,

or arithmetic operations. Consider the following algorithm for computing the sum

of each row of an n x n matrix and an overall sum of the entire matrix:

Suppose we want to analyze the algorithm based on the number of additions performed. In
this example, there are only two addition operations, making this a simple task. The
algorithm contains two loops, one nested inside the other. The inner loop is executed n
times and since it contains the two addition operations, there are a total of 2n additions
performed by the inner loop for each iteration of the outer loop. The outer loop is also
performed n times, for a total of 2n2 additions.
Can we improve upon this algorithm to reduce the total number of addition operations
performed? Consider a new version of the algorithm in which the second addition is moved
out of the inner loop and modified to sum the entries in the rowSum array instead of
individual elements of the matrix.

Page 24 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR

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 results for any n greater than 1. Thus, the second version will
execute faster than the results, but the difference in execution times will not be significant.
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 approximately the
same rate (though one is slightly better), as illustrated numerically in
Table 4.1 and graphically in Figure 4.1.

4.1.2 Evaluating Python Code

As indicated earlier, when evaluating the time complexity of an algorithm or code segment,
we assume that basic operations only require constant time. But what exactly is a basic
operation? The basic operations include statements and function calls whose execution time
does not depend on the special c values of the data that is used or manipulated by the
given instruction. For example, the assignment statement x = 5 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

Page 25 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR
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.

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 mechanism 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:

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).

Page 26 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR

Quadratic Time Examples

When presented with nested loops, such as in the following, the time required by

the inner loop impacts the time of the outer loop.

Linear Time Examples

Now, consider the following assignment statement:

y = ex1(n)

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 right-hand 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

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:

Page 27 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR
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 iteration 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:

T(n) = n(n + 1)

2= n2 + n2

which results in a quadratic time of O(n2).

Page 28 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR
Logarithmic Time Examples

The next example contains a single loop, but notices the change to the modification

step. Instead of incrementing (or decrementing) by one, it cuts the loop variable

in half each time through the loop.

def ex6( n ):

count = 0

i=n

while i >= 1 :

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 _ve 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

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 = log a 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

Page 29 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR
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

4.2 Evaluating the Python List

We defined several abstract data types for storing and using collections of data in
the previous chapters. The next logical step is to analyze the operations of the
various ADTs to determine their efficiency. The result of this analysis depends on
the efficiency of the Python list since it was the primary data structure used to
implement many of the earlier abstract data types.
The implementation details of the list were discussed in Chapter 2. In this
section, we use those details and evaluate the efficiency of some of the more common
operations. A summary of the worst case run times are shown in Table 4.4.

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:

Page 30 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR
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 iterations. 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

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.

Page 31 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR
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.

Inserting and Removing Items

Inserting a new item into a list is very similar to appending an item except the new

item can be placed anywhere within the list, possibly requiring a shift in elements.

An item can be removed from any element within a list, which may also involve

shifting elements. Both of these operations require linear time in the worst case,

the proof of which is left as an exercise.

Page 32 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR
CHAPTER 4: ABSTRACT DATA TYPES(ADT)

Abstract Data Types

An abstract data type (or ADT) is a programmer-defined data type that specifies a set of
data values and a collection of well-defined operations that can be
performed on those values. Abstract data types are defined independent of their

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 interaction 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 abstraction 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 implementations 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 where it was not intended. This type of logical

Page 33 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR
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, allowing 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 previous 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.

What is data structure?

Using the ADT

To illustrate the use of the Date ADT, consider the program in Listing 1.1, which processes a
collection of birth dates. The dates are extracted from standard input and examined. Those
dates that indicate the individual is at least 21 years of age based on a target date are
printed to standard output. The user is continuously prompted to enter a birth date until
zero is entered for the month.

This simple example illustrates an advantage of working with an abstraction by focusing on

what functionality the ADT provides instead of how that functionality is implemented. By
hiding the implementation details, we can use an ADT independent of its implementation. In
fact, the choice of implementation for the Date ADT will have no effect on the instructions in
our example program.

Page 34 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR

Preconditions and Postconditions

In defining the operations, we must include a specification of required inputs and

the resulting output, if any. In addition, we must specify the preconditions and
postconditions for each operation. A precondition indicates the condition or
state of the ADT instance and inputs before the operation can be performed. A
postcondition indicates the result or ending state of the ADT instance after the
operation is performed. The precondition is assumed to be true while the post condition is a
guarantee as long as the preconditions are met. Attempting to perform
an operation in which the precondition is not satisfied should be agged as an error. Consider
the use of the pop(i) method for removing a value from a list. When this method is called,
the precondition states the supplied index must be within the legal range. Upon successful
completion of the operation, the post condition guarantees the item has been removed from
the list. If an invalid index, one that is out of the legal range, is passed to the pop()
method, an exception is raised. All operations have at least one precondition, which is that
the ADT instance
has to have been previously initialized. In an object-oriented language, this pre-
condition is automatically verified since an object must be created and initialized

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

Page 35 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR
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 program. 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 implementation 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.

Implementing the ADT

After defining the ADT, we need to provide an implementation in an appropriate
language. In our case, we will always use Python and class definitions, but any
programming language could be used. A partial implementation of the Date class is
provided in Listing 1.2, with the implementation of some methods left as exercises.

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 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.

Page 36 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR

Page 37 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR

STACKS:

A stack is a collection of objects that are inserted and removed according to the last-in,
first-out (LIFO) principle.
A user may insert objects into a stack at any time, but may only access or remove the
most recently inserted object that remains (at the so-called “top” of the stack). The name
“stack” is derived from the metaphor of a stack of plates in a spring-loaded, cafeteria
plate dispenser. In this case, the fundamental operations involve the “pushing” and
“popping” of plates on the stack.
When we need a new plate from the dispenser, we “pop” the top plate off the stack,
and when we add a plate, we “push” it down on the stack to become the new top
plate. Perhaps an even more amusing example is a PEZ® candy dispenser, which
stores mint candies in a spring-loaded container that “pops” out the topmost candy
in the stack when the top of the dispenser is lifted (see Figure 6.1). Stacks are
a fundamental data structure. They are used in many applications, including the
following.
Example 6.1: Internet Web browsers store the addresses of recently visited sites
in a stack. Each time a user visits a new site, that site’s address is “pushed” onto the
stack of addresses. The browser then allows the user to “pop” back to previously
visited sites using the “back” button.
Example 6.2: Text editors usually provide an “undo” mechanism that cancels recent
editing operations and reverts to former states of a document. This undo operation
can be accomplished by keeping text changes in a stack.

Page 38 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR

6.1.1 The Stack Abstract Data Type

Stacks are the simplest of all data structures, yet they are also among the most
important. They are used in a host of different applications, and as a tool for many
more sophisticated data structures and algorithms. Formally, a stack is an abstract
data type (ADT) such that an instance S supports the following two methods:

[Link](e): Add element e to the top of stack S.

[Link](): Remove and return the top element from the stack S;
an error occurs if the stack is empty.
Additionally, let us define the following accessor methods for convenience:
[Link](): Return a reference to the top element of stack S, without removing it; an error
occurs if the stack is empty.
[Link] empty( ): Return True if stack S does not contain any elements.
len(S): Return the number of elements in stack S; in Python, we implement this with the
special method len .
By convention, we assume that a newly created stack is empty, and that there is no
a priori bound on the capacity of the stack. Elements added to the stack can have
arbitrary type.

Example 6.3: The following table shows a series of stack operations and their effects on
an initially empty stack S of integers.

Page 39 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR

The Stack ADT

A stack is used to store data such that the last item inserted is the first item removed. It is
used to implement a last-in first-out (LIFO) type protocol. The stack is a linear data
structure in which new items are added, or existing items are removed from the same end,
commonly referred to as the top of the stack. The opposite end is known as the base.
Consider the example in Figure 7.1, which

illustrates new values being added to the top of the stack and one value being
removed from the top.

Page 40 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR

To illustrate a simple use of the Stack ADT, we apply it to the problem of

reversing a list of integer values. The values will be extracted from the user until a
negative value is entered, which ags the end of the collection. The values will then
be printed in reverse order from how they were entered. We could use a simple list
for this problem, but a stack is ideal since the values can be pushed onto the stack
as they are entered and then popped one at a time to print them in reverse order.
A solution for this problem follows.
PROMPT = "Enter an int value (<0 to end):"
myStack = Stack()
value = int(input( PROMPT ))
while value >= 0 :
[Link]( value )
value = int(input( PROMPT ))
while not [Link]() :
value = [Link]()
print( value )
Suppose the user enters the following values, one at a time:
7 13 45 19 28 -1

When the outer while loop terminates after the negative value is extracted, the
contents of the stack will be as illustrated in Figure 7.2. Notice the last value
entered is at the top and the first is at the base. If we pop the values from the
stack, they will be removed in the reverse order from which they were pushed onto
the stack, producing a reverse ordering.

Page 41 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR

Implementing the Stack

The Stack ADT can be implemented in several ways. The two most common
approaches in Python include the use of a Python list and a linked list. The choice
depends on the type of application involved.
Using a Python List
The Python list-based implementation of the Stack ADT is the easiest to implement. The
first decision we have to make when using the list for the Stack ADT
is which end of the list to use as the top and which as the base. For the most
efficient ordering, we let the end of the list represent the top of the stack and the
front represent the base. As the stack grows, items are appended to the end of the
list and when items are popped, they are removed from the same end. Listing 7.1
on the next page provides the complete implementation of the Stack ADT using a
Python list.
The peek() and pop() operations can only be used with a non-empty stack
since you cannot remove or peek at something that is not there. To enforce this
requirement, we first assert the stack is not empty before performing the given
operation. The peek() method simply returns a reference to the last item in the
list. To implement the pop() method, we call the pop() method of the list structure, which
actually performs the same operation that we are trying to implement.
That is, it saves a copy of the last item in the list, removes the item from the list,
and then returns the saved copy. The push() method simply appends new items
to the end of the list since that represents the top of our stack.

Page 42 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR

The individual stack operations are easy to evaluate for the Python list-based
implementation. isEmpty(), len , and peek() only require O(1) time. The
pop() and push() methods both require O(n) time in the worst case since the
underlying array used to implement the Python list may have to be reallocated
to accommodate the addition or removal of the top stack item. When used in
sequence, both operations have an amortized cost of O(1).

Using a Linked List

The Python list-based implementation may not be the best choice for stacks with
a large number of push and pop operations. Remember, each append() and pop()
list operation may require a reallocation of the underlying array used to implement
the list. A singly linked list can be used to implement the Stack ADT, alleviating
the concern over array reallocations.
To use a linked list, we again must decide how to represent the stack structure.
With the Python list implementation of the stack, it was most efficient to use the
end of the list as the top of the stack. With a linked list, however, the front of the
list provides the most efficient representation for the top of the stack. In Chapter 6,
we saw how to easily prepend nodes to the linked list as well as remove the first
node. The Stack ADT implemented using a linked list is provided in Listing 7.2.

Page 43 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR

The class constructor creates two instance variables for each Stack. The top
field is the head reference for maintaining the linked list while size is an integer
value for keeping track of the number of items on the stack. The latter has to be
adjusted when items are pushed onto or popped o_ the stack. Figure 7.3 on the
next page illustrates a sample Stack object for the stack from Figure 7.1(b).
The StackNode class is used to create the linked list nodes. Note the inclusion
of the link argument in the constructor, which is used to initialize the next field of
the new node. By including this argument, we can simplify the prepend operation
of the push() method. The two steps required to prepend a node to a linked list
are combined by passing the head reference top as the second argument of the
StackNode() constructor and assigning a reference to the new node back to top.

Page 44 of 52
 SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR

The peek() method simply returns a reference to the data item in the first node after
verifying the stack is not empty. If the method were used on the stack represented by the
linked list in Figure 7.3, a reference to 19 would be returned.
The peek operation is only meant to examine the item on top of the stack. It should not be
used to modify the top item as this would violate the definition of the Stack ADT.
The pop() method always removes the first node in the list. This operation is illustrated in
Figure 7.4(a). This is easy to implement and does not require a search to find the node
containing a specific item. The result of the linked list after popping the top item from the
stack is illustrated in Figure 7.4(b).
The linked list implementation of the Stack ADT is more efficient than the Python-list based
implementation. All of the operations are O(1) in the worst case, the proof of which is left as
an exercise.

Stack Applications
The Stack ADT is required by a number of applications encountered in computer
science. In this section, we examine several basic applications that traditionally
are presented in a data structures course.

Balanced Delimiters
A number of applications use delimiters to group strings of text or simple data
into subparts by marking the beginning and end of the group. Some common examples
include mathematical expressions, programming languages, and the HTML
markup language used by web browsers. There are typically strict rules as to how
the delimiters can be used, which includes the requirement of the delimiters being paired
and balanced. Parentheses can be used in mathematical expressions to
group or override the order of precedence for various operations. To aide in reading
complicated expressions, the writer may choose to use different types of symbol

Page 45 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR
pairs, as illustrated here:
{A + (B * C) - (D / [E + F])}
The delimiters must be used in pairs of corresponding types: {}, [], and ().
They must also be positioned such that an opening delimiter within an outer pair
must be closed within the same outer pair. For example, the following expression
would be invalid since the pair of braces [] begin inside the pair of parentheses ()
but end outside.
(A + [B * C)] - {D / E}
Another common use of the three types of braces as delimiters is in the C++
programming language. Consider the following code segment, which implements a
function to compute and return the sum of integer values contained in an array:
int sumList( int theList[], int size )
{
int sum = 0;
int i = 0;
while( i < size ) {
sum += theList[ i ];
i += 1;
}
return sum;
}
As with the arithmetic expression, the delimiters must be paired and balanced.
However, there are additional rules of the language that dictate the proper placement and
use of the symbol pairs. We can design and implement an algorithm
that scans an input text _le containing C++ source code and determines if the
delimiters are properly paired. The algorithm will need to remember not only the
most recent opening delimiter but also all of the preceding ones in order to match
them with closing delimiters. In addition, the opening delimiters will need to be
remembered in reverse order with the most recent one available first.

The Stack ADT is a perfect structure for implementing such an algorithm.

Consider the C++ code segment from earlier. As the file is scanned, we can push each
opening delimiter onto the stack. When a closing delimiter is encountered, we pop the
opening delimiter from the stack and compare it to the closing delimiter. For properly paired
delimiters, the two should match. Thus, if the top of the stack contains a left bracket [, then
the next closing delimiter should be a right bracket ]. If the two delimiters match, we know
they are properly paired and can continue processing the source code. But if they do not
match, then we know the delimiters are not correct and we can stop processing the file.
Table 7.1
shows the steps performed by our algorithm and the contents of the stack after each
delimiter is encountered in our sample code segment.

Page 46 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR

So far, we have assumed the delimiters are balanced with an equal number of
opening and closing delimiters occurring in the proper order. But what happens if
the delimiters are not balanced and we encounter more opening or closing delimiters
than the other? For example, suppose the programmer introduced a typographical
error in the function header:
int sumList( int theList)], int size )
Our algorithm will find the first set of parentheses correct. But what happens
when the closing bracket ] is scanned? The result is illustrated in the top part of
Table 7.2. You will notice the stack is empty since the left parenthesis was popped
and matched with the preceding right parenthesis. Thus, unbalanced delimiters in
which there are more closing delimiters than opening ones can be detected when
trying to pop from the stack and we detect the stack is empty.

Page 47 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR

Delimiters can also be out of balance in the reverse case where there are more
opening delimiters than closing ones. Consider another version of the function
header, again containing a typographical error:
int sumList( int (theList[], int size )
The result of applying our algorithm to this code fragment is illustrated in the
bottom chart in Table 7.2. If this were the complete code segment, you can see we
would end up with the stack not being empty since there are opening delimiters
yet to be paired with closing ones. Thus, in order to have a complete algorithm,
we must check for both of these errors.
A Python implementation for the validation algorithm is provided in Listing 7.3.
The function isValidSource() accepts a _le object, which we assume was previously opened
and contains C++ source code. The _le is scanned one line at a time and each line is
scanned one character at a time to determine if it contains properly paired and balanced
delimiters.
A stack is used to store the opening delimiters and either implementation can
be used since the implementation is independent of the definition. Here, we have
chosen to use the linked list version. As the _le is scanned, we need only examine

Evaluating Postfix Expressions

We work with mathematical expressions on a regular basis and they are rather
easy for humans to evaluate. But the task is more difficult in a computer program
when an expression is represented as a string. Given the expression

A*B+C/D

we know A * B will be performed first, followed by the division and concluding

with addition. When evaluating this expression stored as a string and scanning
one character at a time from left to right, how do we know the addition has to wait
until after the division? Your first response is probably that we know the order

Page 48 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR
of the precedence for the operators. But how do we represent that in our string

the characters that correspond to one of the three types of delimiter pairs. All
other characters can be ignored. When an opening delimiter is encountered, we
push it onto the stack. When a closing delimiter occurs, we first check to make sure
the stack is not empty. If it is empty, then the delimiters are not properly paired
and balanced and no further processing is needed. We terminate the function and
return False. When the stack is not empty, the top item is popped and compared
to the closing delimiter. The two delimiters do match corresponding opening and
closing delimiters; we again terminate the function and return False. Finally,
after the entire _le is processed, the stack should be empty when the delimiters are
properly paired and balanced. For the final test, we check to make sure the stack
is empty and return either True or False, accordingly.

scanning process? Suppose we are evaluating a string containing nine non-blank

characters and have scanned the _rst three:
A + B / (C * D)
At this point, we have no way of knowing if the addition operation is to be
performed on the two variables A and B or if we have to save this information for
later. After moving to the the next character
A + B / (C * D)
we encounter the division operator and know that the addition is not the _rst
operation to be performed. Is the division the _rst operation to be performed? It
does have higher precedence than the addition, but it may not be the _rst operation
since parentheses can override the order of evaluation. We will have to scan more
of the string to determine which operation is the _rst to be performed.
A + B / (C * D)
After determining the _rst operation to be performed, we must then decide
how to return to those previously skipped. This can become a tedious process if

Page 49 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR
we have to continuously scanned forward and backward through the string in order
to properly evaluate the expression. To simplify the evaluation of a mathematical
expression, we need an alternative representation for the expression. A representation in
which the order the operators are performed is the order they are specified
would allow for a single left-to-right scan of the expression string.
Three different notations can be used to represent a mathematical expression.
The most common is the traditional algebraic or infix notation where the operator
is specified between the operands A+B. The prefix notation places the operator
immediately preceding the two operands +AB, whereas in postfix notation, the
operator follows the two operands AB+.
At first glance, the different notations may seem to be nothing more than different operator
placement. But the postfix and prefix notations have the advantages
that neither uses parentheses to override the order of precedence and both create
expressions in unique form. In other words, each expression is unique and produces
a specific result unlike infix notation in which the same expression can be written in multiple
ways.
Converting from Infix to Postfix
Infix expressions can be easily converted by hand to postfix notation. The expression A + B
- C would be written as AB+C- in postfix form. The evaluation of this
expression would involve first adding A and B and then subtracting C from that
result. We will examine the evaluation of postfix expressions later; for now we
focus on the conversion from infix to postfix.
Short expressions can be easily converted to postfix form, even those using
parentheses. Consider the expression A*(B+C), which would be written in postfix
as ABC+*. Longer expressions, such as the example from earlier, A*B+C/D, are a bit
more involved. To help in this conversion we can use a simple algorithm:
1. Place parentheses around every group of operators in the correct order of
evaluation. There should be one set of parentheses for every operator in the
infix expression.
((A * B) + (C / D))
2. For each set of parentheses, move the operator from the middle to the end
preceding the corresponding closing parenthesis.
((A B *) (C D /) +)
3. Remove all of the parentheses, resulting in the equivalent postfix expression.
AB*CD/+
Compare this result to a modified version of the expression in which parentheses
are used to place the addition as the first operation:
A * (B + C) / D
Using the simple algorithm, we parenthesize the expression:
((A * (B + C)) / D)
and move the operators to the end of each parentheses pair:
((A (B C +) *) D /)
Finally, removing the parentheses yields the postfix expression:
ABC+*D/
A similar algorithm can be used for converting from infix to prefix notation.
The difference is the operators are moved to the front of each group.

Postfix Evaluation Algorithm

Parentheses are used with infix expressions to change the order of evaluation. But
in postfix notation, the order cannot be altered and thus there is no need for parentheses.
Given the unique form or single order of evaluation, postfix notation is a
good choice when evaluating a mathematical expression represented as a string.
Of course the expression would have to either be given in postfix notation or first
converted from infix to postfix. The latter can be easily done with an appropriate algorithm,
but we limit our discussion to the evaluation of existing postfix expressions.
Evaluating a postfix expression requires the use of a stack to store the operands

Page 50 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR
or variables at the beginning of the expression until they are needed. Assume we
are given a valid postfix expression stored in a string consisting of operators and
single-letter variables. We can evaluate the expression by scanning the string, one
character or token at a time. For each token, we perform the following steps:
1. If the current item is an operand, push its value onto the stack.
2. If the current item is an operator:
(a) Pop the top two operands o_ the stack.
(b) Perform the operation. (Note the top value is the right operand while the
next to the top value is the left operand.)
(c) Push the result of this operation back onto the stack.
The final result of the expression will be the last value on the stack. To illustrate
the use of this algorithm, let's evaluate the postfix expression A B C + * D / from
our earlier example. Assume the existence of an empty stack and the following
variable assignments have been made:
A=8C=3
B=2D=4
The complete sequence of algorithm steps and the contents of the stack after
each operation are illustrated in Table 7.3.

The postfix evaluation algorithm assumes a valid expression. But what happens
if the expression is invalid? Consider the following invalid expression in which there
are more operands than available operators:
AB*CD+
After applying the algorithm to this expression, there are two values remaining
on the stack as illustrated in Table 7.4. What happens if there are too many
operators for the given number of operands? Consider such an invalid expression:
AB*+C/
In this case, there are too few operands on the stack when we encounter the
addition operator, as illustrated in Table 7.5. If we attempt to perform two pops
from the stack, an assertion error will be thrown since the stack will be empty
on the second pop. We can modify the algorithm to detect both types of errors.

Page 51 of 52
SYBSCCS PAPER III UNIT I DATA STRUCTURES USING PYTHON BY:[Link] PASHANKAR
In step 2(a), we must first verify the stack is not empty before popping an item.
If the stack is empty, we can stop the evaluation and flag an error. The second
modification occurs after the evaluation of the entire expression. We can pop the
result from the stack and then verify the stack is empty. If the stack is not empty,
the expression was invalid and we must fag an error.

Page 52 of 52