ADT and Tries
CSE332 Section 01
Take the handouts and take a look at Q0
STAFF_NAME_HERE
STAFF_CLASS_STANDING_HERE
STAFF_FUN_FACT_HERE
STAFF_IMAGE_HERE
Email: STAFF_EMAIL_HERE@cs
Office Hours: TBA
Icebreakers!
In Groups:
Announcements
Abstract Data Types
(ADT)
Abstract Data Type (ADT)
From lecture:
Mathematical description of a “thing” with set of operations on that “thing”
Main Idea:
Based on the point of view from the USER (as opposed to the implementer)
3 Descriptors:
Data Structure
From lecture:
A specific organization of data and family of algorithms for implementing an ADT
Main Idea:
Based on the point of view from the IMPLEMENTER (as opposed to the user)
i.e. it is the specification (data + algorithms) of an ADT
e.g. stack can use an underlying array data structure and specific pop/push algorithms
Questions?
Problem 0
Go into your groups and discuss!
Problem 0 Recap
ADT | Description |
Stack | LIFO Properties |
Queue | FIFO Properties |
Underlying Data Structure | Description |
Array | Linear collection of elements with indexes to specific elements |
LinkedList with front *Singly LinkedList | Linear collection of elements where each element points to the next element |
LinkedList with front and back | Same as LinkedList with front but we have access to a pointer to the back most element |
Problem 0 (a)
You're designing a tool that checks code to verify that all opening brackets, braces, parentheses have closing counterparts.
We want to match the most recent bracket we’ve seen first so we want LIFO properties.
We can use an Array to efficiently simulate a stack by adding and removing elements from the back.
A LinkedList will work if we add and remove elements from the front but LinkedList with front is simpler.
Stack
Array, Linked List with front
Problem 0 (b)
Disneyland has hired you to find a way to improve the processing efficiency of their long lines at attractions. There is no way to forecast how long the lines will be.
We're dealing with a line that wants FIFO properties.
The Array implementation will work if we implement it as a CircularArrayFIFOQueue (will be talked about later).
We can use a LinkedList with front and back to efficiently simulate a Queue by adding elements to the front and removing elements from the back. There is no way to make the LinkedList with front work efficiently; either adding or removing from the Queue will be slow.
Queue
Array, Linked List with front and back
Problem 0 (c)
A sandwich shop wants to serve customers in the order that they arrived, but also wants to look ahead to know what people have ordered.
Same as before, we're dealing with a line that wants FIFO properties.
We need to access both ends of the data structure but also want to know what someone has ordered at a specific index. The LinkedList will not allow us to access a specific index efficiently.
As a bonus, this can work efficiently if implemented as a CircularArrayFIFOQueue (P1!).
Queue
Array
Questions?
Trie Microteach
Pronounced try
Problem
Autocomplete.
How would you store common search queries?
How would you then retrieve them based on a prefix?
Weights, higher = more common query
Trie: A tree-like data structure
Has the regular tree properties: root, nodes, and leaves
Represents the map (and set) ADT.
Every node represents 1 character:
Node {
Map<Character, Node> children
int value // int can be any type
}
2
0
1
0
C
3
D
H
I
A B C D E ...X Y Z
int value
Node:
Trie: insert("DOT", 3)
Break down the word into characters.
"D", "O", "T".
value: null
value: null
value: null
value:
""
"D"
"DO"
"DOT"
D
O
T
value: 3
Trie: insert("DO", 21)
value: null
value: null
value: null
value: 3
""
"D"
"DO"
"DOT"
D
O
T
value: 21
Questions?
Trie: find(word)
find("D") // miss
find("DOT") // returns 3
find("DO") // returns 21
value: null
value: null
value: 3
""
"D"
"DO"
"DOT"
D
O
T
value: 21
Questions?
Trie: delete("DO")
Deleting nodes with children
value: null
value: null
value: 3
""
"D"
"DO"
"DOT"
D
O
T
value: 21
value: null
Trie: delete("DOT")
Deleting nodes without children
value: null
value: null
""
"D"
"DO"
"DOT"
D
O
T
value: 3
value: 21
value: null
Trie: delete("D")
Deleting nodes that don't exist
value: null
value: null
value:
""
"D"
"DO"
"DOT"
D
O
T
value: 3
value: 21
Questions?
Solution
Autocomplete.
How would you store common search queries?
Store the search queries in a Trie, Keys are the search queries, Values are the weights
How would you then retrieve them based on a prefix?
We traverse the trie and grab all the Keys that exist below a node based on the prefix
Weights, higher = more common query
Problem 1
Go into your groups and discuss!
Problem 1 (a)
0 1
true
true
true
0 1
true
true
true
0 1
true
true
true
0 1
true
true
true
0 1
true
0 1
true
0 1
true
Insert all possible binary strings of lengths 0-3 (i.e. "", "1", "0", "10", ..., "110", "111") into a Trie.
Problem 1 (b)
0 1
true
true
true
0 1
true
true
true
0 1
true
true
true
0 1
true
true
true
0 1
true
0 1
true
0 1
true
If we deleted all binary numbers of length 2, how many nodes would we have to delete?
false
false
false
false
0 deleted nodes
(since we still have pointers to
the nodes for length-3 binary strings)
Problem 1 (c)
false
false
false
false
0 1
true
true
0 1
true
true
0 1
true
true
0 1
true
true
0 1
true
0 1
true
0 1
true
From here, remove all binary strings of length 3 (e.g. "000"). How many nodes would disappear? Why?
false
false
false
false
false
false
false
false
12 deleted nodes (representing strings of length 2 and length 3)
Questions?
Thank You