CSC 201 - Discrete Mathematics for Computer Scientists

Shai Simonson    306 Stanger    (508) 565-1008

Email:  shai@stonehill.edu

Homepage: http://www.stonehill.edu/compsci/shai.htm


Lectures:  TTh  1:00 - 2:15,   001 Stanger.

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

Exams:  There will be one midterm (25%) and one final examination  (35%).  Final will be on Monday, Dec. 17, 9:00 AM.

Teaching Assistant:  Nate Bowditch  Help sessions every Wednesday night 7 PM in the lab.

Assignments:  Homework assignments will be worth 40% of your grade.  You may do these with a partner, and one grade will be given to both people in each group, but you may work alone if you prefer to do so.  Read our department's 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.  This semester will concentrate on functions, number theory, recurrence equations, recursion, combinatorics, and their applications.  Next semester concentrates on sets, Boolean algebra, linear algebra, and their applications.  

          Special Dates:    The Tuesdays September 18 and October 2 are Jewish holidays.  I will not lecture these days but I will announce other plans for these days in class.

Description:   The two-semester discrete math sequence 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, linear algebra, 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.  Linear algebra has a vast variety of applications including:  Markov chains, cryptography,  computer graphics, curve fitting, electrical circuits, and data mining.  The first semester concentrates on induction, proofs, combinatorics, recurrence relations, functions, computational complexity, and number theory.  The second semester concentrates on logic, sets, countability, Boolean algebra, linear algebra and applications.

 

Useful Links

Rosen Online Help       Cut-the-Knot        Math in CS         My Video Lectures      Wolfram Alpha

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.   Make sure to do a few problems every few days, and not wait until the last few days.  You will learn more and get better grades if you do.  I will review any question before we start class on any day.  I will give hints and guide you.  Never give up.


Assignment 1 Assignment 2 Assignment 3 Assignment 4 

Brief Syllabus

Week Topics Reading
1 What kinds of problems are solved in discrete math? What are proofs? Examples of proofs by contradiction, and proofs by induction: Triangle numbers, irrational numbers, and prime numbers. 1.7-1.8, 2.4
2 Primes, Greatest Common Divisors and the Euclidean 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 and theory of computation. 2.3, 3.1-3.3
5 Recursion and solving recurrence equations by repeated substitution:  Compound Interest, Binary search, Insertion Sort, Merge Sort.  Towers of Hanoi –  graphs as a visual tool.  5.3-5.4
6 Recursion and solving recurrence equations by repeated substitution:  Chinese rings puzzle – Grey codes, change of variable technique. Pages 702-703.
7 Solving recurrence equations:  Master Theorem with applications to algorithms, guessing and proving correct by induction.  The Josephus Problem. 8.1, 8.3
8 Midterm Exam
 TBA
9 Solving recurrence equations – Linear homogeneous equations, linear non-homogeneous equations. 8.2
10 Combinations and permutations. Pascal’s triangle and binomial coefficients.  6.1, 6.3-6.4
11 Counting problems using combinations, distributions and permutations. 6.5-6.6
12 Sets.  The inclusion/exclusion theorem and advanced examples. 2.1-2.2, 8.5-8.6
13 The pigeonhole principle and examples.  6.2
14 Discrete probability, the birthday paradox, conditional probability, expected value, and many examples.  7.1-7.4
15 Review