PROFESSOR/

CONTACT:

Dr. Lucia Moura, Office: STE 5-027

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

subject line "CSI2101 <student full name>" or it may not be read)

Office hours: Mondays 12:00-13:00

WEB PAGE: http://www.site.uottawa.ca/~lucia/courses/2101-09/

LINKS/INFO:

• Lecture and tutorial material
• Assignments: A1 (posted Jan14, due Jan28), A2 (posted Feb 3, due Feb 12),
  A3 (posted Feb 27, due Mar 19), A4 (posted Mar 24, due Apr 9).
  
• MIDTERM INFORMATION
• EXAM INFORMATION (new)
• News/Announcements

LECTURES/TUTORIALS:

TUT  Mondays 8:30-10:00 (MCD 121) - tutorials are integral part of the course, presence is mandatory

Lec1  Mondays 10:00-11:30 (MCD 121)

Lec2  Thursdays 1:00-2:30 (STE J0106)

POLICIES:

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

Any mass communication with the class is going to be posted under

News/Announcements check regularly. 

TEXTBOOK:

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

Edition, McGraw Hill, 2007.

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

with tentative dates

1. Introduction to discrete structures and review of propositional logic (Sections 1.1,1.2) Jan 8,12
2. Predicate logic (Sections 1.3, 1.4) Jan 15,19
3. Review of rules of inference and proof methods (Sections 1.5, 1.6, 1.7) Jan 22, 26
4. Review of mathematical induction and strong induction (Sections 4.1, 4.2) Jan 29, Feb 2
5. Program correctness of recursive algorithms and program verification (Sections 4.4, 4.5) Feb 2, 5, 9
6. [Review lecture/Study Break/Midterm Test] Feb 12/Feb16-20/Feb 23
7. Recursive definitions and structural induction (section 4.3) Feb 26
8. Growth of functions and complexity of algorithms (Section 3.2, 3.3) Mar 2
9. Basic number theory and applications (Sections 3.4, 3.5, 3.7) Mar 5, 9, 12
10. Solving recurrence relations and complexity of divide-and-conquer algorithms (Sections 7.1, 7.2, 7.3) Mar 16, 19, 23
11. Selected problems involving graphs and trees (Selection from Chapter 9, 10 and/or other sources) Mar 26, 30, Apr 2,6
12. Review of the course Apr 9

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: February 23 (Monday) start 9:30 in MCD121
First lecture: January 8 (Thursday).
Study break: February 16-20.
Last date to drop: March 2.
Last lecture: April 9 (Thursday).
Final Exam Period: April 14-30, 2009