PROFESSOR/

CONTACT:

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/

LINKS/INFO:

• Lecture and tutorial material
• Assignments: To be posted in balckboard.

LECTURES/TUTORIALS:

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

POLICIES:

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

TEXTBOOK:

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

Edition, McGraw Hill, 2012.

CALENDAR DESCRIPTION

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.

COURSE 

OBJECTIVES

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. 

COURSE 

OUTLINE

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

MARKING 

SCHEME:

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

IMPORTANT 

DATES:

Assignment (currently tentative) due dates:

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