# [CSOR E4010] Graph Theory: A Combinatorial View

- Departments: Industrial Engineering and Operations Research
- Professors: Maria Chudnovsky

The class was definitely a math class, though I happen to know that the curriculum of the other graph theory class is equally un-applied (it is much easier though). If you are interested in Graph Theory specifically, you should definitely take it. Maria Chudnovsky is one of the rising stars of the field.

As a teacher, she's decent. Her lectures are solid and she takes time to go over things twice if they're difficult. Unfortunately, the sheer volume of information sometimes means that problems on the homework call for answers that came from peripheral facts in class. In addition, the most difficult theorems she proves in class are almost impossible to wrap your head around the first time hearing them - they take up multiple blackboards and take some deep thinking to grasp.

Homeworks are proof-based and reviewed upon handing in with students giving the solutions. These review sessions were semi-helpful, and Maria elucidated the worse-written proofs. Still, I sometimes slept through this part a little.

The class when I took it was over a third PhD and masters students, so as an undergrad I was pretty intimidated. I had the impression that Maria and her TA would have given a lot of help if I had sought it more aggressively, but I didn't end up doing so.

Overall: A very solid course, with a nice and helpful teacher. If you don't mind the math orientation and fairly high level of difficulty, you should definitely take it.

#### Workload:

Homeworks: Ostensibly weekly, which were assigned annoyingly often with just 5 days to complete. However, they often ended up being two-week assignments instead, which was much easier to deal with. Content was tough, but half-proofs and almost-right proofs were given generous partial credit, especially on the final. Rigor is not demanded unreasonably in the proofs, in keeping with it being a class open to non-math majors. Not all problems will be doable - There were some that almost nobody in the class was confident enough to present their answer for. Maria intends and accepts that this is occasionally the case, so don't worry when you can't get 90%. Normally below the level of the difficult lectures also.

Exam: One hellish take-home. An experience I hope not to repeat. Graded very leniently though, with lots of partial credit. Know the lecture content.

This course started off with really basic things but moved along very quickly, covering a broad range of material at quite a deep level. Seemed that we were getting definitions in one class, and moving on to prove some famous/important theorem the next.

We got homework every 1.5 weeks or so on average, and the professor would get students to volunteer to share their answers with the class on the board, which was quite an interesting exercise.

Prof Chudnovsky is brilliant and really knows her stuff. This comes across in her lucid explanations, and her live critiques of students' proofs. (Though it was sometimes cringe inducing to see a poor soul's proof being shredded to bits in front of the whole class, I can understand that it was good training for graph theorist wanabbes.) She's also very approachable and willing to explain really basic stuff if asked.

Its not an easy course to get an A in, especially if you don't have some previous experience with mathematical proofs (speaking from experience here). But I'd recommend it if you're looking to learn something interesting and be intellectually inspired.

#### Workload:

Pretty heavy. Assignments take a fair amount of time, which can either be really enjoyable or painful-depending on whether or not you like staring at a blank sheet of paper and thinking.

Material:

Don't be mislead by the cross-listing as CSOR, this is a MATH class all the way, taught by a math person. You won't learn how to solve any real world problems using graph theory by taking this class. By "application" Prof. Chudnovsky means proving a theorem using another theorem instead of proving it only from first principles, she doesn't mean applications in real world problems.

I even had an interview where having seen this course on my resume, I was asked a very reasonable (for someone who has taken a CSOR graph theory class) applied question which of course I couldn't answer properly as we totally skipped that in the class, and what was an otherwise decent interview got spoilt. Needless to say I wasn't picked for the next round and I have now actually knocked the course off of my resume.

So, unless you are a math major or theoretical computer science Ph.D. student or some equivalent thereof in another department, this course is just going to be a wasted effort in terms of time and money. Probably the CS version of the class is a better option if you are a CS student or have spare electives left in OR.

Grading:

We were told in class that "75 is a good score in this class" and also that "you shouldn't worry too much about your grades, I know it's an advanced course, so I won't be doing averages and curves, [although it's not officially on the grading rubric] participation will count".

Assuming that 75 was indeed an A-, if you end up a point or 2 short at the end of the day, don't expect to be bumped up even if you have a 100% attendance (there were only 16 students and Prof. Chudnovsky handed back homeworks in class, so she definitely knew who is who and how regularly they came to class). In summary, appearances are deceptive, Prof. Chudnovsky has a very sugary sweet personality, but when time to assign grades comes along she can be cold hearted and mean.

#### Workload:

1 week take home exam due on the last lecture counting 50% of the grade, and is graded by the professor.

Homeworks (we ultimately managed to have 9 of them) count for the other 50%, and are graded by the TA. The homeworks are generally on a assigned on Thursday, due to the following Tuesday cycle, but adjustments were made when we didn't get through enough material in lectures.

They are all proofs, so it's hard work. If there were 4 or fewer problems (generally the case) 4 days was enough time to do them provided you don't have more that 2 other classes. There were a couple of homeworks with 5 or more problems and these are ones you are likely to bomb a problem and a half because there just isn't enough time, especially when you have exams/projects due in other classes. With the no mercy if you end up on the borderline final grading policy, this can end up making the difference.

## Directory Data

Dept/Subj | Directory Course | Professor | Year | Semester | Time | Section |
---|---|---|---|---|---|---|

IEOR / CSOR | IEOR CSOR E4010: Graph Theory: Combinatl View | Maria Chudnovsky | 2012 | Spring | TR / 5:40- 6:55 PM | 1 |

IEOR / CSOR | IEOR CSOR E4010: Graph Theory: Combinatl View | Maria Chudnovsky | 2011 | Spring | TR / 5:40- 6:55 PM | 1 |

IEOR / CSOR | IEOR CSOR E4010: Graph Theory: Combinatl View | Maria Chudnovsky | 2010 | Spring | TR / 5:40- 6:55 PM | 1 |