## CPSC 1820 - Discrete structures (Spring 2011)

### Lecture times and location

 Day Time Room M W F 11:00-11:50 C 640

Office hours: W F 12:00 - 12:50, or by appointment.

## Requests for remarking

If you disagree with your mark in an assignment or test, please fill out this form. Include the form and your marked test/assignment in an envelope and hand them in during the office hours or in class no later than one week after the marked test is returned. Your entire work will then be re-marked and, as a result, your mark may go up or down, or remain unchanged.

## Tests

Tests are given during normal class time, on Wednesdays, except for test no 6 which is scheduled during the exam period. The topics covered are subject to change. Duration for tests 1-5: 50 min.

 Test # Date Topics Solution 1 Feb 2 Logic and Proofs (1.1, 1.3, 1.4, 1.6); [pdf] 2 Mar 2 Big-O notation, Integers,v(3.2; 3.4-3.8); [pdf] 3 Mar 16 Induction, Counting (4.1; 5.1-5.4) [pdf] 4 Mar 30 Probability (6.1-6.4) [pdf] 5 Apr 13 Graphs and trees (9.1-9.5, 9.7; 10.1, 10.3, 10.4) 6 Apr 29, 9 - 12 room TBD Everything!

Test 6: cummulative. Problems will be chosen from the following set of exercises:
 Section Exercises Section Exercises Section Exercises 1.6 16, 17 1.4 26 3.2 14, 24 3.4 16,20 3.5 12 3.6 24,22 3.7 8 4.1 11,20 5.1 24,30 5.2 7 5.3 12,20,22 5.4 3,6 6.1 12,13,24 6.2 6,12,34 6.3 9 6.4 10,22,24 9.2 26,47,53 9.1 13 9.3 22,30 9.4 11,30,32 9.5 2,26,27,28 9.7 4,16 10.1 16, 39-41 10.3 7,10,13 10.4 7,10,17,18

## Handouts

• 10 Jan: Real and rational numbers axioms: [PDF]

## Homework

It is strongly recommended that you work on exercises and problems for 6-7 hours per week. A few exercises are suggested below. Feel free to do additional problems. I would be happy to discuss the solutions with you. Exercises marked (*) are iteresting but optional.

 Section Exercises Solutions 1.1 1-8; 12-14; 18-21; 27-30 [PDF] 1.2 7-9 [PDF] 1.3 5-10; 11-14; 17-20; 30-36 [PDF] 1.4 1-4; 10-13; 27-29; 31-32; 37-38 [PDF] 1.6 1-16; 30-33; 39; 41-42 [PDF] 3.2 1-2; 5-14; 17; 19-21; 24-26 [PDF] 3.4 1; 3-10; 16; 18-21; 24 3.5 1-5; 10-14; 20-26; 32 3.6 19-26; 29 [PDF] 3.7 1-8; 11-12; 27-29 3.8 1-4; 10-11; 18-21; 28-31; 36 [PDF] 4.1 3-11; 19-23; 31-34 [PDF] 5.1 1-31; 38-43; 46-49; 61 5.2 1-9 5.3 1-28; 30-39 5.4 1-9 5.5 1-18; 21-26; 30-32; 39-42 (not covered in this offering) 6.1 1-18; 22-27; 35-36; 41 6.2 1-2; 6-12; 16; 23-26; 30-33 6.3 1-6 [PDF] 6.4 1-8; 10-13; 19; 23-24; 32-33; 27(*) 9.1 3-10; 13 9.2 1-5; 7-11 (read Theorems 1 and 3); 20-35; 42-45; 47-57 9.3 1-27; 9.4 1-6; 11-12; 14-15, 29-32 9.5 1-15; 18-23; 26-28; 30-40; 42-45 9.7 1-9; 12-14; 19-22; 10.1 1-12; 16; 39-41 10.3 7-15 10.4 1-10; 13-21

Some examples of graphs: [Wikipedia] ; [Large graphs] ; [Small graphs]