GOAT Notes: Data Structures

BEN FROST
GOAT NOTES: DATA STRUCTURES (CSC2001F)
Analysis of Algorithms:

Empirical Analysis:
Running implementations of multiple different algorithms and seeing
which one is fastest.

- Algorithms have to be implemented before any insight on their
speed can be gained.
- Should actual, random or adversarial data be used for testing?
- Scaling of testing can be impractical.
- Important to identify which parts of programs influence speed
most.

Algorithm Analysis:
Carrying out mathematical analysis on algorithms while they are
still abstract.

- Algorithms do not need to be implemented before any insight on
their speed can be gained.
- Enables performance predictions to be made before any code needs
to be implemented or run.
- Important to consider factors such as resource usage including
hardware availability and the chosen programming language.
- Abstract operations need to be identified and counted.

Asymptotic Analysis ~ Determining the bounds on resources needed as
the size of data needing to be processed increases.

Time-Complexity Analysis ~ The consideration of Best, Average &
Worst cases.

N ~ The primary parameter affecting run-time. (typically represents
input data size)

Use some basic operation to create an operation(y) = input(N) data
function: f(N)

When considering functions only consider the N term of the highest
order.

Asymptotic Analysis:
Big-O Notation is a type of asymptotic analysis in which f(N) is
bounded by a multiple of g(N), for N of the highest order.

f(N) is O(g(N)) if g(N) grows as fast or faster than f(N)


1

, BEN FROST
Formal Definition: f(N) is O(g(N)) if there exists a positive real
number M and a real number NO such that:
|f(N)| <= M x g(N) for all N>=NO
Big-O Examples:

3N2 + N -> O(N2)
N2 -> O(N2)
1000N + 500 -> O(N)
N(N + log(N)) -> O(N2)

Other Types of Asymptotic Analysis:




Order of Common Growth Functions:




Algorithm Trade-Offs:
Time-Space ~ Using additional memory to make operations faster.
~ Using slower operations to reduce memory requirements.

Time-Time ~ Insertion Time vs Search Time

Data Structures:

Intro to Data Structures:


2

, BEN FROST
A data structure is an efficient mechanism to store data and
provide access operations.
- Can be in-memory or on-disk.
- In-memory is faster.
- On-disk is larger & non-volatile.
Maps ~ An abstract data type of items with keys and values that
support two main operations; the insertion of a new item with a
specified key and the search and return of an item with a specified
key. (aka symbol table, dictionary, or associative array)

Map Operations:
-Create -Sort
-Insert -Select
-Delete -Join
-Search -isEmpty
-Traverse -Size

Map Implementations:

Array:
- Indices = Integer Keys
- Insert, Search, Remove in constant time.
- Select and Sort in Linear Time. Worst case; iterate
through whole array, N.

Singly Linked List:
- Node = Value & Key
- Search in linear time. Worst case; N. Avg. Case; N/2.
- Search + insert in linear time. Worst case; N. Avg.
Case; N.




Doubly Linked List:




Map Data Structures & Time Complexity:




3

, BEN FROST




Recursion in Data Structures:

Recursive Algorithm ~ Solves a problem by solving one or more
smaller instances of the same problem.

Recursive Method ~ A method that calls itself and has a base case
to end its recursion. Any returned value is stored in the method’s
continuous “stack”.

Any recursive method can generally be converted into an iterative
one and vice versa.

Examples:

Addition of Integers 1 to n:

public int sum(int n) {
Stack when n = 4:
// Base Case:
if (n == 0) R1: 4 + sum(3)
{ R2: 4 + 3 + sum(2)
return 0; R3: 4 + 3 + 2 + sum(1)
} R4: 4 + 3 + 2 + 1 + sum(0)
else R5: 4 + 3 + 2 + 1 + 0
{
// Recursive Call: RESULT = 10
return n + sum(n-1);
}
}




Printing out an Integer Array:

public void print(int start, int stop) {

// Base Case:
4