Epsilon approximations, PTAS and FPTAS. Techniques for the design of approximation algrorithms. P, NP, NP-complete problems, polynomial transformations, Turing reductions, strong NP-completeness, NP-hardness and inapproximability results. Topics in algorithms include: amortized analysis, advanced graph algorithms and data structures.

Prerequisites: Computer Science 130A-B.

4

Units

Letter

Grading

1, 2, 3

Passtime

None

Level Limit

Engineering

College
These majors only cmpsc
LOKSHTANOV D
Daniel Lokshtanov
3.8
19 reviews
See All
CMPSC 230 Gonzalez T F Spring 2018 Total: 6
CMPSC 230 Gonzalez T F Winter 2017 Total: 6
See All
19
3.8
CS130B . Lokshtanov D 3 Months Ago

Prof. Lokshtanov is a super engaging lecturer. His exams/homework are hard because the material is hard. He genuinely wants us to learn, so he avoids questions that test for memorization, which results in very complicated premises--most of the time I struggled with understanding the question. He's also caring and accessible through office hours.

0 helpful 0 unhelpful
130B . Lokshtanov D 3 Months Ago

I don't know why he's not rated higher. Incredibly good lecturer, really makes sure you actually understand the material. Homework was fair and tests were generously curved (and they weren't crazy hard or anything.) He made difficult concepts, like dynamic programming, seem simple.

0 helpful 0 unhelpful
CS130B . Lokshtanov D 1 Year, 9 Months Ago

Hardest class I've taken. He had no idea how hard to make the tests, since he's very smart and struggles to think down at our level. I did enjoy lectures, he was passionate and left me at a loss for words every time (I was lost). The few people who understood everything made sure to let everyone know they understood everything. Generous curve.

0 helpful 0 unhelpful
CS130B . Lokshtanov D 1 Year, 9 Months Ago

He's a passionate lecturer that's for sure. But that's really as far of credit as I can give him. Most times I felt I was learning significantly better from just youtube videos. Not the best at making his lectures easy to regurgitate. Doesn't provide much if any resources besides "go read the textbook". Doesn't post any notes. Best to avoid.

0 helpful 0 unhelpful
CS130B . Lokshtanov D 1 Year, 9 Months Ago

Lectures are super thorough and you can tell he really loves teaching algorithms. You have to make sure you're ready to understand and paying 100% attention during lectures though because if you get distracted even for a few minutes, you will be completely lost. Exams are really hard but very good prep for CS internships and interviews.

0 helpful 0 unhelpful
CS130B . Lokshtanov D 1 Year, 9 Months Ago

Prof is super knowledgable about subject, but bad at explaining concepts to those seeing them for the first time. Lecture material not provided outside of class, and exam questions are confusing.

3 helpful 0 unhelpful
See all 19 reviews
CMPSC 192
0 / 20 Enrolled
Projects in Computer Science
T B A
95.9% A
CMPSC 193
0 / 5 Enrolled
Internship in Industry
T B A
98.3% A
CMPSC 196
0 / 10 Enrolled
Undergraduate Research
T B A
98.6% A
CMPSC 196B
0 / 5 Enrolled
Undergraduate Research
T B A
100.0% A
CMPSC 199
0 / 5 Enrolled
Independent Studies in Computer Science
T B A
100.0% A
CMPSC 211C
4 / 11 Enrolled
Numerical Solution of Partial Differential Equations--Finite Difference Methods
Hector Ceniceros 3.1
T R
09:30 AM - 10:45 AM