CS 170 | Efficient Algorithms and Intractable Problems
Fall 2018
Lecture: Tu/Th 2:00-3:30pm, 155 Dwinelle
Calendar
Wk | Date | Lecture Topic | Readings | Section | Homework |
---|---|---|---|---|---|
Lecture Webcast | |||||
01 | 8/23 Th | Introduction, big-O notation, arithmetic | Chapters 0, 1.1, 2.1, 2.2 | Homework 00 Solution | |
02 | 8/28 Tu | Divide-and-Conquer | Chapter 2.1, 2.2, 2.3 | Section 00 Solution | Homework 01 Solution |
8/30 Th | Divide-and-Conquer | Chapter 2.4, 2.5, 2.6 | |||
03 | 9/4 Tu | Fast Fourier Transform | Chapter 2.6 | Section 01 Solution | Homework 02 Solution |
9/6 Th | Decompositions of graphs | Chapter 3 | |||
04 | 9/11 Tu | Paths in graphs | Chapter 4.1, 4.2, 4.3, 4.4 | Section 02 Solution | Homework 03 Solution |
9/13 Th | Paths in graphs, Minimum Spanning Trees | Chapter 4.4, 4.5, 4.6, 4.7, 5.1 | |||
05 | 9/18 Tu | Midterm 1 –– No lecture | Section 03 Solution | Homework 04 Solution | |
9/20 Th | Minimum Spanning Trees | Chapter 5.1 | |||
06 | 9/25 Tu | Greedy Algorithms | Chapter 5 | Section 04 Solution | Homework 05 Solution |
9/27 Th | Greedy Algorithms | Chapter 5 | |||
07 | 10/2 Tu | Dynamic Programming | Chapter 6 | Section 05 Solution | Homework 06 Solution |
10/4 Th | Dynamic Programming | Chapter 6 | |||
08 | 10/9 Tu | Linear Programming | Chapter 7.1 | Section 06 Solution | Homework 07 Solution |
10/11 Th | Network Flow | Chapter 7.2 | |||
09 | 10/16 Tu | Duality | Chapter 7.4 | Section 07 Solution | Homework 08 Solution |
10/18 Th | Zero-Sum Games | Chapter 7.5 | |||
10 | 10/23 Tu | Midterm 2 –– No Lecture | Section 08 Solution | Homework 09 Solution | |
10/25 Th | Reductions, Bipartite Matching | Chapter 7.3 | |||
11 | 10/30 Tu | Search Problems | Chapter 8.1 | Section 09 Solution | Homework 10 Solution |
11/1 Th | NP-Completeness | Chapter 8.2, 8.3 | |||
12 | 11/6 Tu | Coping with NP-Completeness | Chapter 9 | Section 10 Solution | Homework 11 Solution |
11/8 Th | Modular arithmetic, Primality Testing | Chapter 1.2, 1.3 | |||
13 | 11/13 Tu | Hashing, Sketching, Streaming | Chapter 1.5, notes and notes | Section 11 Solution | Homework 12 Solution |
11/15 Th | Hashing, Sketching, Streaming | Streaming | |||
14 | 11/20 Tu | Quantum factoring (or other) | Chapter 10 | Section 12 (Cancelled) | Homework 13 Solution |
11/22 Th | Thanksgiving –– No Lecture | ||||
15 | 11/27 Tu | Multiplicative updates | notes and notes | Section 13 Solution | Homework 14 Solution |
11/29 Th | Applications of multiplicative updates | Same as above | |||
16 | 12/4 Tu | RRR Week –– Review | Section 14 | Homework 15 Solution | |
12/6 Th | RRR Week –– Review |
Discussion Schedule
Start Time | Section | |||||
---|---|---|---|---|---|---|
Mon 9:00 a.m. | Dwinelle 243 (Perla) | Soda 320 (Jenny) | ||||
Mon 10:00 a.m. | Cory 241 (Sean) | Wheeler 222 (Yining) | ||||
Mon 11:00 a.m. | Etcheverry 3113 (Jerry) | Dwinelle 130 (Jeff) | ||||
Mon 12:00 p.m. | Evans 3 (Peter) | Wheeler 108 (David) | Soda 320 (Nate) | |||
Mon 1:00 p.m. | Dwinelle 182 (James) | Soda 320 (Mudit) | Barker 110 (Arun) | |||
Mon 2:00 p.m. | Evans 9 (Jierui) | Evans 70 (Simin) | Dwinelle 242 (Brandon) | |||
Mon 3:00 p.m. | Cory 289 (Ming) | Evans 9 (Harley) | ||||
Mon 4:00 p.m. | Dwinelle 79 (Aarash) | Etcheverry 3119 (Vinay) | Evans 70 (Zheng) | |||
Mon 5:00 p.m. | Dwinelle 79 (Zihao) | Dwinelle 243 (Max) | ||||
Tue 9:00 a.m. | Wheeler 108 (Matthew) | Etcheverry 3113 (Ajay) | ||||
Tue 11:00 a.m. | Etcheverry 3111 (Nick) | |||||
Tue 12:00 p.m. | Etcheverry 3111 (Sam) | |||||
Tue 1:00 p.m. | Etcheverry 3119 (Julia) |
Resources
Piazza (Ask Questions Here)
Required Textbook
Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. VaziraniLogistic Email
cs170 [at] berkeley.eduPast Exams
Semester | Midterm 1 | Solution | Midterm 2 | Solution | Final Exam | Solution |
---|---|---|---|---|---|---|
Fall 2017 | 170-fa17-mt1 | solutions | 170-fa17-mt2 | solutions | 170-fa17-final | solutions |
Spring 2017 | 170-sp17-mt1 | solutions | 170-sp17-mt2 | solutions | 170-sp17-final | solutions |
Fall 2015 | 170-fa15-mt1 | solutions | 170-fa15-mt2 | solutions | 170-fa15-final | solutions |
TA and Previous TA Resources
Raymond Chan's Slides Tutorial VideosAllen Tang's Resources
Course Staff
Instructors
Alessandro Chiesa
alexch@
|
Satish Rao
satishr@cs
|
GSIs
Vinay Koshy
Head TA
Admin: cs170@
Personal: vkoshy@
Hey, I'm Vinay! I'm currently a senior, majoring in CS, and this is my second semester teaching CS 170. I love consuming
food, movies, and music almost as much as I love talking about them, so do stop by and chat some
time.
|
Mudit Gupta
Head TA
Admin: cs170@
Personal: mudit@
Hey folks. I have an electric skateboard, a yellow notebook and a blue pen. I recently bought the skateboard; you'll probably
see me wobbling around. Apart from that, I'm a third-year EECS major from Dubai who loves CS170
and, trust me, you will love it too.
|
Aarash Heydari
aheyd@ |
Ajay Raj
araj@
The tiny police leave the jalopy and put one out front (4)
|
Arun Ganesh
arunganesh@
Hey, I'm Arun, a second year CS PhD student interested in approximation algorithms. Outside of research, I enjoy SSBM, board
games, crosswords, puzzlehunts, and spicy food. Feel free to ask me about any of these!
|
Brandon Lee
brandonxxlee@
Hello! I'm Brandon Lee, a fourth-year EECS student from Irvine, CA. In my free time I try to go outside and sometimes play
games. Come say hi!
|
David Vendrow
davidv@
Hi! I'm a third-year EECS major and former CS70 TA. In my free time, I enjoy playing chess, reading classics, lifting, and
eating chicken.
|
Harley Patton
hpatton@
Hi everybody! I'm a 4th year CS and Applied Math major. In my spare time I enjoy biking, playing the saxophone, and stalking
my TAs on EECS department course websites.
|
James Hulett
jhulett@
Hi! I'm a fourth year Math and CS major. In my free time, I enjoy writing self-referential staff bios that have exactly one
hundred fifty seven characters.
|
Jeff Xu
jeffxusichao@
Hi! I'm a third year CS major. I like theory, Go, musicals and FIFA. I hope you enjoy this class as I do! Feel free to chat
with me about anything or recommend a musical to me. Hail to TASanana!
|
Jenny Huang
jph17@
Hi! My name is Jenny and I'm a third year CS major from Canada, NJ, and MA. In my free time, I like eating, cooking, baking,
drinking boba, dogspotting (CORGIS), dancing, and hiking. Feel free to introduce yourself and
come talk to me!
|
Jerry Park
jjhpark@
I would put a photo of my kittens, but that would be confusing... if you want to see pictures of them, ask me at office hours!
https://youtu.be/dQw4w9WgXcQ
|
Jierui Lin
jerrylin0928@
Hi all! I am a third-year CS & Applied Math major. I just took CS 170 last semester, so I have a pretty fresh memory of the
course material. To me, this course is like an art appreciation of the most brilliant minds in
the history of CS & Math. I’m sure you’ll learn a lot from this. In my free time, I enjoy watching
movies, listening to music and playing soccer. Feel free to chat with me about anything!
|
Julia Luo
julialuo@
Hi there! I'm Julia, a third-year EECS student from London, Ontario, Canada (it's near Toronto). I love playing soccer, snowboarding,
hitting the gym, painting, dog spotting, and algorithms (obviously) - come talk to me about any
of these things :) CS 170 is a beautiful, fascinating class and I know you'll agree with me after
the semester is over!
|
Matthew Soh
matthewsoh@
Hi! I'm a third-year EECS major from sunny Singapore. I love algorithms (especially graph algos), musical theatre (especially
Hamilton) and making good coffee (especially flat whites).
|
Max Ovsiankin
maxov@
Hello, I'm beyond excited to teach for you all, I adore CS theory and math! My other interests include music, reading, pop
philosophy, hacking, hiking and lifting, and eating my corn in rows. I was born in Israel and
grew up in the Bay Area.
|
Ming Li
mingyli@
Hi, I'm Ming and I'm a third-year. Recently I've been watching BoJack Horseman and trying to play chess. Algorithms are pretty
neat and I hope you enjoy this course!
|
Nate Young
nateyoung@
I'm Nate. I'm a 3rd year EECS major. My best quality is that I own a cotton candy machine and in my free time I try to do
theoretical CS research, think about machine learning, and sleep. And just waste an embarrassing
amount of time. 170 is the best class. Handwavy math philosophy is the best type of philosophy.
|
Nick Spooner
nick.spooner@
I'm a PhD student in the theory group, interested in complexity theory and cryptography.
|
Perla Gamez
perlagamez@
Hello :) I am a CS transfer student. I am from Honduras, a small country in Latin America, so feel free to chat with me in
Spanish. Outside of CS I absolutely enjoy cooking, dancing, playing with my dogs, reading nonfiction
in Spanish and swimming.
|
Peter Manohar
manohar@
Hello there! I'm a fourth year EECS major from San Diego, interested in theoretical CS. Hope you enjoy CS 170 this semester!
|
Sam Zhou
jhgzhou@
Hi all! I'm a 4th year CS major from upstate NY. I love cooking and baking outside of school so I may bring some treats near
exam days. Always feel free to come chat with me about anything at all, I'm always happy to listen!
I'm very excited to teach my favorite class to everyone and I wish you all the best this semester!
|
Sean Luchen
sean.luchen@
Hiya! Junior CS major from Canada - I love making and playing games. This is my first time TAing; I love CS Theory and I
hope you enjoy this class as much as I did :)
|
Simin Liu
simin.liu@
Hey! I’m a fourth year EECS student. Outside of school activities, I am an avid snacker (ask me about Takis), only watch
bad television, and like to swim. I think CS170 is beautiful and hope you’ll find it so too!
|
Yining Liu
lyining@
Hi, I'm a third year studying CS and Applied Math. I enjoy teaching, writing notes, learning math and watching cooking videos
:P I hope you'll have a great time in 170!
|
Zheng Shi
merlin_sz@
Hi! I'm a fourth year CS student. In my spare time, I watch movies and play video games. My favorite movies for now are Terminator
2, and Prestige. I also like going around and taking photographs. I hope you all enjoy CS 170
as much as I did!
|
Zihao Chen
zihaochen@
hahaha
|
Please add berkeley.edu to all emails |
Readers
Alex Le-Tu
alexletu@ |
Andrew Chan
andrewkchan@
|
Anindit Go
aninditg@
I'm Anindit, a 3rd year CS/Math Minor. I grew up in Libertyville, Illinois but moved to the Bay Area in grade 6. Recently
I've gone through a series of severe existential crises, so I'm not 100% sure what my passions
or goals are or really even who I am as a person. I do enjoy racket sports, psychological board
games, and meeting new people, so please feel free to reach out to me about anything at all.
|
Arpita Singhal
arpitasinghal@
Hi Everyone! I’m a third year studying Computer Science and Bioengineering, hailing from the heart of Silicon Valley. I am
passionate about the intersection of technology and medicine. Outside of class, I enjoy dancing,
reading up on political issues, playing tennis, and hanging out with friends. I look forward
to meeting you all, and hope you enjoy CS 170 as much as I did! :)
|
Asli Akalin
asliakalin@
Hi, I am a third year CS and Econ major student. I like playing chess, playing piano and laughing at memes in public --inappropriately
loudly. I really enjoyed this class so I hope you do too because this class is awesome. Talk
to me about books, TV shows, languages, cats, and especially cs170, haha. Look forward to meeting
you all!
|
Dee Guo
deeguo@ |
Gillian Chu
gillichu@
Hi all! I'm a 3rd year CS and BioE minor. In my free time I like to pretend I understand math and other miscellaneous theoretical
subjects. I also enjoy cooking, loud carpool karaoke and running.
|
Gordon Jake Kole
spaceshark@
Hey! I'm a junior from the Bay Area. I play video games and watch anime when I should be working. Feel free to chat about
anything and try to enjoy this class too.
|
Jason Lum
jasonlum109@
Hello everyone, I’m a Junior cs student from New Jersey. I was a reader for this class last semester as well, so don't be
afraid to ask me any questions you may have! I loved this class and I hope you do too.
|
Jason Wang
zhanshi_wang@
Hey all I am an intern @facebook this summer and is interested in exploring many things. I like traveling. Went to Cancun
last year and this year I went to Hawaii(big island and honolulu) maybe go to (Maui and Kauai)
this thanksgiving^^ Feel free to give me recs!
|
Jiazheng Zhao
zodzhao@
Hi! I’m a a third year CS and Applied Math major. I love Rubik’s cube as you can see from the picture, and have been teaching
the decal since my second semester here. Besides that I watch TV and movies a lot. CS 170 is
my favorite class so far and I hope you all enjoy it!
|
Joe Deatrick
jldeatrick@
Hey folks! I’m a senior CS major from Florida, mainly interested in theory and security. When I’m not doing 170, I’m probably
playing some Nintendo game from the 90’s, “playing” guitar, or encrypting CS memes. 170 is one
of my favorite courses here 👌 so I can’t wait to meet you all!
|
John Son
johnyson@
If you like algorithms half as much as I like memes, you're in the right class.
|
John Xiang
johnxiang@
hi
|
Kevin Liu
kevinliu743@
Hi! I'm a third year EECS major, and I love algorithms (especially trading algorithms). In my free time I like to play basketball,
watch basketball, and dream about hitting that buzzer beater. I also like watching movies until
I run out of good movies to watch :( Hope you all enjoy this class as much as I did :D
|
Leslie Tsai
leslietsai@
Hello! I'm a 4th year CS & CogSci major. In my free time, I like playing clarinet in marching band, figure skating, drinking
boba, and watching reality TV shows & documentaries. Hope you enjoy 170! :)
|
Neha Kunjal
nkunjal@
Hi! I’m a third year computer science major from the South Bay. In my free time, I enjoy listening to music, hanging out
with friends, and exploring places. I also love meeting new people, and reading! Feel free to
recommend me a book and/or talk about anything from algorithms to cats! :)
|
Noah Krakoff
nkrakoff@
Hi, I'm Noah. I'm a third year in the Engineering Math and Stats major. I usually run or rock climb in my free time. Algorithms
are pretty cool so you'll probably enjoy this class.
|
Raymond Feng
raymondhfeng@
3rd year CS major. Talk to me about Mura Masa, The Wire, basketball, ... or efficient algorithms and intractable problems.
|
Sarah Young
sarahisyoung98@
Hi! I'm a third year CS major from the Bay Area. When I'm not doing 170 homework, I like playing piano and tennis and badminton
and cello and board games and other games and swimming!! This is one of my favorite classes ever
so I hope it will be one of yours too!
|
Shruthi Chockkalingam
shruthi_chock@
Hey :) I'm Shruthi, a third year Math and CS major. In my free time, I enjoy watching way too many NBA games, following politics
and cooking my infamous "I didn't even know pasta could be bad" pasta. Looking forward to meeting
you all, and hope you enjoy 170!
|
Teddy Tran
teddytheodoretran248@
www.creedthoughts.gov.www/creedthoughts. Check it out.
|
Timmy Liu
tliu12@
|
Yi Zhao
yi@
Hello! I'm a 3rd year EECS major from New York! In my free time, I like hiking, watching cooking videos and napping. CS 170
was one of my favorite courses at Berkeley. I hope you enjoy it as much as I do!
|
Please add berkeley.edu to all emails |