COMP/MATH 1805: Discrete Structures

This is my personal homepage for COMP/MATH 1805. The official SCS page for the course can be found here. Both pages will include up to date information on assignments, etc. This page will be used to post detailed information on topics covered in lectures and suggested exercises.

Classes will be held on Tuesday and Thursday nights in Southam Hall, Room 306 from 6.00pm to 9.00pm.

Course Updates

This section will be used to post updates related to the course throughout the term.
DateUpdate
May 8thThere were some minor errors discovered in the posted lecture notes tonight. These will be corrected and hopefully posted by Thursday.
May 8thI have requested that the library place 2 copies of the course textbook (6th Edition!) on 2 hour reserve. THE TEXTBOOK IS NOW ON 2 HOUR RESERVE.
May 9thPlease note, there has been a change to the TA room. TAs can be visited in 3341 HP (Herzberg Building) rather than 1170 HP. There will be no office hours during the first week of class.
May 15thThere is an error in Assignment 2 in that part of question 9 was missing. It should start off with '"Indicate if each of the following statements is true or false. As was done in class you should provide witnesses to demonstrate when a function is of the order specified.'" A correct version of this assignment was posted tonight.
May 16thSome of you enquired if cuLearn had a discussion board. It does, they are entitled Forum's in cuLearn. I've created a Forum for general discussions. Hopefully a few of you can try it out.
May 29thThe mid-term will cover everything up to the lecture on May 24th. Specifically no material from tonight's (Tuesday) lecture will be on the mid-term. The mid-term is 1 1/2 hours long.

There is an error in question 9 of Assignment 3. Ignore the bit about non-zero digits and assume 0 is an even digit (even when used as a placeholder). This will make the question a bit easier to understand and answer. I've updated the Assignment on this site and on cuLearn.
May 31st The solutions to the midterm, if you are curious are posted here.
June 12th Note that the mid-term will be graded out of 30 marks. So if you initial mark was 23/34 you now have 23/30. cuLearn has been updated to reflect this.
June 14th The final exam is on 23-June-2012 at 14:00 (2pm). Examination services has not yet posted the location, but I will post as soon as I find out (likely tomorrow). In the meantime this link links to a few questions that will NOT be on the final, but may give you an idea of what the final is like. It does however include only a few questions, so the material covered on the final is much broader than shown here. Good luck everyone!
June, 17thThe final exam will be held in Room 302 of the Azrieli Theatre on Saturday, June 23rd at 14:00. Note that in the final lecture we skipped some topics which will not be on the final exam, these include Graph Isomorphism, Special and Bipartite graphs. A cheat sheet, like that provided for the mid-term will NOT be part of the final exam.
June, 23rd Hope everyone enjoyed the final exam. I will hold office hours on Tuesday, June 26th, between 2-5 PM in the Herzberg Building, Room 5170 (Computational Geometry Lab). If you have any last questions about the course please come by then and ask. I am adding grades for the final to cuLearn as I mark them so some are already up, but it may be as late as Tuesday before I get them all done.

Course Instructor

Craig Dillabaugh
Email: cdillaba at connect dot carleton dot ca
Office Hours:

I work during the days, and I assume a number of you do too, so I have odd office hours, before and after class each night, so that hopefully anyone who needs to see me can manage that way:

Teaching Assistants

Note that the TA's will not hold office hours during the week of May 8th

Teaching Assistant Email Office Hours Location
Vinh Nguyen vnguyen1 at connect.carleton.ca Wednesdays: 4-6pm HP 3341
Zhicheng (Jason) Song jsong at connect.carleton.ca Fridays: 4-6pm HP 3341

Lectures

Lectures will be held on Tuesday and Thursday nights from 6:00pm to 9:00pm (with a 10 minute break in there somewhere!) in Southam Hall, Room 306. First lecture is Tuesday, May 8th last lecture is Thursday, June 14th.

Grading Scheme

Component Grading
4 Assignments10% each
In class mid-term20 %
Final exam40%

Textbook

The course textbook for this course is Discrete Mathematics and Its Applications, Sixth Edition by Kenneth Rosen. If you have an earlier (or later) edition you should be fine but the sections/questions outlined below are for the 6th Edition.

Smiley face

Assignments

Assignments must be handed in by the half-way break of the class in which they are due. Late assignments will not be accepted.
AssignmentDueSolutions
Assignment 1 Tuesday, May, 15th Solutions
Assignment 2 Thursday, May, 24th Solutions
Assignment 3 Thursday, June, 7th Solutions
Assignment 4 Thursday, June, 14th Solutions

Mid-Term Examination

The mid-term will be held in class on Thursday, May, 31st at the START of class. If you require special accomodations (i.e PMC student) you must contact me (Craig) ASAP. I will not be able to accomodate students who approach me a day or two before the exam. The following study guide will be provided as part of the examination, but it may also be useful to you in your studies.

Final Exam

Date: Saturday, June 23rd, at 14:00
Location: 302 AZRIELI THEATRE

Class Schedule

Section numbers given below are from the course textbook, with green highlighted topics being optional. Optional topics will not be required reading for the exam. Assignment due dates and exam times will not be changed, but exact timing of lecture topics may vary depending on how quickly we can cover materials in class.

Lecture Topics Suggested Excercises
Try ODD numbered excercises in ranges indicated.		 Assignments/Tests
Tuesday, May 8th

1.1 Logic

