DATA Exam 1

Data (Definition)

Information or knowledge represented or coded in some form suitable for better usage or processing.

Data Structure (Definition)

Any data representation and its associated operations.

Algorithm (Definition)

In mathematics and computer science, a self-contained step-by-step set of operations to be performed.

The relationship between Algorithms and Data Structures

They should be thought of as a unit, neither one making sense without the other.

Two key aspects of Analysis of Algorithms

1. Time analysis: How many instructions does the algorithm execute? 2. Space analysis: How much memory does the algorithm need to execute?

The type of running time typically focused on in algorithm analysis

Worst-case running time, as it's easier to analyze and provides a bound for all possible inputs.

Primitive Operations (Definition)

Basic computations performed by an algorithm, assumed to take a constant amount of time in the RAM model.

Sum of the first N integers (∑i)

\frac{N\left(N+1\right)}{2} . For large N, this is approximately \frac{N^2}{2} .

Sum of the first N terms of a geometric series (∑A^i)

\frac{A^{N-1}-1}{A-1}

Logarithm Definition: logX​(B)=A

X^{A}=B

Logarithm Rule: loga​(AB)

\log_{a}A+\log_{a}B

Logarithm Rule: loga​(A/B)

\frac{\log_{a}A}{\log_{a}B}

Logarithm Rule: loga​(A^n)

n\log_{a}A

Logarithm Change of Base formula: logA​(B)

\frac{\log_2B}{\log_2A}

Big-Oh Notation (f(n)=O(g(n)))

f(n) ≤ g(n). Upper bound (possibly equal). f(n) grows at a rate no faster than g(n).

Big-Oh cheat

f(n) = O(g(n)) == f(n) ≤ g(n)

Formal definition of Big-Oh (f(n)=O(g(n)))

There are positive constants c and n₀ such that f(n) ≤ c⋅g(n) for all n ≥ n₀

Big-Omega Notation (f(n)=Ω(g(n)))

f(n) ≥ g(n). Lower bound (possibly equal). f(n) grows at a rate no slower than g(n).

Big-Omega cheat

f(n) = Ω(g(n)) == f(n) ≥ g(n)

Formal definition of Big-Omega (f(n)=Ω(g(n)))

There is a constant c > 0 and an integer constant n₀ ≥ 1 such that f(n) ≥ c⋅g(n) for n ≥ n₀.

Big-Theta Notation (f(n)=Θ(g(n)))

Growth rates are equal. It's the tightest description.

Big-Theta cheat

f(n) = Θ(g(n)) == f(n) = g(n)

Formal definition of Big-Theta (f(n)=Θ(g(n)))

There are constants c′>0 and c′′>0 and an integer constant n₀≥1 such that c′⋅g(n) ≤ f(n) ≤ c′′⋅g(n) for n ≥ n₀.

Little-oh Notation (f(n)=o(g(n)))

Upper bound (not equal). f(n) grows strictly slower than g(n).

Little-oh cheat

f(n) = o(g(n)) == f(n) < g(n)

Limit definition for Little-oh (f(n) = o(g(n)))

lim_n→∞​g(n)f(n)​ = 0.

Little-Omega cheat

f(n) = ω(g(n)) == f(n) > g(n)

Big-Oh Rule 1(Addition)

If T₁(N)=O(f(N)) and T₂(N)=O(g(N)), then T_1​(N)+T_2​(N)=max(O(f(N)),O(g(N))). (Drop lower-order terms).

Big-Oh Rule 2 (Multiplication)

If T_1​(N)=O(f(N)) and T_2​(N)=O(g(N)), then T₁(N)⋅T₂(N)=O(f(N)⋅g(N)).

Big-Oh Rule for Polynomials

If T(N) is a polynomial of degree k, then T(N)=Θ(N^k). (Drop lower-order terms and constant factors).

Time Complexity Rule 1: For Loops

Running time = (running time of statements inside the loop) × (number of iterations).

Time Complexity Rule 2: Nested Loops

Analyze inside out. Running time of statements inside × the product of loop sizes. Example: nested loops of size N and M is O(N⋅M).

Time Complexity Rule 3: Consecutive Statements

Add them, and the complexity is the maximum of the individual running times.

Time Complexity Rule 4: If/Else

Running time = (running time of the test) + max(running time of S_1​, running time of S_2​).

Rule for Simple Recursive Function (e.g., Factorial)

O(N) because the function calls itself once and reduces N by 1 each time until the base case.

Rule for Fibonacci-like Recursion (T(N)=T(N−1)+T(N−2)+C)

