General Information

Student: Linda Cook
Office: Core 446
School: Rutgers University
E-mail: me
Project: 3-Dimensional Numerical Matching and Complexity
Mentor: Jacob Baron, Mathematics Department

Project Description

This summer I will be working on showing whether a special case of the NP-Hard 3-Dimensional Matching Problem is also NP Hard.


Weekly Log

Week 1:
I spent most of this week working out the parameters of my project. I started reading Garey and Johnson's Computers and Intractability to get a better foundation on NP-completness. I met with Professor Saks and recieved some excellent advice. I met with Jacob Baron and confirmed that he will be my mentor this summer. He showed me his attempt to reduce the special case of 3DNM to the general case. He also explained the coast guard boat sharing origins of this problem. On Friday gave my first presentation to the REU.
Week 2:
Thus far, I have typed up everything I know 3DNM and asked about the parts of my mentors reduction attempt I didn't understand. I have also been continuing to read Computers and Intractability. I attended my first Bridge Workshop and was treated to a most interesting presentation about Chomp with Dr. Zeilburger. I drew some better figures to illustrate 3DNM and the special case for use in future presentations. My goal is to understand the reduction of why 3-Dimensional Matching is NP-Hard.
Week 3:
I continued to read Computers and Intractability. I watched some of Erik Demaine's lectures on Reductions. I began working on a possible reduction of 3DNM to the special case of 3DNM.
Week 4:
I was having difficulty proving that the reduction from last week is in fact a reduction, so I worked on some scripts to see if a counterexample could be found. My module will be checking to see if there is an instance of 3DNM which has no matching but has a matching when it is "reduced" to an instance of the special case. Unfortunately since 3DNM is NP-Hard and obviously at this point I don't know if there is a polynomial time algorithm, so I am trying to find a resonable algorithm for this and am somewhat limited in my dataset size. I have also been learning about some existing reductions including that of 3DNM and recieved some excellent explanations from Adam. I met with my mentor and discussed the current reduction attempt and some other approaches I might try. He agrees that the reduction idea I've been working on is probably correct, but proving it is another story.
Week 5:
I continued working on the proof of the reduction attempt and read about other reductions in Garey and Johnson. I finalized my lesson plan for the introduction to programming workshop I will be leading next week and taught it to my two co-teachers. The workshop is being put on as a part of a research program for women in STEM through the Douglass Project at Rutgers and hopefully it will be an encouraging first experience with computer science. I was able to get some great teaching advice from REU member Jen, that I will certainly use in the workshop and in my teaching through Douglass Dimacs Computing Corps . <\dd>
Week 6:
My workshop was this Monday and I think it went well. There were about 30 attendents from programs including Douglass Stem Summer Stipends, Rodkin's Scholars, a Verizon Internship and the Dimacs REU. We first introduced the idea of an algorithm by playing a guessing game with a Finch robot I was able to borrow from Douglass Dimacs Computing Corps. The Finch would choose a random number in a range and ask participants to guess it until they got the right number. Everytime a number was guessed, the finch would say if it was too high, too low, or do a fabulous dance routine if the number was correct. The participants were able to discover binary search as a strategy after 2 games. For the second part of the workshop we introduced the concepts of variables, conditionals and loops. Since we only had an hour for the entire workshop, I opted to use Scratch an introductory programming tool so my co-teachers and I wouldn't have to explain syntax and could get through more concepts. Finally we were able to guide the group through the implementation of the guessing game on Scratch . At the end of the workshop, we talked about online programming resources and Computer Science resources at Rutgers. The evaluations from the participants were mostly positive and I will likely be running an improved version of the workshop in the Spring. The week was largely spent reading other reductions and working through more of Garey and Johnson in the hopes that I would get an idea for my problem.
Week 7:
This is my last week before leaving for the Prague component of the REU. I'm doing the final work on my project and getting ready for my final presentation on Friday.