Course overview

Foundations of Computing Systems

How humans made computation possible, from electrical signals and circuits to memory, machine language, and a working computer.

The lectures develop the underlying ideas; the laboratory turns those ideas into hardware components that students build and test.

View lectures

At a glance

Course information

Class schedule, assessment, and the principal textbook.

Timings and location

Monday: 11:00 am-noon, A01-102
Wednesday: 9:00-10:00 am, A01-102
Thursday: 8:00-9:00 am, A01-102
Laboratory: Thursday, 2:00-5:00 pm, A01-109

Evaluation

CS2011 Theory

Test 1: 25% · Test 2: 25% · End-semester examination: 50%

CS2111 Laboratory

Lab work: 10% · Test 1: 25% · Test 2: 25% · End-semester examination: 40%

Each lab carries 1%; the best 10 of 11 labs are counted.

Textbook

Noam Nisan and Shimon Schocken, The Elements of Computing Systems: Building a Modern Computer from First Principles, The MIT Press.

Nand2Tetris course website

Slides

Lectures

Use the arrow keys or the on-screen controls to move through a lecture.

Week 1

The Story

Course orientation and the human story behind chips and computation.

Course orientation 29 July

Lecture 0: Course Details

Expectations, timings, evaluation, and laboratory details.

Open slides

Story 29 July

Lecture 1: The Story of Chips

How humans learned to control electrical signals and made computation possible.

Open slides

Week 2

Boolean Logic

From Boolean functions to gates, Hardware Description Language, and design practice.

Introduction 30 July

Lecture 2: Boolean Algebra

Boolean variables and functions, truth tables, expressions, and canonical representation.

Open slides

Gates and HDL 5 August

Lecture 3: Gate Logic and Hardware Description Language

Logic gates, composite gates, gate specifications, and HDL.

Open slides

Laws and tutorial 6 August

Lecture 4: Boolean Laws and Logic Design Tutorial

Boolean laws, expression simplification, truth-table verification, gate diagrams, and HDL practice.

Open slides

Laboratory 6 August

Lab 1: Basic Gates

Implement Not, And, Or, Mux, DMux, And16, Mux16, Or8Way, Mux4Way16, and DMux4Way using Nand or any previously built gates.

Open web IDE

Week 3

Boolean Arithmetic

Binary representation, arithmetic circuits, and the Arithmetic Logic Unit.

Introduction 10 August

Lecture 5: Boolean Arithmetic

Binary numbers, word size, addition, and signed integers using two's complement.

Open slides

Adders and ALU 12 August

Lecture 6: Building Adders

HalfAdder, FullAdder, Add16, Inc16, and the path from bit addition to an Arithmetic Logic Unit.

Open slides

ALU and tutorial 13 August

Lecture 7: Arithmetic Logic Unit (ALU)

Control bits, the ALU specification, its eighteen functions, implementation planning, and tutorial exercises.

Open slides

Laboratory 13 August

Lab 2: Adders and ALU

Implement HalfAdder, FullAdder, Add16, Inc16, and ALU using only the chips gradually built in this lab and chips from the previous week.

Open web IDE

Week 4

Sequential Logic

From time and state to registers, memory banks, and the Program Counter.

Time and registers 17 August

Lecture 8: Time, State, and Registers

Clock cycles, Data Flip-Flops, controlled feedback, Bit, and the 16-bit Register.

Open slides

Memory hierarchy 19 August

Lecture 9: Random Access Memory

Addresses, read and write timing, RAM8, and recursive construction through RAM16K.

Open slides

Counter and tutorial 19 August

Lecture 10: Program Counter

Control priority, PC construction, sequential simulation, and Chapter 3 design exercises.

Open slides

Laboratory 20 August

Lab 3: Sequential Logic

Implement Bit, Register, RAM8, RAM64, RAM512, RAM4K, RAM16K, and PC using DFF and previously built chips.

Open web IDE

Week 5

Machine Language

