CSI 2101B Discrete Structures, WINTER 2017



Lucia Moura, Office: STE 5-027

email: lucia@eecs.uottawa.ca  (Your email message must have in the 

subject line "CSI2101 <student full name>" or there is a risk of not being read)

Office hours:
Wednesdays 10:15-11:45 (Prof Lucia Moura STE5027)
(TA office hours start the week of Jan 30)
Mondays 11:30-1:00 TA: Thais Bardini Idalino (room: STE0109)
Tuesdays 12:00-1:30 TA: Parinaz Sobhani (room: STE0109)
Thursdays 12:30-2:00 TA: Rana Khalil (room: STE0109)

WEB PAGE: http://www.eecs.uottawa.ca/~lucia/courses/2101-17/



LEC1  Mondays 10:00-11:30 (MRT 205)

LEC2  Wednesdays 8:30-10:00 (MRT 205)

Students must attend one of the two tutorials below:
(note that the first Tutorial will be on January 17)

TUT B1  Tuesdays 5:30-7:00 (SCS C211); TA: Thais Bardini Idalino

TUT B2  Tuesdays 5:30-7:00 (UCU 205); TA: Rana Khalil


You are responsible for reading the course's policies on plagiarism, remarking, and missed midterm.


Kenneth H. Rosen, Discrete Mathematics and Its Applications, Seventh 

Edition, McGraw Hill, 2012.


CSI2101 Discrete Structures  (3,1.5,0) 3 cr.

Discrete structures as they apply to computer science, algorithm analysis and design. Predicate logic. Review of proof techniques; application of induction to computing problems. Graph theory applications in information technology. Program correctness, preconditions, postconditions and invariants. Analysis of recursive programs using recurrence relations. Properties of integers and basic cryptographical applications. Prerequisite: MAT1348.



Discrete mathematics and structures form the very foundation for computer science, and are essential in every branch of computing.  In MAT1348 (discrete mathematics for computing) you have been introduced to fundamental problems and objects in discrete mathematics. In CSI2101 (discrete structures) you will learn more advanced concepts in this area, and at the same time increase your knowledge of  how to apply them to various types of problems in computing. While learning how to analyse an algorithm, prove the correctness of  a program, model a network problem with graphs or use number theory in cryptography, you will be sharpening your mathematical skills by practicing     problem solving, modeling, logical reasoning and writing precise proofs. 



  1. Introduction to discrete structures and review of propositional logic
  2. Predicate logic
  3. Rules of inference and proof methods
  4. Basic number theory and applications
  5. Review of mathematical induction and strong induction. Recursive definitions and structural induction.
  6. Program correctness of recursive algorithms and program verification
  7. Solving recurrence relations and complexity of divide-and-conquer algorithms
  8. Selected problems involving graphs and trees



Assignments (A)

25 %

Midterm exam (M)

25 %

Final exam (F)

50 %

Grade (G)

100 %


Final Grade (G): 

if (0.25*M + 0.50*F)/0.75 < 50% then G=(0.25*M + 0.50*F)/0.75  

if (0.25*M + 0.50*F)/0.75>= 50% then G=0.25*M + 0.50*F + 0.25*A



Assignment (currently tentative) due dates:

(A) is the average of: 

Due date: 

Assignment 1

Mon Feb 6

Assignment 2

Fri Feb 17

Assignment 3

Assignment 4

Mon Mar 13

Mon Mar 27

Tutorial quiz (participation & correctness) enters as bonus 2% addition towards 25%(A)

Midterm test date: Wednesday March 1st (8:30-10:00 room STEA0150 & STEF0126)

First lecture: January 9 (Monday).
Study break: February 19-25.
Last date to drop: March 24.
Last lecture: April 5 (Wednesday).
Final Exam Period: April 11-28, 2017