Foundations of Computer Science: Theory and Practice

Explore how and, or, and not govern truth values and how to combine comparisons with and to test if a value lies between a low and high bound, inclusive.

Compare for loops and while loops as two ways to execute a block in a loop; while loops are more general, but for loops are easier to reason about.

Explore string slicing with square brackets, including start, end (end is not inclusive), and step, plus negative indices. Learn string immutability, character iteration, and ord/chr encoding with Unicode.

Understand Python variable scope: global versus function scope, how function calls create separate locals, and how the global keyword enables an outer scope to be modified.

Functions decompose complex programs into reusable, independent units; provide a callable signature with parameters, accept input arguments, and return a value, enabling abstraction and reuse throughout the program.

Explore how functions partition programs and recursion lets a function call itself, illustrated by Fibonacci with base cases 0 and 1 to ensure termination and prevent stack overflow.

Explore the introduction of data structures to represent composite values from simpler ones, reducing complexity and expanding what we can express with tools like dictionaries and sets.

Learn how lists serve as ordered collections with square-bracket syntax, including empty lists and literals. See how slicing, concatenation, and destructive operations mutate lists and enable iteration.

Explore dictionaries, mapping unique keys to values, with hashable, immutable types; perform creation, indexing, updating, and safe access using get and in, and note that order is not guaranteed.

Explore exponential and logarithmic functions, examining how base-exponentiation drives growth and how logarithms recover exponents, with examples like 2^6=64 and digits needed to represent numbers.

Ensure program correctness while balancing performance, as timing and efficiency prevent failures in safety-critical and consumer facing systems. Explore tradeoff between conceptual complexity and computational complexity in algorithm design.

Explore Big O notation with a quadratic complexity example that intersects two lists using nested loops, a unique function, and worst-case analysis.

Explore bubble sort, a multi-pass sorting algorithm that compares adjacent elements in a sliding window, swapping out-of-order pairs to bubble the largest element to its final position.

Selection sort selects the minimum from the unsorted list and places it at the target index, repeating until array is sorted, using nested loops and swaps to illustrate quadratic-time behavior.

Explore the linked list structure, where each node stores data and a next reference, enabling traversal, insertion at the head, and removal of nodes.

Explore how stacks enforce last-in, first-out behavior with push and pop, implemented in Python via list methods, and how postfix (reverse Polish) notation uses a stack to evaluate expressions.

Explore the queue data structure, its enqueue and dequeue operations, and its first-in, first-out behavior in simulations, distributed systems, and path-finding algorithms.

Illustrates a naive priority queue that stores items in an unsorted list, assigns priority by value, and removes the maximum by scanning, highlighting inefficiency and preparation for advanced data structures.

Explore how a hash table provides constant-time access to keys and values, maps keys to buckets via a hash function, and supports add, get, and remove operations in Python.

Explore how trees organize data with nodes that can have multiple children, enabling adding, removing, and searching elements, and traversing an ordered set; binary search trees have two children.

Explore binary search trees built from nodes with left and right subtrees, where values are kept sorted. Implement recursive search, insertion, and deletion, including handling roots, parents, and successors.

Explore graphs as abstract data types that model connections between nodes via edges, using adjacency matrices and adjacency lists to represent directed or undirected relationships.

Leverage depth-first search to build candidate paths, track the current shortest path, and prune branches that cannot improve the result, demonstrated on a graph with A, B, C, and D.

Use breadth-first search to find the shortest path by expanding paths from a queue of possible routes to adjacent nodes, avoiding cycles, and returning the first shortest path found.