User:Jmiller

Joel Miller studies Computer Science at Oberlin College in Ohio, and is part of the 2016 REU program Marquette. He is working on the Sudoku Distances project with Julia Beilke, advised by Dr. Kim Factor. In his free time, he enjoys rock climbing and making music.

Progress Log

Week 1 (5/31 - 6/3)

• Attended various orientation events to become familiarized with Marquette campus, libraries, etc.
• Began research on the Travelling Salesman Problem, and its application to Sudoku Distances
• Began research on various distance metrics and their applications to Sudoku Distances

Week 2 (6/6 - 6/10)

• Learned the Christofides Algorithm, a 3/2-approximation algorithm for the TSP.
• Attended a lecture on the components of good research talks and papers led by Dr. Brylow.
• Defined terms for and made simple deductions about the nature of points in the Sudoku Distances project, including proving a stronger version of the triangle equality for some subsets of points in spaces which obey the taxicab metric.
• Formalized a definition of "in-line" points: points for which an ordering by x-coordinate corresponds to an ordering by y-coordinate.
• Found a heuristic for finding the shortest path with 3 points, and an arbitrary starting point, given that they're in-line. Proved the correctness of the heuristic.

Week 3 (6/13 - 6/17)

• Attended a lecture on good latex practices by Dr. Corliss.
• Proved that the heuristic from the previous week could be applied to paths with any number of in-line points. Proved the correctness of the heuristic.

Week 4 (6/20 - 6/24)

• Showed a method for "uncrossing" crosses in a path in the SDP, proved that the aforementioned method lowered path distance or kept it the same.
• Showed and proved optimality of a heuristic for deciding the first point in a path (after the start point).

Week 5 (6/27 - 7/1)

• Gave an 8-minute talk on the SDP and the progress made on it.
• Using the result from last week, showed that an optimal path never needs to cross itself and that a path with any number of crosses can be "un-crossed" with no addition in distance.

Week 6 (7/4 - 7/8)

• Defined the concept and construction of "Crossing graphs", which encode information about a graph and some geometric properties of that graph when it is placed in euclidean space.
• Attended a talk led by Dr.Dennis Brylow on the benefits and drawbacks of Grad School and the school choosing/application process.

Week 7 (7/11 - 7/15)

• Attended a talk on good research posters given by Dr.Kim Factor
• Proved a theorem about crossing graphs which allows one to know which edges will, when followed, lead to crossed paths.
• Proved that crossing graphs can be constructed in polynomial time, therefore enabling them to be used as part of poly-time heuristics.

Week 8 (7/18 - 7/22)

• Made poster for poster presentation next week
• Finalized a heuristic to take advantage of crossing paths/ which utilizes crossing graphs
• Finalized a heuristic to take advantage of in-line points.

Week 9 (7/25 - 7/29)

• Presented poster at poster presentation on Friday (7/29)
• Wrote first draft of paper
• Wrote first draft of final presentation
• Did analysis of two aforementioned heuristics

Week 10 (8/1 - 8/5)

• Gave final 15-minute presentation on Wednesday (8/3)
• Turned in final paper on Friday (8/5)