Fractal Image

CISC 203:  Fall 2011

Discrete Mathematics for Computing Science

Instructor: Mary McCollam

This page provides information on the course.  It tells you about the instructor, teaching assistants, help sessions, course schedule, and marking scheme and tests.  It also contains a course description, textbook title, and some important dates and places, particularly test dates and test rooms (not our usual classroom).  Practice problems can also be found here, as well as sample tests and solutions to test questions.

Lecture notes will be posted in Moodle, since they include some copyrighted material:  https://moodle.queensu.ca/

Instructors, Teaching Assistants, and Schedule

The instructor and teaching assistants of this course are:

Instructor Office E-mail Phone Office Hours
  Mary McCollam 
   527 Goodwin Hall 
   mccollamATcsDOTqueensuDOTca 
  533-6763 
   Tuesdays, 1-3 pm or by appointment 


   E-mail
  Anna Belkova 
   annaATcsDOTqueensuDOTca 
  Jesse Lu
     8jjl1ATqueensuDOTca 
  Xianrong Zheng  
   xianrongATcsDOTqueensuDOTca 


Stop by during our office hours to ask questions and get help with solving problems, or make an appointment with me for a more convenient time.  

The lectures for this course are scheduled at:

Slot Day Time Room
  3

  Jeff 126 

  Mondays   10:30-11:20

  Wednesdays 
   9:30- 10:20

   Fridays   8:30-9:20 


The help sessions for this course start in the 2nd week of classes. 

Day Time TA
   Room  
 TBA 


  Goodwin 544 
  All Mondays
   3-4
   Anna 
 
  All Tuesdays except Sept 20 
  11-12 
  Xianrong  
  All Thursdays 
  3-4
   Jesse 

  Monay, Sept 26, Oct 31, Nov 14
   3-6
   Anna 3-5
  Jesse 5-6
  Tuesday, Sept 27, Nov 1, Nov 15 
  9-12
   Xianrong
  Thursday, Oct 13 and Dec 1
   9-12
   Xianrong
  
  Thursday, Oct 13 and Dec 1
   3-6
   Jesse
  

There will not be an extra test tutorial for Test 5, but here is the 2009 Test 5 for extra practice and here are the solutions to the 2009 Test 5:   2009 Test 5 Answers

Back to top

Course Description

This course provides an introduction to mathematical discourse and proof methods. Topics to be covered include: Sets, functions, and relations; Natural numbers, integers, and rational numbers; Induction; Combinatorics; Graph theory.

Textbook

K. H. Rosen, Discrete Mathematics and its Applications, Sixth Edition, McGraw-Hill, Boston, Massachusetts, 2007 and Student Solutions Guide.

The textbook and the solutions guide are available at the Queen's Bookstore and have been placed on reserve in the Engineering and Science Library.  Relevant sections of the text are indicated in the course outline below.

You will find the Student Solutions Guide very useful.  It describes the steps used to find the solutions to the odd-numbered exercises in the text, as well gives the answers.

Back to top

Schedule

   Week      Dates    Lectures   Lecture Topic           
  Read in Text 





  1 Sept 12, 14, 16
   Sets, Functions, and Algorithms
   1, 2
   2.1-2.3, 3.1, 3.2
  2 Sept 19, 21, 23
   Complexity of Algorithms, Number Theory
   3, 4
   3.3-3.6
  3 Sept 26, 28, 30
   Review 1, Test 1, Number Theory, con.   4, con.
   3.7
  4 Oct 3, 5, 7
   Matrices, Proof Methods, Mathematical Induction, Recursive Definitions     5, 6, 7, 8
   3.8, 1.6, 1.7, 4.1 - 4.4 
  5 Oct 10, 12, 14
   Thanksgiving, Review 2, Test 2

  6
 Oct 17, 19, 21
   Counting, Pigeonhole Principle, Perms & Combs, Binomial Coefficients
   9, 10, 11
   5.1-5.4
  7 Oct 24, 26, 28
   Generalized Perms and Combs, Recurrence Relations   11, con., 12  
  5.5, 7.1, 7.3
  8 Oct 31, Nov 2, 4
   Review 3, Test 3, Binary Relations
  13
   8.1
  9 Nov 7, 9, 11
   n-ary Relations & Representing Relations, Closure of Relations, Equivalence Relations   14, 15, 16
   8.2-8.5
  10 Nov 14, 16, 18
   Review 4, Test 4, Partial Orderings   17
   8.6
  11 Nov 21, 23, 25
   Hasse Diagrams, Graphs    17, con., 18
   8.6, 9.1-9.3 
  12 Nov 28, 30, Dec 2
   Trees, Review 5, Test 5   19
   10.1, 10.2


Back to top


Marking Scheme and Tests

Your mark is calculated solely from five tests.  There are no assignments to be handed in and no final examination.  A record of marks will be kept in WebCT, where you can look up yours. 

