DC 2338, trevor "dot" brown "at" uwaterloo "dot" ca.
Office hours: Mondays 3-4pm
DC3351, semih "dot" salihoglu "at" uwaterloo "dot" ca.
Office hours: Thursdays at 4pm.
DC 3522, dstinson "at" uwaterloo "dot" ca.
Office hours: Tuesdays 11am-12pm
|LEC 001||11:30-12:50 TTh||MC 2054||Semih Salihoglu|
|LEC 002||02:30-03:50 TTh||MC 2038||Semih Salihoglu|
|LEC 003||04:00-05:20 TTh||PHY 235||Douglas R Stinson|
|LEC 004||01:00-02:20 TTh||MC 2035||Douglas R Stinson|
|LEC 005||04:00-05:20 TTh||E2 1736||Trevor Brown|
Tutorials start on Friday, January 11.
|TUT 101||03:30-04:20F||MC 4060|
|TUT 102||02:30-03:20F||MC 4041|
|TUT 103||08:30-09:20F||MC 1056|
|TUT 104||01:30-02:20F||MC 4063|
|TUT 105||09:30-10:20F||MC 4041|
|TUT 106||12:30-01:20F||MC 4063|
|TUT 107||11:30-12:20F||MC 4042|
Wednesday, January 23: 10:30am-11:30am, DC 3102
Friday, January 25: 11:30am-12:30pm, DC 3126
After the first week, all Friday office hours will be in DC 2136A and DC 2136B. We couldn't obtain DC 2136B for all of the Wednesday consulting hours, so the alternate room (in addition to DC2136A) is listed beside each date below.
Your final course mark is a weighted average of the above three components.
|Week||Topics & Reading||Dates||Brown||Salihoglu||Stinson|
|1||Overview, Examples of Algorithmic Design Paradigms
Math Review: Asymptotic Notation, Loop Analysis, Recurrences (CLRS 3)
|Tuesday, Jan. 8||PDF, PowerPoint||PDF, PowerPoint||Revised PDF,
supplementary note (PDF)
|Thursday, Jan. 10||PDF, PowerPoint, Required background||PDF, PowerPoint|
Asymptotic Notation (CLRS 3), Recurrences (CLRS 4.3-4.6), Reductions
(Some sections may cover example Divide & Conquer algorithms)
|Tuesday, Jan. 15||PDF, PowerPoint||(Please See Doug & Trevor's Notes on Math Review & Recurrences)||Revised PDF|
|Thursday, Jan. 17||PDF, PowerPoint|
|3||D & C Example Computational Problems and Algorithms (CLRS 4.2, DPV 2.1)||Tuesday, Jan. 22||PDF, PowerPoint||PDF, PowerPoint|
|Thursday, Jan. 24||v2: PDF, PowerPoint|
|4||D & C Finish (DPV 2.1) & Greedy Algorithms 1 (CLRS 16.1, 16.2)||Tuesday, Jan. 29||v1: PDF, PowerPoint||PDF, PowerPoint||note2.pdf
Revised Greedy Algorithm PDF
|Thursday, Jan. 31||v2: PDF, PowerPoint||PDF, PowerPoint|
|5||Greedy Algorithms Finish (CLRS 16.1, 16.2)||Tuesday, Feb. 5||v2: PDF, PowerPoint||PDF, PowerPoint|
|Thursday, Feb. 7||v2: PDF, PowerPoint|
|6||Dynamic Programming (CLRS 15.1-15.3)||Tuesday, Feb. 12||Snow day||PDF, PowerPoint|
|Thursday, Feb. 14||v4: PDF, PowerPoint (updated coin changing complexity *again*)||PDF, PowerPoint|
|7||Dynamic Programming and Graphs||Tuesday, Feb. 26||v1: PDF, PowerPoint||Revised PDF|
|Thursday, Feb. 28||v1: PDF||PDF, PowerPoint|
|8||Graphs (CLRS 22.4-22.5, 23.1-23.2)||Tuesday, Mar. 5||
v2: PDF, PowerPoint
v2: PDF, PowerPoint
|Thursday, Mar. 7||
v1: PDF, PowerPoint
v2: PDF, PowerPoint
|9||Graphs (CLRS 24.1-24.3, 25.1-25.2)||Tuesday, Mar. 12||v1: PDF, PowerPoint||PDF, PowerPoint|
|Thursday, Mar. 14||v2: PDF, PowerPoint|
|10||Graphs (CLRS 24.1-24.3, 25.1-25.2)||Tuesday, Mar. 19||v1: PDF, PowerPoint||PDF, PowerPoint|
|Thursday, Mar. 21||v2: PDF, PowerPoint|
|11||NP Completeness (CLRS ?)||Tuesday, Mar. 26||v3: PDF, PowerPoint||PDF, PowerPoint||
|Thursday, Mar. 28||v2: PDF, PowerPoint||PDF, PowerPoint|
|12||NP Completeness (CLRS ?)||Tuesday, Apr. 2||v2: PDF, PowerPoint||Thursday, Apr. 4||v2: PDF, PowerPoint||PDF, PowerPoint|
When the CrowdMark instance is ready, all students enrolled in the class will receive an email with a link to their individual submission site. In order to submit, upload a JPEG or PDF file (multiple pages are allowed) to each question. Please submit a separate file for each question to make the markers' lives easier! You may resubmit as often as necessary until the due date. (More detailed CrowdMark information is available at https://crowdmark.desk.com/customer/portal/articles/1639407-completing-and-submitting-an-assignment.)
Assignments will be handed out and due as follows:
|Assignment Number||Handed Out||Due||Hand In Via||Markers||Solutions|
|Fri., Jan. 11||Fri., Jan. 25, 6pm||CrowdMark||
|See "a1-solutions.pdf" on Learn, under "Assignment Solutions".|
|Fri., Jan. 25||Fri., Feb. 8, 6pm||CrowdMark||
|See "a2-solutions.pdf" on Learn, under "Assignment Solutions".|
Updated: PDF, LaTeX
|Mon., Feb. 11||
Mon., Mar. 4, 6pm
and Marmoset (Q5)
| Q1: Hong
|See "a3-solutions.pdf" on Learn, under "Assignment Solutions".
Solution has been corrected yet again (as of March 20, 2019, 9:03am). See Piazza post @515 for details.
Solution has been corrected yet again (as of April 4, 2019, 7:41pm). See Piazza post @515 for details.
|Fri., Mar. 1||
Mon., Mar. 25, 6pm
|CrowdMark|| Q1: Akshay
|See "a4-solutions.pdf" on Learn, under "Assignment Solutions".|
|Fri., Mar. 22||Sun., Apr. 7, 6pm||CrowdMark (Q1-3)
and Marmoset (Q4)
| Q1: Stavros
The work you hand in must be your own. Acknowledge any sources you have used. Unless specified otherwise, you can always use any result from the textbook, notes, previous assignment, or previous course, just by citing it.
Since solutions will be posted almost immediately online, late assignments will not be accepted under any circumstances. No extensions!
In all assignments and exams, unless otherwise directed, you are expected to justify any claims that you make. The level of explanation we generally expect is "enough to convince a skeptical TA". Usually this means that a complete formal proof from first principles is not needed (unless we say so). Furthermore, since this course is essentially all about efficient use of time and space, strive to make your solutions as efficient as possible. Solutions that are technically correct, but extremely wasteful in terms of time and space, will not receive full credit.
This is not a software engineering course. We will basically never worry about trivial edge cases (such as the case of empty input), or inputs that do not match our specifications. We will not test such trivial edge cases for the programming assignments, and therefore will not take off marks for code that doesn't handle these trivial edge cases correctly. In your solutions, there is no need to spend any time dealing with these (unless you want to). However, your program should take care of the (edge) cases that are crucial to the algorithm's correctness or analysis. For example, unless the problem states so, you should not usually assume that the input size is a power of 2.
The default in this course is that all numbers we deal with are integers. If there are exceptions, we'll let you know.
Some of the algorithms we will discuss in this class have multiple versions and variations. All assignment and exam questions deal with the versions we present. If you choose to learn the material from other sources, such as Wikipedia, rather than from the course notes and textbook, be aware that sometimes these minor differences may affect the answers.
If you have a question or complaint about how your assignment was marked, you need to submit a written request for remarking to the TA who marked the relevant question. You must make initial contact with the TA within one week from the day your assignment is returned. For complaints about exam marking, you need to submit the written request to your section's instructor.
Similarly, do not solicit hints or provide hints about how to solve the homework problems on other bulletin boards, such as Facebook. Violations can result in academic sanctions.
Piazza is not the place to dispute how assignments are marked. If you have a complaint, please follow the process given above.
Marks will be available through LEARN.
This book is available electronically through the UW library catalog.
Additional reference: [DPV], Dasgupta, Papadimitriou, Vazirani, Algorithms, available here.
Additional books on DC library reserve for 3-hour loan:
There are three other resources that you might find useful:
Mental Health: If you or anyone you know experiences any academic stress, difficult life events, or feelings like anxiety or depression, we strongly encourage you to seek support.
Diversity: It is our intent that students from all diverse backgrounds and perspectives be well served by this course, and that students’ learning needs be addressed both in and out of class. We recognize the immense value of the diversity in identities, perspectives, and contributions that students bring, and the benefit it has on our educational environment. Your suggestions are encouraged and appreciated. Please let us know ways to improve the effectiveness of the course for you personally or for other students or student groups. In particular: