Data Structures and Algorithms part 1

Andy Novocin

Daily Problem


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







Remember The Cafeteria?


Sample stack implementation

def IsEmpty(S):
  if ( == 0):
    return True
  return False
def Push(s, x): = + 1
  S[] = x
def Pop(S):
  if IsEmpty(S):
    Error "Underflow"
  else: = - 1
  return S[ + 1]


Sample Queue implementation

def Enqueue(Q, x):
  Q[Q.tail] = x
  if (Q.tail == Q.length):
    Q.tail = 1
    Q.tail = Q.tail + 1
def Dequeue(Q):
  x = Q[Q.head]
  if Q.head == Q.length:
    Q.head = 1
    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