Data Structures and Algorithms part 1
Andy Novocin
Daily Problem
2-20
Find two functions \(f(n)\) and \(g(n)\) that satisfy the following relationship. If no such \(f\) and \(g\) exist, write "None".
- \(f(n) = o(g(n))\) and \( f(n) \neq \Theta(g(n))\)
- \(f(n) = \Theta(g(n))\) and \( f(n) = o(g(n))\)
- \(f(n) = \Theta(g(n))\) and \( f(n) \neq \mathcal{O}(g(n))\)
- \(f(n) = \Omega(g(n))\) and \( f(n) \neq \mathcal{O}(g(n))\)
- \(f(n) = \omega(g(n))\) and \( f(n) = \mathcal{O}(g(n))\)
Molecular Composition
The Atomic Structures:
Contiguous Arrays
Linked Structures
(The nuclei are objects or other structures)
Contiguous Arrays
Each entry is accessed instantly (with index)
A finite amount of space is allocated at a time
The entries are very tightly packed (great for RAM)
Overflow is an issue
Linked Objects
Objects which contain pointers to other objects
If sequential/linear then it is a linked list
With several outward pointers it is a graph
If a graph has no cycles then it is a tree
Linked Objects pros/cons
Adding and removing objects is simpler
Finding a specific object can be harder
No overflow (unless your machine is full)
Less memory efficient
Nuts and Bolts
An array can by expanded on the fly
Dynamic Arrays: if you need more space, allocate twice your length and move current items.
Say \(n = 2^{k} \) then final move hits \( \frac{n}{2} = 2^{k-1} \) things.
In the second-to-last move it was \( \frac{n}{4} = 2^{k-2} \) elements that moved.
In the \( i^{\textrm{th}}\) move there are \( \frac{n}{2^{k-i}} = 2^{i} \) moving elements.
\( 1 + 2 + 2^2 + \cdots + 2^{k-1} = 2^{k} - 1 = n - 1 \) moves
if you include the inserts then \( 2n \)
\( \frac{1}{2} + \frac{1}{4} + \cdots \to 1\)
Linked List Basic Ops
Can be singly linked or doubly linked.
How does one search in a linked list?
How does one insert into a linked list?
How does one delete from a linked list?
Data structures: API vs Implementation
Program to an interface, not an implementation.Head First Design Patterns
Most structures have versions of these:
Insert(p)Delete(p)
Our molecules all have APIs, the atoms are the implementations
Simple APIs
Stacks:
Push(x)
Pop()
Queues:
Enqueue(x)
Dequeue()
Remember The Cafeteria?
Stacks
Sample stack implementation
def IsEmpty(S):
if (S.top == 0):
return True
return False
def Push(s, x):
S.top = S.top + 1
S[S.top] = x
def Pop(S):
if IsEmpty(S):
Error "Underflow"
else:
S.top = S.top - 1
return S[S.top + 1]
Queues
Sample Queue implementation
def Enqueue(Q, x):
Q[Q.tail] = x
if (Q.tail == Q.length):
Q.tail = 1
else:
Q.tail = Q.tail + 1
def Dequeue(Q):
x = Q[Q.head]
if Q.head == Q.length:
Q.head = 1
else:
Q.head = Q.head + 1
return x
Wild and Crazy Plan
Rest of the class is group work
Peter and I will wander and help.
Some answers get presented
Dictionary API
Search(k)Insert(x)Delete(x)Successor(x)Previous(x)Min()Max()
What is the complexity of each when implemented with:
A) Singly Linked Unsorted List?
B) Doubly Linked Sorted List?
C) Sorted Array?
D) Unsorted Array?
Chapter 1
1-8 Prove the correctness of Horner's Method for polynomial evaluation:
Input: Coefficient Array for \(f(x) = a_0 + a_1 x + \cdots a_n x^n \), and \(t \) a real value
Output: \( f(t) \)
p = A[n]
for i from n-1 to 0:
p = p*t + A[i]
return p1-29 There are 25 horses, 5 race at a time. Find the fastest 3 using as few races as possible. How many races did you need?
Chapter 2
2-2 What value is returned by the following code (as a function of \(n\))? What is the big-oh complexity of the code?
r = 0
for i from 1 to n:
for j from 1 to i:
for k from j to i+j:
r = r + 1
return r