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)

Office Hours Schedule

All Office Hours are in 411 Soda

 

Resources

Piazza (Ask Questions Here)

Required Textbook

Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani

Logistic Email

cs170 [at] berkeley.edu

Past Exams

TA and Previous TA Resources

Raymond Chan's Slides Tutorial Videos
Allen Tang's Resources

Course Staff

Instructors

Alessandro Chiesa
Satish Rao

GSIs

Vinay Koshy
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
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
I grew up in Virginia and here I am in my last year of undergrad and my second semester on this staff. I like to play piano and drums in my free time. I hope you have a great semester! Feel free to literally ask me anything.
Ajay Raj
The tiny police leave the jalopy and put one out front (4)
Arun Ganesh
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
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
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
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
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
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
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
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
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
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
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
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
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
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
I'm a PhD student in the theory group, interested in complexity theory and cryptography.
Perla Gamez
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
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
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
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
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
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
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
hahaha
Please add berkeley.edu to all emails

Readers

Alex Le-Tu
Hi there! I'm a third year studying CS with a heavy interest in ML, AI, and teaching! The last one is really something I've picked up over the past few years and am still looking for ways to improve my teaching experience, an hopefully yours in 170!
Andrew Chan
Anindit Go
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
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
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
Hello! I am a third year CS major. I like penguins :)
Gillian Chu
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
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
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
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
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
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
If you like algorithms half as much as I like memes, you're in the right class.
John Xiang
hi
Kevin Liu
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
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
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
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
3rd year CS major. Talk to me about Mura Masa, The Wire, basketball, ... or efficient algorithms and intractable problems.
Sarah Young
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
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
Timmy Liu
Yi Zhao
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