| Home | Publications | Teaching | CV |
Final Project. Due: Last day of class
Homework 1. Due: Jan 28
Homework 2. Due: Feb 13
Homework 3. Due: Mar 4
Homework 4. Due: Mar 27
Homework 5. Due: Apr 17. Pledged homework, work alone!
Mar 25. Hint for HW4 #1 forward direction: hint.
Mar 22. There was a typo in HW4 #2 part b): it should say incidence matrix instead of adjacency matrix. Moreover, the incidence matrix of a digraph is signed, so a_{i,j}=1 if vertex v_i is the tail of edge e_j, a_{i,j}=-1 if vertex v_i is the head of edge e_j, and a_{i,j}=0 otherwise.
Mar 18. The long-awaited final project is posted. I had said in class that there would be two different tasks for the two different groups, but I decided it's more fair to have the same project for everyone. Now you can also work in any groups you want (including groups of size 1, if you prefer).
Jan 27. HW 2 is posted, and may be updated with a third question next week. Note that Question 2 of HW 2 is not the same as Question 2 of HW 1.
Jan 23. HW 1 has been updated with a second question. Feel free to consult outside sources in answering the homework. Part of the point of Question 2 is to do a bit of research! Just make sure you cite any outside sources you use. I will hold an office hour on Monday at 2:00pm if there are any last-minute questions.
Jan 14. Part of HW1 is posted. 1-2 more questions will be added to it next week. I'll make an announcement when the new version is posted. We will cover the 1-tree bound for TSP referred to in Homework 1 next time I'm in class. To install the integer programming solver Gurobi, request an academic licence from here, download the latest version of the solver from here, and read the documentation and code tutorials here.
Jan 14. This Wednesday (1/16) I will be out of town, but the class will have a guest speaker (Dr. Schaefer) who will talk about an application of integer programming in airline crew scheduling. Attendance may be taken. Since I will be out of town, Wednesday's office hour will be cancelled, but I will have a make-up office hour some time the following week. Also feel free to ask me any questions by email.
Jan 14. Your groups for homeworks and projects should be close to finalized. Could one person from each group please email me the names of the members of the group? If you do not have a group, also please email me, and I will assign you to a group. I encourage you to work together with your group members, as students in this class have different backgrounds and the homeworks will be easier for everyone if you work together.
Jan 7. Here are the results of the survey I gave in class today.
Knowledge in class topics:
{5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 2, 2, 1} - Linear programming
{4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1} - Integer programming
{4, 4, 4, 4, 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1} - Graph theory
{4, 4, 4, 4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1} - Computational complexity theory
{4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1} - Machine learning
{4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2} - Coding
Want to learn more about: Data science, machine learning, graph theory, deep learning, dynamic programming, approximate algorithms for combinatorial problems, proof strategies, redistricting, scheduling and optimization for healthcare logistics, aviation scheduling and routing, transplant scheduling.
I will try to cover all these topics in class at some point.
Jan 7. Welcome to the class. This page will contain assignments and other information about the class.
Some notation from Bondy & Murty
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. 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.
Directions for final project. Due April 12, 2018.
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.
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.
Apr 3. Here is a list of the midterm grades and a rough interpretation.
| Excellent: | {100, 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).
