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.

 Synopsis:

The course is designed to provide a shortcut to the concept of a one-way function. Cybersecurity and modern cryptography are based on that concept. The shortcut is possible by highlighting the basic concepts of computer science in string diagrams, a computationally complete graphic language, which is derived incrementally.

Time and place:

• Tuesdays and Thursdays 3-4 pm from August 23 until December 8
• Kuykendall Hall 213

Lectures:

• Introduction
• • presentation: types and functions
  • presentation: abstraction (FYI)
  • text
• Successor: Counting, induction
  • presentation 1: counting
  • presentation 2: induction, recursion
  • text
• Addition: State, coinduction
  • presentation 1: machines
  • presentation 2: automata, streams, coinduction
  • text
• Multiplication: Program, computability
  • presentation 1: idea of computer
  • presentation 2: Turing’s computer (FYI)
  • presentation 3: abstract computer
  • presentation 4: computability
  • presentation 5: undecidability
  • text

• Iteration: Metaprogram, software
  • presentation
  • text
• Resource: Complexity, one-way function