Write the test dates in your calendar now, so you don't miss a test!  Tests will be held during class in weeks 3, 5, 8, 10, and 12.  Weeks 6 and 7 have been purposely avoided to give you time to study for midterms in other courses.  There will be an in-class review before each test.  Each test will be a written, `closed-book', exam.  No computers or calculators will be allowed; required numeric calculations will be minimal, so you won't need a calculator.

   Test   Percentage Date 
Sections Covered
    Room 
   1    20   Wednesday, September 28, 9:30 am
  2.1 - 2.3, 3.1 - 3.6
   Ellis Auditorium   
   2    20   Friday, October 14, 8:30 am 
  3.7, 3.8, 1.6, 1.7, 4.1-4.4
   Kingston Hall Rm 201  
   3    20   Wednessday, November 2, 9:30 am
   5.1 - 5.5
    Ellis Auditorium      
   4    20   Wednesday, November 16, 9:30 am
  Bring your Student ID Card
  7.1, 7.3, 8.1 - 8.4
    Ellis Auditorium  
   5    20   Friday, December 2, 8:30 am
  Bring your Student ID Card 		  8.5, 8.6, 9.1 - 9.3, 10.1, 10.2 
   Kingston Hall Rm 201 

 

Picking-up your marked tests

Marked tests will be returned in class.  Unclaimed tests will be discarded after one week.

If you have any question about your mark, please fill out this form. Include the form and your marked test in an envelope and hand them in to a any one of the TAs no later than one week after the marked test is returned. Your entire test will then be re-marked and, as a result, your mark may go up or down, or remain unchanged. Please note that no request for a re-mark will be considered if your answers were written in pencil or erasable ink.

Back to top

Practice problems

Below is a list of practice problems to do.  Try to work through these problems and solve them first before looking at the solutions.  Some of the problems are more difficult than what will appear on tests.  If you solve these problems, you will be very well-prepared for the tests.  The more difficult problems are marked with an asterisk (*). 

Section Pages Problems
2.1
  119 - 120
    5, 17, 19, 23, 27
2.2
  130 - 131
    11, 25, 37, 45*
2.3
  146 - 147
     5, 17, 19
3.1
  178
    23, 27, 33
3.2   191
     1, 7, 21
3.3   199 - 200
     7, 15, 21
3.4   209
    17, 19, 21, 23a, 27
3.5
   218
     21, 23
3.6
  230
    11, 25, 27*
3.7
  244 - 245
     11, 15*
3.8
  255 - 256
     17, 29, 33, 35, 37
1.6
  85 - 86
     17, 27, 29, 31, 41*
1.7
  102
    3, 9; also 9*, p. 217
4.1
   279 - 282
     3, 15, 55*
4.2
   291 - 292
     3, 15*
4.3   308 - 309
     7, 25, 35
4.4
  321 - 322
    11, 15 35
5.1   345 - 346
     35, 51, 55
5.2   353 - 354
     13, 25*, 33
5.3   361 - 362
     23, 33, 41
5.4   369 - 370
     15, 23, 33*
5.5   379 - 381
     9a-d, 9e*, 15a-c, 15d*, 31, 45
7.1   458 - 459
     35, 37*, 41*
7.3   482
    11, 13, 15
8.1   528
     7, 19, 29
8.2   536
    3, 17, 19
8.3   543 - 544
     13, 23, 31
8.4   553 - 554
     3, 5, 21, 25
8.5   563 - 565
     3, 21, 55
8.6   579 - 580
     9, 19, 27, 29, 43
9.1   596 - 597
    13
9.2   608 - 611
     5, 29, 53
9.3   618 - 621
     1, 3, 15, 21, 31, 43, 51, 61
10.1   694 - 695
     21, 23*, 39, 45
10.2   708 - 709
     1, 3, 7, 19, 21, 23

Back to top

Sample Tests and Solutions

Sample Test 1  and Solutions

Sample Test 2  and Solutions

Sample Test 3  and Solutions

Sample Test 4  and Solutions

Sample Test 5  and Solutions


Solutions to This Year's Tests

Solutions to test questions will be posted here following each test period.

Test 1 Solutions

Test 2 Solutions

Test 3 Solutions

Test 4 Solutions

Test 5 Solutions

Back to top


COMPSA Tutors

If you need additional help, COMPSA keeps a list of upper-year students who are interested in tutoring.  Check the COMPSA web page and search for "Tutor List".

ASUS Tutors

Mindfind is a tutoring service run by ASUS (Arts and Science Undergraduate Society) that pairs student tutors with students who are in need of academic assistance. The hourly cost of tutoring is partly subsidized by ASUS. 

Back to top

 http://research.cs.queensu.ca/home/mccollam/cisc203/2011/info11.html

Last Updated November 12, 2011