CS 222   Discrite Mathematics (Fall 2008)

Prerequisite: CS 160
Corequisite:  Math 181

 

 

Key Information

 

Lecture time:  12:45p – 2:00p TR,   Reid 101

Instructor: Year-Back Yoo, yoo@cs.montana.edu

Office hours:  9:00 – 10:50 M, 11:00 – 11:50 T, 9:00 – 9:50 W

Help session: 11:00 – 11:50 T

Textbook: Rosen, Discrete Mathematics and Its Applications, 6th Edition

 

 

Course Outline

 

This course covers logic, discrete probability, recurrence relations, Boolean algebra,

sets, relations, counting, functions, maps, Big-O notation, proof techniques including

induction, and proof by contradiction, and basic combinatorics.

 

 

Course Outcomes

 

By the end of course students will:

  • Be able to use formal proof techniques, including mathematical induction and

     proof by contradiction

  • Understand algorithmic complexity and be able to use it to compare different

     program designs for a problem

  • Solve problems that use logic, sets, and functions
  • Solve problems that use permutations and combinations
  • Solve problems that use discrete probability
  • Solve problems using Boolean algebra

 

 

Homework

 

Homework will be given throughout the semester, and will be graded.

 

 

Exams

 

Midterm and Final

 

 

Grading Scheme

 

Homework      60%    (180 pts)

Midterm          15%    (  45 pts)

Final                25%    (  75 pts)

   

 

 

                          CS 222  Lecture Schedule

 

 

Date

Readings

Topic

Homework

9/ 2   (T)

1.1

Syllabus, Propositional Logic

 

    4   (R)

1.2, 1.3

Propositional Equivalence, Predicates, Quantifiers

 

    9   (T)

1.4, 1.5

Nested Quantifiers, Rules of Inference

 

   11  (R)

1.6, 1.7

Proofs

HW 1

   16  (T)

2.1, 2.2

Sets

 

   18  (R)

2.3

Functions           

 

   23  (T)

2.4

Sequences and Summations              

 

   25  (R)

3.1, 3.2

Algorithms, The Growth of Functions         

HW2

   30  (T)

3.3, 3.4

Complexity, Integer Divisions

 

10/2  (R)

3.5, 3.6

Primes, GCD, LCM              

 

     7  (T)

4.1

Mathematical Induction                                                  

 

     9  (R)

4.3

Recursive Definitions            

HW3

    14 (T)

4.4

Recursive Algorithms

 

    16 (R)

5

Counting                

 

    21 (T)

 

                         Midterm (15%)

 

    23 (R)

6.1

Discrete Probability

 

    28 (T)

6.2

Probability Theory

 

    30 (R)

7

Recurrence Relations

HW4

11/6  (R)

7

Recurrence Relations             

 

    13 (R)

7

Recurrence Relations

 

    18 (T)  

8

Relations

 

    20 (R)

9

Graphs

HW5

    25 (T)

9

Graphs

 

12/ 2 (T)

10

Trees

 

      4 (R)

11

Boolean Algebra

HW6

      9 (T)

12

Modeling Computation

 

     11 (R)

 

Review

 

 

 

 

 

12/16 (T)

12-1:50pm

                        Final (25%)

 

   

 

                                    

Grades

Class Notes

Grading Policy 

        300 – 270   A

        270 – 261   A-

        261 – 249   B+

        249 – 240   B

        240 – 231   B-

        231 – 219   C+

        219 – 210   C

        210 – 201   C-

        201 – 189  D+

        189 – 180  D

        180 -   0     F