CPSC 121

Models of Computing

About the Course

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 you on a journey from 0s and 1s to languages of logics to circuits and, eventually, to full computers (well, a simplified version). You will learn how to construct and recognize valid proofs of a variety of forms, express yourself logically and precisely in the manner of a computer, and create working circuits to show off your 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, you must have already completed either CPSC 107 or CPSC 110, have been granted an exemption from it, or be taking it concurrently. If you do not meet one of these conditions, you 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 Level Learning Goals

By the end of the course, you will be able to:

- Model computational systems (e.g., programs and circuits) 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.

- Clearly and precisely communicate computational models to computer scientists.

- Identify alternate methods to solve or simplify a variety of problems by translating between (1) English language, (2) simple formal representations (i.e., propositional and shallowly nested predicate logic statements) and (3) closely related equivalent formal representations, and then use the different representations to solve the problem.

- 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 by contrapositive, indirect proofs by contradiction, proofs by weak and strong mathematical induction. Justify why each step of the proof is correct.

- Prove features of simple algorithms (e.g.,selection sort, recursive binary search, or quicksort) correct or bound in their running time. Justify why each step of the proof is correct.

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

Textbook

Book Cover
Discrete Mathematics with Applications

By: Susanna Epp

Edition: 5th

Publisher: Nelson Education

Year: 2020

DISCRETE MATHEMATICS WITH APPLICATIONS explains complex, abstract concepts with clarity and precision and provides a strong foundation for computer science and upper-level mathematics courses of the computer age. Author Susanna Epp presents not only the major themes of discrete mathematics, but also the reasoning that underlies mathematical thought. Students develop the ability to think abstractly as they study the ideas of logic and proof. While learning about such concepts as logic circuits and computer addition, algorithm analysis, recursive thinking, computability, automata, cryptography and combinatorics, students discover that the ideas of discrete mathematics underlie and are essential to today's science and technology.

Course Componets

Labs

In lab, you will solve practical problems and test your ideas, using computer software.

Tutorial

During the Tutorial, students will work on some selected problems with the help of TAs.

Assignments

Assignments provide challenging questions to students, so they practice what they learn in lecture and prepare for exams.

Pre-Lecture Quizzes

CPSC 121 promotes an "interactive engagement" lecture approach to facilitate your learning. For this approach to work best, you must prepare before the lecture by reading the appropriate sections of the text, 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.

Exams

All sections will write common midterms and final exam.

Main Topics

Module 01: Logic Operators, Logic Gates, Digital Circuits, Propositional Logic

Module 02: Logical Equivalences

Module 03: Binary Numbers, Floating Point Representation, Computer Addition, Two's Complements, ALU

Module 04: Argument Validity, Rules of Inference

Module 05: Predicates and Quantified Statements, Sets

Module 06: Regular Expression, DFA, Turing Machine, Sequential Circuits

Module 07: Direct Proofs

Module 08: Contradiction Proofs, Contraposition Proofs

Module 09: Weak Induction

Module 10: Strong Induction

Module 11: Big O, Von Neumann Architecture, Instruction Cycle

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 to honour its original inhabitants.