## 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 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
```