General Information ====================================================================================== Course Name: * [*CS121*: Methods of Computation](https://registrar.corpuschristi.ca/classes/2379/) Term/Year: * 2023W T2 (Jan-April 2024) Class Schedule: * Lecture: Friday 9-11:50am * Lab: Friday 1:30-2:30pm Instructor: * Geoffrey Woollard Office Hours: * Day and time TBD. Room 302. Calendar Description ====================================================================================== Explores formal modeling systems that help us to understand and to explore the capabilities of computers and, more generally, of any problem solving process. Course Description ====================================================================================== An introduction to discrete mathematics through the lens of computer science. This course will bridge the gap between applied mathematics and computer science showing why the many names in computer science such as Alan Turing, Ada Lovelace and George Boole were first mathematicians. We will look at aspects of Boolean algebra, logic circuits, basic proof techniques, sequential circuits, sets theory, finite state machines, sequential instruction execution and the Von Neumann architecture. Course Pre-requisite(s): : - Principles of Mathematics 12 or Pre-calculus 12 Course Co-requisite(s): : - CPSC 110 Learning Outcomes ====================================================================================== * Convert binary values such as unsigned integers, two's complement, and signed integers to decimal and vice-versa. * Convert unsigned integers from hexadecimal to binary and vice-versa. * Translate back and forth between simple natural language statements and propositional logic. * Evaluate the truth of propositional logic statements using truth tables. * Explore alternate forms of propositional logic statements by application of equivalence rules, especially in order to simplify complex statements or massage statements into a desired form. * Translate back and forth between propositional logic statements and circuits that assess the truth of those statements. * Build computational systems to solve real problems, using both propositional logic expressions and equivalent digital logic circuits. * Determine whether or not a propositional logic proof is valid, and explain why it is valid or invalid. * Explore the consequences of a set of propositional logic statements by application of equivalence and inference rules, especially in order to massage statements into a desired form. * Evaluate the truth of statements that include predicates applied to particular values. * Translate between statements in formal predicate logic notation and equivalent statements in closely matching informal language (i.e., informal statements with clear and explicitly stated quantifiers). * Build statements about the relationships between statements about sets and predicate logic. * Sketch the structure of a proof that uses the strategies: * constructive/non-constructive proofs of existence * generalizing from the generic particular * direct proof (antecedent assumption) * indirect proofs by contrapositive and contradiction * proof by cases * logical equivalences * rules of inference * universal modus ponens/tollens * Manipulate formulas in summation/product notation by adjusting their bounds, merging or splitting summations/products, and factoring out values. * Establish properties of self-referential structures using inductive proofs that naturally build on those self- references. * Critique formal inductive proofs to determine whether they are valid and where the error(s) lie if they are invalid. * Trace the operation of a DFA (deterministic finite-state automaton) represented as a diagram on an input, and indicate whether the DFA accepts or rejects the input. * Deduce the language accepted by a simple DFA after working through multiple example inputs. * Translate a DFA into a sequential circuit that implements the DFA. * Explain the difference between a DFA and a non-deterministic finite-state automaton (NFA). * Explain how and why each part of the resulting circuit works. * Specify the overall architecture of a (Von Neumann) stored program computer. An architecture that instantiates the principle that both program and data are bits (i.e., state) loaded and stored in (common) memory. * Trace execution of an instruction through a working computer in a logic simulator (currently logisim): the basic fetch-decode-execute instruction cycle and the data flow to/from the arithmetic logic unit (ALU), the main memory and the Program Counter (PC). Required Texts & Resources ====================================================================================== **Textbooks**: * *_Epp_*: Epp, Susanna. *Discrete Mathematics with Applications*, 5th edition, Nelson Education, 2020. https://www.cengage.ca/c/discrete-mathematics-with-applications-5e-epp/9781337694193/ * *_SR_*: Kreeft, Peter. *Socratic Logic: A Logic Text Using Socratic Method, Platonic Questions, and Aristotelian Principles*, 3.1st edition, St. Augustine's Press, 2008. https://www.staugustine.net/9781587318085/ Hardware: : - (Recommended) A personal laptop running a modern web browser (Linux, macOS, Windows). Course Requirements ====================================================================================== Basic computer literacy is expected including keyboarding skills, file management and use of a web browser. It is highly recommended that you have access to a personal computer that is equipped to access Canvas and CircuitVerse.org. Grade Distribution ====================================================================================== Component | Percentage --------------------------|------------------- In-class worksheets and overall participation | 15% Quizzes | 10% Labs | 15% Assignments | 15% (Midterm) Exam 1* | 10% (Midterm) Exam 2* | 10% (Final) Exam 3* | 25% * The instructor reserves the right to assign a failing grade to a student whose average exam mark (midterms and final) is not above 50% to pass the course. Course Policies ====================================================================================== It is the responsibility of every student to read and understand the College Policies. The College Policies on Academic Honesty, Academic Standing, Academic Concession, Final Exam , Grading Practices, Student Conduct, Technology Usage, and more can be found here: [https://corpuschristi.ca/current-students/#Policies](https://corpuschristi.ca/current-students/#Policies) In addition to the College Policies, this course also upholds the following policies and practices: * **Rule #1**: You must **own** your own work. You must be able to deeply understand and defend on your own submitted work (assignments, labs, worksheets, quizzes, exams), without needing to consult external material. For instance, at any time, the course instructor should be able to inquire you about your submitted work, and you should be able to give a satisfactory explanation. **The course instructor reserves the right to perform oral interviews or other spot checks to verify the originality of submitted student work, and significantly reduce your mark if your have violated this rule.** * **Rule #2**: You are encouraged to collaborate together with other students, and use learning resources available to you (textbooks, notes, large language models, asking experts). You must acknowledge all learning resources that you use. * **Rule #3**: No collaboration of any kind is permitted during the quizzes, midterms or during the final exam. * **Any violation of the rules listed above will result in a 0 on the work containing misconduct and will be reported, in writing, to the Academic Dean.** * NB: these policies substantially may depart from the UBC Department of Computer Science’s Policy regarding collaboration on academic work, and in particular the CPSC 121 policies. It’s highly recommended you be aware of their policies, in case you want to transfer into that Department. Attendance: * As per the college Final Exam policy, students who miss more than 25% of course lectures may be barred from writing the final exam. Accomodations: * Students with documented disabilities who may require accommodations must contact the [UBC Centre for Accessibility](https://students.ubc.ca/about-student-services/centre-for-accessibility) as soon as possible. Please be aware of the deadlines during the term for requesting accomodation. Assignments: * It is encouraged that assignments are done in groups of two, though you may work alone if you choose. Assignments will be submitted on Canvas. For groups, only one submission should be made per group. * **You must *typeset* your assignments on a computer. Handwritten solutions are not accepted.** You can use any software you choose (e.g. Microsoft Word, Google Docs, LaTeX). **Overleaf, an online LaTeX editor is highly recommended!** see their website for supporting documentation and tutorials (overleaf.com/learn/latex/Tutorials). Here are some [helpful notes on LaTeX](https://personal.math.ubc.ca/~andrewr/maths220/2018/latex/) from a UBC MATH 220 instructor. * **Figures of circuits must be done in CircuitVerse or software of at least equal quality, not by hand.** * **Consult each assignment in detail for their specific instructions.** * Not all parts of the assignment may be marked. * We may have a peer review component to assignments [Canvas ComPAIR](https://compair.open.ubc.ca/faq/). In-class Worksheets and Overall Participation: * You **must pre-read** the assigned readings in the _Epp_ textbook before the lecture. * Participation marks will be awarded in each lecture based on your active participation: questions asked, volunteering to work out a problem in front of the class. Note that you don't need to already lnow the answer, it is your engagement to learn the material actively that is awarded marks. * Most/all classes will have an in-class worksheet that must be completed during the specified class time (not for take home work). Quizzes and Labs: * There will be no opportunity for extensions / make up quizzes and labs. * The lowest quiz will be dropped (but not labs). * If an officially excused absence is granted then the affected quizzes and labs typically be omitted from the final grade (i.e. you will not be penalized). Late/Missing Assignments: * A late assignment will be deducted 10% for every day the assignment is late. For instance, an assignment that is 2 days late and graded out of 100 points will be awarded a maximum of 80 points. * If an officially excused absence is granted then the affected assignments may be omitted from the final grade (i.e. you will not be penalized). Extensions on Assignments: * As a general rule, extensions on assignments will almost never be granted. Instead, the lowest assignment will be dropped. Extensions on course work will only be granted due to illness or similar **extraordinary** circumstances. In such a case, a note signed by a physician stating the date and time of the visit to the doctor’s office may be required. * **Any late work cannot be accepted three weeks after the end of term for any reason.** Missed Exams: * Missing midterm exams due to an officially excused absense will either result in a make-up midterm exam, or omission from the mark. * In the case of the final exam, as per existing policy, the student must get in touch with the instructor within 48 hours of the missed final. Grading Scale ====================================================================================== Letter Grade | Numerical Equivalent | Grade Point | Grasp of Subject Matter | Other qualities expected of students --------------|----------------------|-------------|-------------------------|------------------------------------- **A range:** | Excellent: Student shows original thinking, analytic and synthetic ability, critical evaluations, broad knowledge base. A+ |90-100 |4.33 | Extraordinary | Strong evidence of original thought, of analytic and synthetic ability. Superior grasp of subject matter with sound and penetrating critical evaluations, which identify assumptions of those they study as well as their own; ; mastery of an extensive knowledge base. A |85-89 |4.0 | Excellent | Clear evidence of original thinking, of analytic and synthetic ability; Strong grasp of subject matter with sound critical evaluations; evidence of broad knowledge base. A- |80-84 |3.67 | Very, very good | Strong grasp of subject matter and sound critical assessments with appreciation for the larger context. **B range:** | Good: Student shows critical capacity and analytic ability, understanding of relevant issues, familiarity with the literature. B+ |76-79 |3.33 | Very good | Good critical capacity and analytic ability; reasonable understanding of relevant issues; good evidence of familiarity with literature. B |72-75 |3.0 | Good | Solid critical capacity and analytic ability; reasonable understanding of relevant issues; good evidence of familiarity with literature. B- |68-71 |2.67 | Satisfactory | Adequate critical capacity and analytic ability; reasonable understanding of relevant issues; evidence of familiarity with literature. **C range:** | Acceptable to minimum. C+ |64-67 |2.33 | Acceptable | Basic critical capacity and analytic ability; some understanding of relevant issues; some evidence of familiarity with literature. C |60-63 |2.0 | Barely Acceptable | Acceptable in expression but deficient in analysis or in structure. C- |55-59 |1.67 | Needs Improvement | Acceptable in expression but deficient in both analysis and in structure. D |50-54 |1.0 | Minimum Pass | Addresses the topic but significant deficiencies in expression, analysis and structure. **Failed:** | F |0-49 |0 | | Failure to meet the above criteria Student Evaluations of the Course ====================================================================================== During the last two weeks of class, the faculty lecturer will allow students time in class to evaluate the course. Course Schedule ====================================================================================== The following schedule may be altered according to the instructor's judgment. Week | Date | Course Content | Readings for each Class | Other Information -----|------|----------------|-------------------------|----------------- 1 | Fri 12 Jan 2024 | Course overview; Propositional Logic | - This syllabus! - _Epp_ Preface, 1.2 The Language of Sets, 2.1 Logical Form and Logical Equivalence, 2.4 Application: Digital Logic Circuits - _SL_ Introduction 1. What is good logic? ; Introduction 4. All of logic in two pages, 5. The three acs of the mind | - Lab 0 2 | Fri 19 Jan | Conditionals and Logical Equivalences | - _Epp_ Chapter 2.2 Conditional Statements | - Lab 1 3 | Fri 26 Jan | Number Systems | - _Epp_ Chapter 2.5 Application: Number Systems and Circuits for Addition | - Lab 2 - Assignment 1 Due 4 | Fri 2 Feb | Propositional Logic Proofs | - _Epp_ Chapter 2.3 Valid and Invalid Arguments - _SL_ X. Syllogisms 1. The structure and strategy of the syllogism, IX. Checking Syllogisms for Validity 1. By Euler's Circles, 4. Venn Diagrams | - Lab 3 5 | Fri 9 Feb | Predicate Logic | - _Epp_ Chapters 3.1 Predicates and Quantified Statements I, 3.3 Statements with Multiple Quantifiers - _SL_ V. Second Act of the Mind: Judgement 1. Judgements, propositions, and sentences, 3. The four kinds of categorical propositions 4. Logical form, 5. Euler's circles | Lab 4 - Assignment 2 due 6 | Fri 16 Feb | Sets and Predicate Logic | - _Epp_ Chapter 6.1 Set Theory: Definitions and the Element Method of Proof - _SL_ IV. Changing Propositions 1. Immediate inference, 2. Conversion, 3. Obversion, 4. Contraposition | **Midterm 1** 7 | Fri 23 Feb | No Class - Reading Break | | 8 | Fri 1 Mar | Inference and Predicate Logic | - _Epp_ Chapters 3.2 Predicates and Quantified Statements II, 3.4 Arguments with Quantified Statements - _SL_ VII. Contradiction 1. What is contradiction, 2. The Square of Opposition; XII. More Difficult Syllogisms 1. Enthymemes: abbreviated syllogisms, 4. Complex argument maps | - Lab 5 - Assignment 3 Due 9 | Fri 8 Mar | Proof Techniques | - _Epp_ Chapters 4.1 Direct Proof and Counterexample I: Introduction, 4.6 Direct Proof and Counterexample VI: Floor and Ceiling, 4.7 Indirect Argument: Two Famous Theorems - _SL_ IX. Difference Kinds of Arguments 2. Simple argument maps; X. Syllogisms 5. How to construct convincing syllogisms | - Lab 6 10 | Fri 15 Mar | Sequential Circuits | - _Epp_ Chapters 12.2 Finite-State Automata | - Lab 7 - Assignment 4 Due 11 | Fri 22 Mar | Mathematical Induction | - _Epp_ Chapters 5.1 Sequences, 5.2 Mathematical Induction I: Proving Formulas, 5.3 Mathematical Induction II: Applications, 5.4 Strong Mathematical Induction and the Well-Ordering Principle for the Integers | - **Midterm 2** 12 | Fri 29 Mar | **No Class - Good Friday** | | | 13 | Fri 5 Apr | Models of Computation and Functions | - _Epp_ Chapters 6.1 Set Theory: Definitions and the Element Method of Proof, 7.1 Functions Defined on General Sets, 7.2 One-to-One, Onto, and Inverse Functions, 7.4 Cardinality with Applications to Computability | - Lab 8 - Assignment 5 Due 14 | Fri 12 Apr | Review and Perspective | - _SL_ Introduction 3. The two logics; Appendix: Problems with Mathematical Logic | - | Fri 19 Apr (9am-12pm) | Exam 3 (final) | | Appendix ====================================================================================== **Recommendations for Related Courses at Corpus Christi College (check if offered)**: * PHIL 104: Critical Thinking * PHIL 230: Introduction to Formal Logic * MATH 230: Introduction to Finite Mathematics Credit Transferability: : - Consult http://www.bctransferguide.ca