COMPSCI SG FINAL

Algorithm Efficiency

// Algorithm Efficiency: Linear vs Constant time
void example(int[] arr) {
System.out.println(arr[0]); // O(1)
for (int i : arr) { // O(n)
System.out.println(i);
}
}

Growth Functions of a program

// Growth Function Example
void growthExample(int n) {
for (int i = 0; i < n; i++) { // O(n)
for (int j = 0; j < n; j++) { // O(n)
System.out.println(i + j); // Total O(n^2)
}
}
}

Asymptotic Complexity of an algorithm

// Asymptotic Complexity: ignores lower order terms
void example(int n) {
int count = 0;
for (int i = 0; i < n; i++) count++; // O(n)
for (int j = 0; j < 1000; j++) count++; // O(1)
// Overall: O(n)
}

Big-O Notation

// Big-O: Upper bound for growth
void logExample(int n) {
while (n > 1) {
n /= 2;
System.out.println(n);
} // O(log n)
}

Big-O/order Categories

// Big-O Categories
// O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n)

Comparing Growth Functions and orders

// Comparing growths
// Linear: O(n), Quadratic: O(n^2)
// n = 1000 → n = 1000, n^2 = 1,000,000

Analyzing Loop/Nested loops Execution

// Loop Analysis
void nestedLoops(int n) {
for (int i = 0; i < n; i++) { // O(n)
for (int j = 0; j < n; j++) { // O(n)
System.out.println(i * j); // O(n^2)
}
}
}

ADT

// Abstract Data Type (ADT) Example: Stack
interface StackADT {
void push(T item);
T pop();
boolean isEmpty();
}

Stack

// Stack with Java
Stack stack = new Stack<>();
stack.push(10);
System.out.println(stack.pop()); // 10

Linear and Non-Linear Collections

// Linear: ArrayList, Stack, Queue
// Non-Linear: Tree, Graph

Stack Operations

// Stack Operations
Stack stack = new Stack<>();
stack.push(1); // add
stack.peek(); // top
stack.pop(); // remove
stack.isEmpty(); // check empty

The concept of Implementation of Stacks

// Stack using array
class ArrayStack {
int[] data = new int[100];
int top = -1;

void push(int x) { data[++top] = x; }
int pop() { return data[top--]; }

}

Idea of applications of stack

// Applications of Stack
// Expression evaluation, Undo feature, DFS in graphs

Linked Structures

// Linked Node
class Node {
int data;
Node next;
Node(int d) { data = d; next = null; }
}

Linked Lists

// Singly Linked List insert
Node head = new Node(1);
head.next = new Node(2);

What is a queue? Queue’s features.

// Queue: FIFO
Queue q = new LinkedList<>();
q.add(1); q.add(2);
System.out.println(q.remove()); // 1

Operations of queue

// Queue Operations
Queue q = new LinkedList<>();
q.add(10); // enqueue
q.remove(); // dequeue
q.peek(); // front

Implementation of queue

// Queue using array
class Queue {
int[] arr = new int[100];
int front = 0, rear = 0;

void enqueue(int x) { arr[rear++] = x; }
int dequeue() { return arr[front++]; }

}

What is a list?

// List: ordered collection
List list = new ArrayList<>();
list.add(5); list.add(10);

Three types of list collections

// Types of Lists
// ArrayList, LinkedList, Vector

Standard Linkedlist in Java

// LinkedList in Java
LinkedList list = new LinkedList<>();
list.add("A");
list.add("B");

Recursion

// Recursion Example
int factorial(int n) {
if (n == 0) return 1;
return n * factorial(n - 1);
}

Recursive Definitions

// Fibonacci recursively
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}

Infinite Recursion

// Infinite Recursion (no base case)
void infinite() {
infinite();
}

Recursion in Math

// Recursion: factorial
// n! = n * (n-1)!

Recursive Programming

// Print 1 to n
void print(int n) {
if (n == 0) return;
print(n - 1);
System.out.println(n);
}

Recursion vs. Iteration

// Compare Recursion vs Iteration
// Recursion: concise, more memory
// Iteration: efficient, less stack usage

Linear Search

// Linear Search
int search(int[] arr, int x) {
for (int i = 0; i < arr.length; i++)
if (arr[i] == x) return i;
return -1;
}

Binary Search

// Binary Search (sorted array)
int binarySearch(int[] a, int x) {
int l = 0, r = a.length - 1;
while (l <= r) {
int m = (l + r) / 2;
if (a[m] == x) return m;
if (a[m] < x) l = m + 1;
else r = m - 1;
}
return -1;
}

Comparing Search Algorithms

// Linear: O(n), Binary: O(log n) (sorted only)

Selection Sort

// Selection Sort
void selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
for (int j = i + 1; j < arr.length; j++)
if (arr[j] < arr[min]) min = j;
int t = arr[i]; arr[i] = arr[min]; arr[min] = t;
}
}

Insertion Sort

// Insertion Sort
void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) { int key = arr[i], j = i - 1; while (j >= 0 && arr[j] > key)
arr[j + 1] = arr[j--];
arr[j + 1] = key;
}
}

Merge Sort

// Merge Sort
void mergeSort(int[] arr, int l, int r) {
if (l < r) {
int m = (l + r) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}

Comparing Sorts

// Time Complexity:
// Selection & Insertion: O(n^2)
// Merge Sort: O(n log n)

Trees

// Binary Tree Node
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}

Binary search in a sorted array

// Binary search - see earlier card

Tree Traversals

// Inorder Traversal
void inorder(TreeNode root) {
if (root != null) {
inorder(root.left);
System.out.print(root.val + " ");
inorder(root.right);
}
}

Create a binary with given numbers

// Tree with numbers 5, 3, 7
TreeNode root = new TreeNode(5);
root.left = new TreeNode(3);
root.right = new TreeNode(7);

What is a Graph?

// Graph: set of nodes and edges
// Directed/Undirected, Weighted/Unweighted

Terminologies of graph

// Terms: vertex, edge, degree, path, cycle

Graph Representations

// Adjacency List
Map

Graph Traversal

// DFS
void dfs(int v, boolean[] visited, List