CS50x: Introduction to Computer Science Foundations and Computational Thinking Syllabus

What precondition must hold before binary search can be used, and roughly how many steps does it take on $n$ items?

The data must be sorted. Binary search halves the search space each step, taking about $\log_{2} n$ steps—e.g., a $1024$-page book needs only about $10$ halvings since $2^{10} = 1024$.

Compare linear search and binary search on $n$ items.

Linear search checks items one by one: works on unsorted data, worst case $n$ steps. Binary search repeatedly halves a sorted collection: requires sorted data, worst case about $\log_{2} n$ steps—much faster for large $n$.

What common building blocks does pseudocode share with real programming languages?

Functions (verbs/actions), conditionals (branches like 'if/else'), Boolean expressions (yes/no questions), and loops (repeated steps)—the same constructs appear in nearly every language.

Define 'abstraction' in computer science.

Abstraction is the simplification of a complex system by hiding its implementation details and exposing only what is needed to use it—treating lower-level complexity as a 'black box'.

Why is abstraction such a powerful idea in programming?

It lets programmers solve problems in layers: once a subproblem is solved (e.g., a function), you can reuse it without rethinking its internals, which reduces complexity, avoids duplication, and makes large systems manageable.

Give an example of layers of abstraction in how a computer works.

Transistors form logic gates; gates form circuits; circuits run machine code; machine code underlies programming languages; languages implement functions; functions build programs. Each layer hides the details of the layer below.

How is a function an example of abstraction?

A function wraps a multi-step process behind a single name (e.g., 'get_input' or 'move'). Callers only need to know what it does, its inputs, and its output—not how it works internally.

What is a function in programming?

A function is a named, reusable block of code that performs a specific task. It may take inputs (arguments) and may produce an output (a return value).

What is an argument to a function?

An argument is an input value passed to a function that influences its behavior—e.g., in print("hello"), the string "hello" is the argument.

What is a return value?

A return value is the output a function hands back to the code that called it, so the result can be stored in a variable or used in further computation—e.g., an input function returning what the user typed.

What is the difference between a function's return value and its side effect?

A return value is data passed back to the caller for later use. A side effect is something observable the function does besides returning (e.g., printing to the screen). A print function has a side effect; an input function has a return value.

What is the difference between a parameter and an argument?

A parameter is the variable named in the function's definition that receives an input; an argument is the actual value supplied when the function is called.

Why do programmers break programs into functions?

Functions enable reuse (write once, call many times), abstraction (hide details), readability, and easier testing/debugging since each piece does one well-defined task.

What is a variable?

A variable is a named storage location in memory that holds a value which the program can read and change—like a labeled box containing data.

In code, what does the statement counter = counter + 1 mean?

It is assignment, not an equation: evaluate the right side (the current value of counter plus $1$), then store the result back into counter. The value of counter increases by $1$.

What is variable scope?

Scope is the region of a program where a variable is accessible. A local variable exists only inside the function (or block) where it is defined; a global variable is accessible throughout the program.

What is the typical pattern for using a counter variable with a loop?

Initialize it once before the loop (e.g., set counter to $0$), then update it inside the loop each iteration (e.g., increase by $1$), and optionally test it in the loop condition to decide when to stop.

What is a Boolean expression?

A Boolean expression is an expression that evaluates to exactly one of two values—true or false—such as $x < y$ or a question like 'is it raining?'.

What is a conditional statement?

A conditional lets a program choose between different paths of execution based on a Boolean expression—e.g., if a condition is true, run one block; else, run another. It creates a 'fork in the road'.

List the standard comparison operators used in Boolean expressions.

Equal to ($==$ in most languages), not equal ($\neq$, written !=), less than ($<$), greater than ($>$), less than or equal ($\leq$, written <=), and greater than or equal ($\geq$, written >=).

In most programming languages, what is the difference between = and ==?

A single = is assignment (store a value in a variable); a double == is comparison (test whether two values are equal, yielding true or false). Confusing them is a classic bug.

How do the logical operators AND, OR, and NOT combine Boolean values?

AND (&&) is true only if both operands are true; OR (||) is true if at least one operand is true; NOT (!) inverts a value, turning true into false and vice versa.

In an if / else if / else chain, how many branches execute, and why prefer 'else if' over separate ifs?

Exactly one branch executes—the first whose condition is true (or the final else). Using else if makes the branches mutually exclusive and avoids wastefully re-checking conditions that separate independent ifs would evaluate.

What is a loop and why are loops useful?

A loop is a construct that repeats a block of code multiple times. Loops eliminate copy-pasted repetition, make programs shorter and easier to change, and allow repetition a number of times determined at runtime.

How does a while loop work, and what is the minimum number of times its body can run?

A while loop checks its Boolean condition before each iteration and runs the body only while the condition is true. If the condition is false initially, the body runs zero times.

What three parts appear in a typical for loop, and what does each do?

(1) Initialization: create/set a counter, e.g., $i = 0$. (2) Condition: checked before each iteration, e.g., $i < n$. (3) Update: runs after each iteration, e.g., increment $i$ by $1$. The body repeats until the condition is false—here, exactly $n$ times.

What is an infinite loop, when is one useful, and how can a program leave it?

An infinite loop repeats forever because its condition is always true (e.g., while true, or Scratch's 'forever' block). It is useful for programs that must run continuously, such as waiting for events; code can exit early with a break statement (or by stopping the program).

How does a do-while style loop differ from a while loop, and when is it useful?

A do-while checks its condition after the body, so the body always runs at least once; a while checks before, so it may run zero times. Do-while is ideal for prompting a user repeatedly until the input is valid.

What is an event in programming, and what is event-driven programming?

An event is an occurrence the program can detect and respond to—a key press, mouse click, or a received message. Event-driven programming structures code as handlers (listeners) that run when their event fires, like Scratch's 'when green flag clicked' or 'when I receive message' blocks.

What is a thread, and what does multithreading enable?

A thread is an independent sequence of instructions that a computer can execute alongside others. Multithreading lets a program do multiple things concurrently—e.g., in Scratch, multiple sprites (or scripts) each run in their own thread and act simultaneously.