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 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.
• Found a heuristic for finding the shortest path with 3 points, and an arbitrary starting point, under some circumstances in the Sudoku Distances project. 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 points, under similar circumstances. 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.