Transcript Data-Structures

Introduction to
Computational Thinking
Abstraction &
Data Structures
(C) Dennis Kafura 2016
1
Abstraction & Data Structures
property --> value
property --> value
property --> value
data structure
identifying the information properties of an entity
relevant for a given stakeholder; each property has
a value.
abstraction
CT@VT
computer
state
algorithm
organizing the properties and their values
so that they can be processed by an
algorithm executed by a computer.
(C) Dennis Kafura 2016
Slide 2
CT@VT
Abstraction


An abstraction can be depicted by a table
Example: an abstraction of a weather
report
properties
City
Temperature
"Blacksburg, VA"
77
values
(C) Dennis Kafura 2016
Slide 3
CT@VT
Dictionary: a data structure



A dictionary is a data structure used to represent a
single instance
A dictionary is organized as a collection of propertyvalue pairs
In Python the term key-value pair is used
City
Temperature
"Blacksburg, VA"
77
key-value pair
key-value pair
temps = { "City" : "Blacksburg, VA", "Temperature" : 77}
key
value
(C) Dennis Kafura 2016
Slide 4
Dictionary operations
CT@VT
temps = { " City" :"Blacksburg, VA" , "Temperature" : 77}

retrieval
cityTemp = temps["Temperature"]
cityName = temps["City"]

update
temps["Temperature"] = 82
(C) Dennis Kafura 2016
Slide 5
CT@VT
For today


Work in your cohorts on the class work
problems for 30 minutes
More discussion of abstraction and
dictionaries to follow
(C) Dennis Kafura 2016
Slide 6
CT@VT
Abstracting multiple entities


Similar abstracted entities (e.g., weather
reports for different locations) have the same
properties but different values.
They are called instances.
properties
instances
City
Temperature
"Blacksburg, VA"
77
"New York, NY"
85
"San Jose, CA"
75
"Miami, FL"
88
(C) Dennis Kafura 2016
Slide 7
CT@VT
Representing an abstraction
City
Temperature
"Blacksburg, VA"
77
"New York, NY"
85
"San Jose, CA"
75
"Miami, FL"
88
list
multiple instances,
one property
(C) Dennis Kafura 2016
dictionary
multiple properties
one instance
Slide 8
CT@VT
Representing Abstractions

Abstractions are represented using data
structures

Dictionary



a collection of key-value pairs
used to represent multiple properties of a single
instance of an abstraction
List


a collection of similar things
used to represent one property of multiple
instances of an abstraction
(C) Dennis Kafura 2016
Slide 9
CT@VT
An Example
report =
[ {
{
{
{
"City"
"City"
"City"
"City"
City
Temperature
"Blacksburg, VA"
77
"New York, NY"
85
"San Jose, CA"
75
"Miami, FL"
88
:
:
:
:
"Blacksburg, VA"
"New York, NY"
"San Jose, CA"
"Miami, FL"
,
,
,
,
"Temperature"
"Temperature"
"Temperature"
"Temperature"
(C) Dennis Kafura 2016
:
:
:
:
77} ,
85} ,
75} ,
88} ]
Slide 10
CT@VT
Dictionaries/Lists and iteration
reports
=
[ { "City"
{ "City"
{ "City"
{ "City"
:
:
:
:
"Blacksburg, VA"
"New York, NY"
"San Jose, CA"
"Miami, FL"
,
,
,
,
"Temperature"
"Temperature"
"Temperature"
"Temperature"
:
:
:
:
77} ,
85} ,
75} ,
88} ]
# find average temperature
total = 0
number= 0
for report in reports:
total= total + report["Temperature"]
number = number + 1
average = total / number
(C) Dennis Kafura 2016
Slide 11