ICS 222: Basic Concepts of Computer Science

Catalog entry:

What is Computer Science about? How did we get from counting to programming? What is a supercompiler? Why are some things easy to compute, some hard, and some impossible? Answers in pictures. Learn how hardness is used for security.


This course presents the conceptual background of Computer Science as a science, and the fundamental ideas and methods of theory and practice of computation, with emphasis on security. We use a diagrammatic language and lots of pictures to study and use the concepts of counting, state, program, software, complexity, network, and to recognize the problems that arise from them.

People, time and place:

  • Lecturer: Dusko Pavlovic
  • Teaching Assistant: Mariam Doliashvili
  • Lectures and practica:
    • Time: Tuesday and Thursday 15:00-16:15
    • Place: Sakamaki A103
  • Office ours:
    • Time: Tuesday¬† 16:15-17:15, Thursday 13:00-14:00, or by appointment
    • Place: POST 311 or 312
  • Calendar (Please check Laulima for updates.)

Slides and lecture notes (uploaded after each lecture)

  • Introduction – slides
  • Prerequisite concept: Function – slides, notes
  • First concept: Counting (induction) – slides, notes
  • Second concept: State (coinduction) – slides, notes
  • Third concept: Program (computability) – slides, notes
  • Fourth concept: Software (metaprogramming) – slides, notes
  • Fifth concept: Resource (complexity) – slides

Practica and homeworks with model solutions are distributed through Laulima