Syllabus, CPSC 331, Fall 2010

home page -  news -  syllabus -  schedule -  assignments -  tutorials -  tests -  java -  references -  Mike Jacobson


about CPSC 331 -  learning goals -  CS background -  math background -  writing background -  how to succeed -  what to avoid -  assessment

 Math Background

Student should have complete MATH 271 or 273 before taking this course.

In Computer Science 331 mathematical language will be used to describe the problems that are to be solved in a reasonably precise and formal way. Mathematics will also be used to identify conditions that are expected to hold at various points during the execution of computer programs, and to state and prove claims about the correctness and efficiency of the algorithms and data structures that are being presented in the course.

Consequently a background (even a minimal one) in mathematical logic and in discrete mathematics will be very useful for this course.

A significant amount of the material concerning discrete mathematics, that is presented in Mathematics 271 or 273, will be applied in Computer Science 331. Proof techniques, especially including mathematical induction, will be extremely useful. However, tt certainly will not be assumed that students are already familiar with this material. Accordingly, this material will be applied in a gradual way and only after (or, occasionally, at the same time as) the time when it is introduced in the discrete mathematics course.

Mathematical logic is used whenever requirements for programs are specified in a formal way and whenever algorithms and programs are proved to be correct. It is therefore helpful (but not essential) if students in Computer Science programs have taken Philosophy 279 or 377 before or at the same time as they are taking Computer Science 331: The material about propositional logic and (First order) predicate logic introduced in these courses will be useful here.

Recommended References

Each of the following references could be used as a textbook for Mathematics 271 (indeed, one of these is commonly used as the textbook for this course) and includes a readable introduction to the material from mathematics and logic that will be used in Computer Science 331.

  1. Susanna S. Epp
    Discrete Mathematics with Applications, Third Edition
    Thomson, 2002

    This book has been used as the textbook for Mathematics 271 in recent years. Printed copies can be purchased at Amazon or Chapters.

  2. Kenneth H. Rosen
    Discrete Mathematics and Its Applications, Sixth Edition
    McGraw Hill, 2007

    This book is somewhat more advanced than Epp’s text but also provides a readable introduction to the material that will be used in Computer Science 331. Printed copies can be purchased at Amazon or Chapters.

Note: Several other books have been used as textbooks for Mathematics 271 over the years. These are generally less suitable as references for Computer Science 331 than the ones listed above because they do not include material about proving correctness of algorithms.


Last updated:
http://www.cpsc.ucalgary.ca/~jacobs/cpsc331/F10/syllabus/math_background.html