The right way to teach and learn math -- my new book: Rediscovering Mathematics

UIC - CS 151 - Mathematical Foundations of Computing

Shai Simonson    Office:  1216 SEO



Lectures:  MWF  12:00 - 12:50,   Room LC-D4

Office Hours:  I will be in my office (1216 SEO) every Monday and Wednesday from 9:30 - 11:30.  You are welcome to see me anytime I am in, and if you cannot make those hours, feel free to email me about another time.

Text:  Discrete Mathematics and its Applications, Rosen, McGraw Hill, 7th edition.

Description:   This course  covers the mathematical topics most directly related to computer science. Topics include: logic, relations, functions, basic set theory, countability and counting arguments, proof techniques, mathematical induction, graph theory, combinatorics, discrete probability, recursion, recurrence relations, and number theory.  Emphasis will be placed on providing a context for the application of the mathematics within computer science. The analysis of algorithms requires the ability to count the number of operations in an algorithm. Recursive algorithms in particular depend on the solution to a recurrence equation, and a proof of correctness by mathematical induction. The design of a digital circuit requires the knowledge of Boolean algebra.  Software engineering uses sets, graphs, trees and other data structures. Number theory is at the heart of secure messaging systems and cryptography. Logic is used in AI research in theorem proving and in database query systems. Proofs by induction and the more general notions of mathematical proof are ubiquitous in theory of computation, compiler design and formal grammars. Probabilistic notions crop up in architectural trade-offs in hardware design.

Exams:  There will be 6 quizzes (40% total) and one final examination (35%).  Each quiz will be worth 20 points and the lowest quiz grade will be droppedQuizzes will be taken in discussion sections and administered and graded by the TAs.

Teaching Assistants:  The teaching assistants will grade your homework assignments and quizzes, and answer questions at labs under my guidance and with my instructions.  If you have a question or complaint about a HW or quiz grade, and you are unable to resolve it with the TA, please see me for help. 

Discussion Sections:  The TAs will alternate between giving quizzes, and reviewing.  You are expected to attend the discussion section for which you are signed up.  The TAs will take attendance and it will be counted in your HW grade.

The teaching assistants this semester are: 

Assignments:  Homework assignments will be worth 25% of your grade (5% each assignment).   The HWs are meant to force you to study and practice.  If you work hard and meet with the TAs and myself, you can always be sure to work through every problem and get full credit. You may work with a partner on the homework and submit one assignment for both of you.  If you choose to do this, then stick together all semester.  It is easier to work with a partner but you will get less practice.

Grades:  I count your HWs and lab attendance for 25%, quizzes for 40%, and the final as 35%.  You can guarantee an A, B, C, D grade with at least a 90, 80, 70, 60 percent respectively.  I may lower these numbers (in your favor) at the end of the semester if I feel a curve is justified.

Academic Honesty:  I value hard work and honest effort.  If you are working with a partner, make sure the TAs know you are submitting work as a group.  If you use any resource on the Internet to help you with your HW, or you get a hint from a fellow student or TA, you must rewrite the idea in your own words and reference your source.   Copying work or rewriting it in your own words without any reference has potential serious consequences, including failing the course.  Moreover, this kind of dishonesty will not prepare you properly for the quizzes and final.  If a TA reports that your HW violates academic integrity guidelines, I will take a look and if I agree, then you will get a zero on that assignment.  If it happens twice, then I will follow the school's more serious policies.   Read my academic integrity guidelines before you hand in any written work.

Goals:  To understand the mathematics that underlies computer science, and to appreciate where it is used.

          Special Dates:    April 16 and 21 are Jewish holidays and I will not lecture on those dates.  There will be a substitute lecturer, or possibly a quiz.


Useful Links

Rosen Online Help          Math in CS         My Video Lectures      Wolfram Alpha   Old Course Link

Reading and Other Assignments

Written Assignments

Note:  These are long assignments so you should spread your efforts over a period of 2-3 weeks for each one;  you will learn more and get better grades if you do.  The TAs will review any questions you have, and I will give hints and guide you.  Never give up.

Assignment 1 Assignment 2 Assignment 3 Assignment 4 Assignment 5 - Due last day of class

Brief Syllabus

Week Topics  Reading
1 What kinds of problems are solved in discrete math? What are proofs? Examples of proofs by contradiction, constructive proofs, and proofs by induction: Triangle numbers, irrational numbers, and prime numbers.
1.7-1.8, 5.1
2 Primes, Greatest Common Divisors and the Euclidean Algorithm.   Binary numbers and conversions from binary to decimal and vice versa.  The Egyptian fast-exponentiation algorithm.  The two-jug puzzle as demonstrated by Bruce Willis in Die Hard III.  Congruences and Fermat’s Little theorem. Applications to Cryptography.  4.1-4.6
3 Mathematical induction – a flexible and useful tool. Many examples and the idea of strong induction. 5.1-5.2
4 Basic arithmetic and geometric sums, closed forms. Growth rate of functions, Big-O notation. Applications to algorithms. 2.3-2.4, 3.1-3.3
Recursion and solving recurrence equations by repeated substitution:  Compound Interest, Binary Search, Insertion Sort, Merge Sort. 
Towers of Hanoi –  graphs as a visual tool.

Recursion and solving recurrence equations by repeated substitution:  Chinese rings puzzle – Grey codes, change of variable technique.

Solving recurrence equations:  Master Theorem with applications to algorithms.
Guessing and proving correct by induction - The Josephus Problem, and kth largest.

8.1, 8.3

Solving recurrence equations:  Linear homogeneous equations, linear non-homogeneous equations.


Combinations and permutations. Pascal’s triangle and binomial coefficients.

6.1, 6.3, 6.4
Counting problems using combinations, distributions and permutations.


Discrete probability, the birthday paradox, conditional probability, expected value, and many examples. 7.1-7.4
Set Theory - Inclusion/Exclusion Theorem, Associative, Distributive, and De Morgan's Laws.  Bit Operations in Java.
Functions, 1-1 correspondence, and Countability -  Diagonalization.  Applications to Computability and Undecidability.

Propositional Logic and Boolean Algebra, Logic Gates, Circuits and Applications 12.1-12.3