PA Review

Divide-and-conquer approach

A top-down algorithm design approach that breaks a problem into smaller subproblems, solves them, and combines the results.

Brute-force approach

An approach that tries possible solutions directly or exhaustively rather than using a more efficient shortcut.

Definiteness

Every step of an algorithm must be clearly and precisely defined.

Unambiguity

Each algorithm step must have only one clear interpretation.

Recurrence relation

An equation that defines a function using a smaller instance of the same function, such as f(n) = f(n - 1) + 2.

Recursion

A technique where a function solves a problem by calling itself on a smaller version of the problem.

Base case

The condition that stops a recursive function from calling itself again.

T(N) = N + T(N - 8) recursion-tree levels

Approximately N / 8 levels because each recursive call reduces N by 8.

Linearithmic runtime

O(N log N).

Constant-time operation

O(1), meaning the amount of work does not grow with the input size.

Why does a constant number of operations remain O(1)?

Big O ignores fixed constants because the amount of work does not grow with N.

Hash table average insertion

O(1).

Hash table average search

O(1).

Hash table worst-case search

O(N) when collisions cause many items to be examined.

Operator precedence

Parentheses, exponentiation, multiplication/division/modulus, addition/subtraction, comparisons, then logical operators.

In X / 2 + Y

2 == 10, what happens first?

Y

2 because exponentiation has higher precedence than division, addition, and comparison.

List slicing

my_list[start:end] creates a new list containing elements from start up to but not including end.

Else range after if x < 5 and elif x > 30

The else covers values from 5 through 30 inclusive.

break

Immediately exits the current loop.

Overloaded methods

Methods that share the same name but differ in their parameters or implementation context.

Stack

A last-in, first-out data structure.

Python list method used to push onto a stack

append().

Queue

A first-in, first-out data structure.

peek() on an empty queue

May result in undefined behavior depending on the queue implementation.

Singly linked-list queue node

Stores data and a reference to the next node.

Deque

A double-ended queue that allows insertion and removal from both ends.

Dummy node in a linked list

A permanent placeholder node that eliminates special-case handling for the head node.

Removing the first node of a singly linked list

Update the head reference so it points to the next node.

Circular linked list

A linked list where the last node points back to the first node, allowing continuous cycling.

Abstract data type (ADT)

Defines what operations are available without requiring the programmer to know the internal implementation.

Abstraction

Hides implementation details so the programmer can work with higher-level operations.

Record

A data structure containing named fields or subitems.

Binary space partitioning

Repeatedly divides a region of space into two parts and catalogs objects within those regions.

Counting sort

A sorting algorithm that uses the known range of possible values to count occurrences.

Quicksort high partition

Contains values greater than or equal to the pivot.

Quicksort low partition

Contains values less than or equal to the pivot.

Pivot

The value used to divide data into low and high partitions during Quicksort.

Merge sort index variables

Typically uses three index variables to track positions while merging arrays.

Radix sort

Sorts integers or strings by processing individual digits or characters.

Bubble sort nested loops

Repeatedly compare and swap adjacent elements until the list is sorted.

Quickselect

Uses partitioning like Quicksort but only continues into the partition containing the desired ranked element.

Quicksort vs Quickselect

Quicksort recursively processes both partitions; Quickselect follows only the relevant partition.

Bucket sort

Divides values into groups or buckets, sorts each bucket, and combines the buckets.

Dictionary compression

Replaces repeated phrases or data with shorter codes and stores the mappings in a dictionary.

Huffman coding

Compresses data by assigning shorter codes to more frequent characters and longer codes to less frequent characters.

Huffman coding frequency rule

The more frequently a character occurs, the shorter its binary code should be.