CS50x: Introduction to Computer Science Foundations and Computational Thinking Syllabus

Foundations and Computational Thinking syllabus — full chapter and topic list

Expand any chapter to see its topics and sub-topics. This is the whole examinable outline for Foundations and Computational Thinking in CS50x: Introduction to Computer Science, not a summary of it.

1. 1

   Binary and Representation

   4 topics

   • Binary and the Bit
   • Representing Data
   • Algorithms and Pseudocode
   • Abstraction
2. 2

   Scratch

   5 topics

   • Functions, Arguments, and Return Values
   • Variables
   • Boolean Expressions and Conditionals
   • Loops
   • Events and Threads

Foundations and Computational Thinking flashcards for CS50x: Introduction to Computer Science

25 of 50 cards from the Foundations and Computational Thinking deck — real questions with worked answers.

1. What is a bit, and what values can it hold?

   A bit (binary digit) is the smallest unit of information in computing. It can hold exactly one of two values: $0$ or $1$.

2. What is a byte, and how many distinct values can one byte represent?

   A byte is a group of $8$ bits. It can represent $2^{8} = 256$ distinct values, typically the range $0$ to $255$.

3. How many distinct values can $n$ bits represent, and what is the largest unsigned integer they can store?

   $n$ bits can represent $2^{n}$ distinct values; the largest unsigned integer is $2^{n} - 1$.

4. Why do computers use binary (base-2) rather than decimal (base-10)?

   Computer hardware is built from millions of transistors, which are switches with only two reliable states: on ($1$) and off ($0$). Two states map naturally to base-2.

5. In the binary number system, what does each digit position represent?

   Each position represents a power of $2$: from right to left the place values are $2^{0}, 2^{1}, 2^{2}, 2^{3}, \ldots$ (i.e., $1, 2, 4, 8, \ldots$), just as decimal positions represent powers of $10$.

6. Convert the binary number $1010_{2}$ to decimal, showing the expansion.

   $1010_{2} = 1 \times 2^{3} + 0 \times 2^{2} + 1 \times 2^{1} + 0 \times 2^{0} = 8 + 0 + 2 + 0 = 10$.

7. How is the decimal number $7$ written in binary?

   $7 = 4 + 2 + 1 = 1 \times 2^{2} + 1 \times 2^{1} + 1 \times 2^{0}$, so $7_{10} = 111_{2}$.

8. What is integer overflow?

   Integer overflow occurs when a computed value exceeds the maximum a fixed number of bits can store (e.g., above $2^{n} - 1$ for $n$ unsigned bits), so the value wraps around or becomes incorrect because there are no more bits to carry into.

9. What is ASCII and what problem does it solve?

   ASCII (American Standard Code for Information Interchange) is a standard that maps numbers to text characters so computers can represent letters, digits, and symbols as bits. For example, capital 'A' is the number $65$.

10. What are the ASCII codes for 'A' and 'a', and what pattern do the letters follow?

    'A' is $65$ and 'a' is $97$. Letters are numbered consecutively ('B' $= 66$, 'b' $= 98$, etc.), and each lowercase letter is exactly $32$ greater than its uppercase counterpart.

11. What is Unicode and why was it created?

    Unicode is a character-encoding standard that extends ASCII, using more bits per character so it can represent characters from virtually all human languages plus symbols and emoji—far beyond ASCII's limited English-centric set.

12. How does a computer represent a color using the RGB model?

    A color is stored as three numbers giving the intensity of red, green, and blue light. With one byte per channel, each value ranges from $0$ to $255$; e.g., $(255, 0, 0)$ is pure red and $(255, 255, 255)$ is white.

13. How does a computer represent an image?

    An image is a grid of pixels (dots), where each pixel's color is stored as numbers—typically an RGB triple. More pixels and more bits per pixel give higher resolution and color depth.

14. How are videos and music represented digitally?

    A video is a sequence of images (frames) shown rapidly, e.g., $24$ or $30$ frames per second. Music can be represented as numbers encoding notes, duration, and volume (e.g., MIDI), or as digitized sound waves.

15. If the byte pattern for $65$ is stored in memory, how does the computer know whether it means the number $65$, the letter 'A', or a color value?

    Context. The bits themselves are just $0$s and $1$s; the program or file format being used (text editor, image viewer, calculator) determines how the pattern is interpreted.

16. Define 'algorithm'.

    An algorithm is a step-by-step set of precise instructions for solving a problem—transforming an input into a desired output.

17. In the input-output model of computational thinking, where does the algorithm fit?

    Computing is modeled as: input $\to$ algorithm $\to$ output. The algorithm is the 'black box' of steps that converts the problem's input into the correct output.

18. What is pseudocode?

    Pseudocode is a human-readable, language-independent description of an algorithm's steps, written in structured plain language rather than actual programming syntax.

19. What two properties must a good algorithm have?

    Correctness (it always produces the right output) and efficiency (it does so using as little time/as few steps as reasonably possible).

20. In CS50's phone book example, what are the three searching approaches and how fast is each?

    (1) Linear search one page at a time: up to $n$ steps. (2) Two pages at a time: about $\frac{n}{2}$ steps (and can miss entries without a correction step). (3) Divide-and-conquer (binary search), halving the book each time: about $\log_{2} n$ steps.

21. 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$.

22. 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$.

23. 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.

24. 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'.

25. 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.

See more Foundations and Computational Thinking flashcards →

Planning Foundations and Computational Thinking for CS50x: Introduction to Computer Science

Foundations and Computational Thinking (CS50x: Introduction to Computer Science) FAQ