Almost doubles each time, resulting in exponential growth. This is a very slow algorithm.

List ADT Operations

printList, makeEmpty, find, insert (at position), remove (at position), findKth.

ArrayList - Underlying implementation

A growable array implementation of List.

LinkedList - Underlying implementation

A doubly linked list implementation.

ArrayList: get() and set() complexity

O(1) (Constant Time).

LinkedList: get() and set() complexity

O(N) (Linear Time).

ArrayList: add/remove at end complexity

O(1) (Constant Time).

LinkedList: add/remove at end complexity

O(1) (Constant Time).

ArrayList: add/remove at front complexity

O(N) (Linear Time) because elements must be shifted.

LinkedList: add/remove at front complexity

O(1) (Constant Time).

Advantage of ArrayList

Most efficient if you need random access through an index without frequent insertions/removals, except at the end.

Advantage of LinkedList

Best if your application requires frequent insertion or deletion of elements from the beginning or middle.

Stack ADT definition

A list with the restriction that insertions and deletions can only happen from the end called top.

Stack fundamental scheme

Last In, First Out (LIFO).

Main Stack Operations

1. Push: Insertion. 2. Pop: Deletion (removes and returns top element). 3. Top (or peek): Returns top element without removing it.

Time complexity for all main Array-based Stack operations (push, pop, top)

O(1) (Constant Time).

Application of Stack: Balancing Symbols

Used to check if every right symbol (brace, bracket, parenthesis) corresponds to its left counterpart.

Application of Stack: Evaluating Postfix Expressions (Algorithm logic)

When an operand is seen, push it onto the stack. When an operator is seen, pop two operands, apply the operator, and push the result back onto the stack.

Application of Stack: Infix to Postfix Conversion (Parentheses rule)

If a right parenthesis is seen, pop the stack, writing symbols to output until the left parenthesis is seen, which is popped but not output.

Application of Stack: Method Calls (JVM)

The Java Virtual Machine (JVM) uses a stack to keep track of active methods, pushing a frame when a method is called and popping it when the method ends.

How to implement Two Stacks in One Array to maximize space utilization

Have one stack grow from the left to the right and the other from the right to the left. They overflow only when their top elements are adjacent.

Queue ADT definition

A data structure where insertions and deletions follow the First-In, First-Out (FIFO) scheme.

Queue operations: enqueue and dequeue

enqueue(o): Inserts an element at the rear of the queue. dequeue(): Removes and returns the element at the front of the queue.

Implementation using a fixed-size array is called a Circular Queue because...

The indices wrap around: if the back index reaches the end of the array, it moves to the beginning.

Time complexity for all main Array-based (Circular) Queue operations (enqueue, dequeue)

O(1) (Constant Time).

Application of Queue: Jobs to a printer

Jobs are arranged and processed in order of arrival (FIFO).

Application of Queue: Round Robin Schedulers

A round robin scheduler can be implemented using a queue to repeatedly dequeue, service, and then enqueue the element.

How to implement a Queue using Two Stacks (enqueue operation)

Push the new element onto Stack1.

How to implement a Queue using Two Stacks (dequeue operation)

If Stack2 is empty, pop all elements from Stack1 and push them onto Stack2. Then, pop and return the top element from Stack2. (Each element is pushed twice and popped twice for a total O(1)[cites​tart] amortized cost).

Binary Tree

A tree in which no node can have more than two children.

Binary Search Tree (BST)

A binary tree where for every node X: 1. Values in the left subtree are smaller than X. 2. Values in the right subtree are larger than X.

Inorder Traversal (for binary trees)

Left child, Parent, Right child. Used to retrieve elements in sorted order from a BST.

Preorder Traversal

Parent, Left child, Right child. Used to print a directory (parent name before children).

Postorder Traversal

Left child, Right child, Parent. Used for processing children before the parent, such as summing file sizes.

AVL Tree

A Binary Search Tree with a balance condition. The height of the left and right subtree of any node can differ by at most 1.

Average running time for all BST operations (contains, insert, remove, etc.)

O(logN) for an average tree. For an AVL tree, all operations are guaranteed to be O(logN).

Worst-case height of a standard BST

Can be as large as N−1 (if inserts result in a skewed list).

Single Rotation (in AVL Tree)

Performed to restore balance for "left-left" or "right-right" imbalance cases.

Double Rotation (in AVL Tree)

Performed to restore balance for "left-right" or "right-left" imbalance cases.

Strategy for deleting a node with two children in a BST

Replace the node with the smallest data in its right subtree and recursively delete that node.