W1D5 - Abstract Data Types/Structures
Topics
Abstract Data Types - the abstract set of data types
Agnostic to programming language
ADTs can be made using several specific data structures, as long as they retain the same functionality/have the same public API
Set - collection of objects such that each object either exists or does not exist in the set (all are unique, no duplicates)
include - add to set
query - check if in set
remove - from set
Map
set - value from key (must check whether key already exists)
get - value from key
delete - by key
HashMap - most common way of implementing a Map
Stack
LIFO - Last In, First Out (considered unfair)
Similar to cafeteria trays
push/pop || shift/unshift - push/pop most common
Queue
FILO - First In, First Out (considered fair)
dequeueing - take object away from front of queue
enqueue -- add object ot end of queue
Similar to line at the register
push/shift || pop/unshift
Trees
Parent-child relationships where each child has at most 1 parent
Trees have directionality
Root/Base - single node with no children
Empty tree is still a tree!
Binary - max 2 children per node
Ternary - max 3 children per node
Unary - max 1 child per node (also called a Linked List)
Polytree / N-ary Tree - a tree with no guarantee of its number of children
Subtrees often named/referenced by root
Tree Traversal & Tree Searching Algorithms
Depth First Search (BFS) - use a Stack, recursion
Breadth First Search (DFS) - use a Queue, iterative
Very useful for predicting the outcome of a game/set of steps
Projects
PolyTreeNode class - a class for defining an uncapped number of children for a given node
@parent, @children, @value
@parent= - set new parent and update new & old parent as well as child's instance variables
add_child(child_node)
remove_child(child)
dfs(target_value) - Depth First tree searching algorithm to find a given child node
bfs(target_value) - Breadth First tree searching algorithm to find a given child node
Knight's Travails - find all the possible positions a knight can get to from a given starting position on a chess board. Find the shortest path to get from one tile to another.
Tic-Tac-Toe AI - Build an AI that can predict all possible winning/losing moves in a polytree, so that it always to chooses a move that will not allow it to lose. It's unbeatable!
Learnings
Traversing Trees is cool!!
Although technically Depth First Search visits & checks all of the leaves before the upper branches, it is more efficient to check a given node when you first reach it. So developers generally check a parent before all its children, even on its way down to the roots.
attr_accessor / attr_reader - make a setter & getter method for instance variables that have the same name as the instance variable.
public vs private
public methods are available to all objects of all classes
private methods - available only to objects of the same class
private instance variable methods -- vailable only to the object itself (cannot be called by different objects of the same class
class methods
defined as self.method_name
called as ClassName.method_name
Ampersand & in &prc is used to convert in both directions:
Block --> Proc
Proc --> Block
Generally used as method_name(&prc)
Exception Handling
begin
regular body of code
rescue OneTypeOfException
What to do for this exception
rescue AnotherTypeOfException
What to do for this type of exception
else
What to do for all all other exceptions
ensure
Will always be executed
end
Partner: Jie Wei