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 it may not be read)

Office hours: Mondays and Fridays 1:15PM-2:15PM

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

LINKS/INFO:

• Lecture and tutorial material
• Assignments: a1 (solution), a2 (solution), a3 (solution), a4 (solution)
  OFFICE HOURS WITH T.A. Morvarid Sehatkar (room SITE-3033):
  questions on A4; questions on marking of A2.
  • Thursday March 29; 11:30AM-1:00PM
  • Friday March 30; 12:00-1:30PM
  • Tuesday, April 3rd, 5:30 -7:00PM
  • Wednesday, April 4th, 12:00 - 1:30
• Quiz solutions: quiz 1,quiz 2 quiz 3,quiz 4, quiz 5,quiz 6, quiz 7,quiz 8, quiz 9.
• MARKS: all marks (new!), quizes 1-9
• PREVIOUS FINAL EXAM

LECTURES/TUTORIALS:

Lec1  Mondays 11:30-1:00 (MRT 250)

TUT  Tuesdays 4:00-5:30 (FTX 133) - tutorials are mandatory

Lec2  Thursdays 1:00-2:30 (MRT 250)

POLICIES:

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

TEXTBOOK:

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

Edition, McGraw Hill, 2007 or 2012. (references given to 6th edition as it was voted the official version by vast majority of students)

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.20*A + 0.05 *Q

IMPORTANT 

DATES:

Assignment (currently tentative) due dates:

Midterm test date: Thursday March 1st (room to be announced)

First lecture: January 9 (Monday).
First tutorial: January 10 (Tuesday).
Study break: February 19-25.
Last date to drop: March 16.
Last lecture: April 5 (Thursday).
Final Exam Period: April 11-24, 2012