CS
Tasks Glossary RU

Computer Science Base course

From the first line of code to the limits of computation

Python from scratch, data structures and algorithms, the machine from logic gates to the processor, operating systems, networks, databases, languages and compilers, the theory of computation, cryptography. The syllabus follows courses at MIT, Stanford, Berkeley, CMU, Cambridge and Oxford.

Start with chapter 0 Course tasks

66 of 66 chapters written

The course board

Each part is a chip, each chapter one of its pins. The trace runs through every chapter in order; the pins you have read light up.

INTRO·0

Introduction

Five surprises and how the course works

  1. 00 What a program can do
LANG·I

Language

Python from scratch: from print to classes, tests and functions as values

  1. 01 First program, first bug
  2. 02 Names and values
  3. 03 Forks in the road
  4. 04 Again and again
  5. 05 Words of your own
  6. 06 Lists
  7. 07 A conversation made of strings
  8. 08 Dictionaries and the telegraph
  9. 09 A problem inside a problem
  10. 10 Functions as values
  11. 11 The inquiry report
  12. 12 The island of rabbits and foxes
DATA·II

Data structures

Complexity, arrays, stacks, hash tables, trees, heaps, graphs

  1. 13 What a program costs
  2. 14 How a list lives in memory
  3. 15 Stacks, queues and a calculator
  4. 16 Hash tables: attack and defense
  5. 17 A garden of search trees
  6. 18 Who is next
  7. 19 Six handshakes
ALGO·III

Algorithms

Search and sort, divide and conquer, dynamic programming, greed, graphs, randomness

  1. 20 The sorting tournament
  2. 21 Divide and conquer
  3. 22 Remember instead of recomputing
  4. 23 Greed and electricity
  5. 24 The navigator
  6. 25 Flows and matchings
  7. 26 Let's flip a coin
  8. 27 A needle in a haystack
CPU·IV

The machine

From bits and gates to the Iskra-8 processor, caches and pipelines

  1. 28 Everything is bits
  2. 29 Logic from switches
  3. 30 The machine does arithmetic
  4. 31 Memory and the clock
  5. 32 You are the processor
  6. 33 An X-ray of Python
  7. 34 Near and far
  8. 35 The pipeline and the fortune-teller
OS·V

Operating system

Processes, scheduling, virtual memory, races, storage

  1. 36 A tour of a living system
  2. 37 Mission control
  3. 38 The hotel of addresses
  4. 39 Races
  5. 40 The rescue operation
NET·VI

Networks

Packets, TCP/IP, the web and distributed systems

  1. 41 A day in the life of a packet
  2. 42 Inventing a protocol
  3. 43 Anatomy of this page
  4. 44 The parliament of Paxos
DB·VII

Storing and finding

Databases, indexes, compression and a search engine

  1. 45 The archivist
  2. 46 The library and the bank
  3. 47 The packing contest
  4. 48 A search engine for our textbooks
LANG2·VIII

Languages

Grammars, an interpreter, a compiler for your own machine, types

  1. 49 The museum of languages
  2. 50 The field linguist
  3. 51 The nesting doll
  4. 52 Closing the circle
  5. 53 Null on trial
TM·IX

Limits of computation

Automata, the Turing machine, the undecidable, P and NP

  1. 54 Automata and regular expressions
  2. 55 The Turing machine
  3. 56 A conversation with the Oracle
  4. 57 Gödel’s letter
  5. 58 The salesman’s expedition
SEC·X

Secrets and attacks

Ciphers, public keys, how systems get broken

  1. 59 The cipher bureau
  2. 60 A secret in plain sight
  3. 61 The training range
AI·XI

Horizons

Games, machine learning, qubits and the blank spots

  1. 62 The bot tournament
  2. 63 The machine learns
  3. 64 The qubit lab
  4. 65 The blank spots

Eleven big questions

One for every part of the course: each part ends by answering its question. The first answer comes in chapter 7, then roughly every six chapters.

I II III IV V VI VII VIII IX X XI
17 213 324 432 539 644 748 852 956 1060 1163
  1. 1

    Part I · Language

    Can a program print itself?

    To print its own text a program must hold that text inside — so it must be longer than itself. And yet such programs exist. You will take one apart as early as Chapter 7.

    Answered in chapter 7 → ✓ You have the answer
  2. 2

    Part II · Data structures

    Why does one program solve a problem in a second while another wouldn’t finish before the end of the universe?

    Same computer, same problem, different ideas — and a gap of thousands of times, sometimes infinite. Can you predict a program’s speed without running it?

    Answered in chapter 13 → ✓ You have the answer
  3. 3

    Part III · Algorithms

    How does a navigation app find the shortest route among millions of roads in a second?

    There are more routes through a city than anyone could ever try. Yet your phone lays out the way before you lift your finger off the screen.

    Answered in chapter 24 → ✓ You have the answer
  4. 4

    Part IV · The machine

    How do you get a computer out of switches?

    Inside a processor there is nothing but billions of tiny switches. How does “on — off” grow into a machine that runs your program?

    Answered in chapter 32 → ✓ You have the answer
  5. 5

    Part V · Operating system

    How do a hundred programs run on two cores without wrecking each other’s data?

    A browser, music, a messenger and hundreds of background processes, and the processor has two or eight cores. Who decides who runs now, and why can’t one program spoil another’s memory?

    Answered in chapter 39 → ✓ You have the answer
  6. 6

    Part VI · Networks

    How do billions of computers work together when none of them is in charge?

    The internet has no center, machines fail, messages get lost. And yet the email arrives and the bank does not lose money.

    Answered in chapter 44 → ✓ You have the answer
  7. 7

    Part VII · Storing and finding

    How does a search engine find what you need among billions of pages in a fraction of a second?

    Nobody can read the whole web in the blink of an eye. So the answer is ready in advance — but how, if the question has not been asked yet?

    Answered in chapter 48 → ✓ You have the answer
  8. 8

    Part VIII · Languages

    How does one program understand another?

    Python is a program too. It reads your text, understands it and runs it. By the end of this part you will write one yourself — for your own computer.

    Answered in chapter 52 → ✓ You have the answer
  9. 9

    Part IX · Limits of computation

    Are there problems no computer can solve?

    Not “not yet solved”: never solvable, however much time and memory you give it. The proof fits on a page.

    Answered in chapter 56 → ✓ You have the answer
  10. 10

    Part X · Secrets and attacks

    How do you agree on a secret when every word is overheard?

    You and your bank’s server meet for the first time, the whole conversation runs over strangers’ wires — and a second later you share a secret key.

    Answered in chapter 60 → ✓ You have the answer
  11. 11

    Part XI · Horizons

    Can a machine learn what nobody taught it?

    Nobody wrote the rules of Go or handwriting into the program. So where does the machine get them from?

    Answered in chapter 63 → ✓ You have the answer

Which syllabi

MIT 6‑3, Stanford CS, Berkeley EECS, CMU SCS, Harvard CS50, the Cambridge Computer Science Tripos, Oxford, ETH Zürich, HSE and the ACM/IEEE CS2023 curriculum.

Computer Science. The base course