
CMPUT 272: Formal Systems and Logic (2014 Winter Term)
CMPUT 272 Formal Systems and Logic (University Calendar Description, see also
Department Course Description)
*3 (fi 6) (either term, 33s0).
An introduction to the tools of set theory, logic, and induction, and their use in the practice of reasoning about algorithms and programs.
Basic set theory.
The notion of a function.
Counting.
Propositional and predicate logic and their proof systems.
Inductive definitions and proofs by induction.
Program specification and correctness.
Prerequisites: Any 100level CMPUT course or SCI 100.
Course Objectives
This course is the first theory course in computing science and its nature is mathematical.
You will be exposed to basic tools of logic, set theory, and number theory.
You will practice proving theorems and reasoning about some basic algorithms.
Student Responsibilities
Preview the lecture content before coming to the class.
Review the lecture coverage after class to identify unclear points.
Do assignments.
Review solutions to the assignments.
Forward constructive feedback to the instructor and/or TAs.
Time 
Monday 
Tuesday 
Wednesday 
Thursday 
Friday 
9:00

 Office hour (ATH 353) 50 min
 Office hour (ATH 353) 50 min



12:30

 B1/EB1 (CAB 239) 80 min

 B1/EB1 (CAB 239) 80 min






2:00
 Office hour (ATH 353) 110 min





3:00


 J2/EJ2 (CAB 269) 170 min


4:00
 J1/EJ1 (CSC B10) 170 min









 Office
 Phone
 Email

Guohui Lin (B1/EB1 instructor)
 ATH 353
 4923737
 guohui AT ualberta DOT ca


Karan Aggarwal (TA)


 kaggarwa AT ualberta DOT ca

Mohammad Salameh (TA)


 msalameh AT ualberta DOT ca

Weitian Tong (TA)


 weitian AT ualberta DOT ca

Yining Wang (TA)


 yining AT ualberta DOT ca

Code of Student Behavior
Department Course Policies
Recording of teaching is permitted only with the prior written consent of the instructor or if recording is part of an approved accommodation plan.
Course discussion and announcements from instructor done through
eClass/ualberta webpage!
Required Textbook:
Reference Textbooks:
 Susanna S. Epp.
"Discrete Mathematics with Applications"
(3rd Edition). Thomson (2004), ISBN 0534359450.
 Ralph P. Grimaldi.
"Discrete and Combinatorial Mathematics"
(5th Edition). Pearson (2003), ISBN 0201726342.
 Section mapping:
 Epp
 Grimaldi

BF Sec 1
 1.4


BF Sec 2
 1.5


Lo Sec 1
 1.1, 1.2, 1.3
 2.1, 2.2, 2.3

Lo Sec 2
 Chap 2
 2.4, 2.5

IS Sec 1
 4.2, 4.3, 4.4
 4.1

NT Sec 1
 3.2, 3.3, 3.4, 3.5, 3.6, 3.7
 4.3, 4.5, Appendix 3

NT Sec 2
 3.8, 10.4
 4.4

SF Sec 1
 5.1, 5.2, 5.3
 3.1, 3.2, 3.3

SF Sec 2
 7.1, 7.2, 7.3, 7.4
 5.2, 5.3, 5.4, 5.5, 5.6

EO Sec 1
 10.2, 10.3, 7.3
 5.5, 7.1, 7.4

EO Sec 2
 10.5
 7.3

Lecture Schedule
(sign in eClass/ualberta to see assignments, sample exams, and seminar coverage):
Week 
Dates 
Lecture Topics 
1
 Jan 610
(no seminar)
 Course overview
Extra materials: variants and invariants
IS Sec 1: Induction
BF Sec 1: Boolean Functions

2
 Jan 1317
Seminar 1
 BF Sec 1: Boolean Functions
BF Sec 2: Number systems and Computer arithmetic

3
 Jan 2024
Seminar 2
 Lo Sec 1: Propositional logic
Extra materials: logic puzzles and games such as Sudoku

4
 Jan 2731
Seminar 3

Lo Sec 2: Predicate logic

5
 Feb 37
Seminar 4
 Extra materials: variants and invariants
Feb 5 is the refund deadline
IS Sec 1: Induction

6
 Feb 1014
Seminar 5 (midterm review)

IS Sec 1: Induction
Midterm course evaluation
Review
NT Sec 1: Basic Facts about Numbers

7
 Feb 1721
(no seminar)
 Reading week, no class

8
 Feb 2428
(no seminar on 24)
Seminar 6 (27 & 3)
 Marked assignment 2 to be picked up Monday from ATH 353
Tuesday Feb 25: Midterm
(in Tory Lecture Theatre B2, 80 minutes, closed book, coverage: Assignments 1 & 2)
NT Sec 1: Basic Facts about Numbers

9
 Mar 37
Seminar 7 (6 & 10)
 NT Sec 2: Cryptography and Secrecy (The gcd, lcm, and φ functions)

10
 Mar 1014
Seminar 8 (13 & 17)

SF Sec 1: Sets

11
 Mar 1721
Seminar 9 (20 & 24)
 SF Sec 2: Functions

12
 Mar 2428
Seminar 10 (27 & 31)

EO Sec 1: Equivalence
UTS Teaching evaluation

13
 Mar 314
Seminar 11 (3 & 7)
 EO Sec 1: Equivalence
Apr 2 is the last day for withdrawal
EO Sec 2: Order

13.5
 Apr 79
 EO Sec 2: Order
Final review

 Apr 24
 Final exam: 25pm, Main Gym rows 2, 4, 6, 8
(3 hours, closed book, coverage: all material)

 Apr 30
 Deferred Final exam starting at 9:00am, ATH 328


Grading Scheme:
 Mark distribution:
 40% 5 Assignments (8% each)
 10% 10 Seminars (1% each, Seminar 5 not required)
 15% 1 Midterm (in class, 80 minutes, closed book)
 35% Final (3 hours; closed book)
 Notes:
 No late assignments.
 On collaboration, you are encouraged to discuss the assignments with each other, but you must write your solutions alone and
independently. You must use the mandatory assignment coversheet to submit your work.
 Any questions concerning the marking of a midterm (by instructor) or an assignment/seminar (by TAs)
should be brought to the attention of the marker within 7 days of the date
on which the papers are returned to the class in question;
After that time, marks cannot be changed.
 Midterm and final exam absence may result in a mark of 0, unless an acceptable excuse exists.
In this case:
 for missed midterm, the marks will be added to the final exam;
 for missed final exam, the student must apply to the Faculty of Science (not the instructor) for permission to write the deferred exam.
 Final grades will be approximately curved, with reasonable cutoffs.
Historical cutoffs have been:
 A+: 90+
 A, A: 80+
 B+, B: 70+
 B, C+: 60+
 C, C: 55+
 D+, D: 50+
 