DSAN 5500: Data Structures, Objects, and Algorithms in Python
Today’s Planned Schedule:
| Start | End | Topic | |
|---|---|---|---|
| Lecture | 6:30pm | 7:00pm | Object-Oriented Programming (OOP) → |
| 7:00pm | 7:30pm | LinkedList: Lists from Scratch → |
|
| 7:30pm | 8:00pm | Other Data Structures = Fancy Linked Lists → | |
| Break! | 8:00pm | 8:10pm | |
| 8:10pm | 9:00pm | HashTable: Logarithmic to Constant Efficiency 🤯 → |
.py files may be easier than .ipynb for development! Can you think of why?)
Screen class, another person can write the Button class, and so onScreen team doesn’t need to know the internal details of Button (just it’s API), and vice-versapublic_var_protected_var__private_varclass MySecretInfo:
__the_info = "I love Carly Rae Jepsen"
info_obj = MySecretInfo()
info_obj.__the_info--------------------------------------------------------------------------- AttributeError Traceback (most recent call last) Cell In[1], line 5 2 __the_info = "I love Carly Rae Jepsen" 4 info_obj = MySecretInfo() ----> 5 info_obj.__the_info AttributeError: 'MySecretInfo' object has no attribute '__the_info'
Guess we can’t access it then, right? 😮💨
info_obj._MySecretInfo__the_info'I love Carly Rae Jepsen'print()?print() (through __str__()) takes on many (!) forms (!): each type of object has its own implementation of __str__()
class Bookstore:
def __init__(self, name, location):
self.name = name
self.location = location
self.books = []
def __getitem__(self, index):
return self.books[index]
def __repr__(self):
return self.__str__()
def __str__(self):
return f"Bookstore[{self.get_num_books()} books]"
def add_books(self, book_list):
self.books.extend(book_list)
def get_books(self):
return self.books
def get_inventory(self):
book_lines = []
for book_index, book in enumerate(self.get_books()):
cur_book_line = f"{book_index}. {str(book)}"
book_lines.append(cur_book_line)
return "\n".join(book_lines)
def get_num_books(self):
return len(self.get_books())
def sort_books(self, sort_key):
self.books.sort(key=sort_key)
class Book:
def __init__(self, title, authors, num_pages):
self.title = title
self.authors = authors
self.num_pages = num_pages
def __str__(self):
return f"Book[title={self.get_title()}, authors={self.get_authors()}, pages={self.get_num_pages()}]"
def get_authors(self):
return self.authors
def get_first_author(self):
return self.authors[0]
def get_num_pages(self):
return self.num_pages
def get_title(self):
return self.title
class Person:
def __init__(self, family_name, given_name):
self.family_name = family_name
self.given_name = given_name
def __repr__(self):
return self.__str__()
def __str__(self):
return f"Person[{self.get_family_name()}, {self.get_given_name()}]"
def get_family_name(self):
return self.family_name
def get_given_name(self):
return self.given_namemy_bookstore = Bookstore("Bookland", "Washington, DC")
plath = Person("Plath", "Sylvia")
bell_jar = Book("The Bell Jar", [plath], 244)
marx = Person("Marx", "Karl")
engels = Person("Engels", "Friedrich")
manifesto = Book("The Communist Manifesto", [marx, engels], 43)
elster = Person("Elster", "Jon")
cement = Book("The Cement of Society", [elster], 311)
my_bookstore.add_books([bell_jar, manifesto, cement])
print(my_bookstore)
print(my_bookstore[0])
print("Inventory:")
print(my_bookstore.get_inventory())Bookstore[3 books]
Book[title=The Bell Jar, authors=[Person[Plath, Sylvia]], pages=244]
Inventory:
0. Book[title=The Bell Jar, authors=[Person[Plath, Sylvia]], pages=244]
1. Book[title=The Communist Manifesto, authors=[Person[Marx, Karl], Person[Engels, Friedrich]], pages=43]
2. Book[title=The Cement of Society, authors=[Person[Elster, Jon]], pages=311]sort_alpha = lambda x: x.get_first_author().get_family_name()
my_bookstore.sort_books(sort_key = sort_alpha)
print(my_bookstore.get_inventory())0. Book[title=The Cement of Society, authors=[Person[Elster, Jon]], pages=311]
1. Book[title=The Communist Manifesto, authors=[Person[Marx, Karl], Person[Engels, Friedrich]], pages=43]
2. Book[title=The Bell Jar, authors=[Person[Plath, Sylvia]], pages=244]sort_pages = lambda x: x.get_num_pages()
my_bookstore.sort_books(sort_key = sort_pages)
print(my_bookstore.get_inventory())0. Book[title=The Communist Manifesto, authors=[Person[Marx, Karl], Person[Engels, Friedrich]], pages=43]
1. Book[title=The Bell Jar, authors=[Person[Plath, Sylvia]], pages=244]
2. Book[title=The Cement of Society, authors=[Person[Elster, Jon]], pages=311]
Book
from enum import Enum
class BookType(Enum):
NONFICTION = 0
FICTION = 1
class Book:
def __init__(self, title: str, authors: list[Person], num_pages: int, type: BookType):
self.title = title
self.authors = authors
self.num_pages = num_pages
self.type = type
def __str__(self):
return f"Book[title={self.title}, authors={self.authors}, pages={self.num_pages}, type={self.type}]"joyce = Person("Joyce", "James")
ulysses = Book("Ulysses", [joyce], 732, BookType.FICTION)
schelling = Person("Schelling", "Thomas")
micromotives = Book("Micromotives and Macrobehavior", [schelling], 252, BookType.NONFICTION)
print(ulysses)
print(micromotives)Book[title=Ulysses, authors=[Person[Joyce, James]], pages=732, type=BookType.FICTION]
Book[title=Micromotives and Macrobehavior, authors=[Person[Schelling, Thomas]], pages=252, type=BookType.NONFICTION]# class Book defined as earlier
class FictionBook(Book):
def __init__(self, title, authors, num_pages, characters):
super().__init__(title, authors, num_pages)
self.characters = characters
class NonfictionBook(Book):
def __init__(self, title, authors, num_pages, topic):
super().__init__(title, authors, num_pages)
self.topic = topicjoyce = Person("Joyce", "James")
ulysses = FictionBook("Ulysses", [joyce], 732, ["Daedalus"])
schelling = Person("Schelling", "Thomas")
micromotives = NonfictionBook("Micromotives and Macrobehavior", [schelling], 252, "Economics")
print(ulysses)
print(micromotives)Book[title=Ulysses, authors=[Person[Joyce, James]], pages=732]
Book[title=Micromotives and Macrobehavior, authors=[Person[Schelling, Thomas]], pages=252]LinkedListclass MyTuple:
def __init__(self, thing1, thing2):
self.thing1 = thing1
self.thing2 = thing2
def __repr__(self):
return f"({self.thing1}, {self.thing2})"
def __str__(self):
return self.__repr__()
t1 = MyTuple('a','b')
t2 = MyTuple(111, 222)
print(t1)
print(t2)(a, b)
(111, 222)The list itself just points to a root item:
class MyList:
def __init__(self):
self.root = None
def append(self, new_item):
if self.root is None:
self.root = MyListItem(new_item)
else:
self.root.append(new_item)
def __repr__(self):
return self.root.__repr__()An item has contents, pointer to next item:
class MyListItem:
def __init__(self, content):
self.content = content
self.next = None
def append(self, new_item):
if self.next is None:
self.next = MyListItem(new_item)
else:
self.next.append(new_item)
def __repr__(self):
my_content = self.content
return my_content if self.next is None else f"{my_content}, {self.next.__repr__()}"users = MyList()
users.append('Jeff')
users.append('Alma')
users.append('Bo')
print(users)Jeff, Alma, BoMyTuple?MyTuple?MyList?MyList?With a MyTuple:
t1.thing1'a'\(\implies\) 1 step
t1.thing2'b'\(\implies\) 1 step
With a MyList:
print(users.root.content)Jeff\(\implies\) 1 step
current_node = users.root
while current_node.next is not None:
current_node = current_node.next
print(current_node.content)Bo\(\implies\) (3 steps)
…But why 3? How many steps if the list contained 5 elements? \(N\) elements?
LinkedListsfrom hw2 import LinkedList, InventoryItem
ll = LinkedList()
item1 = InventoryItem('Mango', 50)
ll.append(item1)
item2 = InventoryItem('Pickle', 60)
ll.append(item2)
item3 = InventoryItem('Artichoke', 55)
ll.append(item3)
item5 = InventoryItem('Banana', 123)
ll.append(item5)
item6 = InventoryItem('Aardvark', 11)
ll.append(item6)
HTML(visualize_ll(ll))
class LinkedList(BaseModel):
root: LinkedListNode | Noneclass LinkedListNode(BaseModel):
content: object
next: LinkedListNode | None
class BinaryTree(BaseModel):
root: BinaryTreeNode | Noneclass BinaryTreeNode(BaseModel):
content: object
left: BinaryTreeNode | None
right: BinaryTreeNode | None
class QuadTree(BaseModel):
root: QuadTreeNode | Noneclass QuadTreeNode:
content: object
nw: QuadTreeNode | None
ne: QuadTreeNode | None
sw: QuadTreeNode | None
se: QuadTreeNode | NoneBinarySearchTreefrom hw2 import 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))Warning: node None_0, port f1 unrecognized
Warning: node None_1, port f1 unrecognized
Warning: node None_2, port f1 unrecognized
Warning: node None_3, port f1 unrecognized
Warning: node None_4, port f1 unrecognized
Warning: node None_5, port f1 unrecognized
key)price_list = []
price_list.append(('Banana', 10))
price_list.append(('Apple', 2))
price_list.append(('Four Loko', 5))
price_list[('Banana', 10), ('Apple', 2), ('Four Loko', 5)]\[ T(n) = \overline{O}(1 + \underbrace{\epsilon}_{\mathclap{\text{Collision rate}}} \cdot n) \]
\[ p^{✅} = [T(n) = \overline{O}(1 + \epsilon n)], q^{✅} = [\epsilon \approx 0],\text{ so } p \wedge q \implies T(n) \overset{✅}{=} \overline{O}(1). \]
hash(item) = first letter of item\[ h(\texttt{x}) = \texttt{x[0]} \]
h('Banana') = 'B', h('Monkey') = 'M'item hashes to'Banana'), we compute the hash (B), look in that slot, and obtain the price for bananas.h('Blueberries') = 'B'B slot and see that (Bananas, 10) is already there!!! Wtf do we do here… don’t panic!LinkedList that we can use whenever and however we want!LinkedList? Why not just… another length-26 array, for example?B (or, if we do, we want to be able to expand/contract our price list to handle new/discontinued items)HashTable is an Array that “degenerates into” a LinkedList (when there are collisions)LinkedList) was \(\overline{O}(n)\) for everythihgLinkedListBinarySearchTree (BST)LinkedList, we’ll be able to take our HashMap from today and “drop in” the BST to play the role the LinkedList is playing right nowBST with its \(\overline{O}(\log(n))\) operations, rather than a LinkedList with its \(\overline{O}(n)\) operationsHashMap will go from: