Learning Data Structures and Algorithms

Explore complexity theory by studying time and space performance, algorithm efficiency, and data-dependent behavior; compare algorithms and learn to predict and prove performance, with quicksort and Big O notation upcoming.

Learn to analyze algorithm performance with Big-O notation, focusing on upper bounds, worst-case and asymptotic behavior, using rules to determine order of growth.

Explore common big O complexity functions from constant time to logarithmic, linear, quadratic, and factorial, plus why runtimes vary with input size and tree searches.

Compare runtime functions by analyzing growth rates from log and square root to n and n^2. Show how 2^n and n! explode, illustrating practical limits for problem sizes.

Explore the fundamental P versus NP question, comparing deterministic and non-deterministic polynomial time, using subset sum to illustrate cryptography implications and quantum computing considerations.

Explore pseudo random number generators and their deterministic state. Contrast cryptographically secure pseudo random number generators and learn when true randomness matters, with atmospheric noise or random.org.

Explore linear congruential generators, a fast pseudo random number generator using a recurrence with a, b, and m. Learn seed influence and full-period conditions, and compare multiplicative generators with b=0.

Learn in part 1 how pseudorandom numbers randomize an array. Use an outer loop and swap items to randomize order and analyze the one over n probability for each position.

Learn how to randomize arrays and two-dimensional arrays with algorithms that produce equal probability without repetition, compare full shuffles to partial shuffles, and apply to random selections.

Learn the Euclidean algorithm for computing the gcd of two integers, using remainders and updating a to b and b to a mod b until b becomes zero.

Compute the least common multiple of two integers by gcd and the product divided by gcd, using Euclid's algorithm, and note overflow considerations for large numbers.

Learn how to factor small numbers using a prime factorization method, pulling out twos, threes, and other primes up to the square root, with an efficient loop and mod checks.

Analyze the factoring algorithm by input size in bits, showing the worst case tests up to the square root of n, yielding exponential runtime in the number of input bits.

Describe the sieve algorithm for generating primes, using an is_prime array to cross out multiples, and explain optimizations like starting at p^2 and stopping at sqrt(n).

Test primality with Fermat's little theorem by selecting a value n and computing n^(p−1) mod p to identify primes, noting false liars and that repeated tests reduce error to 1/2^t.

Explore numerical integration methods such as the rectangle rule and trapezoid rule, including adaptive quadrature and speed improvements, with practical C# examples comparing errors.

Learn how singly linked lists store data in connected cells with a next pointer, enabling dynamic growth, iteration, and insertion or removal at the beginning, middle, or end.

Explore singly linked lists with sentinels to simplify insertions and removals, handling top and empty list cases uniformly.

Demonstrate how sorted linked lists maintain order by inserting values at the correct position using a before pointer and end sentinels. Learn removal and loop simplifications.

Learn how a sorted linked list can sort a collection by inserting items in order and iterating to output sorted values, with runtime analysis showing overall O(n^2) performance.

Explore doubly linked lists, enabling forward and backward traversal with next and previous links; learn to add, remove, and manage nodes in an object oriented style.

Learn to compute basic statistics on one dimensional arrays, including the minimum, maximum, total, mean, variance, and standard deviation, using simple algorithms that examine each item once.

Create triangular arrays to save memory by storing only the unique half of a matrix. Map row and column to a 1d index using row*(row-1)/2 plus column, swap when row<column.

Wrap a triangular array in a class to simplify access by mapping row and column to a storage index, enabling set and get methods and noting the space-time tradeoff.

Learn how sparse arrays use a linked list of linked lists with row headers and sentinels to store only non-default entries, and how get and set operations work.

Extend the sparse array with column headers and a second set of links to traverse rows and columns, enabling efficient access while balancing the space time tradeoff.

Learn stacks as last in, first out data structures with push and pop operations, built from linked lists or arrays, and understand size and cleanup considerations.

Explore how stacks drive simple algorithms, such as reversing an array by pushing and popping. See how train sorting and the Tower of Hanoi model use stacks to sort and move items.

Explore double stacks, using a single array to host two stacks that grow toward each other, with push right and pop right operations and next left and next right tracking.

Explore how queues operate in first-in, first-out order with enqueue and dequeue. Compare with stacks, and learn about circular and double-ended queues, including doubly linked list implementations and real-world uses.

Study sorting algorithms, including divide-and-conquer, recursion, and counting sort, and see how linked lists, heaps, trees, and library sorting routines depend on data types and initial order.

Explore insertion sort, inserting each item into its proper position to build a sorted list. Analyze its worst-case and best-case runtimes, and compare linked list and array implementations.

Explore the selection sort algorithm, which finds the smallest unsorted item and swaps it into the current position, and compare it with insertion sort's approach and quadratic time.

Quicksort divides the list into two groups around a dividing item and recursively sorts the two halves, highlighting runtime behavior and variations that affect performance.

Quicksort partitions the array around a dividing item and recursively sorts the two groups, with balanced splits yielding n log n total steps.

Learn how heapsort uses a heap built as a complete binary tree, added at the bottom and percolated up to preserve heap order, with order n log n steps.

Learn how heapsort builds a heap, moves the root to the output array, fixes the heap by swapping with the larger child, and keeps an O(n log n) runtime.

Map a complete binary tree to an array to build and store a heap, then perform heap operations, swap root with last and restore the heap for sorting with heapsort.

Explore how merge sort divides items into two equal groups, recursively sorts them, and merges the results into a single ordered list, with motivation from quicksort and discussions of runtime.

Explore merge sort’s recursive splitting and merging, its O(n log n) runtime, its memory use with an auxiliary array, and hybrid approaches like sorting chunks then merging.

Explore the bubble sort algorithm, including scanning and swapping adjacent items. Analyze its runtime performance, especially in worst and mostly sorted cases, and learn practical modifications to boost efficiency.

Explore bidirectional bubble sort with alternating down and up scans and last-swapped tracking to move out-of-order items more quickly, reducing scan lengths and improving performance on mostly sorted arrays.

Discover how counting sort sorts integers by counting occurrences and emitting a sorted list from a limited range, by tallying inputs and expanding counts.

Analyze the runtime of counting sort by tracing steps—from initializing the count array to tallying input values and writing the output—showing a total time of O(m+n) versus O(n log n).

Compare sorting algorithms by runtime and use cases, from insertion and selection sorts to quicksort, heapsort, and merge sort, with emphasis on when counting sort excels for integers.

Introduce the linear search algorithm by looping through each item in an array until the target is found or the end is reached, noting its suitability for small unsorted arrays.

Learn the binary search algorithm on sorted arrays, halving the search range each step by comparing the mid value to the target and adjusting min or max.

Learn how interpolation search estimates a target's position in a sorted array using the min, max, and value range, then refine with outward binary search when needed.

Explore hash tables, a dictionary-like data structure that maps keys to records with a hashing function, enabling fast insertion and retrieval, while addressing collisions and space-time tradeoffs.

Explore hash tables with chaining to resolve collisions by linking items in buckets, using sentinel nodes and sorted lists, and analyze performance, hashing functions, and resizing strategies.

Explore how hash tables use open addressing to resolve collisions by probing an index sequence. Understand add, find, and remove algorithms, resizing, and in-place rehashing strategies.

Explore open addressing with linear probing in hash tables, using k mod N for the initial index and a constant step to form the probe sequence, and discuss primary clustering.

Explore open addressing with quadratic probing to avoid primary clustering in hash tables, improving efficiency. See how quadratic probing compares to linear probing and its potential secondary clustering.

Explore open addressing with double hashing to form probe sequences that avoid primary and secondary clustering, using two hash functions to compute initial locations and offsets, with resizing considerations.

Explore recursion basics, including direct and indirect recursion, multiple recursion, and examples like factorial and quicksort, showing how runtime, memory use, and recursion depth affect performance and stack limits.

Explore Fibonacci numbers and a recursive algorithm to compute them using a recurrence relation and base cases, then analyze the runtime via a call tree and leaf-node growth.

Learn a recursive solution to the Tower of Hanoi, moving disks between three pegs under strict rules, with a step-by-step example and runtime insights.

Explore the recursive Koch curve algorithm that subdivides each segment into thirds and replaces the middle third with two segments, level by level, illustrating infinite length within finite area.

Explore the Hilbert curve, a self-similar fractal drawn by four rotated copies of lower level curves, using dx and dy to track orientation and connect segments.

Explore fractal gaskets such as the Sierpinski triangle and carpet, built by recursive subdivision and removal, with runtimes 3^n, 5^n, and 8^n.

Learn how tail recursion can exhaust stack space and how to remove it by converting recursive steps into a loop, updating parameters and computing results without extra calls.

Remove recursion by simulating calls with stacks and a loop. Push initial parameters, pop and process them, then push new ones as needed, with quicksort as the example.

Fixing Fibonacci replaces slow recursion with a table of computed values using an array f and a bottom-up loop to achieve order n runtime.

Explore generating selections or combinations with duplicates using a candy-store example, compare nested loops with recursion, and learn a make-selection algorithm that fills an array to enumerate all valid choices.

Explore a recursive algorithm for generating permutations, including duplicates-allowed and duplicates-prohibited versions, with examples of five-item permutations from 1 to 10.