Ds Introduction

DATA STRUCTURES
Introduction
Digital Data
•
Music Photos
Movies
Protein
Shapes
DNA
•gatcttttta tttaaacgat ctctttatta gatctcttat taggatcatg atcctctgtg
gataagtgat tattcacatg gcagatcata taattaagga ggatcgtttg ttgtgagtga
ccggtgatcg tattgcgtat aagctgggat ctaaatggca tgttatgcac agtcactcgg Maps
cagaatcaag gttgttatgt ggatatctac tggttttacc ctgcttttaa gcatagttat
acacattcgt tcgcgcgatc tttgagctaa ttagagtaaa ttaatccaat ctttgaccca
•0010101001010101010100100100101010000010010010100....
ASCII table:
agreement for
RAM = Symbols + Pointers the meaning
of bits
(for our purposes)
•16-bit words
0 0100101001111011
2 01101110 10 100000
4 00 10000 100 1000 11
6 10000 1000 10 1000 1

We may agree to
8 0000000000000100
interpret bits as an
10 100 10 10 11000 10 10 address (pointer)
12 1000000111000001
1111111111111111
14
Physically, RAM is => We can store and

a random accessible
manipulate arbitrary
array of bits.
symbols (like letters) and
associations between them.
Digital Data Must Be ...
Encoded (e.g. 01001001 <-> )
Arranged
- Stored in an orderly way in memory / disk
Accessed The focus of

- Insert new data this class
- Remove old data
- Find data matching some condition
Processed
Algorithms: shortest path, minimum cut, FFT, ...
Data Structures -> Data Structuring
How do we organize information so that we can find, update, add, and
delete portions of it efficiently?
Data Structure Example Applications
1. How does Google quickly find web pages that contain a

search term?
1. What’s the fastest way to broadcast a message to a network

of computers?
1. How can a subsequence of DNA be quickly found within

the genome?
1. How does your operating system track which memory

(disk or RAM) is free?
1. In the game Half-Life, how can the computer determine

which parts of the scene are visible?
What is a Data Structure Anyway?
It’s an agreement about:

 how to store a collection of objects in memory,
 what operations we can perform on that data,
 the algorithms for those operations, and
 how time and space efficient those algorithms are.
Ex. vector in C++:

 Stores objects sequentially in memory
 Can access, change, insert or delete objects
 Algorithms for insert & delete will shift items as needed
 Space: O(n), Access/change = O(1), Insert/delete = O(n)
Abstract Data Types (ADT)
class Dictionary { insert() int main() {
Dictionary();
delete() D = new Dictionary()
void insert(int x, int y);
D.insert(3,10);
void delete(int x); find _min() cout << D.find(3);
... }
find()
}
 Data storage & operations encapsulated by an ADT.
 ADT specifies permitted operations as well as time and space

guarantees.
 User unconcerned with how it’s implemented
(but we are concerned with implementation in this class).
 ADT is a concept or convention:

•- not something that directly appears in your code
programming language may provide support for communicating ADT to users
•-
(e.g. classes in Java & C++)

Dictionary ADT
Most basic and most useful ADT:

 insert(key, value)
 delete(key, value)
 value = find(key)
Many languages have it built in:

•awk: D[“AAPL”] = 130 # associative array
•perl: my % D; $ D [ “AAPL”] = 130; # hash
•python: D = { }; D [ “AAPL”] = 130 # dictionary
•C++: map<string,string> D = new map<string, string>();
•D[“AAPL”] = 130; // map
Insert, delete, find each either O(log n) [C++] or expected constant

[perl, python]
Suppose You’re Google Maps...
You want to store data about cities (location, elevation, population)...
What kind of operations should your data structure(s) support?
Operations to support the following scenarios...
 Finding addresses on map?
•- Lookup city by name...
 Mobile iPhone user?

•- Find nearest point to me...
 Car GPS system?

•- Calculate shortest-path between
cities...
•- Show cities within a given
window...
 Political revolution?
•- Insert, delete, rename cities
•Data Organizing Principles
 Ordering :
 Put keys into some order so that we know something about where each key
•is are relative to the other keys.
 Phone books are easier to search because they are alphabetized.
 Linking :
 Add pointers to each record so that we can find related records quickly.
 E.g. The index in the back of book provides links from words to the pages
•on which they appear.
 Partitioning :
 Divide the records into 2 or more groups, each group sharing a particular
•property.
 E.g. Multi-volume encyclopedias (Aa-Be, W-Z)
 E.g. Folders on your hard drive
Ordering
Pheasant, 10 Albatross, 0
Grouse, 89 Bluejay, 24
Quail, 55 Cardinal, 102
Pelican, 3 Chicken, 7
Partridge, 32 Duck, 18 Search for
Duck, 18 Eagle, 43
Woodpecker, 50 Egret, 88 “Goose”
Robin, 89 Finch, 38
Cardinal, 102 Binary Search
Goose, 67
Eagle, 43 Grouse, 89 O(log n)
Chicken, 7 Heron, 70 (1)
Pigeon, 201 Loon, 213
Swan, 57 Partridge, 32
Loon, 213 Pelican, 3
Turkey, 99 Every step discards
Pheasant, 10
Albatross, 0 Pigeon, 201 half the remaining
Ptarmigan, 22 Ptarmigan, 22 entries:
Finch, 38 Quail, 55
Bluejay, 24 Robin, 89 n/2k = 1
Heron, 70 Swan, 57
Egret, 88 2k = n
Turkey, 99
Goose, 67 Woodpecker, 50 •k = log n
Linking
97
43
2 24
78
 Records located any where in memory

 Green pointers give “next” element
 Red pointers give “previous” element
 Insertion & deletion easy if you have a pointer to the middle of the list
 Don’t have to know size of data at start

 Pointers let us express relationships between pieces of information.
Partitioning
 Ordering implicitly gives a partitioning based on the “<“ relation.
 Partitioning usually combined with linking to point to the two halves.
 Prototypical example is the Binary Search Tree:
Find 18
31
19 58
16 35 98
9 18
•All keys in the left subtree are < the root

•All keys in the right subtree are ≥ the root

Ds Introduction

Uploaded by

Copyright:

Available Formats

Ds Introduction

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Ds Introduction

Uploaded by

Copyright:

Available Formats

DATA STRUCTURES

6 10000 1000 10 1000 1

Physically, RAM is => We can store and

Accessed The focus of

1. How does Google quickly find web pages that contain a

1. What’s the fastest way to broadcast a message to a network

1. How can a subsequence of DNA be quickly found within

1. How does your operating system track which memory

1. In the game Half-Life, how can the computer determine

It’s an agreement about:

Ex. vector in C++:

 Data storage & operations encapsulated by an ADT.

 ADT specifies permitted operations as well as time and space

 ADT is a concept or convention:

(e.g. classes in Java & C++)

Most basic and most useful ADT:

Many languages have it built in:

Insert, delete, find each either O(log n) [C++] or expected constant

 Mobile iPhone user?

 Car GPS system?

 Records located any where in memory

 Red pointers give “previous” element

 Don’t have to know size of data at start

•All keys in the left subtree are < the root

You might also like