| |
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, 3-3s-0).
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 100-level 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
| 492-3737
| 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 0-534-35945-0.
- Ralph P. Grimaldi.
"Discrete and Combinatorial Mathematics"
(5th Edition). Pearson (2003), ISBN 0-201-72634-2.
- 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 6-10
(no seminar)
| Course overview
Extra materials: variants and invariants
IS Sec 1: Induction
BF Sec 1: Boolean Functions
|
| 2
| Jan 13-17
Seminar 1
| BF Sec 1: Boolean Functions
BF Sec 2: Number systems and Computer arithmetic
|
| 3
| Jan 20-24
Seminar 2
| Lo Sec 1: Propositional logic
Extra materials: logic puzzles and games such as Sudoku
|
| 4
| Jan 27-31
Seminar 3
|
Lo Sec 2: Predicate logic
|
| 5
| Feb 3-7
Seminar 4
| Extra materials: variants and invariants
Feb 5 is the refund deadline
IS Sec 1: Induction
|
| 6
| Feb 10-14
Seminar 5
(midterm review)
|
IS Sec 1: Induction
Midterm course evaluation
Review
NT Sec 1: Basic Facts about Numbers
|
| 7
| Feb 17-21
(no seminar)
| Reading week, no class
|
| 8
| Feb 24-28
(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 B-2, 80 minutes, closed book, coverage: Assignments 1 & 2)
NT Sec 1: Basic Facts about Numbers
|
| 9
| Mar 3-7
Seminar 7 (6 & 10)
| NT Sec 2: Cryptography and Secrecy (The gcd, lcm, and φ functions)
|
| 10
| Mar 10-14
Seminar 8 (13 & 17)
|
SF Sec 1: Sets
|
| 11
| Mar 17-21
Seminar 9 (20 & 24)
| SF Sec 2: Functions
|
| 12
| Mar 24-28
Seminar 10 (27 & 31)
|
EO Sec 1: Equivalence
UTS Teaching evaluation
|
| 13
| Mar 31-4
Seminar 11 (3 & 7)
| EO Sec 1: Equivalence
Apr 2 is the last day for withdrawal
EO Sec 2: Order
|
| 13.5
| Apr 7-9
| EO Sec 2: Order
Final review
|
|
| Apr 24
| Final exam: 2-5pm, 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 cover-sheet 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+
| |