From machine-language abstractions and addressing modes to Hack computation, programs, branching, symbols, and memory-mapped input/output.

Machine language 20 August

Lecture 11: Machine Language

Memory, processors, registers, command families, addressing modes, and an introduction to Hack's memory spaces, A, D, M, and unconditional goto.

Open slides

Hack instructions 21 August · 90 minutes

Lecture 12: Hack Machine Language

A- and C-instructions, computation, destination and jump fields, assembly symbols, and memory-mapped screen and keyboard access.

Open slides

Laboratory 27 August

Lab 4: Hack Machine Language

Write and test Mult.asm and Fill.asm using the assembler and CPU emulator.

View lab question

Week 6

Computer Architecture

Stored programs, the von Neumann model, and the construction of the Hack CPU, memory system, and complete computer.

Lab Test 1: Thursday, 3 September, 2:30–4:30 p.m. View question paper (PDF)

Architecture and Hack 31 August

Lecture 13: Computer Architecture

The stored program concept, von Neumann architecture, CPU, memory, registers, memory-mapped I/O, and the Hack platform.

Open slides

Review 2 September

Lecture 14: Course Review

A review of Boolean logic, gates, arithmetic, the ALU, sequential logic, memory, and Hack machine language.

Construction activity 3 September

Lecture 15: Building the Hack Computer

Students used the gates, ALU, registers, memory, and Program Counter built so far to attempt the complete Hack computer.

Week 7

The Hack Computer and Assembler

Complete the Hack hardware platform, then begin translating symbolic assembly programs into binary machine instructions.

CPU, Memory, Computer 8 September

Lecture 16: Completing the Hack Computer

Instruction decoding, ALU and destination control, jump logic, the Hack memory map, whole-computer wiring, and layered testing.

Open slides

Assembler 9 September

Lecture 17: Building an Assembler

An introduction to the three central parts of an assembler: parsing instructions, generating binary code, and maintaining a symbol table.

Open slides

Written test 10 September

Written Test 1

A two-hour written examination covering Boolean logic, binary arithmetic, sequential logic, Hack machine language, and computer architecture.

View question paper (PDF)

Laboratory 10 September

Lab 5: Build the Hack Computer

Complete the Chapter 5 project by implementing and testing the Memory, CPU, and top-level Computer chips.

Open web IDE

Week 8

Assemblers and Native Machine Code

Complete the Hack assembler, then connect a small C program to the assembly and machine instructions executed by a real processor.

Assembler 16 September

Lecture 18: Completing the Assembler

Continued from Lecture 17 by first summarizing its main ideas, then completed parsing, instruction-code generation, symbol-table construction, and symbol resolution to finish the chapter on assembly language and assemblers.

Open assembler slides

Compilation demonstration 17 September

Lecture 19: From C to Machine Code

Compiled a C program that sums the numbers from 1 to 100 and prints the result, then examined both its Intel-syntax assembly and machine code.

Commands and what they do

gcc -O0 -fno-pie -S -masm=intel sum.c -o sum.s

Compile sum.c only as far as assembly and save it as sum.s. Disable optimization and position-independent code, and use Intel assembly syntax.

gcc -g -O0 -fno-pie -no-pie sum.c -o sum

Compile and link sum.c into the executable sum. Include debugging information, disable optimization, and produce a non-position-independent executable.

objdump -d -S -Mintel --disassemble=main sum

Disassemble only main from the executable, showing machine-code bytes together with source and Intel-syntax assembly instructions.

Laboratory 17 September

Lab 6: Build a Hack Assembler

Implement the assembler in Python in two stages: first translate symbol-less programs, then add labels, variables, and predefined symbols. Verify the output using the supplied Project 6 programs and reference assembler.

View lab question

Week 9

The Virtual Machine

Introduce a stack-based intermediate language and translate its arithmetic and memory-access commands into Hack assembly.

VM introduction 21 September

Lecture 20: Introducing the Virtual Machine

