|Homework||Post Date||Due Date||Solution|
|Homework 0||Example only; no need for submission||Solution 0|
||1/22/2020, by 11:59 pm
||2/5/2020, by 11:59 pm
||2/12/2020, by 11:59 pm
||3/4/2020, by 11:59 pm
||3/25/2020, by 11:59 pm
||4/8/2020, by 11:59 pm||Solution 6
||4/15/2020, by 11:59 pm
||4/22/2020, by 11:59 pm||Solution 8
Office Hour: Tuesdays 1:00 - 2:00 PM, Fridays 11:00 AM - 12:00 at LSRC D226 (First office hour Friday 1/17)
After Spring break: I'm
going to keep the Tuesdays 1 - 2 PM office hour on zoom. Instead of the
office hour, I will offer two 30-min sessions where I will be on piazza
trying to answer all questions posted (First two will be Thursday
3-3:30 pm and Friday 10:30-11:00 am, 4/2 and 4/3). For the first two
hour Tuesday 3/24 and 3/31 I need to change the time to 12:30 - 1:30 PM.
TA office hoursPhysics 259 6:30 - 8:30 PM Sundays and Tuesday 2/4
Recitations: Check your individual recitation sessions.
After Spring break: See this post on piazza, you are
recommended to stay with your section if your TA is still teaching at
the same time and it's possible for you to attend. If you have any
difficulty, you can go to a different recitation session that is most
convenient for you. We will also record one of the session so you can
watch it offline even if you cannot attend.
For most recent recitation materials please check this folder on Sakai.
Notice: The first
recitation will be a review of materials already covered in 230 and is
optional. Only some of the sessions will be open, you should go to the
classroom based on your time.
1:25 pm and 4:40 pm in LSRC D106, 3:05 pm in Soc. Psych. 126
Text Book:Lecture notes will be uploaded on the course website after every lecture. In addition, the following books cover most of the syllabus:
There are two hard prerequisites (equivalent courses are also acceptable):
Evaluation:The grades will be determined by homework, two midterm exams and final exam. All exams are in-class closed-book exams.
Note: According to school policy, the
course is defaulted to S/U grading. All of you should expect to get an
S as long as you continue to work on the homework/exams to your capacity, and I'd be
happy to discuss with anyone who has more difficulties. If you do want
a letter grade, you need to submit a form by April 22 (the form is required by Trinity so check your email for the exact date).
There will be 8 homeworks. In normal cases
homeworks are due
one week after they are posted. The worst two grade out of 8 homeworks
will be dropped.
Homework will be submitted through GradeScope. Homework should be typed and submit as a PDF file. LateX is highly preferred.
If you are not familiar with LaTeX and want to learn, I learned how to use it by reading this (but there are also other resources you can find online).
Please make sure to read the guideline on collaboration. Every incidence of cheating will be reported.
Questions about homework problems should be posted to Piazza (instead of emailing the TAs or the instructor).
|1/8||Intro: Algorithms, Asymptotic Notations||Slides Notes Scribe
|Basic Algorithm Design Techniques|
|1/13||Divide and Conquer||Slides Notes Scribe
2, KT 5, CLRS 4
|1/15||Slides Notes Scribe
||Martin Luther King, Jr. Day holiday. No
classes are held.
||Slides Notes Scribe
6, KT 6, CLRS: 15
|1/27||Slides Notes Scribe
|1/29||Slides Notes Scribe
||Greedy Algorithm||Slides Notes Scribe
||DPV 5, KT 4, CLRS: 16|
|2/5||Slides Notes Scribe
|2/10||Slides Notes Scribe
Exam 1 (in class)
All previous materials.
|2/19||Graph representations and traversal||Slides Notes Scribe
||DPV 3, KT 3, CLRS 22|
|2/24||Slides Notes Scribe
|2/26||Shortest Path Algorithms
||Slides Notes Scribe
||Homework 4||DPV: 4.6, 6.6 KT: 6.8
CLRS: 24.1, 25
||Minimum Spanning Tree||Slides Notes Scribe
||DPV: 5 KT: 4 CLRS: 16, 23|
|3/4||Slides Notes Scribe
|3/23||Linear Programming, Relaxations||Slides Notes Scribe
|3/25||Duality||Slides Notes Scribe
|3/30||Bipartite Matching, Max Flow
||Slides Notes Scribe
||Linear Programming Algorithms||Slides Notes Scribe
|Topics: Randomized Algorithms and Amortized Analysis|
||Basic Probabilities, Quicksort revisited, fast selection||Slides Notes Scribe
CLRS: 5, 11
|4/8||Hashing||Slides Notes Scribe
|4/13||P vs NP, reductions||Slides Notes Scribe||DPV:
8 KT: 8|
|4/15||More reductions||Slides Notes Scribe
||Even more reductions||Slides Notes Scribe
|4/22||Amortized Analysis||Slides Notes
||KT 4.6 CLRS 17, 20|
Everything covered in class
|Previous Second Midterm