Day 1 — Huffman/Compression, Algorithm Vocabulary, Deque

Huffman coding

Assigns shorter binary codes to more frequent characters and longer codes to rare ones, minimizing total encoded size

Dictionary based compression

Assigns unique short codes to repeated phrases or words and stores the mapping in a dictionary

Definiteness

All steps of an algorithm must happen in a specific, certain order

Unambiguity

Each step of an algorithm has exactly one clear interpretation

Abstraction

ADT feature that hides implementation details from the user

Brute force

Design strategy that tries all possibilities exhaustively

Divide and conquer

Design strategy that breaks a problem into smaller subproblems, solves each, then combines results

Backtracking

Tries a path and undoes it to try another if it fails, often used to implement brute force

Greedy algorithm

Picks the locally best option at each step

Branch and bound

Like backtracking but prunes paths that cannot beat the best known solution

Deque

Double ended queue allowing insertion and removal from both ends

Queue

Allows insertion at one end and removal from the other end only, FIFO order

Record

Data structure that stores subitems with a name associated with each subitem

Single operation in Big O analysis

Treated as O(1) because any constant time operation does not change the growth ra