CPSC 121 explores formal modeling systems that help us to understand and to explore the capabilities of computers and, more generally, of any problem solving process.

Modern computation is founded on the happy coincidence that silicon and other semiconductors and metals in special configurations execute a logical operation. But, how do we get from little logical operations to high-level programs?

CPSC 121 will take students on a journey from 0s and 1s to languages of logics to circuits and, eventually, to full computers (well, a simplified version). Students will learn how to construct and recognize valid proofs of a variety of forms, express themselves logically and precisely in the manner of a computer, and create working circuits to show off their models using the Magic Box.

One of CPSC 107 - Systematic Program Design or CPSC 110 - Computation, Programs, and Programming is a required co-requisite for this course. This means that in order to remain enrolled in CPSC 121, students must have already completed either CPSC 107 or CPSC 110, have been granted an exemption from it, or be taking it concurrently. If they do not meet one of these conditions, they will be removed from CPSC 121. Instructors do not have the power to change this rule or make any kind of exceptions.

Furthermore, instructors don't have any control over the registration process, therefore we are not allowed to add, remove or change students from sections or waitlists; change the number of reserved or total seats; or make any kind of registration requests. If you have any questions or requests, please send them to CS advising instead.

Course Components

Labs

In lab, students will solve practical problems and test students' ideas, using computer software.

Discussions

During Discussions, students will work on some selected problems with the help of TAs. Discussions are graded based on attendance.

Pre-Lecture Quizzes

CPSC 121 promotes an "interactive engagement" lecture approach to facilitate learning, so students must prepare before the lecture by doing a reading, and completing an online quiz.

Clickers

Clickers are a way of engaging students in lecture and also get immediate feedback, so instructors can manage the time spent in each topic based on the students response.

Homework

The homework provides challenging proof questions to students, so they practice what they learn in lecture and prepare for the final exam.

Examlets

Every other week, students are assessed with a set of autograded questions, that offer immediate feedback and multiple opportunities to correct any mistakes.

Learning Goals

Model computational systems and apply valid reasoning to these models, i.e. prove relevant properties or reason through functionality of computational systems using predicate logic, propositional logic and state machines.

Write proofs for simple theorems by translating the theorem into first-order logic, decomposing the statement, and applying an appropriate proof-technique such as direct proofs, indirect proofs, and proofs by mathematical induction.

Identify alternate methods to solve or simplify problems by translating between English language, simple formal representations and closely related equivalent formal representations, and then use them to solve the problem.

Prove features of simple algorithms correct or bound in their running time. Justify why each step of the proof is correct.

Clearly and precisely communicate computational models to computer scientists.

Create regular expressions and DFAs to solve problems that are important in programming.

Modules

Land Acknowledgement

UBC's Point Grey Campus is located on the traditional, ancestral, and unceded territory of the xwməθkwəy̓əm (Musqueam) people. The land it is situated on has always been a place of learning for the Musqueam people, who for millennia have passed on their culture, history, and traditions from one generation to the next on this site. It’s important that this recognition of Musqueam territory and our relationship with the Musqueam people does not appear as just a formality. Take a moment to appreciate the meaning behind the words we use:

TRADITIONAL recognizes lands traditionally used and/or occupied by the Musqueam people or other First Nations in other parts of the country.
ANCESTRAL recognizes land that is handed down from generation to generation.
UNCEDED refers to land that was not turned over to the Crown (government) by a treaty or other agreement.

As you begin your journey at UBC, take some time to learn about the history of this land and honor its original inhabitants.