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".

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:


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


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 p

1-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

Prove \( \mathcal{O}()\) traits:

2-13, 2-15 Suppose: \( f_1(n) = \mathcal{O}(g_1(n))\) and \( f_2(n) = \mathcal{O}(g_2(n)) \)

Prove that: \( f_1(n) + f_2(n) = \mathcal{O}(g_1(n) + g_2(n)) \)

Prove that: \( f_1(n) \cdot f_2(n) = \mathcal{O}(g_1(n) \cdot g_2(n) ) \)

If you need more:


2-23 and 2-31


3-3 and 3-29

Next time: Trees


Also: C++ standard library