Boris Brimkov

Home Publications Teaching Resources CV

CAAM 570 Introduction to Graph Theory

Thank you all for being a part of this class and for your interest in graph theory. I enjoyed teaching and getting to know you, and I'm proud of your achievements. Have a great summer vacation, and to the graduating students, good luck in your future careers!

Resources

Syllabus

Groups

Some notation from Bondy & Murty

Assignments

Homework 1. Due Feb 1, 2018.

Homework 2. Due Feb 13, 2018.

Homework 3. Due Feb 27, 2018.

Homework 4. Due Mar 27, 2018.

Homework 5. Due Apr 19, 2018. Can be turned in by Apr 26 for half credit.

Final Exam

Final Exam. Due Apr 26, 2018.

You may use up to 5 hours for completing the final. The exam must be completed and turned in at or before 5pm on April 26, 2018, to my mailbox, or my office, or scanned and e-mailed. You may use your class notes, homeworks, and the textbook by Bondy&Murty.

Don't worry if you can't solve some problems, just do the best you can; there will be a curve, etc.

Final Project

Directions for final project. Due April 12, 2018.

Midterm Exam

Midterm Exam. Due Mar 8, 2018.

You may use up to 5 hours for completing the midterm. The exam must be completed and turned in at or before the beginning of class on March 8, 2018. You may use your class notes, homeworks, and the textbook by Bondy&Murty.

Announcements

Apr 19.The review session for the final will be held on Apr 20 at 3pm in DCH 3132. There are about 8 chairs in the room, so if you'd like to sit, arrive early. If there are too many people, we could try to find another room. If you can't make it to the review session, feel free to email me with questions or to schedule a meeting.

Apr 17. The final exam will be posted immediately after class on Thursday, April 19. You will have a week to complete it. I will hold a review session for the final (time and location to be determined on Thursday during class). If your score on the midterm was in the "Could be better" category (see below), I encourage you to attend. I also have a number of unclaimed homework assignments; if one of them is yours, please pick it up next class. If you want to make sure the Graders have recorded grades for everything you have turned in, please see me. In particular, students with the following initials are missing at least one homework grade: JC, GH, KK, RP, VS. If you are behind with work, Homework 5 can be turned in for half credit on 4/26/2018. As mentioned earlier, the students who have worked on the semester-long research projects are exempt from taking the final exam; however, if such a student wishes to take the final, he may replace his midterm grade with max{his midterm grade, his final grade}.

Apr 3. Here is a list of the midterm grades and a rough interpretation.

Super duper: {100}
Excellent: {97, 97, 93, 90, 89, 88}
Very good: {85, 83, 83, 80, 79, 78, 77, 77, 75}
Good: {70, 69, 69, 68}
Could be better: {58, 57, 53, 49, 42, 40, 39}

Mar 1. The midterm has been posted. Homework 4 will be posted soon, and will be due some time after the break. The directions for the final project will also be posted soon; check back here for those in a few days. The final exam will be a similar format as the midterm and will be given the last week of classes.

Feb 24. See the following paper for a linear-time algorithm for even/odd-length paths between two vertices; see also the bibliography therein for less efficient polynomial algorithms: A. S. LaPaugh, C. H. Papadimitriou. The even-path problem for graphs and digraphs. Networks 14.4: 507-513 (1984).

Feb 6. Apparently Thursday Feb 8 and Friday Feb 9 is Spring Recess? I just randomly found out by walking past two people talking about this in the hallway. So, for anyone else who wasn't aware: there are no classes on Thursday Feb 8 and Friday Feb 9.

Jan 24. The due date for HW 1 is changed to Feb 1 because of the snow day we had.

Jan 19. So far I've met with three groups about the extended research project: Bell-Brown-Kroeger, Mikesell-Smith(-Mildebrath?), and Patel-Suriyanarayana-Teich. If you want to work on an extended research project but have not yet talked to me, please do so ASAP.

Jan 16. I've received some concerned emails about the homework. Yes, the homework is somewhat challenging, but it's meant to be done in a group, and with some help from outside references. These are all standard problems, but think about them for a bit before seeking the solutions online. Also, we have not yet covered some of the material for this homework; I was planning on finishing it today, but I may extend the due date because of the snow day.

Jan 16. Class today is cancelled due to the weather!

Jan 10. We have been assigned a new room, effective immediately: Mech Lab 251. It seats 45 people - no need to bring your own chair.

Jan 9. Regarding the room situation: I have alerted the Registrar and they are working on a solution. There is no larger room available for the entire semester during our class time; however, they may be able to switch us with another class held in a larger room during the same time. This may take about a week; until then, there's not much that can be done.

Jan 8. Welcome to the class. The graders are Tayo Ajayi (temitayo.ajayi AT rice.edu) and Yuchen Yang (yuchen.yang AT rice.edu).