Transcript ppt

Array-Based Sequences
Hongfei Yan
April 1, 2015
Array-Based Sequences
1
Recap: The Three Laws of Recursion



A recursive algorithm must have a base
case.
A recursive algorithm must change its
state and move toward the base case.
A recursive algorithm must call itself,
recursively.
Array-Based Sequences
2
Q: How many recursive calls are made
when computing the sum of the list
[2,4,6,8,10]?
a)6
b)5
c)4
d)3
Q: Suppose you are going to write a
recursive function to calculate the factorial
of a number.
fact(n) returns n * n-1 * n-2 * ...
Where the factorial of zero is definded to
be 1. What would be the most appropriate
base case?
a)n==0
b)n==1
c)n>=0
d)n<=1
Assignment #3: Recursion



C-4.16 Write a short recursive Python function that takes a
character string s and outputs its reverse. For example, the
reverse of 'pots&pans' would be 'snap&stop' .
C-4.19 Write a short recursive Python function that rearranges a
sequence of integer values so that all the even values appear
before all the odd values.
C-4.21 Suppose you are given an n-element sequence, S,
containing distinct integers that are listed in increasing order.
Given a number k, describe a recursive algorithm to find two
integers in S that sum to k, if such a pair exists. What is the
running time of your algorithm?
Array-Based Sequences
5
Array-Based Sequences
6
Array-Based Sequences
7
Array-Based Sequences
8





Caesar: An interesting application of
strings and lists is cryptography
Dynamic arrays and amortization
Sorting high scores for a game
Insertion sort
Tic tac toe
Array-Based Sequences
9
Array-Based Sequences
10
Array-Based Sequences
11
Array-Based Sequences
12
Array-Based Sequences
13
Array-Based Sequences
14
Array-Based Sequences
15
5.5 Using Array-Based
Sequences


5.5.1 Storing High Scores for a Game
The first application we study is storing a
sequence of high score entries for a
video game.
Array-Based Sequences
16
Array-Based Sequences
17
Array-Based Sequences
18
Array-Based Sequences
19
Array-Based Sequences
20
Python Sequence Classes



Python has built-in types, list, tuple, and str.
Each of these sequence types supports indexing to
access an individual element of a sequence, using a
syntax such as A[i]
Each of these types uses an array to represent the
sequence.

An array is a set of memory locations that can be
addressed using consecutive indices, which, in Python,
start with index 0.
A
0 1 2
© 2013 Goodrich, Tamassia, Goldwasser
i
n
Array-Based Sequences
21
Arrays of Characters or
Object References


An array can store primitive elements, such as
characters, giving us a compact array.
An array can also store references to objects.
© 2013 Goodrich, Tamassia, Goldwasser
Array-Based Sequences
22
Compact Arrays

Primary support for compact arrays is in a
module named array.


That module defines a class, also named array,
providing compact storage for arrays of primitive
data types.
The constructor for the array class requires a
type code as a first parameter, which is a
character that designates the type of data that
will be stored in the array.
© 2013 Goodrich, Tamassia, Goldwasser
Array-Based Sequences
23
Type Codes in the array Class

Python’s array class has the following
type codes:
© 2013 Goodrich, Tamassia, Goldwasser
Array-Based Sequences
24
Insertion


In an operation add(i, o), we need to make room
for the new element by shifting forward the n - i
elements A[i], …, A[n - 1]
In the worst case (i = 0), this takes O(n) time
A
0 1 2
i
n
0 1 2
i
n
0 1 2
o
i
A
A
© 2013 Goodrich, Tamassia, Goldwasser
Array-Based Sequences
n
25
Element Removal


In an operation remove(i), we need to fill the hole left by
the removed element by shifting backward the n - i - 1
elements A[i + 1], …, A[n - 1]
In the worst case (i = 0), this takes O(n) time
A
0 1 2
o
i
n
0 1 2
i
n
0 1 2
i
A
A
© 2013 Goodrich, Tamassia, Goldwasser
Array-Based Sequences
n
26
Performance

In an array based implementation of a
dynamic list:




The space used by the data structure is O(n)
Indexing the element at I takes O(1) time
add and remove run in O(n) time in worst case
In an add operation, when the array is full,
instead of throwing an exception, we can
replace the array with a larger one…
© 2013 Goodrich, Tamassia, Goldwasser
Array-Based Sequences
27
Growable Array-based Array List



In an add(o) operation
(without an index), we could Algorithm add(o)
if t = S.length - 1 then
always add at the end
A  new array of
When the array is full, we
size …
replace the array with a
for i  0 to n-1 do
larger one
A[i]  S[i]
SA
How large should the new
nn+1
array be?
S[n-1]  o
 Incremental strategy: increase

the size by a constant c
Doubling strategy: double the
size
© 2013 Goodrich, Tamassia, Goldwasser
Array-Based Sequences
28
Comparison of the Strategies



compare the incremental strategy and the
doubling strategy by analyzing the total time
T(n) needed to perform a series of n add(o)
operations
assume that we start with an empty stack
represented by an array of size 1
call amortized time of an add operation the
average time taken by an add over the series
of operations, i.e., T(n)/n
© 2013 Goodrich, Tamassia, Goldwasser
Array-Based Sequences
29
Incremental Strategy Analysis




We replace the array k = n/c times
The total time T(n) of a series of n add
operations is proportional to
n + c + 2c + 3c + 4c + … + kc =
n + c(1 + 2 + 3 + … + k) =
n + ck(k + 1)/2
Since c is a constant, T(n) is O(n + k2), i.e.,
O(n2)
The amortized time of an add operation is O(n)
© 2013 Goodrich, Tamassia, Goldwasser
Array-Based Sequences
30
Doubling Strategy Analysis




We replace the array k = log2 n
times
geometric series
The total time T(n) of a series of n
add operations is proportional to
2
4
n + 1 + 2 + 4 + 8 + …+ 2k =
1 1
k
+
1
n+2
-1 =
3n - 1
8
T(n) is O(n)
The amortized time of an add
operation is O(1)
© 2013 Goodrich, Tamassia, Goldwasser
Array-Based Sequences
31
Python Implementation
© 2013 Goodrich, Tamassia, Goldwasser
Array-Based Sequences
32
5.6 Multidimensional Data Sets

For example, the two-dimensional data

might be stored in Python as follows.
data = [ [22, 18, 709, 5, 33], [45, 32, 830, 120, 750], [4, 880, 45, 66, 61] ]
Array-Based Sequences
33
Constructing a Multidimensional List


initialize a one-dimensional list, rely on a
syntax such as
data = [0] * n to create a list of n zeros.
list comprehension syntax for a 2D list of
integers
data = [ [0] c for j in range(r) ]
Array-Based Sequences
34
Summary
Array-Based Sequences
35