unit 3

Algorithm

A set of rules or instructions for completing a task, applicable to both humans (e.g., a recipe) and computers.

Standard flowchart symbols and their functions

• Rectangle: Action or processing step
• Diamond: Yes/no decision that branches the flow
• Oval: Start or end point

Stack

A data structure adhering to the LIFO (Last In, First Out) rule where only the top element is accessible. Elements are added via push and removed via pop.

Primary advantage of using a Stack

Uses less memory than other structures, making it the most efficient choice when a problem only requires access to the most recent element.

Linked List

A data structure where each element holds data and a pointer to the next element, ending in null. It requires sequential access but allows efficient middle insertion and deletion.

Array

A data structure with elements accessed via a 0-based index, providing random access to jump directly to any position.

Core tradeoffs between Stack, Linked List, and Array

• Stack: Minimal memory, but only top element is accessible
• Linked List: Easy mid-sequence insertion/deletion, but sequential access only
• Array: Random access, but larger memory footprint

2D array indexing

Accesses elements using two 0-based indices representing $(row, column)$, such as board[3,5].

Linear Search

A search algorithm that checks every element sequentially from the start until found. Works on unsorted data, but slow for large datasets.

Binary Search (requirement and mechanism)

Requires sorted data. It repeatedly checks the middle element and discards the half that cannot contain the target.

Jump Search

A search algorithm for sorted data that advances in fixed-size steps of −−−−−\n\sqrt{n} until overshooting the target, then performs a linear search within that section.

Bubble Sort

A sorting algorithm that repeatedly compares adjacent pairs and swaps them if out of order, shifting the largest remaining value to the end each pass.

Binary Insertion Sort

A sorting algorithm that takes unsorted elements one by one and uses binary search to find their correct insertion positions in a sorted output list.

Quicksort

A divide-and-conquer sorting algorithm that picks a pivot, splits data into smaller and larger elements, and recursively sorts each pile.

Necessity of exact sort criteria in computer science

Computers cannot handle ambiguity (such as 'size' meaning length vs. volume), so exact criteria must be defined before sorting.

Three key requirements for algorithm quality

1. Correctness: Must be mathematically accurate
2. Termination: Must finish in finite time without wasting processing power
3. Appropriate Accuracy: Must achieve optimal or sufficient results based on the task

Traveling Salesman Problem (TSP)

The problem of finding the shortest route visiting a set of cities once and returning to start. Route options grow factorially ($n!$), making exhaustive checks impractical.

Exhaustive search (Brute Force)

A search technique that checks every item in the search space. Guarantees the optimal solution, but becomes impractical for very large datasets.

Big-O notation

A measure describing how an algorithm's required steps grow as the data size $n$ increases.

Order of Big-O complexity categories (best to worst)

$O(1)$ (constant) → $O(n)$ (linear) → $O(n \log(n))$ → $O(n^2)$ (quadratic) → $O(n^3)$ (cubic) → $O(n^k)$ (exponential/factorial)

Big-O complexity comparison of Bubble Sort, Binary Insertion Sort, and Quicksort

• Bubble Sort & Binary Insertion Sort: $O(n^2)$
• Quicksort: $O(n \log(n))$ (significantly more efficient at scale)