Motivated Virtual Machine (VM) code as an intermediate language between high-level programs and assembly. Introduced the stack, stack-based arithmetic and logical operations, VM memory segments, and their simulation in Hack assembly.

Memory access 23 September

Lecture 21: VM Memory Segments

Studied local, argument, static, this, that, temp, and pointer, then translated push constant 5, push local i, and pop local i into Hack assembly.

VM translation 24 September

Lecture 22: Translating Push and Pop

Completed the translation of push and pop for every VM memory segment and prepared the implementation plan for the first VM-translator laboratory.

Laboratory 24 September

Lab 7: VM Translator, Part I

Implement stack arithmetic, logical commands, and memory access in Python; translate the Project 7 VM programs into Hack assembly and test the results using the VM and CPU emulators.

View lab question

Week 10

Program Flow and Functions

Complete the VM language by translating branching, function calls, returns, stack frames, and multi-file programs into Hack assembly.

Program flow 28 September

Lecture 23: Branching in VM Code

Studied loops and the VM program-flow commands label, goto, and if-goto, including their translation into Hack assembly labels and conditional or unconditional jumps.

Function calls 30 September

Lecture 24: Translating VM Functions

Translated function declaration, call, and return commands. Used the stack to preserve return addresses and the caller's LCL, ARG, THIS, and THAT segment pointers.

Translation tutorial 1 October

Lecture 25: VM Translation Tutorial

Worked through translations from the laboratory's VM programs to Hack assembly, with emphasis on program flow, function-call frames, return handling, and multi-file programs.

Laboratory 1 October

Lab 8: VM Translator, Part II

Extend the Project 7 translator with program flow, functions, calls, returns, directory translation, and bootstrap code; test it with the supplied Project 8 programs.

View lab question

Week 11

The Jack Programming Language

Move from VM code to a high-level language: read Jack syntax, use its operating-system services, and build small interactive programs.

No class 5 October

Class Skipped

No lecture was held on Monday.

Jack syntax 7 October

Lecture 26: Writing Jack Programs

Introduced the syntax of the Jack programming language: classes, variables, subroutines, statements, expressions, and program structure.

Jack OS and exercises 7 October

Lecture 27: Programming with Jack

Held in the laboratory. Explored the operating-system calls available to Jack programs, then wrote programs for Hello World, factorial calculation and input, drawing a circle inside a square, and—as a challenge—an arrow-key-controlled rotating cube.

Laboratory 8 October

Lab 9: Open Jack Project

Form a team of at most three students and build something interesting in the Jack programming language. Choose a manageable idea, divide the work, test it, and be prepared to demonstrate the result.

Week 12

Compiler I: Syntax Analysis

Build the front end of the Jack compiler: turn characters into tokens, recognize grammatical structure, and emit a testable XML representation.

Lexical analysis 8 October

Lecture 28: From Source Code to Tokens

Locate syntax analysis in the compiler, introduce lexical analysis, classify Jack's five token types, and specify the tokenizer's XML output and interface.

Open slides

Grammars and parsing 14 October

Lecture 29: From Tokens to Structure

Use context-free grammars to recognize valid programs, construct parse trees, and implement the grammar with recursive-descent routines and limited lookahead.

Analyzer construction 19 October

Lecture 30: Building the Jack Syntax Analyzer

Apply the complete Jack grammar, represent terminals and non-terminals in XML, and organize the implementation into JackAnalyzer, JackTokenizer, and CompilationEngine.

Theory assessment 15 October · Class time

Test 2

The second theory test will be held during the regular class period.

Laboratory assessment 15 October · Laboratory time

Lab Test 2

The second laboratory test will be held during the regular laboratory period.

Thirteen weeks

The journey

Each layer will be built from parts created in the layer below it.

Boolean logicGates, HDL
ArithmeticBinary numbers, Adders, ALU
MemoryRegisters, RAM, sequential logic
Machine languageInstructions, assembly, I/O
Computer architectureCPU, memory, stored programs
Systems perspectiveHow software meets the machine