RaySenseiLEARN WITH RAY · UNDERGRADUATE
Introduction to computing
Learn how computers work and how to write programs in Python. Explore algorithms, data structures, testing and the web.
One step at a time.
Short lessons. Time to practise.
Learn at your own pace.
Choose a lesson, or search this topic.
Computing / University introductory course
84small concepts
12 subtopics · your own pace
12 subtopics · your own pace
Foundations: representing information
Bits, text, pixels and the distinction between rounding and range limits.
- Algorithms and implementations ▶
Specify a finite, unambiguous procedure with inputs and an output; distinguish the procedure from a particular implementation and check that its steps cover the allowed inputs. - Bits, bytes and unsigned ranges ▶
Convert between binary and decimal using powers of two. A byte has eight bits; n bits encode 2^n patterns and unsigned integers from 0 through 2^n−1. Leading zeros do not change an unsigned value. - Characters and encoded bytes ▶
Use a stated mapping to encode and decode characters. Distinguish characters, Unicode code points and encoded bytes; UTF-8 may use several bytes for one code point. - Pixels, channels and image dimensions ▶
Interpret an image as a grid of pixels with channel values. For 8-bit RGB each channel ranges from 0 to 255; image width and height count pixels, while channel depth determines possible intensities. - Finite precision and rounding ▶
Explain why a finite representation cannot encode every real number exactly. Distinguish an exact mathematical value from its rounded stored value and why numerical equality can fail after approximate arithmetic. - Range limits differ from rounding ▶
Distinguish exceeding a fixed-width integer range from rounding a fractional value. Overflow behavior depends on the format; ordinary Python integers grow as needed subject to available resources.
Foundations: reading and running Python
Values, expressions, assignment, observable execution and block structure.
- Values, literals and types ▶
Distinguish Python integer, floating-point, string and Boolean values. Interpret quotes as part of the literal syntax and understand that an operation depends on operand types. - Evaluating arithmetic expressions ▶
Evaluate Python arithmetic expressions using parentheses and precedence; distinguish /, //, %, and **. For integers b≠0, use a=(a//b)*b+a%b to relate quotient and remainder. - Assignment binds a name to a value ▶
Trace name binding and reassignment in Python. Assignment is not mathematical equality; the right-hand expression is evaluated before rebinding the left-hand name, and an undefined name cannot be read. - Statements and execution state ▶
Trace the current statement and named values as a program executes in order. Distinguish an expression’s value, a statement’s effect and displayed output. - Run a program and observe its output ▶
Run a supplied Python script and use print(...) to display a value. Distinguish source code, interpreter execution, printed output and an error diagnostic; a script is not a saved output transcript. - Indentation defines a block ▶
Recognize Python statements grouped by indentation after a colon; distinguish indentation that controls structure from spaces inside an expression. Use a supplied if True: wrapper solely to identify the block; general conditional behavior is taught later.
Conditions and repetition
Read input, choose branches and trace bounded or condition-controlled loops.
- Text input and numeric conversion ▶
Read input() as a string and explicitly convert suitable text with int or float before arithmetic. Invalid numeric text raises ValueError; recognizing the failure is enough here, with handling taught later. - Comparisons and Boolean conditions ▶
Construct true/false conditions from comparisons and Boolean operands using and, or and not. Distinguish == from assignment and use parentheses to make grouping explicit; do not treat a verbal range as two unrelated tests. - Short-circuit conditions ▶
Trace left-to-right short-circuit evaluation: and skips its right operand when the left is false, while or skips it when the left is true. Use a guard to avoid an invalid operation; keep examples to Boolean results. - Selecting a conditional branch ▶
In an if/elif/else chain only the first true branch executes; else covers remaining cases, and without else no branch may execute. Contrast this with independent if statements and check interval boundaries. - For loops over a range ▶
Trace a for loop over range(start, stop, step), excluding stop. A negative step counts down; a range pointing away from stop is empty. The loop variable takes successive values and an empty range executes no body. - While loops and termination ▶
A while loop tests before each iteration and may run zero times. Trace both the condition and the update; show that a chosen nonnegative measure decreases toward termination for a simple countdown. An update alone does not guarantee stopping. - Accumulating a result ▶
Initialize an aggregate before a loop and update it once per item. Use zero for a sum and one for a product, including empty input. Explain why reinitializing inside the loop loses earlier contributions. - Skipping or ending a loop ▶
Use continue to skip the rest of the current iteration and break to leave the innermost loop. Distinguish both from a false loop condition; in while loops make sure a skipped update cannot prevent progress. - Tracing nested loops ▶
The inner loop runs afresh for each outer iteration. Enumerate small pairs in execution order and count body executions; distinguish independent bounds from an inner bound depending on the outer index.
Functions and abstraction
Separate inputs, returned results and local state; compose functions and import a library.
- Defining versus calling a function ▶
Use def to bind a function name and a later call to execute its indented body. Defining it does not run that body; every call starts a new execution. Keep this first definition parameter-free. - Parameters and argument binding ▶
A parameter is a name in a definition; an argument is a value supplied at a call. Bind positional arguments in order and match named arguments by name, using a fixed required-parameter signature. Missing or duplicate bindings are errors. - Returned values differ from output ▶
return supplies a result to the caller and immediately ends this call. Printing displays text but does not supply that computed result; reaching the end without return yields None. Callers may use a returned value in an expression. - Local names in each call ▶
Parameters and ordinary assignments inside a function bind local names for that call. A local assignment does not rebind an outer name with the same spelling. Distinguish name scope from shared-object mutation, which is taught in collections. - Inputs, outputs and side effects ▶
State accepted inputs, the promised returned result, and whether a function may change its inputs or print. Separate this contract from the implementation; invalid inputs need a stated policy rather than an accidental behavior. - Composing returned results ▶
Use the returned value of one function as the argument to another, evaluating the inner call first. An output contract must fit the next input contract; matching names alone is insufficient. - Using a library through an import ▶
Import a standard-library module and call a named function through module.function(...). Distinguish a built-in name from an imported name; use supplied API documentation rather than expecting the import to perform the desired task.
Collections and references
Choose sequence or keyed storage and reason about mutation, copying and identity.
- Indexing a mutable list ▶
Retrieve and replace items in a Python list using zero-based indices, len and negative indices. A valid nonnegative index is below len; indexing an empty list or past its end raises IndexError. Assignment at an index replaces rather than inserts. - Growing and traversing a list ▶
Use append to add one item, pop to remove and return an item, and for to traverse items in order. These mutations differ from rebinding a name; append returns None. Avoid changing list length during the taught traversal. - Slicing sequences with an exclusive stop ▶
For lists, a[start:stop] selects a half-open interval and makes a new shallow list; omitted endpoints use the corresponding end. Out-of-range slice bounds are clipped, unlike invalid individual indices. Defer nested sharing to shallow copying. - Strings are immutable sequences ▶
Index and slice a string using sequence boundaries while leaving it unchanged. Element assignment is invalid; a transformation creates a new string. String length and indexing concern Unicode code points, not encoded bytes or always user-perceived characters. - Shared objects versus rebinding ▶
After b=a for a list, both names refer to the same object. Mutating that object is observable through either name; rebinding b leaves a unchanged. Use is for identity and == for value equality, never infer identity from equal contents. - What a shallow copy separates ▶
A list copy creates a new outer list but retains references to its elements. For nested lists, changing a shared inner list affects both outer views; replacing an outer element does not. Deep-copy algorithms are deferred. - Tuples and fixed-position records ▶
Use an immutable tuple to group fixed-position values and unpack them into names. A one-item tuple needs a comma. Tuple immutability prevents replacing its slots, but does not freeze a mutable object stored inside it. - Dictionary keys, values and missing entries ▶
Retrieve and update a dictionary by a unique hashable key; replacing a value for an existing key does not create a second entry. Membership tests keys, and a missing lookup raises KeyError while get can supply a default. Use strings and integers as keys; mutable lists cannot be keys. - Set uniqueness and membership ▶
Use a set of hashable values for uniqueness and membership, with union and intersection on small examples. Sets do not provide positional indexing or a promised iteration order; an empty set is set(), whereas {} is an empty dictionary.
Data structures and object lifetime
Understand stack, queue, linked and hierarchical models without requiring classes or C pointers.
- A stack removes the newest item ▶
Apply last-in, first-out push/pop operations and identify empty-stack underflow. A Python list can implement the top at its end using append and pop; the stack contract is independent of that representation. - A queue removes the oldest item ▶
Apply first-in, first-out enqueue/dequeue operations and identify an empty queue. Use a supplied collections.deque scaffold with append and popleft; repeatedly removing index zero from a Python list shifts remaining entries. - Following references in a linked chain ▶
Read a diagram whose nodes hold values and next references, ending at None. Access by position requires following links; given a predecessor, insertion changes references rather than shifting all later values. Keep implementation diagrammatic; classes and C pointers are deferred. - Rooted trees and hierarchy ▶
Identify a root, parent, child, leaf and ancestor in a rooted tree; every non-root node has one parent and there are no cycles. A tree provides hierarchical paths, not necessarily key order; a general tree is not automatically a binary search tree. - Reachability and managed memory ▶
An object remains reachable while accessible references lead to it; deleting or rebinding one name need not release it. Unreachable objects may be reclaimed, without promising a portable collection time. Memory management does not replace explicit file-resource cleanup.
Searching, sorting and cost
State input assumptions, trace algorithm invariants and qualify operation-count claims.
- Scanning for the first matching item ▶
Examine list items in order, returning the first matching index or an explicit not-found marker after exhaustion. No sortedness assumption is needed; a prefix already checked contains no earlier match. Treat index zero as a valid result rather than a false not-found signal. - Binary search keeps a valid candidate interval ▶
On a list sorted by the comparison used, maintain the half-open interval [lo,hi). Compare its middle item and discard only impossible candidates, using lo=mid+1 or hi=mid so the interval shrinks. Empty intervals mean absence; with duplicates a basic match need not be the first. - Choosing an input size and counted operation ▶
Define input size n and one basic operation before comparing algorithms. Distinguish best and worst cases; for a linear search, count equality tests rather than seconds. State assumptions such as constant-cost indexing and comparisons for the chosen input values. - Growth bounds describe increasing input size ▶
Interpret O(f(n)) as an eventual upper growth bound up to a constant, not an exact runtime or necessarily a tight bound. Under stated unit-cost assumptions, identify tight growth classes for constant work, halving, a scan and a rectangular nested scan; worst-case and O are different qualifiers. - Selection sort grows a sorted prefix ▶
Find the smallest item in the unsorted suffix and place it at the next prefix position. Explain the sorted-prefix invariant, preserve all input items including duplicates, and distinguish comparisons from swaps. Count comparisons directly on a tiny example; the general cost is a separate node. - The cost of repeated minimum scans ▶
For ordinary selection sort, suffix comparisons total (n-1)+(n-2)+...+1=n(n-1)/2, giving quadratic growth even for already sorted input. There are at most n-1 swaps when self-swaps are skipped. The comparison count differs from the swap count. - Merging sorted inputs without losing duplicates ▶
Merge two already sorted lists by taking the smaller current item and advancing only that input; append the remainder after one is exhausted. Taking the left item on ties preserves relative order across the merge. Every item is emitted once, including duplicates. - Hash collisions still require key comparison ▶
A hash function helps select a bucket; different keys may select the same bucket. In a supplied separate-chaining model, compare stored keys to identify the correct entry and distinguish a collision from an update to the same key. This is a teaching model, not a claim about Python dictionary internals. - When hashing gives fast average lookup ▶
In a separate-chaining model with a suitable hash distribution and controlled load, expected bucket size can stay bounded, supporting expected constant-time lookup for fixed-cost keys. A worst-case bucket may contain every key, requiring linear work; hashing itself may depend on key length.
Recursion and divide and conquer
Connect base cases, decreasing inputs and pending calls; distinguish time, depth and copied storage.
- A recursive call needs a base case ▶
A base case returns a known answer without another recursive call. Select it from the input contract, and distinguish a valid empty input from an invalid input. In the supplied list-length example, an empty list has length zero. - Reducing a recursive problem ▶
For a nonempty list, compute one plus the recursively computed length of its tail. The tail is strictly shorter, so repeated calls reach the empty base case; use the returned result instead of ignoring it. Slicing creates work and storage, analyzed separately. - Pending recursive calls keep local state ▶
Trace call entry and return as a last-in, first-out stack of separate call frames. Each frame retains its arguments and unfinished computation while waiting for a smaller call; returning unwinds in reverse call order. - Recursion depth and copied subproblems ▶
Distinguish number of calls, maximum active call depth and storage for copied input slices. A list counter that slices tails retains lists of decreasing lengths, so total copied elements grow quadratically. An index-based version avoids those copies but still needs linear call depth; Python recursion has a finite depth limit. - Merge sort solves two smaller sorting problems ▶
Return an input list of length zero or one as sorted; otherwise split into two strictly smaller halves, recursively sort each, and merge their sorted results. Distinguish the original unsorted halves from the sorted values returned by recursive calls. - Counting work across merge-sort levels ▶
For conventional merge sort under fixed-cost comparisons and list operations, merging all subproblems at one level takes O(n) work and balanced splitting creates O(log n) levels. This yields O(n log n) time; list copying also costs work and storage, so logarithmic call depth does not imply logarithmic total memory.
Testing and debugging
Distinguish error kinds, debug from a specification, test boundaries and understand the limits of tests.
- Syntax errors, exceptions and wrong answers ▶
Distinguish code that cannot be parsed, a runtime exception, and a successfully executed program that violates its contract. Read the error type and relevant source location in a small supplied diagnostic; a wrong answer need not raise an exception. - Finding the first divergence from a specification ▶
Record input, executed statement, state and output to compare actual behavior with a stated procedure. Locate the earliest divergence and keep procedural requirements distinct from an input-output contract: different intermediate steps can still compute the same function. - Handle an anticipated exception narrowly ▶
Surround the operation expected to fail with try and catch its specific exception. An exception skips the remainder of that try block; unrelated errors must remain visible. Converting text successfully does not establish domain constraints such as a nonnegative age. - Assertions check expected internal properties ▶
An assert statement checks a Boolean property and raises AssertionError if false in normal execution. Use it for developer expectations; assertions may be disabled, so they cannot enforce input validation or access control. A passed assertion only checks the state reached. - A loop invariant relates processed input to state ▶
For a sum loop, state the invariant: total equals the sum of the processed prefix. Explain initialization, preservation by the update, and what the invariant implies when all items are processed. An invariant alone does not establish termination. - A focused test needs an independent expected result ▶
Call a deterministic function on a stated input and compare its returned result with an expected result derived from the contract. Separate computation from console input/output so tests do not need an interactive session; avoid computing the expected value with the same faulty implementation. - Choose cases around boundaries ▶
Choose ordinary, empty, singleton and boundary-adjacent cases according to the function contract. Include invalid inputs only when their behavior is specified. For threshold branches, exercise just below, at and just above the threshold. - Passing examples are evidence, not a general proof ▶
Passing a finite selection of tests establishes those observed cases, not every allowed input. A failing test provides a counterexample to the claimed behavior; add a regression test after fixing that fault. Distinguish test coverage from a correctness argument.
Files and structured records
Read and write files safely, parse CSV and validate records before computing with them.
- Read text with a resource boundary ▶
Open a text file with an explicit encoding and a with block; iterate over its lines without loading the entire file. The context manager closes a successfully opened file when the block exits, including during exceptions. File lines may retain their newline; use the supplied print(line, end="") idiom to avoid adding another newline without stripping a final character. - Parse CSV with its quoting rules ▶
Use import csv and csv.reader on a text file opened with newline="" and an explicit encoding. Consume a known header with next(reader,None) and read field lists; quoted commas belong inside a field. Fields arrive as strings, so numeric conversion is a separate step. - Validate a parsed record before using it ▶
Check field count, convert designated numeric fields and check domain constraints before accepting a CSV record. Choose an explicit reject-or-report policy; parsing success alone does not establish a valid record. Keep the input row number in the supplied scaffold for a useful diagnostic. - Write records without accidental truncation ▶
Distinguish text-file modes r, w and a: w truncates an existing file, while a appends. Use a with block, newline="" and encoding="utf-8" with csv.writer.writerow for fields needing quoting instead of hand-built comma text. Work only with a supplied scratch destination.
Relational data and SQL
Use keys, filters, ordering, missing values, grouping, joins and bound query values.
- Rows, columns and keys ▶
Model a table as rows with named columns. Choose a unique, non-null primary key to identify each row and enforce both properties; in SQLite ordinary non-INTEGER primary keys need an explicit NOT NULL constraint to guarantee this. A foreign key refers to a candidate key in a related table and may repeat across many child rows. Names and visible row order are not reliable identifiers. - Filter rows and choose output columns ▶
Use SELECT to choose columns, FROM to name the table and WHERE to filter each row. A query can return zero or many rows and does not change the stored table. Repeated output values remain unless DISTINCT is requested. - Order query results explicitly ▶
SQL result order is unspecified without ORDER BY. Choose ascending or descending keys and add a tie-breaker when deterministic order matters; LIMIT restricts the result count rather than guaranteeing a meaningful selection by itself. - Missing values use NULL ▶
Distinguish NULL from zero and the empty string. Ordinary equality to NULL is not a true match; use IS NULL or IS NOT NULL. WHERE retains rows whose condition is true, so a comparison with a missing value is not treated as an ordinary numeric comparison. - Summarize rows with grouping ▶
Use COUNT and SUM, grouping by a categorical key for per-group summaries. COUNT(*) counts rows while COUNT(column) ignores NULL in that column; WHERE filters before grouping and HAVING filters groups. Supply all selected nonaggregate grouping keys explicitly. - Join multiplicity follows matching rows ▶
An inner join emits a row for every pair satisfying its join condition; unmatched rows disappear and one-to-many relationships repeat parent data. Qualify ambiguous column names. A left join also retains unmatched left rows with NULL right fields, taught through a small contrast. - Bind values instead of building SQL syntax ▶
With a supplied SQLite connection, pass SQL containing ? value placeholders and a separate parameter tuple to execute. Binding keeps a string value from becoming SQL syntax; a one-item tuple needs a trailing comma. Parameters cannot substitute a table or column identifier, and they do not confer access permission.
How a web application works
Build a small document interaction and explain HTTP, browser/server roles and resource authorization.
- Requests and responses across a boundary ▶
An HTTP request identifies a target and method; a response carries a status, headers and possibly a body. Use a supplied URL to distinguish host, path and query. GET retrieves a representation by convention; a 404 reports a missing resource, not a failure to send any request. - HTML gives a document semantic structure ▶
Use headings, paragraphs, lists and a button to structure a document. Elements, attributes and text are different parts; nest elements correctly and give unique IDs for later selection. HTML content structure does not itself attach click behavior. - Selectors attach presentation rules ▶
A CSS rule pairs a selector with property:value declarations. Contrast element, class and ID selectors and identify the matching elements in a supplied document. Keep this lesson to explicit nonconflicting rules; full cascade and layout systems belong later. - Read the JavaScript needed for one handler ▶
Translate the small supplied browser scaffold: const and let bind names, braces delimit blocks, function name(...) defines behavior, and === compares without type coercion. Read a call and return in JavaScript without assuming Python syntax works unchanged; advanced JavaScript is deferred. - Select a document element and change its text ▶
Treat the DOM as the browser's document object model. After the document exists, select an element by ID and update textContent; a missing match is null and needs a guard. textContent inserts text rather than parsing it as HTML. - An event handler runs when an event occurs ▶
Register a supplied named function with addEventListener("click", handler). Registration passes the function instead of calling it immediately; when the click occurs, the handler updates an already selected DOM element. This local change does not automatically send an HTTP request. - Divide browser, server and storage work ▶
Trace a supplied record-viewing flow: the browser initiates a request, the server validates it and queries stored records, and the browser renders the returned data. Browser state and persistent server-side records are distinct. Use a sequence diagram rather than requiring fetch, async syntax or a web framework. - Check permission for the requested resource ▶
Distinguish authentication (establishing identity) from authorization (permission for an action on a resource). On every protected request, the server checks the authenticated identity and relevant permission, denying when not allowed. Hidden controls and caller-supplied user IDs are not proof of authority.