Models of Computing
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.
- 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.
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.
In lab, you will solve practical problems and test your ideas, using computer software.
During the Tutorial, students will work on some selected problems with the help of TAs.
Assignments provide challenging questions to students, so they practice what they learn in lecture and prepare for exams.
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 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.
All sections will write common midterms and final exam.
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
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.