DSAN 5500: Data Structures, Objects, and Algorithms in Python
Today’s Planned Schedule:
| Start | End | Topic | |
|---|---|---|---|
| Lecture | 6:30pm | 7:00pm | Inductive Thinking → |
| 7:00pm | 7:30pm | LinkedList: Our Core Linear Data Structure → |
|
| 7:30pm | 8:00pm | BinarySearchTree aka FancyLinkedList → |
|
| Break! | 8:00pm | 8:10pm | |
| 8:10pm | 9:00pm | HashTable: The Final Missing Piece! → |
(What I should have done on the board)
| \(n\) | \(f(n)\) | Prime? |
|---|---|---|
| 0 | 41 | ✅ |
| 1 | 43 | ✅ |
| 2 | 47 | ✅ |
| 3 | 53 | ✅ |
| \(\vdots\) | \(\vdots\) | ✅ |
| \(n\) | \(f(n)\) | Prime? |
|---|---|---|
| 38 | 1523 | ✅ |
| I can stop checking now right? | ||
| 39 | 1601 | ✅ |
| Surely I’ve checked enough terms? | ||
| 40 | 1681 | ❌ \(1681 = 41 \times 41\) 💀 |
| Maybe that’s the only exception? | ||
| 41 | 1763 | ❌ \(1763 = 41 \times 43\) 💀 |
| Maybe we can get composites \(n > 41\)? | ||
| 42 | 1847 | ✅ 💀💀💀 USELESS! |
\[ \sum_{i=0}^{1} = 0 + 1 \overset{?}{=} \frac{(1)(1+1)}{2} \iff 1 \overset{?}{=} \frac{2}{2} \iff 1 \overset{✅}{=} 1 \]
\[ \begin{align*} \boxed{\sum_{i=0}^{n+1}i} &= \underbrace{0 + 1 + 2 + \cdots + n}_{\sum_{i=0}^{n}i} + (n+1) = \underbrace{\sum_{i=0}^{n}i}_{\mathclap{\text{LHS of }p(n)}} + (n+1) \\ &= \frac{n(n+1)}{2} + (n + 1) = \frac{n^2 + n}{2} + \frac{2(n+1)}{2} \\ &= \frac{n^2 + 3n + 2}{2} = \boxed{\frac{(n+1)(n+2)}{2}} \; ~ ✅ \end{align*} \]
“Direct” proof, in this case, is doable but requires stuff like…
Break into [Case 1: \(n\) even] and [Case 2: \(n\) odd]
In case 2
\[ \sum_{i=0}^{n}i = 1 + 2 + \cdots + \left( \left\lceil \frac{n}{2} \right\rceil - 1\right) + \left\lceil \frac{n}{2} \right\rceil + \left( \left\lceil \frac{n}{2} \right\rceil + 1\right) + \cdots + (n-1) + n \]
Need to show (…with induction?) \(\left\lceil \frac{n}{2} \right\rceil = \begin{cases}\frac{n}{2} &\text{if }n\text{ even} \\ \frac{n+1}{2} &\text{if }n\text{ odd}\end{cases}\)
And so on…
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)