System Specifications

Boolean Searches

Logic Puzzles

Logic and Bit Operations

1.2 Propositional Equivalences

 Section 1.1: 1,5-15,19-23,27,29
Section 1.2: 5-11,15-33
See if you find this funny. 		Lecture notes.
Thursday, May 10th

1.3 Predicates and Quantifiers

Other Quantifiers

Qualifiers with Restricted Domains

Using Quantifiers in System Specifications

Logic Programming

1.4 Nested Quantifiers

1.5 Rules of Inferences

Resolution

 Section 1.3: 1, 5-13, 19, 23-29, 35, 37
Section 1.4: 1, 3, 7-15, 19, 25, 27, 33, 37, 39
Section 1.5: 3, 5, 9, 13-17, 23, 27
Section 1.6: 1-17 		Lecture notes.
Tuesday, May 15th

1.6 Introduction to Proofs

Mistakes in Proofs

1.7 Proof Methods and Strategies

Proof Strategy in Action

Tilings

The Role of Open Problems

2.1 Sets

Using Set Notation with Quantifiers

Truth Sets of Quantifiers

2.2 Set Operations

Generalized Unions and Intersections

Computer Representation of Sets

 Section 1.6: 25-29
Section 1.7: 3,5,9,15,17,33
Section 2.1: 1-9, 17-27
Section 2.2: 3-13, 17, 21-27 		Lecture notes.
Assignment 1 due at break in class.
Thursday, May 17th

2.3 Functions

2.4 Sequences and Summations

Special Integer Sequences

 Section 2.3: 1, 5-11, 17, 19, 25-31, 35, 47, 53, 59, 61, 65, 69, 71
Section 2.4: 1-9, 13-19 		Lecture notes.
Tuesday, May 22nd

3.1 Algorithms

Greedy Algorithms

The Halting Problem

3.2 The Growth of Functions

The Growth of Combinations of Functions

3.3 Complexity of Algorithms

 Section 3.1: 1,3,7-11, 19, 35, 37, 39
Section 3.2: 1-23, 31, 35
Section 3.3: 1,5,7 		Lecture notes.
Thursday, May 24th

4.1 Mathematical Induction

Why Mathematical Induction is Valid

Errors in Proofs Using Mathematical Induction

4.2 Strong Induction and Well-Ordering

Using Strong Induction in Computational Geometry

Proofs Using the Well-Ordering Property

The Growth of Combinations of Functions

4.3 Recursive Definitions and Structural Induction

Structural Induction

Generalized Induction

 Section 4.1: 1-7,13-45, 57
Section 4.2: 3,5,9,25,29
Section 4.3: 1-15, 23-31 		Assignment 2 due at break in class
Lecture notes.
Tuesday, May 29th

4.4 Recursive Algorithms

Proving Recursive Algorithms Correct

Recursion and Iteration

5.1 The Basics of Counting

Tree Diagrams

7.5 Inclusion-Exclusion

 Section 4.4: 1, 7-11, 17, 45, 47
Section 5.1: 1-35, 39, 41, 42, 45
Section 7.5: 1-7, 11, 13 		Lecture notes.
Thursday, May 31st

5.2 The Pigeonhole Principle

5.3 Permutations and Combinations

 Section 5.2: 1-9, 13-19, 29-37
Section 5.3: 1-27, 31-41
 In class mid-term exam (1 hour 20 mins)
Lecture notes.
Tuesday, June 5th

5.4 Binomial Coefficients

Pascals Identity and Triangle

Some Other Identities of the Binomial Coefficients

5.5 Generalized Permutations and Combinations

Distributing Objects into Boxes

8.1 Relations and Their Properties

 Section 5.4: 1-11, 15, 17, 25
Section 5.5: 1-13, 17, 19, 31, 33, 35
Section 8.1: 1

Note: There is a small error in the notes on p.69. Example 2, should be 14 choose 11 solutions (or 14 choose 3), not 14 choose 4 as written since r = 11 in this case.

Lecture notes.
Thursday, June 7th

8.1 (continued)

8.3 Representing Relations

8.4 Closures of Relations

 Section 8.1: 1-7, 31, 35, 37, 41, 43, 49-55
Section 8.3: 1, 3, 9, 15, 19-27
Section 8.4: 1-11, 19-29 		Lecture notes.
Assignment 3 due at break in class
Tuesday, June 12th

8.5 Equivalence Relations

8.6 Partial Orderings

Lexicographic Order

Lattices

 Section 8.5: 1-15, 19-33, 39-43, 47
Section 8.6: 1-15, 21-27, 33, 35, 39, 65 		Lecture notes.
Thursday, June 14th

9.1 Graphs and Graph Models

9.2 Graph Terminology and Special Types of Graphs

9.3 Representing Graphs and Graph Isomorphism

Incidence Matricies

9.4 Connectivity

Paths and Isomorphism

Counting Paths Between Vertices

10.1 Introduction to Trees

10.3 Tree Traversal

Universal Address Systems

Infix, Prefix, and Postfix Notation

 Section 9.1: 1-11, 17, 19, 25-29
Section 9.2: 5-11, 21-29, 43, 45, 49
Section 9.3: 1-25, 35-39
Section 9.4: 1-5, 11, 15, 29, 31, 37
Section 10.1: 1
Section 10.3: 9, 13-21 		Lecture notes.
Some additional notes
Assignment 4 due at break in class