DSAN 5500: Data Structures, Objects, and Algorithms in Python
Thursday, February 13, 2025
Today’s Planned Schedule:
| Start | End | Topic | |
|---|---|---|---|
| Lecture | 6:30pm | 6:40pm | W01 Reminders, HW2 \(\leadsto\) HW3 → |
| Lecture | 6:40pm | 7:05pm | DFS in Isolation → |
| 7:05pm | 7:30pm | BFS in Isolation → | |
| 7:30pm | 8:00pm | (Those Who Know…) It’s the Same Algorithm 🤯 → | |
| Break! | 8:00pm | 8:10pm | |
| 8:10pm | 9:00pm | The Scourge of Cycles (Graph Traversal) → |
You’re in Cuba…
…OR u just want that data sci BAG! 💰
LinkedList (Circular / jump-to-end / doubly-linked); non-scary OOP skeleton 🙈InventoryItem classitem_name and price__eq__(other), __ne__(other)__lt__(other), __le__(other), __gt__(other), __ge__(other)__repr__() and __str__()Depth-First Search (DFS)
Breadth-First Search (BFS)
from hw2 import LinkedList, InventoryItem, BinarySearchTree
bst = BinarySearchTree()
item1 = InventoryItem('Mango', 50)
bst.add(item1)
item2 = InventoryItem('Pickle', 60)
bst.add(item2)
item3 = InventoryItem('Artichoke', 55)
bst.add(item3)
item5 = InventoryItem('Banana', 123)
bst.add(item5)
item6 = InventoryItem('Aardvark', 11)
bst.add(item6)
HTML(visualize(bst))
from hw2 import IterAlgorithm, NodeProcessor
print("DFS:")
dfs_processor = NodeProcessor(IterAlgorithm.DEPTH_FIRST)
#print(type(dfs_processor.node_container))
dfs_processor.iterate_over(bst)
print("\nBFS:")
bfs_processor = NodeProcessor(IterAlgorithm.BREADTH_FIRST)
#print(type(bfs_processor.node_container))
bfs_processor.iterate_over(bst)DFS:
InventoryItem[item_name=Mango,price=50]
InventoryItem[item_name=Pickle,price=60]
InventoryItem[item_name=Artichoke,price=55]
InventoryItem[item_name=Banana,price=123]
InventoryItem[item_name=Aardvark,price=11]
BFS:
InventoryItem[item_name=Mango,price=50]
InventoryItem[item_name=Artichoke,price=55]
InventoryItem[item_name=Pickle,price=60]
InventoryItem[item_name=Aardvark,price=11]
InventoryItem[item_name=Banana,price=123]
Now that you have some intuition, you may be thinking that they might require very different code to implement 🤔
This is where mathematically-formal link between the two becomes ultra helpful!
It turns out (and a full-on algorithmic theory course makes you prove) that
\(\implies\) Literally identical code, “pulling out” the word stack and replacing it with the word queue within your code (or vice-versa).
Put your Software Engineer Hat on: this calls for an abstraction layer!
Queue and Stack work, and not asking you to implement it 🤨)NodeProcessor, with a single iterate_over(tree) functionThingContainer (could be a stack or a queue, you won’t know which), with two functions:
put_new_thing_in(new_thing)take_existing_thing_out()ThingContainer: The OOP Structure You See
root to container” (a ThingContainer object)| Procedure | Algorithm |
|---|---|
| Breadth-First Search | while [container not empty]:1. Take thing out 2. Print thing content 3. Add left child to container 4. Add right child to container |
| DFS Procedure | Algorithm |
|---|---|
| Pre-Order Traversal | 1. Print node 2. DFS left subtree 3. DFS right subtree |
| In-Order Traversal 🧐‼️ | 1. DFS left subtree 2. Print node 3. DFS right subtree |
| Post-Order Traversal | 1. DFS left subtree 2. DFS right subtree 3. Print node |
h('AA') = 0, h('AB') = 1, …, h('AZ') = 25,h('BA') = 26, h('BB') = 27, …, h('BZ') = 51,h('CA') = 52, …, h('ZZ') = 675.AlphaHasher vs. CustomHasher# @title define-alpha-hasher
from abc import ABC, abstractmethod
import string
class CustomHasher(ABC):
@abstractmethod
def __init__(self):
pass
@abstractmethod
def get_alphabet_size(self):
pass
@abstractmethod
def hash(self, str_to_hash: str) -> int:
pass
@abstractmethod
def compute_position_in_alphabet(self, uppercase_key: str) -> int:
pass
@abstractmethod
def compute_key_for_index(self, index: int) -> str:
pass
class AlphaHasher(CustomHasher):
def __init__(self):
self.alphabet_size = 26
def get_alphabet_size(self):
return self.alphabet_size
def hash(self, str_to_hash: str) -> int:
if len(str_to_hash) == 0:
first_letter = 'A'
else:
first_letter = str_to_hash.upper()[0]
# And return its index in the alphabet:
# 'A' has index 0, 'B' has index 1, etc.
return self.compute_position_in_alphabet(first_letter)
def compute_position_in_alphabet(self, uppercase_key: str) -> int:
return string.ascii_uppercase.index(uppercase_key)
def compute_key_for_index(self, index: int) -> str:
return string.ascii_uppercase[index]LinkedList via PolymorphicNodeEmptyNode \(\rightarrow\) ContentNode# @title define-linked-list
from abc import ABC, abstractmethod
class LinkedList:
def __init__(self):
self.root = EmptyNode()
def append(self, item):
self.root = self.root.append(item)
def find_item_steps(self, item):
return self.root.find_item_steps(item)
def to_string(self, recurse: bool):
return f'LinkedList[{self.root.to_string(recurse)}]'
def __repr__(self):
return self.to_string(recurse=True)
def __str__(self):
return self.to_string(recurse=False)
class PolymorphicNode(ABC):
@abstractmethod
def __init__(self):
pass
@abstractmethod
def append(self, item):
pass
@abstractmethod
def find_item_steps(self, item):
pass
@abstractmethod
def to_string(self, recurse: bool):
pass
def __repr__(self):
return self.to_string(recurse=True)
def __str__(self):
return self.to_string(recurse=False)
class EmptyNode(PolymorphicNode):
def __init__(self):
super().__init__()
def append(self, item):
"""
This is the only weird part of EmptyNode: because we want to utilize
*polymorphism*, when append() is called on an EmptyNode it
is "transformed into" a FilledNode! That is why, in the
LinkedList's append() function, we have self.root = self.root.append(),
and why the FilledNode's append() function works the same way
"""
#print("EmptyLinkedListNode.append()")
new_form = ContentNode(item)
return new_form
def find_item_steps(self, item):
return np.inf
def __len__(self):
return 0
def to_string(self, recurse: bool):
return ''
class ContentNode(PolymorphicNode):
def __init__(self, content_arg):
super().__init__()
self.content = content_arg
self.next = EmptyNode()
def append(self, item):
self.next = self.next.append(item)
# Return just *self*, since we *haven't* transformed the type of
# FilledLinkedListNode by appending another element to it
return self
def find_item_steps(self, item):
if self.content == item or self.content[0] == item:
return 1
return 1 + self.next.find_item_steps(item)
def get_content(self):
return self.content
def __len__(self):
return 1 + len(self.next)
def to_string(self, recurse: bool):
content_str = f'ContentNode[{str(self.get_content())}] '
if not recurse:
return content_str
next_str = str(self.next)
return f'{content_str}{self.next.to_string(recurse)}'InventoryItem (Part 3.1)# @title define-inventory-item
class InventoryItem:
def __init__(self, item_name_arg, price_arg):
self.item_name = item_name_arg
self.price = price_arg
def __lt__(self, other): # -> [NotImplemented | bool]:
if isinstance(other, InventoryItem):
return self.item_name < other.item_name
if isinstance(other, str):
return self.item_name < other
return NotImplemented
def __le__(self, other): # -> [NotImplemented | bool]
if isinstance(other, InventoryItem):
return self.item_name <= other.item_name
if isinstance(other, str):
return self.item_name <= other
return NotImplemented
def __gt__(self, other): # -> [NotImplemented | bool]
if isinstance(other, InventoryItem):
return self.item_name > other.item_name
if isinstance(other, str):
return self.item_name > other
return NotImplemented
def __ge__(self, other): # -> [NotImplemented | bool]
if isinstance(other, InventoryItem):
return self.item_name >= other.item_name
if isinstance(other, str):
return self.item_name >= other
return NotImplemented
def __eq__(self, other): # -> [NotImplemented | bool]
if isinstance(other, InventoryItem):
return self.item_name == other.item_name
if isinstance(other, str):
return self.item_name == other
return NotImplemented
def __ne__(self, other): # -> [NotImplemented | bool]
if isinstance(other, InventoryItem):
return self.item_name != other.item_name
if isinstance(other, str):
return self.item_name != other
return NotImplemented
def __repr__(self) -> str:
return self.__str__()
def __str__(self) -> str:
return f'InventoryItem[item_name={self.item_name},price={self.price}]'ThingContainer (Part 3.2)# @title define-thing-container
class ThingContainer:
def __init__(self):
self.internal_list = []
@abstractmethod
def put_new_thing_in(self, item):
pass
def is_empty(self) -> bool:
return self.__len__() == 0
def __len__(self):
return len(self.internal_list)
@abstractmethod
def take_existing_thing_out(self):
pass
class Stack(ThingContainer):
def __init__(self):
super().__init__()
def __push(self, item):
self.internal_list.append(item)
def __pop(self):
return self.internal_list.pop()
def put_new_thing_in(self, item):
return self.__push(item)
def take_existing_thing_out(self):
return self.__pop()
class Queue(ThingContainer):
def __init__(self):
super().__init__()
def put_new_thing_in(self, item):
return self.__enqueue(item)
def __enqueue(self, item):
self.internal_list.insert(0, item)
def __dequeue(self):
return self.internal_list.pop()
def take_existing_thing_out(self):
return self.__dequeue()AlphaHasher2 (Part 5)# @title define-alpha-hasher-2
class AlphaHasher2(CustomHasher):
def __init__(self):
self.alphabet_size = 26 * 26
def get_alphabet_size(self):
return self.alphabet_size
def hash(self, str_to_hash: str) -> int:
if len(str_to_hash) == 0:
first_two_letters = 'AA'
elif len(str_to_hash) == 1:
first_letter = str_to_hash.upper()[0]
second_letter = 'A'
else:
first_letter = str_to_hash.upper()[0]
second_letter = str_to_hash.upper()[1]
#print(f'First two letters for {str_to_hash}: {first_letter}{second_letter}')
# And return its index:
# 'AA' has index 0, 'AB' has index 1, etc.
first_letter_pos = AlphaHasher2.compute_position_in_alphabet(first_letter)
second_letter_pos = AlphaHasher2.compute_position_in_alphabet(second_letter)
# The position in the two-letter alphabet is just 26*first + second
final_pos = 26 * first_letter_pos + second_letter_pos
return final_pos
def compute_position_in_alphabet(self, uppercase_key: str) -> int:
if uppercase_key in string.ascii_uppercase:
return string.ascii_uppercase.index(uppercase_key)
return 0
def compute_key_for_index(self, index: int) -> str:
first_letter_part = int(index / 26)
second_letter_part = index % 26
# In case you need to debug!
#print(f'alpha2_index: {index}, first_letter_part: {first_letter_part}, second_letter_part: {second_letter_part}')
return string.ascii_uppercase[first_letter_part] + string.ascii_uppercase[second_letter_part]DSAN 5500 Week 6: Depth-First and Breadth-First Search