# The Computational Lens

# The Computational Lens

# The Computational Lens

# The Computational Lens

# The Computational Lens

Welcome to CS155!

What is knowable, in principle and in practice?

Can creativity be automated?

What is the role of randomness in the universe?

What does it mean to be intelligent, for an individual and a society?

How does an opinion, (mis)information, or a virus spread in a social network?

How certain can we be about the security, privacy, and fairness of our systems?

Can selfish agents cooperate for the greater good?

Do we live in a simulation?

Despite the range and complexity of these questions, theory of computation provides a common umbrella to formalize and study them. The main goal of this course is to help you develop an appreciation of:

What is computation and how does it shape our understanding of life, science, technology, and society?

This course is for everyone interested in understanding the *computational lens* to tackle the above questions. We will find reliable explanations through modeling and rigorous reasoning. We will discuss how insights from the field of theory of computation shed new light on some of the deepest questions we have ever asked.

# Instructors

# Frequently Asked Questions

### Who is this course for?

This course is designed with everyone in mind! Whether your interests are in arts, sciences, engineering, public policy, humanities, business, or something else, you are all welcome!

While computation is often viewed as the process happening on our laptops and smartphones, the phenomenon itself is significantly more general. It can be used to model any process that "evolves" by a sequence of simple steps. It can be used to study the behavior of atoms in matter, neurons in the brain, proteins in a cell, selfish agents in a market, stars in galaxies, qubits in entangled quantum states, and of course, friends on Instagram. As a result, theory of computation is a rich intellectual pillar of human knowledge, understanding and discovery, with connections to physics, biology, mathematics, statistics, economics, philosophy and social sciences. Beyond specific applications, insights from the theory such as models, abstractions, reductions between problems, and algorithmic thinking, are broadly applicable to problem solving in general. Future intellectuals and leaders, regardless of their specialization, will benefit from studying computation and learning to examine problems, models and solutions via the *computational lens*.

### What are the prerequisites?

We only expect some programming experience that would be provided in any introductory programming course. We do not expect any mathematical background beyond high school mathematics.

### How are students assessed?

This course is purely about learning and having fun in the process. There will be no exams! There will be weekly assignments to help you engage with the content covered in lectures. There will also be a project towards the end of the semester in order to give you a chance to dive deeper into an area that you personally find particularly exciting.

### What are the learning resources?

The course material will consist of online notes developed with your input, assigned reading lists, as well as discussions with your peers and the course staff. This course has limited enrollment in order to facilitate an interactive learning experience.

### What is the expected workload?

This is a 9 unit course. We hope that students will find about 4 to 5 hours per week outside lectures to spend on the course.

### How does this course compare to CS251 or other introductory courses in computer science?

CS155 overlaps with CS251 in terms of the topics being covered, however CS155 goes beyond CS251 by covering more diverse fields and their intersections with computer science. In contrast, CS251 dives deeper into the mathematical underpinnings of a smaller subset of the topics.

Other introductory courses in computer science tend to either focus heavily on computer programming, or some other specific area within computer science. On the other hand, CS155 explores many diverse disciplines outside of computer science using the computational lens.

### What specific topics will be covered?

Some of the key topics are the following.

- Introduction to human reasoning.
- Modeling computation.
- Limits of computation and human reasoning.
- Computational efficiency and why it matters.
- P vs NP (the holy grail of computation).
- Network theory.
- Randomness in computation and the universe.
- The science of secrets and security.

- Quantum physics and computation.
- Statistical physics.
- Learning theory.
- Biological evolution as a learning algorithm.
- Modeling the brain.
- Fair division.
- Algorithmic game theory.
- Philosophy and computation.