EECE 320 – Discrete Structures & Algorithms

 

Instructor: Matei Ripeanu

TAs: Sarah Motiee

 

Announcements

[02/04]    Projects due April 21, 11:59pm. No extensions.

[02/04]    Final exam: April 23, 3:30 pm  MCLD 254.

[02/04]    Project description– minor updates.

[19/03]    Assignment 4 posted.  Due date Thursday, March 26.  Submission: drop-in box next to Macleod 242.

[26/02]    Project description posted.

[07/01]    We will not use WebCT for this class. All announcements will be made on this web page and on the class mailing list. Subscribe to the class mailing list either by emailing sympa@ece.ubc.ca with “subscribe eece320@ece.ubc.ca” in the body of the message or by visiting https://oldlists.ece.ubc.ca

 

Logistics

·        Class: Thu 5:00-8:00 McLeod 254

·        Office hours: after each class in KAIS 4033. Other times by appointment.

 

Lecture schedule (tentative)

         

 

Date

Topic

Reading

         

Assignments

W1

8/01

Course orientation. Introduction. Propositional logic [s01.1][s01.2]

Rosen 1.*

 

W2

15/01

More proof examples. Inductive reasoning. [s02.1] [s02.2]

Rosen 1.6, 1.7. Rosen 4.*

A1

[due 01/23]

W3

22/01

More induction. Correctness and complexity proofs for recursive algorithms. [s03.1] Sets [s03.2]

Rosen 4.*

Rosen 2.1, 2.2

 

 

W4

29/01

Quiz. Quiz review. Sets & set representation [s04.1].

Rosen 2.1, 2.2

 

 

W5

05/02

Functions. O-notation. [s05.1] Algorithm complexity.

Binary search trees.[s05.2] Divide and conquer (mergesort).

Rosen 2.3

Rosen 3.1-3.3

Rosen 4.*

Rosen 10.1-10.2

A2

[due 02/26]

W6

12/02

Red-black trees [s06.1]. Summations [s06.2]. Project discussion.  Hufman encoding [s06.3]

Rosen 4*

Rosen 10.1-10.2

Red-black trees

 

 Midterm break

W7

26/02

Quiz. MiniMax [s07.1].  RedBlack trees (cont). Graphs intro. [s07.2]

Rosen 9.1-9.4

[A2 due]

W8

05/03

Graphs (cont). Graph representation [s08.1]. Graph coloring [s08.0]. Spanning trees.  [s08.2]

Rosen 9.* (except 9.6)

Rosen 10.4, 10.5

A3

  [due 03/12]

W9

12/03

More graphs: Traveling Salesman Problem. Dijkstra’s Algorithm. Bipartite Graphs. [s09.1][s09.2][demo Dijkstra]

Rosen 9.*, 10.*

[A3 due]

W10

19/03

Quiz. Counting. [s10]

Rosen 5.*

A4

  [due 03/26]

W11

26/03

More counting. Discrete probability theory. [s11.1] [s11.2]

Rosen 5.*

Rosen 6.1, 6.2

[A4 due]

W12

02/04

Quiz. Complexity Theory: Reductions Between Computational Problems.  The P vs. NP Question [s12.1]

 

 

 

Discussion list

Subscribe to the class mailing list either by emailing sympa@ece.ubc.ca with “subscribe eece320@ece.ubc.ca” in the body of the message or by visiting https://lists.ece.ubc.ca/

 

Textbook

Discrete Mathematics and Its Applications, 6th Edition, by Kenneth H. Rosen,

         

Grading

· Quizzes: 30%

· Final exam: 30% (no midterm)

· Assignments: 20%

  Programming project: 20%

 

Lecture Notes

Some lectures will not have lecture notes. Students are responsible for taking their own lecture notes.

 

Attendance

Class attendance is mandatory, though attendance won't be taken. Most of the course material, including assignments and some lecture notes, will be posted on the class web pages. However, some topics may get covered in class and not reflected in the online notes. You're responsible for all material covered in class, whether or not it appeared on the Web site - I suggest you ask a fellow student, the TA, or the professor to fill in any material you may have missed.