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.
|
Date |
Topic |
|
Assignments |
W1 |
8/01 |
Course
orientation. Introduction. Propositional logic [s01.1][s01.2] |
Rosen 1.* |
|
W2 |
15/01 |
Rosen 1.6, 1.7. Rosen 4.* |
[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 |
[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 |
|
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 |
[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.* |
[due 03/26] |
W11 |
26/03 |
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] |
|
|
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/
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.