Foundations of Computer Science

Overview

This lecture introduces the foundational concepts of computer science and programming, focusing on how information is represented, problem solving through algorithms, and basic programming constructs using Scratch.

Introduction to CS50 and Computer Science

• CS50 is Harvard's introductory computer science course, aimed at both beginners and those with prior experience.
• Computer science is the study of information: how to represent and process it.
• Key focus is on computational thinking—applying problem-solving skills to various domains.

Representing Information: Binary, ASCII, Unicode

• Information in computers is represented using binary digits (bits)—0s and 1s, with each bit as on/off or true/false.
• A group of 8 bits forms a byte; 1 byte can represent up to 256 values (0–255).
• Binary numbers use powers of 2 for each digit's place value, unlike decimal's powers of 10.
• ASCII assigns numeric codes to English letters and common symbols (e.g., 'A' = 65).
• Unicode expands on ASCII to represent characters from all human languages and emojis, using more than 8 bits (often up to 32 bits).

Encoding Numbers, Letters, Colors, Images, Video, and Sound

• Numbers: Binary value (e.g., 011 = 3 in decimal).
• Letters: ASCII/Unicode numerical mapping.
• Colors: Typically encoded with Red, Green, Blue (RGB) values, each ranging 0–255 per byte.
• Images: Stored as grids of colored pixels, each pixel represented by RGB bytes; higher resolution images use more bytes.
• Video: Sequence of images (frames) displayed rapidly to create motion.
• Sound: Encoded as sequences of numbers representing sound wave samples (frequency, volume, duration), possibly including instrument data.

Algorithms and Problem Solving

• An algorithm is a precise, step-by-step set of instructions for solving a problem.
• Example: Searching for a name in a phone book by dividing the search space in half each time (binary search), which is more efficient than page-by-page search.
• Efficiency of algorithms is measured by how the number of steps increases with input size (linear vs. logarithmic growth).

Programming Constructs (Functions, Conditionals, Loops)

• Functions: Reusable blocks of code performing specific actions (verbs); can take inputs (arguments) and return outputs/side effects.
• Conditionals: If/else statements direct decisions in code, based on Boolean (true/false) questions.
• Loops: Code structures that repeat actions until a condition is met (e.g., "repeat 3 times").
• Variables: Named storage for data values, can be used for user input or program results.

Intro to Scratch Programming

• Scratch is a block-based programming language where code is created by snapping together visual blocks.
• "Sprites" are the characters/objects being controlled.
• Inputs, outputs, and algorithms are visually represented through block connections.
• Students implement basic interactions, use conditionals and loops, and create custom blocks (functions) in Scratch.

From Pseudocode to Code

• Pseudocode is an informal, English-like way to express algorithms before coding.
• Good pseudocode is precise, finite, and maps logically to code structures like functions, loops, and conditionals.

Artificial Intelligence Context

• AI chatbots work by mapping inputs to likely outputs using learned data (neural networks), not through explicitly coded conditionals for every scenario.
• CS50 provides its own course AI tools for assistance, but use of general AI tools like ChatGPT is disallowed.

Key Terms & Definitions

• Bit — A single binary digit, either 0 or 1.
• Byte — Eight bits grouped together; represents 256 possible values.
• ASCII — American Standard Code for Information Interchange; maps characters to numbers.
• Unicode — Extended character encoding supporting many languages and symbols.
• RGB — Color model using Red, Green, Blue values.
• Algorithm — Step-by-step procedure for solving a problem.
• Function — A reusable code block; performs a specific task.
• Conditional — Code that branches based on true/false conditions (if/else).
• Loop — Structure that repeats actions (e.g., "repeat" or "forever" blocks).
• Variable — Named storage for a value used in a program.
• Boolean Expression — Logical statement with a true or false outcome.

Action Items / Next Steps

• Attend CS50 Puzzle Day for collaborative problem solving.
• Complete Problem Set 0: Create a Scratch project.
• Review Scratch's user interface and block types at scratch.mit.edu.
• Familiarize yourself with the CS50 syllabus and course policies.