CPSC 320: Intermediate Algorithm Analysis
and Design
Planned Schedule
|
|
Date |
Topics |
KT |
Other
readings |
Tutorials |
|
1 |
M 1/6 |
Overview,
A story about Big-O |
2.1 |
|
|
|
2 |
W 1/8 |
Big-O, Big-Omega,
Theta |
2.2 |
|
|
|
3 |
F 1/10 |
Little-o,
little-omega |
|
|
|
|
4 |
M 1/13 |
Big-O Wrapup: Limits |
|
LLM 14.7 |
|
|
5 |
W 1/15 |
Canceled
due to snow |
|
||
|
6 |
F 1/17 |
Start of
BFS |
3.1, 3.2 |
|
|
|
7 |
M 1/20 |
BFS proof |
3.2 |
|
3: Graphs |
|
8 |
W 1/22 |
BFS proof |
3.2 |
|
|
|
9 |
F 1/24 |
Shortest
paths in weighted graphs |
4.4 |
|
|
|
10 |
M 1/27 |
Topological
ordering |
3.6 |
|
|
|
11 |
W 1/29 |
Recurrences,
Guess-and-check |
5.1 |
LLM 22.2 |
|
|
12 |
F 1/31 |
Divide-and-conquer
recurrences |
5.2 |
LLM
22.4.4 |
|
|
13 |
M 2/3 |
|
LLM 22.4 |
5: Recurrences |
|
|
14 |
W 2/5 |
Counting
inversions |
5.3 |
|
|
|
|
W 2/5 |
Midterm 1 |
|
|
|
|
15 |
F 2/7 |
Maximum
sum subsequence, |
5.5 |
Erickson
1.9 |
|
|
16 |
M 2/10 |
5.5 |
Erickson
1.9 |
||
|
17 |
W 2/12 |
Dynamic
Programming intro: |
6.2 |
|
|
|
18 |
F 2/14 |
Making
change with memoization |
6.2 |
|
|
|
|
|
Break |
|
|
|
|
19 |
M 2/24 |
Making
change with DP |
|
|
7: DP1 |
|
20 |
W 2/26 |
Making
change with backtracking |
|
|
|
|
21 |
F 2/28 |
6.6 |
Erickson
3.6 |
||
|
22 |
M 3/2 |
6.6 |
Erickson
3.6 |
8: DP2 |
|
|
23 |
W 3/4 |
6.4 |
|
||
|
24 |
F 3/6 |
Splitting
loot (Partition
problem) |
6.4 |
|
|
|
25 |
M 3/9 |
8.1 |
|
9: DP3 |
|
|
26 |
W 3/11 |
8.1 |
|
||
|
27 |
F 3/13 |
Reductions:
3SUM, Shortest Path in a DAG |
|
|
|
|
28 |
M 3/16 |
Canceled while
transitioning online |
|
|
No
tutorial |
|
29 |
W 3/18 |
Definition
of P |
|
|
|
|
|
W 3/18 |
Midterm 2 |
|
|
|
|
30 |
F 3/20 |
Reductions,
Problems not in P |
|
|
|
|
31 |
M 3/23 |
Definition
of NP |
8.1, 8.3 |
Erickson
12.1-12.3 |
10: Reductions 1 |
|
32 |
W 3/25 |
Definition
of NP-hard, NP-complete |
8.4 |
Erickson
12.3-12.5 |
|
|
33 |
F 3/27 |
3SAT.
Karp’s NP-completeness plan |
8.2-8.4 |
Erickson
12.6-12.6 |
|
|
34 |
M 3/30 |
Independent
Set is NP-complete |
8.2 |
Erickson
12.7 |
11: Reductions 2 |
|
35 |
W 4/1 |
Vertex Cover is
NP-complete |
8.1 |
Erickson
12.9 |
|
|
36 |
F 4/3 |
Decision,
Optimization and Search |
|
|
|
|
37 |
M 4/6 |
Hot water
pipes |
|
|
No
tutorial |
|
38 |
W 4/8 |
|
|
Tutorials
Weekly tutorials, starting in the first week of class,
will involve group and individual problem-solving work. Participation will be
extremely helpful in solving assignment problems and as practice for the
midterms and final. While work done in tutorials will not be graded,
participation will contribute to your overall mark. Tutorial problems will be
posted here, and solutions will be posted on Canvas at the end of each week.
We expect that you will go to the tutorial for which
you are registered. If for some reason that is not possible on occasion, you
may attend a different tutorial on that week, but make sure to let the course
coordinator know.
Hard copies will not be provided in class; the TAs
will display the problems on a projector. If you want a hard copy, print it out
and bring it with you.
Assignments
|
|
Handout |
Due |
Topics |
Link |
Tex Source |
|
1 |
F 01/10 |
M 01/20 |
Asymptotic
notation |
||
|
2 |
F 01/24 |
Su 02/02 |
Graphs,
Greedy algorithms |
||
|
3 |
W 02/12 |
W 02/26 |
Recurrences,
Divide and conquer |
||
|
4 |
F 02/28 |
W 03/11 |
Dynamic
programming |
||
|
5 |
F 03/13 |
F 03/27 |
DP
coding, Reductions |
||
|
6 |
Sa 03/28 |
W 04/09 |
NP-completeness |
Collaboration: You
can work in groups of size up to three. Each group should make a single submission
per assignment.
- The
group must spend at least 15 minutes working on each problem independently
before collaborating with others.
- Collaboration
with others is limited to discussion and brainstorming. No record of any
sort (e.g., written or electronic material) may be exchanged or leave the
brainstorming session.
- After
collaborating, each student must take a half-hour break from the problem.
Treat electronic resources you consult like written resources (set them
aside for a half-hour and then do not consult them while writing your
solution).
- Each
group must write their own independent solution, using their own words.
- Acknowledge
all collaborators or sources of assistance in your submission, although
you need only name CPSC 320 course staff, handouts, and textbooks if you
quote or adapt directly from them. You should record the names of any
other people you collaborate with.
Formatting: We require that
assignments be submitted using LaTeX. We will make the .tex
version of the assignment available, to make it easier for you to prepare your
solutions using latex.
Submission: Submit your assignments
on Gradescope by 11:59:00pm. You can submit early and
resubmit as often as you want up to the deadline. We strongly encourage
you to submit something a few days in advance of the first assignment, to
make sure that things are working properly.
After uploading to Gradescope,
link each question with all the pages of your pdf containing your solution.
Add CSID's of group members on GradeScope after one student has made the
initial submission. See the image below for adding group members to a
submission:
As a secondary failsafe, please clearly write
the CSIDs of all group members on the first page of each submission. Do not
include your names or any other identifying information on your assignments.
Non-conforming submissions:
·
Late homework
submissions will be accepted up to 24 hours past the due date, at a penalty of
15% of the assignment's full value. Please make an effort
to have your documents imaged and ready to upload ahead of time, to avoid any
last-minute stress and glitches.
·
Submissions that are not
typeset in Latex will incur a severe penalty. Their grade will be multiplied by
0.5. (If they are both late and not
in Latex, the 15% penalty will be applied first.)
Midterm Information
Dates:
·
Midterm 1: Wed February 5th, 7pm-8:30pm
·
Midterm 2: Wed March 18th, 7pm-8:30pm
Room
assignments will be announced on Piazza about two weeks before an exam.
Each midterm will cover topics
related to lectures up to the day prior to the exam, tutorials up to the week
prior to the exam and assignments submitted prior to the exam. The material
covered in the second midterm will emphasize post-midterm 1 material, but may
also cover topics earlier in the semester. You may bring ONE double-sided handwritten letter-size sheet of notes.
No textbooks or electronic devices are permitted. There will be no group
portion to the exam. Practice midterms will be posted on Canvas a week or so in
advance.
If you have a conflict with the
midterm times, inform the course coordinator (cpsc320-admin@cs.ubc.ca) by email no later
than two weeks in advance of the exam.
Do not write an exam if a medical
factor might significantly impair your performance. If you are unable to write
a midterm due to illness, inform the course coordinator (cpsc320-admin@cs.ubc.ca) immediately,
detailing the period during which you were ill.
If you do miss one midterm, your
mark for that midterm will be calculated based on your performance on the
final. If you miss two midterms, you will not be able to make up the second
one.
In accordance with UBC
Policy #65, students who are scheduled to write examinations or
attend tutorials on the holy days of their religion must notify their
instructors two weeks in advance of the religious holiday they wish to observe.
Instructors will provide opportunity for students to make up the missed work
without penalty.
Grade Calculation
·
Final exam: 45%
·
Midterm exams: 2 midterms ×
13% = 26%
·
Assignments: 6 assignments ×
4% = 24%
·
Tutorials: 10 tutorials (two
will be dropped) × 0.5% = 5%
To pass the course, you must obtain at least 50% on the weighted
average of the midterms and final exam. Students who fail to meet this
requirement will receive at most a mark of 45% for the course, regardless of
the results of the formula above.
Regrading Requests
We do our best to
grade all submissions fairly and consistently. Because graders occasionally
make mistakes, we welcome regrade requests that help us correct such mistakes
and ensure fairness. You have one week from the time that the grades are posted
to submit a regrade request on Gradescope. Please be
respectful and help us ensure that time spent on regrades is productive by
following these guidelines.
- Prior to making a regrade request,
make sure you understand the solution to the problem, and read any
comments provided on Gradescope or Piazza about
how the problem was graded. If you don't understand what's missing from
your answer, come see one of us during office hours before submitting a
regrade request.
- Explain clearly and specifically
why you believe your mark is inappropriate, referring to your solution,
and the rubric. Good examples: "I lost a point for not initializing
my table entries, but I initialize them in line 6." Or, "My
solution is quite different from the one in the sample solution, but I'm
confident that my approach also works for the following reason..."
- Don't submit a request because you
think the rubric is unfair, or if you disagree with a judgment call of the
grader. A bad example that disputes the rubric is: "I lost a mark for
not justifying my answer, but I didn't think I needed to justify my
answer, and I don't feel I should be penalized." A bad example that
disputes a judgment is: "I should get 'minor errors (-0.5 points)'
instead of 'significant errors (-2 points)'." An example that is not
sufficiently specific is: "My friend gave basically the same answer
and got a higher grade."
The person who graded the question
will review your request, possibly with input from an instructor or other TAs. The decision of your TA or instructor is final. It may
either increase or decrease your mark. Submitting several poorly-explained
regrade requests may result in a penalty.