Foundations of Computer Science: Theory and Practice

Learn how strings store text, use string literals to represent values, and apply the plus and multiply operators to concatenate and repeat strings, as with hello there.

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.

Explore control flow in python through if statements, including single if blocks, else branches, and elif chains, and learn how conditions determine which blocks execute.

Explore while and for loops, evaluating conditions and printing outputs. See doubling x until not less than 1000 and a nested for loop that prints a star triangle.

Exiting a while loop with break is demonstrated in an infinite input scenario, summing numbers to a total until minus 1 is entered and the loop ends.

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.

Explore how strings represent characters, count length, and compare lexicographically, including spaces, prefixes, and empty strings.

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 tuples as immutable, zero-based ordered collections of heterogeneous elements, learn access, slicing, concatenation, comparison, and destructuring to implement min, max, and average calculations.

Explore aliasing, mutability, and copying in lists: learn how multiple names reference the same object and when sorting mutates the original list versus returning a new one.

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 as an abstraction of algorithm performance independent of hardware. Analyze how time and space grow with input size, covering constant, linear, quadratic, and exponential growth.

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

Explore how sorted lists enable bisection search, a divide-and-conquer method using a pivot in the middle to halve the range, yielding logarithmic complexity and recursive or iterative implementations.

Explore sorting algorithms by implementing them yourself, examining how different techniques maintain order between consecutive elements, and analyzing their performance characteristics and computation complexity.

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 classes as blueprints for creating objects, defining class and object attributes, constructors, and behaviors with methods like fullname in Python for data structures.

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.