Data Structures and Abstract Data Types in Computational Thinking
undefined
ESSENTIAL COMPUTATIONAL
THINKING: CHAPTER 06
Dr. Ricky J. Sethi
Essential Computational Thinking
Data Structures
Chapter 6
The story so far…
We found that
data
was the
structured raw facts
, or values,
observed from the physical world
The
way that data is organized
has a significant impact on how
effectively it can be used
The
types
of values represented
by the data, the structured values,
also determine the various
operations defined on it
In addition,
abstraction
, the idea
of
ignoring
or
hiding
certain
details about some system we’re
studying, can help us model or
represent it
Let’s formalize this for different
data representations and
structures
Non-Technical Abstract Type
A familiar idea: different types of data will hold
different kinds of values and so have different kinds
of operations associated with it
For example:
screws
and
nails
!
We can distinguish between the two types of
fasteners based on their
characteristics
(e.g., the
value of the kind of head they have) and their
operations
(the kinds of things you can do to or
with them)
Abstract Fastener Type
We can
abstract
out the essential elements of all
Fasteners
They have a certain value for the Head
characteristic
(is
it flat or slotted, for example)
They have certain common
operations
(they can both be
inserted using some driving implement like a
screwdriver or hammer, for example)
We can then specify the
Abstract
Fastener Type
This is like a like a
blueprint
or an
outline
It doesn’t have any details for any specific kind of Fastener
but describes those elements that all Fasteners must have
Abstract Data Type (ADT)
Like the AFT, ADTs delineate the characteristics and
operations for many kinds of data, not just fasteners
Abstract Data Type denotes the kinds of
characteristics
a certain data structure can have
and the kinds of
operations
it can do or have done
on it
Abstract Data Types show
what
they do but not the
details of
how
they do it
abstract
!
For this reason, ADTs are sometimes called the
specification
or the interface for the data type
Advantages of ADTs
ADTs make our computational solutions
simpler
and easier to
understand or modify by omitting details of how the operations will
be implemented
E.g., all fasteners have the
drive in
operation but the Abstract
Fastener Type doesn’t specify that they should all use only hammers
ADTs give us the
flexibility
to structure the data in memory in the
way that’s optimal for a specific data type without forcing all data
types to follow the same approach
E.g., all fasteners have a HEAD value but the Abstract Fastener Type
doesn’t dictate the same HEAD value for all fasteners
ADTs support
reuse
and
organization
by providing the ability to
generalize
the use of similar data types and the ability to group
tasks
E.g., we can specify we’ll use a fastener for two tasks in some solution
and the two tasks can use different types of fasteners but we know both
tasks are “fastener tasks”
ADTs vs Data Structures
A
Data Type
is the
logical
expression, independent
of any language, of a
type
, the collection of
values
, and the
operations
that are permitted on
that type
An
Abstract Data Type (ADT)
is the
logical
specification of a
Data Type
in some particular
language but without any implementation details
A
Data Structure
is the
implementation
of that ADT
in that particular language
Data Structures
The ADT is just the
interface
without any
implementation
details, it is a theoretical concept
that is a
representation of a Data Type
An Abstract Data Type is a
logical
description while
the Data Structure itself is a
concrete
implementation
A particular
data structure
gives you the concrete
implementations for both the characteristics and the
operations
Logical Interface vs Physical
Implementation
This idea of only examining
what
a system does is a form of
abstraction, hence the word
abstract
in Abstract Data Type.
Abstraction also allows us to differentiate between a
logical
view and a
physical
view of the system or problem.
The logical perspective of the system is sometimes called the
interface
or
logical interface
.
For example, when you turn on your television, you use a
remote control and don’t need to know anything about how
the TV works, how the image is produced, or what the
circuits look like.
The circuits and other machinery of the television are the
physical
implementation
and the remote control would constitute the
logical interface
, which only references
what
the TV does and not
the details of
how
it does it.
Strings
A String is also an example of a Sequential Data Type
in Python
Some useful Sequence Data Structures that Python gives us
are
list
and
tuple
A string is simply some
ordered collection
of characters,
or valid symbols, in Python.
This ordered collection is called a
sequence
Since a string is composed of multiple characters it is also
sometimes called a
compound data type
As opposed to something like the
int
data type, which is a
simple data type since it only holds a single value
It turns out that we can access individual components of
a string as each character, or
element
, is assigned a
unique
index
in the string
Mangoes!
E.g., we can access each individual
character via the
index
, which is a number
indicating the
position
of a particular
character in the string
The index starts at 0 as arrays and
sequences are
zero-indexed
in both
Python and Java.
This often leads to the infamous
off-by-one
error
, in which the programmer forgets that
indexing begins at zero and mistakenly
starts indexing from 1
We can use the subscript operator, which is
indicated by
[]
, to access any element at
a
specific index
, or
range of indices
.
We can see this where we first initialized
the variable foo to “mango” and then used
the subscript operator to access the first
character at index 0
>>> foo = " mango "
>>> letter = foo [0]
>>>
( letter )
m
>>> letters = foo [0:3]
>>>
( letters )
man
Python String Oddities
We can access any sub-sequence of characters
in a string using the subscript operator.
We can indicate individual elements with a
single numeric index or a sub-sequence using a
numeric range
with the
:
character.
This is called slicing a string
It ranges from the lower index (including the
element at the lower index itself) to the upper
index (excluding the element at the upper index).
We can also leave off either the lower or upper
index to indicate the lowest or highest value
One other quick oddity about Python: strings
are immutable
This is true for all objects and values
So unlike other languages like Java, we can’t use
the subscript operator to
assign
values to strings
We can also use the subscript operator on a
string to access (not modify) individual elements
or a range of elements or also access any subset
of elements via a for loop
>>>
(foo [:3])
man
>>>
(foo [3:])
go
>>> count = 0
>>>
for
eachLetter
in
foo:
...
if
eachLetter == ’a’:
... count = count + 1
...
>>>
( count )
1
A First Look at Objects
Strings are actually
objects
, which you can think of as
being derived from an ADT, in a way
We’ll be exploring objects, and the
classes
which create
them, in quite some depth when we get to Object-Oriented
Programming
Just about everything in Python is an object
Objects have access to both their
data
, like the string value
stored in a string variable, and
methods
, or operations that
you can perform on their data
We can use any string method using the string object’s
name (the name of the variable that represents that
object) followed by the
dot operator
>>> bar = foo.upper()
>>>
(bar)
MANGO
>>> bar = foo.lower()
>>>
(bar)
mango
Lists
One of the most obvious and useful ways to organize data is as a list
E.g., we use lists in our everyday lives: shopping lists, to-do lists, checklists, etc.
A list is a means of structuring and accessing a collection of data
In particular, a way of organizing data in a
linear sequence
The
list
ADT
can keep track of elements in a list
The
list
ADT describes what kinds of values
list
s can hold and the operations
they can have
Like insert a new element, locate an existing element, delete an existing element, etc.
Then, we can create specific implementations, or
Data Structures
, like
ArrayList
,
LinkedList
, etc. which implement that required behaviour
in very different ways
different languages implement them differently
The different ways to implement the
list
ADT depend on the kinds of
problems those data structures will help tackle
Python implements the
list
ADT as the list data structure
Lists and Tuples
Just like a string is a
sequence of characters
, a
list
is a
sequence of
values of any type
at all, including other lists (or tuples)
Just like with strings, we can use the subscript operator to access
elements or sub-sequences of lists
Unlike strings, though, lists are
mutable
You can use the subscript operator to
set
or
change
elements of a list
We can still use loops to
traverse
, or access all the elements of, the list
We can also use built-in methods of Python like
len()
to find the
length of any sequence like strings, lists, or tuples
There are many methods only available to list objects that allow you
to do things like
append()
new elements to the lists,
extend()
the list with another list, and
sort()
the elements of the list
We can do things like use the
+
operator to concatenate lists, the
*
operator to repeat a list for the number of times in the right operand,
and do the same kind of
slicing
as you did for strings
Tuples
A tuple is just like a list but:
It’s declared using parentheses,
()
, rather than
brackets,
[]
It’s
not mutable
once you’ve created it
Tuples are also objects that are
comparable
, which
means that we can sort lists of tuples
They’re also
hashable
, which is helpful when we meet the
dict
data type
Data organization and abstraction play a crucial role in computational thinking. Data structures like fasteners exemplify how different types of operations are associated with distinct characteristics. Abstract Data Types (ADTs) serve as specifications for data structures, outlining their essential characteristics and operations. By formalizing data representations and structures, we can model various systems effectively.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
ESSENTIAL COMPUTATIONAL THINKING: CHAPTER 06 Dr. Ricky J. Sethi Essential Computational Thinking
Chapter 6 Data Structures
The story so far We found that data was the structured raw facts, or values, observed from the physical world The way that data is organized has a significant impact on how effectively it can be used The types of values represented by the data, the structured values, also determine the various operations defined on it In addition, abstraction, the idea of ignoring or hiding certain details about some system we re studying, can help us model or represent it Let s formalize this for different data representations and structures
Non-Technical Abstract Type A familiar idea: different types of data will hold different kinds of values and so have different kinds of operations associated with it For example: screws and nails! We can distinguish between the two types of fasteners based on their characteristics (e.g., the value of the kind of head they have) and their operations (the kinds of things you can do to or with them)
Abstract Fastener Type We can abstract out the essential elements of all Fasteners They have a certain value for the Head characteristic (is it flat or slotted, for example) They have certain common operations (they can both be inserted using some driving implement like a screwdriver or hammer, for example) We can then specify the Abstract Fastener Type This is like a like a blueprint or an outline It doesn t have any details for any specific kind of Fastener but describes those elements that all Fasteners must have
Abstract Data Type (ADT) Like the AFT, ADTs delineate the characteristics and operations for many kinds of data, not just fasteners Abstract Data Type denotes the kinds of characteristics a certain data structure can have and the kinds of operations it can do or have done on it Abstract Data Types show what they do but not the details of how they do it abstract! For this reason, ADTs are sometimes called the specification or the interface for the data type
Advantages of ADTs ADTs make our computational solutions simpler and easier to understand or modify by omitting details of how the operations will be implemented E.g., all fasteners have the drive in operation but the Abstract Fastener Type doesn t specify that they should all use only hammers ADTs give us the flexibility to structure the data in memory in the way that s optimal for a specific data type without forcing all data types to follow the same approach E.g., all fasteners have a HEAD value but the Abstract Fastener Type doesn t dictate the same HEAD value for all fasteners ADTs support reuse and organization by providing the ability to generalize the use of similar data types and the ability to group tasks E.g., we can specify we ll use a fastener for two tasks in some solution and the two tasks can use different types of fasteners but we know both tasks are fastener tasks
ADTs vs Data Structures A Data Type is the logical expression, independent of any language, of a type, the collection of values, and the operations that are permitted on that type An Abstract Data Type (ADT) is the logical specification of a Data Type in some particular language but without any implementation details A Data Structure is the implementation of that ADT in that particular language
Data Structures The ADT is just the interface without any implementation details, it is a theoretical concept that is a representation of a Data Type An Abstract Data Type is a logical description while the Data Structure itself is a concrete implementation A particular data structure gives you the concrete implementations for both the characteristics and the operations
Logical Interface vs Physical Implementation This idea of only examining what a system does is a form of abstraction, hence the word abstract in Abstract Data Type. Abstraction also allows us to differentiate between a logical view and a physical view of the system or problem. The logical perspective of the system is sometimes called the interface or logical interface. For example, when you turn on your television, you use a remote control and don t need to know anything about how the TV works, how the image is produced, or what the circuits look like. The circuits and other machinery of the television are the physical implementation and the remote control would constitute the logical interface, which only references what the TV does and not the details of how it does it.
Strings A String is also an example of a Sequential Data Type in Python Some useful Sequence Data Structures that Python gives us are list and tuple A string is simply some ordered collection of characters, or valid symbols, in Python. This ordered collection is called a sequence Since a string is composed of multiple characters it is also sometimes called a compound data type As opposed to something like the int data type, which is a simple data type since it only holds a single value It turns out that we can access individual components of a string as each character, or element, is assigned a unique index in the string
Mangoes! E.g., we can access each individual character via the index, which is a number indicating the position of a particular character in the string The index starts at 0 as arrays and sequences are zero-indexed in both Python and Java. This often leads to the infamous off-by-one error, in which the programmer forgets that indexing begins at zero and mistakenly starts indexing from 1 We can use the subscript operator, which is indicated by [], to access any element at a specific index, or range of indices. We can see this where we first initialized the variable foo to mango and then used the subscript operator to access the first character at index 0 >>> foo = " mango " >>> letter = foo [0] >>> print ( letter ) m >>> letters = foo [0:3] >>> print ( letters ) man
Python String Oddities We can access any sub-sequence of characters in a string using the subscript operator. We can indicate individual elements with a single numeric index or a sub-sequence using a numeric range with the : character. This is called slicing a string It ranges from the lower index (including the element at the lower index itself) to the upper index (excluding the element at the upper index). We can also leave off either the lower or upper index to indicate the lowest or highest value One other quick oddity about Python: strings are immutable This is true for all objects and values So unlike other languages like Java, we can t use the subscript operator to assign values to strings We can also use the subscript operator on a string to access (not modify) individual elements or a range of elements or also access any subset of elements via a for loop >>> print (foo [:3]) man >>> print (foo [3:]) go >>> count = 0 >>> for eachLetter in foo: ... if eachLetter == a : ... count = count + 1 ... >>> print ( count ) 1
A First Look at Objects Strings are actually objects, which you can think of as being derived from an ADT, in a way We ll be exploring objects, and the classes which create them, in quite some depth when we get to Object-Oriented Programming Just about everything in Python is an object Objects have access to both their data, like the string value stored in a string variable, and methods, or operations that you can perform on their data We can use any string method using the string object s name (the name of the variable that represents that object) followed by the dot operator >>> bar = foo.upper() >>> print(bar) MANGO >>> bar = foo.lower() >>> print(bar) mango
Lists One of the most obvious and useful ways to organize data is as a list E.g., we use lists in our everyday lives: shopping lists, to-do lists, checklists, etc. A list is a means of structuring and accessing a collection of data In particular, a way of organizing data in a linear sequence The list ADT can keep track of elements in a list The list ADT describes what kinds of values lists can hold and the operations they can have Like insert a new element, locate an existing element, delete an existing element, etc. Then, we can create specific implementations, or Data Structures, like ArrayList, LinkedList, etc. which implement that required behaviour in very different ways different languages implement them differently The different ways to implement the list ADT depend on the kinds of problems those data structures will help tackle Python implements the list ADT as the list data structure
Lists and Tuples Just like a string is a sequence of characters, a list is a sequence of values of any type at all, including other lists (or tuples) Just like with strings, we can use the subscript operator to access elements or sub-sequences of lists Unlike strings, though, lists are mutable You can use the subscript operator to set or change elements of a list We can still use loops to traverse, or access all the elements of, the list We can also use built-in methods of Python like len() to find the length of any sequence like strings, lists, or tuples There are many methods only available to list objects that allow you to do things like append() new elements to the lists, extend() the list with another list, and sort() the elements of the list We can do things like use the + operator to concatenate lists, the * operator to repeat a list for the number of times in the right operand, and do the same kind of slicing as you did for strings
Tuples A tuple is just like a list but: It s declared using parentheses, (), rather than brackets, [] It s not mutable once you ve created it Tuples are also objects that are comparable, which means that we can sort lists of tuples They re also hashable, which is helpful when we meet the dict data type
