ECE 103    Discrete Math for Engineers
Spring 2008

Lectures:    MWF    12:30  to  1:20  pm,    Room:    RCH  302
Tutorials:    Monday    2:30  to  4:20  pm,    Rooms: MC 4041, MC 4058, 4063
Office hours:    check here

Announcement

Sept. 3: If you wish to review your final exam, I am also available Thu. Sept. 11, from 5 -- 6 pm. You are encouraged to read the solutions before coming for a review.

August 30: The statistics for the course grades are on the marks page. Solutions and the grading scheme for the final exam are available on the exams page. If you wish to review your exam, they are available with your instructor on Tue. Sep. 2, from 3 -- 4 pm. You are encouraged to read the solutions before coming for a review.

August 14: Marks for all graded components except the final exam have been posted on the Marks page; please check for any discrepancies.

Past announcements are available here.

Instructor

 Ashwin Nayak anayak [at] uwaterloo MC 4034 x36601

Teaching Assistants

 Tut 101 Ashkan Aazami aaazami [at] uwaterloo MC 5172 x36674 Tut 102 Mohammad Derakhshani mderakhshani [at] uwaterloo MC 5136A x36895 Tut 103 Kayo Yoshida k2yoshida [at] uwaterloo MC 4018A x37037 Office hours Pu (Jane) Gao p3gao [at] uwaterloo MC 5043 x33922

Outline

This course introduces first year engineering students to basic elements of discrete mathematics. The idea is to gain familiarity with concepts of fundamental importance to computer science on a mathematically rigorous footing.

List of topics:

• Logic, proofs, mathematical induction
• Divisibility, primes, GCD
• Extended Euclidean algorithm, linear Diophantine equations
• Linear congruences, Fermat's little theorem, Chinese remainder theorem
• Public key cryptography, RSA (including fast exponentiation)
• Counting, probability
• Recurrence relations, recursive definitions
• Graph theory basics:
• Connectivity, trees, bipartiteness
• (New) Breadth-first search and applications
• Planarity, Euler's formula
Consult the lecture schedule for a more detailed list of topics.

Text

Discrete Mathematics for Engineers: Course Notes for ECE 103
Department of Combinatorics and Optimization, University of Waterloo
Spring 2008 edition

This is available through Campus Copy locations, e.g., in MC 2018, and costs \$20.07 + tax.

The text should not be treated as a substitute for the lectures. The lectures may present the material covered in the text in a different manner, or deviate from it entirely. You should take your own notes in class.

Homework problems will be assigned from the exercises in the text. If you use an earlier edition of the course notes, please ensure that you solve the questions as in the Spring 2008 edition.

Evaluation

The final mark in the course will be based on homework, quizzes conducted during the tutorials, one midterm, and the final exam. The weight given to the different components  is

1. Homework:    14%
2. Quizzes:          6%
3. Midterm:        30%
4. Final:              50%
(New) An alternative weighting will be applied if it leads to a better mark:
1. Homework:    14%
2. Quizzes:          6%
3. Midterm:        10%
4. Final:              70%
Being regular in attending the lectures and tutorials, and completing the homework will help you do well in the exams and the course as a whole. If you are falling behind, you should seek help from us, i.e., your TA and instructor immediately. We will try our best to help you catch up.

Homework

There will be nine graded homework assignments in all. The best seven of these will be counted towards your final mark in the course.

A homework is due every Monday, except on May 19, June 16, and June 30. It will be posted on the web at least five days in advance. The homework will be based on the material covered in class until the preceding Wednesday. Each assignment will consist of four to five questions. You are required to attempt all of them. The homework will be collected by your TA at the end of the tutorial on the due date. Graded homework will be returned to you in the next tutorial.

You should be able to solve most of the problems in the homework on your own if you have understood the lectures. However you can expect an odd question that will require additional thought. You may work on the homework in small groups (and are encouraged to do so, in case of difficulty). You may also consult your TA or the instructor during their office hours and tutorials. However, you should write up the solutions on your own and mention all sources of help. Solutions will be posted on the web after the due date.

Tutorials

From May 12, there will be a tutorial every Monday (except on university holidays, May 19 and June 30) at 2:30 pm running for roughly two hours.

The first hour and twenty minutes of the tutorials will be open for a discussion of the homework and a review of the lectures. You are encouraged to approach the TAs with any difficulty you face in the lectures and homework during this time.

During the last half hour of the tutorial, there will be a quiz (except on June 16), which each of you is required to complete on your own, possibly with our help. The problems assigned in the quiz will be of similar difficulty to the ones in the homework, and will test the same material. You are free to consult the text, your notes, or us for the quiz. However, you are not allowed to discuss the problems with your classmates.

The homework and quiz will be collected at the end of the tutorial and returned to you in the next tutorial, after grading. Solutions to the quizzes will be posted on this web page on the next day.

There will be nine quizzes in all: one in every tutorial except on June 16. The best seven of these will be counted towards your final mark in the course.

Office hours

The instructor and one TA will make themselves available to help you with the course every week (check here). You are advised to see us during that time (or during the tutorial) if you have any difficulty with the lectures, homework, or any other aspect of the course. Please use email only in special circumstances. We may not be able to answer all your email queries individually.

Feedback

Please pass on your comments, criticism, and opinions on the course to us; these are always welcome. You may choose to do this through your class representatives, or write directly to us.