https://reu.cs.mu.edu/api.php?action=feedcontributions&user=Jmiller&feedformat=atomREU@MU - User contributions [en]2024-03-28T19:24:01ZUser contributionsMediaWiki 1.23.13https://reu.cs.mu.edu/index.php/User:JmillerUser:Jmiller2016-08-03T19:32:12Z<p>Jmiller: </p>
<hr />
<div>Joel Miller studies Computer Science at Oberlin College in Ohio, and is part of the [[Summer 2016 Projects|2016 REU program]] Marquette. He is working on the [[Sudoku Distances]] project with [[User:Jbeilke|Julia Beilke]], advised by Dr. Kim Factor. In his free time, he enjoys rock climbing and making music. Joel can be reached at Jmiller4@oberlin.edu.<br />
<br />
<br />
== Progress Log ==<br />
<br />
<br />
'''Week 1 (5/31 - 6/3)'''<br />
<br />
*Attended various orientation events to become familiarized with Marquette campus, libraries, etc.<br />
*Began research on the Travelling Salesman Problem, and its application to [[Sudoku Distances]]<br />
*Began research on various distance metrics and their applications to [[Sudoku Distances]]<br />
<br />
'''Week 2 (6/6 - 6/10)'''<br />
<br />
*Learned the Christofides Algorithm, a 3/2-approximation algorithm for the TSP.<br />
*Attended a lecture on the components of good research talks and papers led by Dr. Brylow.<br />
*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.<br />
*Formalized a definition of "in-line" points: points for which an ordering by x-coordinate corresponds to an ordering by y-coordinate.<br />
*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.<br />
<br />
'''Week 3 (6/13 - 6/17)'''<br />
<br />
*Attended a lecture on good latex practices by Dr. Corliss.<br />
*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.<br />
<br />
'''Week 4 (6/20 - 6/24)'''<br />
<br />
*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.<br />
*Showed and proved optimality of a heuristic for deciding the first point in a path (after the start point). <br />
<br />
'''Week 5 (6/27 - 7/1)'''<br />
<br />
*Gave an 8-minute talk on the SDP and the progress made on it.<br />
*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.<br />
<br />
'''Week 6 (7/4 - 7/8)'''<br />
<br />
*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.<br />
*Attended a talk led by Dr.Dennis Brylow on the benefits and drawbacks of Grad School and the school choosing/application process.<br />
<br />
'''Week 7 (7/11 - 7/15)'''<br />
<br />
*Attended a talk on good research posters given by Dr.Kim Factor<br />
*Proved a theorem about crossing graphs which allows one to know which edges will, when followed, lead to crossed paths.<br />
*Proved that crossing graphs can be constructed in polynomial time, therefore enabling them to be used as part of poly-time heuristics.<br />
<br />
'''Week 8 (7/18 - 7/22)'''<br />
<br />
*Made poster for poster presentation next week<br />
*Finalized a heuristic to take advantage of crossing paths/ which utilizes crossing graphs<br />
*Finalized a heuristic to take advantage of in-line points.<br />
<br />
'''Week 9 (7/25 - 7/29)'''<br />
<br />
*Presented poster at poster presentation on Friday (7/29)<br />
*Wrote first draft of paper<br />
*Wrote first draft of final presentation<br />
*Did analysis of two aforementioned heuristics<br />
<br />
'''Week 10 (8/1 - 8/5)'''<br />
<br />
*Gave final 15-minute presentation on Wednesday (8/3)<br />
*Turned in final paper on Friday (8/5)</div>Jmillerhttps://reu.cs.mu.edu/index.php/User:JmillerUser:Jmiller2016-08-03T19:31:11Z<p>Jmiller: /* Progress Log */</p>
<hr />
<div>Joel Miller studies Computer Science at Oberlin College in Ohio, and is part of the [[Summer 2016 Projects|2016 REU program]] Marquette. He is working on the [[Sudoku Distances]] project with [[User:Jbeilke|Julia Beilke]], advised by Dr. Kim Factor. In his free time, he enjoys rock climbing and making music.<br />
<br />
<br />
== Progress Log ==<br />
<br />
<br />
'''Week 1 (5/31 - 6/3)'''<br />
<br />
*Attended various orientation events to become familiarized with Marquette campus, libraries, etc.<br />
*Began research on the Travelling Salesman Problem, and its application to [[Sudoku Distances]]<br />
*Began research on various distance metrics and their applications to [[Sudoku Distances]]<br />
<br />
'''Week 2 (6/6 - 6/10)'''<br />
<br />
*Learned the Christofides Algorithm, a 3/2-approximation algorithm for the TSP.<br />
*Attended a lecture on the components of good research talks and papers led by Dr. Brylow.<br />
*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.<br />
*Formalized a definition of "in-line" points: points for which an ordering by x-coordinate corresponds to an ordering by y-coordinate.<br />
*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.<br />
<br />
'''Week 3 (6/13 - 6/17)'''<br />
<br />
*Attended a lecture on good latex practices by Dr. Corliss.<br />
*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.<br />
<br />
'''Week 4 (6/20 - 6/24)'''<br />
<br />
*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.<br />
*Showed and proved optimality of a heuristic for deciding the first point in a path (after the start point). <br />
<br />
'''Week 5 (6/27 - 7/1)'''<br />
<br />
*Gave an 8-minute talk on the SDP and the progress made on it.<br />
*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.<br />
<br />
'''Week 6 (7/4 - 7/8)'''<br />
<br />
*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.<br />
*Attended a talk led by Dr.Dennis Brylow on the benefits and drawbacks of Grad School and the school choosing/application process.<br />
<br />
'''Week 7 (7/11 - 7/15)'''<br />
<br />
*Attended a talk on good research posters given by Dr.Kim Factor<br />
*Proved a theorem about crossing graphs which allows one to know which edges will, when followed, lead to crossed paths.<br />
*Proved that crossing graphs can be constructed in polynomial time, therefore enabling them to be used as part of poly-time heuristics.<br />
<br />
'''Week 8 (7/18 - 7/22)'''<br />
<br />
*Made poster for poster presentation next week<br />
*Finalized a heuristic to take advantage of crossing paths/ which utilizes crossing graphs<br />
*Finalized a heuristic to take advantage of in-line points.<br />
<br />
'''Week 9 (7/25 - 7/29)'''<br />
<br />
*Presented poster at poster presentation on Friday (7/29)<br />
*Wrote first draft of paper<br />
*Wrote first draft of final presentation<br />
*Did analysis of two aforementioned heuristics<br />
<br />
'''Week 10 (8/1 - 8/5)'''<br />
<br />
*Gave final 15-minute presentation on Wednesday (8/3)<br />
*Turned in final paper on Friday (8/5)</div>Jmillerhttps://reu.cs.mu.edu/index.php/User:JmillerUser:Jmiller2016-07-01T19:55:42Z<p>Jmiller: /* Progress Log */</p>
<hr />
<div>Joel Miller studies Computer Science at Oberlin College in Ohio, and is part of the [[Summer 2016 Projects|2016 REU program]] Marquette. He is working on the [[Sudoku Distances]] project with [[User:Jbeilke|Julia Beilke]], advised by Dr. Kim Factor. In his free time, he enjoys rock climbing and making music.<br />
<br />
<br />
== Progress Log ==<br />
<br />
<br />
'''Week 1 (5/31 - 6/3)'''<br />
<br />
*Attended various orientation events to become familiarized with Marquette campus, libraries, etc.<br />
*Began research on the Travelling Salesman Problem, and its application to [[Sudoku Distances]]<br />
*Began research on various distance metrics and their applications to [[Sudoku Distances]]<br />
<br />
'''Week 2 (6/6 - 6/10)'''<br />
<br />
*Learned the Christofides Algorithm, a 3/2-approximation algorithm for the TSP.<br />
*Attended a lecture on the components of good research talks and papers by Dr. Brylow.<br />
*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.<br />
*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.<br />
<br />
'''Week 3 (6/13 - 6/17)'''<br />
<br />
*Attended a lecture on good latex practices by Dr. Corliss.<br />
*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.<br />
<br />
'''Week 4 (6/20 - 6/24)'''<br />
<br />
*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.<br />
*Showed and proved optimality of a heuristic for deciding the first point in a path (after the start point). <br />
<br />
'''Week 5 (6/27 - 7/1)'''<br />
<br />
*Gave an 8-minute talk on the SDP and the progress made on it.<br />
*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.</div>Jmillerhttps://reu.cs.mu.edu/index.php/User:JmillerUser:Jmiller2016-06-10T21:30:28Z<p>Jmiller: </p>
<hr />
<div>Joel Miller studies Computer Science at Oberlin College in Ohio, and is part of the [[Summer 2016 Projects|2016 REU program]] Marquette. He is working on the [[Sudoku Distances]] project with [[User:Jbeilke|Julia Beilke]], advised by Dr. Kim Factor. In his free time, he enjoys rock climbing and making music.<br />
<br />
<br />
== Progress Log ==<br />
<br />
<br />
'''Week 1 (5/31 - 6/3)'''<br />
<br />
*Attended various orientation events to become familiarized with Marquette campus, libraries, etc.<br />
*Began research on the Travelling Salesman Problem, and its application to [[Sudoku Distances]]<br />
*Began research on various distance metrics and their applications to [[Sudoku Distances]]<br />
<br />
'''Week 2 (6/6 - 6/10)'''<br />
<br />
*Learned the Christofides Algorithm, a 3/2-approximation algorithm for the TSP.<br />
*Attended a lecture on proper the components of good research talks and papers by Dr. Brylow.<br />
*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.<br />
*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.</div>Jmillerhttps://reu.cs.mu.edu/index.php/User:JmillerUser:Jmiller2016-06-03T17:05:37Z<p>Jmiller: /* Progress Log */</p>
<hr />
<div>Joel Miller studies Computer Science at Oberlin College in Ohio, and is part of the [[Summer 2016 Projects|2016 REU program]] Marquette. He is working on the [[Sudoku Distances]] project with [[User:Jbeilke|Julia Beilke]], advised by Dr. Kim Factor. In his free time, he enjoys rock climbing and making music.<br />
<br />
<br />
== Progress Log ==<br />
<br />
<br />
'''Week 1 (5/31 - 6/3)'''<br />
<br />
*Attended various orientation events to become familiarized with Marquette campus, libraries, etc.<br />
*Began research on the Travelling Salesman Problem, and its application to [[Sudoku Distances]]<br />
*Began research on various distance metrics and their applications to [[Sudoku Distances]]<br />
*With [[User:Jbeilke|Julia]], wrote an algorithm for finding the optimal solution to the [[Sudoku Distances]] problem for ''k = 3'', and proved it to be correct</div>Jmillerhttps://reu.cs.mu.edu/index.php/User:JmillerUser:Jmiller2016-06-03T17:05:10Z<p>Jmiller: /* Progress Log */</p>
<hr />
<div>Joel Miller studies Computer Science at Oberlin College in Ohio, and is part of the [[Summer 2016 Projects|2016 REU program]] Marquette. He is working on the [[Sudoku Distances]] project with [[User:Jbeilke|Julia Beilke]], advised by Dr. Kim Factor. In his free time, he enjoys rock climbing and making music.<br />
<br />
<br />
== Progress Log ==<br />
<br />
<br />
'''Week 1 (5/31 - 6/3)'''<br />
<br />
*Attended various orientation events to become familiarized with Marquette campus, libraries, etc.<br />
*Began research on the Travelling Salesman Problem, and its application to [[Sudoku Distances]]<br />
*Began research on various distance metrics and their applications to [[Sudoku Distances]]<br />
*With [[User:Jbeilke|Julia]], wrote an algorithm for finding the optimal solution to the [[Sudoku Distances]] project for ''k = 3'', and proved it to be correct</div>Jmillerhttps://reu.cs.mu.edu/index.php/User:JmillerUser:Jmiller2016-06-03T17:04:30Z<p>Jmiller: </p>
<hr />
<div>Joel Miller studies Computer Science at Oberlin College in Ohio, and is part of the [[Summer 2016 Projects|2016 REU program]] Marquette. He is working on the [[Sudoku Distances]] project with [[User:Jbeilke|Julia Beilke]], advised by Dr. Kim Factor. In his free time, he enjoys rock climbing and making music.<br />
<br />
<br />
== Progress Log ==<br />
<br />
<br />
'''Week 1 (5/31 - 6/3)'''<br />
<br />
*Attended various orientation events to become familiarized with Marquette campus, libraries, etc.<br />
*Began research on the Travelling Salesman Problem, and its application to [[Sudoku Distances]]<br />
*Began research on various distance metrics and their applications to [[Sudoku Distances]]<br />
*With [[User:Jbeilke|Julia]], wrote an algorithm for finding the optimal solution in the [[Sudoku Distances]] project for k = 3, and proved its optimality</div>Jmillerhttps://reu.cs.mu.edu/index.php/User:JmillerUser:Jmiller2016-06-03T17:03:04Z<p>Jmiller: </p>
<hr />
<div>Joel Miller studies Computer Science at Oberlin College in Ohio, and is part of the [[Summer 2016 Projects|2016 REU program]] Marquette. He is working on the [[Sudoku Distances]] project with [[User:Jbeilke|Julia Beilke]], advised by Dr. Kim Factor. In his free time, he enjoys rock climbing and making music.<br />
<br />
<br />
== Progress Log ==<br />
<br />
<br />
'''Week 1 (5/31 - 6/3)'''<br />
<br />
*Attended various orientation events to become familiarized with Marquette campus, libraries, etc.<br />
*Began research on the Travelling Salesman Problem, and its application to Sudoku Distances<br />
*With [[User:Jbeilke|Julia]], wrote an algorithm for finding the optimal solution in the [[Sudoku Distances]] project for k = 3, and proved it correct</div>Jmillerhttps://reu.cs.mu.edu/index.php/Sudoku_DistancesSudoku Distances2016-06-03T17:02:13Z<p>Jmiller: /* Notation and Formalization */</p>
<hr />
<div>The Sudoku Distances problem is a graph theoretic problem closely related to the Travelling Salesman Problem.<br />
<br />
== Problem Definition ==<br />
Consider a 9 by 9 Sudoku grid. Suppose that within this grid, the player wishes to write one specific digit in ''k'' different squares around the grid. From an arbitrary starting point, what is the shortest path for the player to take through all ''k'' squares?<br />
<br />
<br />
== Notation and Formalization==<br />
* We represent a Sudoku grid as a weighted graph, in which every square is represented by a vertex, and edges connect all vertices. In other words, we represent a Sudoku grid as ''K<sub>81</sub>''. <br />
* The edge between two squares ''a'' and ''b'' is weighted according to the distance between ''a'' and ''b'', which is determined by some distance metric. We use ''d(a,b)'' to denote the distance between two points.<br />
* We define a path ''p'' as a sequence of vertices ''a<sub>1</sub>a<sub>2</sub>...a<sub>n</sub>''. Since our graph is simple (i.e. there is only one edge between any two vertices), we can omit the edges from our representation of a path.<br />
* We define the ''cost'' of a path ''c(p)'' to be the sum of ''d(a<sub>i</sub>, a<sub>i+1</sub>)'' for all ''a<sub>i</sub>, a<sub>i+1</sub>'' which are adjacent in ''P''.</div>Jmillerhttps://reu.cs.mu.edu/index.php/Sudoku_DistancesSudoku Distances2016-06-03T17:01:37Z<p>Jmiller: /* Notation and Formalization */</p>
<hr />
<div>The Sudoku Distances problem is a graph theoretic problem closely related to the Travelling Salesman Problem.<br />
<br />
== Problem Definition ==<br />
Consider a 9 by 9 Sudoku grid. Suppose that within this grid, the player wishes to write one specific digit in ''k'' different squares around the grid. From an arbitrary starting point, what is the shortest path for the player to take through all ''k'' squares?<br />
<br />
<br />
== Notation and Formalization==<br />
* We represent a Sudoku grid as a weighted graph, in which every square is represented by a vertex, and edges connect all vertices. In other words, we represent a Sudoku grid as ''K<sub>81</sub>''. <br />
* The edge between two squares ''a'' and ''b'' is weighted according to the distance between ''a'' and ''b'', which is determined by some distance metric. We use ''d(a,b)'' to denote the distance between two points.<br />
* We define a path ''p'' as a sequence of vertices ''a<sub>1</sub>a<sub>2</sub>...a<sub>n</sub>''. Since our graph is simple (i.e. there is only one edge between two specific vertices), we can omit the edges from our representation of a path.<br />
* We define the ''cost'' of a path ''c(p)'' to be the sum of ''d(a<sub>i</sub>, a<sub>i+1</sub>)'' for all ''a<sub>i</sub>, a<sub>i+1</sub>'' which are adjacent in ''P''.</div>Jmillerhttps://reu.cs.mu.edu/index.php/Sudoku_DistancesSudoku Distances2016-06-03T17:00:48Z<p>Jmiller: /* Notation and Formalization */</p>
<hr />
<div>The Sudoku Distances problem is a graph theoretic problem closely related to the Travelling Salesman Problem.<br />
<br />
== Problem Definition ==<br />
Consider a 9 by 9 Sudoku grid. Suppose that within this grid, the player wishes to write one specific digit in ''k'' different squares around the grid. From an arbitrary starting point, what is the shortest path for the player to take through all ''k'' squares?<br />
<br />
<br />
== Notation and Formalization==<br />
* We represent a Sudoku grid as a weighted graph, in which every square is represented by a vertex, and edges connect all vertices. In other words, we represent a Sudoku grid as ''K<sub>81</sub>''. <br />
* The edge between two squares ''a'' and ''b'' is weighted according to the distance between ''a'' and ''b'', which is determined by some distance metric. We use ''d(a,b)'' to denote the distance between two points.<br />
* We define a path ''p'' as a sequence of vertices ''a<sub>1</sub>a<sub>2</sub>...a<sub>n</sub>''. Since our graph is simple (there is only one edge between two specific vertices), we can omit the edges from our representation of a path.<br />
* We define the ''cost'' of a path ''c(p)'' to be the sum of ''d(a<sub>i</sub>, a<sub>i+1</sub>)'' for all ''a<sub>i</sub>, a<sub>i+1</sub>'' which are adjacent in ''P''.</div>Jmillerhttps://reu.cs.mu.edu/index.php/Sudoku_DistancesSudoku Distances2016-06-03T17:00:10Z<p>Jmiller: /* Notation and Formalization */</p>
<hr />
<div>The Sudoku Distances problem is a graph theoretic problem closely related to the Travelling Salesman Problem.<br />
<br />
== Problem Definition ==<br />
Consider a 9 by 9 Sudoku grid. Suppose that within this grid, the player wishes to write one specific digit in ''k'' different squares around the grid. From an arbitrary starting point, what is the shortest path for the player to take through all ''k'' squares?<br />
<br />
<br />
== Notation and Formalization==<br />
* We represent a Sudoku grid as a weighted graph, in which every square is represented by a vertex, and edges connect all vertices. In other words, we represent a Sudoku grid as ''K<sub>81</sub>''. <br />
* The edge between two points ''a'' and ''b'' is weighted according to the distance between ''a'' and ''b'', which is determined by some distance metric. We use ''d(a,b)'' to denote the distance between two points.<br />
* We define a path ''p'' as a sequence of vertices ''a<sub>1</sub>a<sub>2</sub>...a<sub>n</sub>''. Since our graph is simple (there is only one edge between two specific vertices), we can omit the edges from our representation of a path.<br />
* We define the ''cost'' of a path ''c(p)'' to be the sum of ''d(a<sub>i</sub>, a<sub>i+1</sub>)'' for all ''a<sub>i</sub>, a<sub>i+1</sub>'' which are adjacent in ''P''.</div>Jmillerhttps://reu.cs.mu.edu/index.php/Sudoku_DistancesSudoku Distances2016-06-03T16:59:53Z<p>Jmiller: /* Notation and Formalization */</p>
<hr />
<div>The Sudoku Distances problem is a graph theoretic problem closely related to the Travelling Salesman Problem.<br />
<br />
== Problem Definition ==<br />
Consider a 9 by 9 Sudoku grid. Suppose that within this grid, the player wishes to write one specific digit in ''k'' different squares around the grid. From an arbitrary starting point, what is the shortest path for the player to take through all ''k'' squares?<br />
<br />
<br />
== Notation and Formalization==<br />
* We represent a Sudoku grid as a weighted graph, in which every square is represented by a vertex, and edges connect all vertices. In other words, we represent a Sudoku grid as ''K<sub>81</sub>''. <br />
* The edge between two points ''a'' and ''b'' is weighted according to the distance between ''a'' and ''b'', which is determined by some distance metric. We use ''d(a,b)'' to denote the distance between two points.<br />
* We define a path ''p'' as a sequence of vertices ''a<sub>1</sub>a<sub>2</sub>...a<sub>n</sub>''. Since our graph is simple (there is only one edge between two specific vertices), we can omit the edges from our representation of a path.<br />
* We define the ''cost'' of a path ''c(p)'' to be the sum of ''d(a<sub>i</sub>, a<sub>i+1</sub>)'' for all ''a<sub>i</sub>, a<sub>i</sub> which are adjacent in ''P''.</div>Jmillerhttps://reu.cs.mu.edu/index.php/Sudoku_DistancesSudoku Distances2016-06-03T16:59:04Z<p>Jmiller: </p>
<hr />
<div>The Sudoku Distances problem is a graph theoretic problem closely related to the Travelling Salesman Problem.<br />
<br />
== Problem Definition ==<br />
Consider a 9 by 9 Sudoku grid. Suppose that within this grid, the player wishes to write one specific digit in ''k'' different squares around the grid. From an arbitrary starting point, what is the shortest path for the player to take through all ''k'' squares?<br />
<br />
<br />
== Notation and Formalization==<br />
* We represent a Sudoku grid as a weighted graph, in which every square is represented by a vertex, and edges connect all vertices. In other words, we represent a Sudoku grid as ''K<sub>81</sub>''. <br />
* The edge between two points ''a'' and ''b'' is weighted according to the distance between ''a'' and ''b'', which is determined by some distance metric. We use ''d(a,b)'' to denote the distance between two points.<br />
* We define a walk ''w'' as a sequence of vertices ''a<sub>1</sub>a<sub>2</sub>...a<sub>n</sub>''. Since our graph is simple (there is only one edge between two specific vertices), we can omit the edges from our representation of a path.<br />
* We define the ''cost'' of a path ''c(p)'' to be the sum of ''d(a<sub>i</sub>, a<sub>i+1</sub>)'' for all ''a<sub>i</sub>, a<sub>i</sub> which are adjacent in ''P''.</div>Jmillerhttps://reu.cs.mu.edu/index.php/Sudoku_DistancesSudoku Distances2016-06-03T16:55:41Z<p>Jmiller: Created page with "The Sudoku Distances problem is a graph theoretic problem closely related to the Travelling Salesman Problem. == Problem Definition == Consider a 9 by 9 Sudoku grid. Suppose..."</p>
<hr />
<div>The Sudoku Distances problem is a graph theoretic problem closely related to the Travelling Salesman Problem.<br />
<br />
== Problem Definition ==<br />
Consider a 9 by 9 Sudoku grid. Suppose that within this grid, the player wishes to write one specific digit in ''k'' different squares around the grid. From an arbitrary starting point, what is the shortest path for the player to take through all ''k'' squares?<br />
<br />
<br />
== Notation and Formalization==<br />
* We represent a Sudoku grid as a weighted graph, in which every square is represented by a vertex, and edges connect all vertices. In other words, we represent a Sudoku grid as ''K<sub>81<\sub>''. <br />
* The edge between two points ''a'' and ''b'' is weighted according to the distance between ''a'' and ''b'', which is determined by some distance metric. We use ''d(a,b)'' to denote the distance between two points.<br />
* We define a walk ''w'' as a sequence of vertices ''a<sub>1</sub>a<sub>2</sub>...a<sub>n</sub>''. Since our graph is simple (there is only one edge between two specific vertices), we can omit the edges from our representation of a path.<br />
* We define the ''cost'' of a path <math> \sum_{i=0}^n-1 d(a_i,a_i+1) <\math></div>Jmillerhttps://reu.cs.mu.edu/index.php/JmillerJmiller2016-06-03T16:27:15Z<p>Jmiller: Blanked the page</p>
<hr />
<div></div>Jmillerhttps://reu.cs.mu.edu/index.php/User:JmillerUser:Jmiller2016-06-03T16:26:51Z<p>Jmiller: Created page with "Joel Miller studies Computer Science at Oberlin College in Ohio, and is part of the 2016 REU at Marquette. He is working on the Sudoku Distances p..."</p>
<hr />
<div>Joel Miller studies Computer Science at Oberlin College in Ohio, and is part of the [[Summer 2016 Projects|2016]] REU at Marquette. He is working on the [[Sudoku Distances]] project with [[User:Jbeilke|Julia Beilke]], advised by Dr. Kim Factor. In his free time, he enjoys rock climbing and making music.<br />
<br />
<br />
== Progress Log ==<br />
<br />
<br />
'''Week 1 (5/31 - 6/3)'''<br />
<br />
*Attended various orientation events to become familiarized with Marquette campus, libraries, etc.<br />
*Began research on the Travelling Salesman Problem, and its application to Sudoku Distances<br />
*With [[User:Jbeilke|Julia]], wrote an algorithm for finding the optimal solution in the [[Sudoku Distances]] project for k = 3, and proved it correct</div>Jmillerhttps://reu.cs.mu.edu/index.php/Summer_2016_ProjectsSummer 2016 Projects2016-06-03T16:25:07Z<p>Jmiller: </p>
<hr />
<div>SimSys Project. [[Dcronce|Daniel Cronce]] and [[Mjbaker4|Michael Baker]]. Mentors:<br />
<br />
Predicting Relative 'Cleanability' from Geometry. [[User:Asisk|Anna Sisk]]. Mentors: Dr. Stephen Merrill and Casey O'Brien <br />
<br />
[[Sudoku Distances]]. [[User:Jbeilke|Julia Beilke]] and [[User:Jmiller|Joel Miller]]. Mentor: Dr. Kim Factor.<br />
<br />
[[Algorithms of CT and SPECT Scans]]. [[kskamp | Kim Sommerkamp]]. Mentor: Dr. Anne Clough<br />
<br />
[[Text Mining in Keywords Extraction | Text Mining in Keywords Extraction]]. Student: [[User:Phucnguyen | Phuc Nguyen]]. Mentor: Dr. Thomas Kaczmarek.<br />
<br />
Applied Probabilistic Forecasting Methods in Energy Consumption. Dr. George Corliss, students Stephen Loew and Alberto Ruiz<br />
<br />
Abstract: In this research we try to find applications for probabilistic forecasting on GasDay energy consumption models. Additionally we will survey literature to find applications of probabilistic forecasting in industry. Furthermore, we will examine forecasting metrics for accuracy including the Brier Score, evaluate strength and weaknesses and consider possible improvements. <br />
<br />
[[Analyzing and Mapping out data of Milwaukee]] . [[ghong|Gina Hong]]. Mentor: Dr. Gary Krenz.<br />
<br />
== Mathematics and Computer Science Education ==<br />
* MUzECS : Really cool things and stuff. David Hunpatin and [[User:Rthomas|Ryan Thomas]]. Mentor: Dr. Dennis Brylow.<br />
<br />
* Embedded Xinu : Really cool things and stuff. David Hunpatin and [[User:Rthomas|Ryan Thomas]]. Mentor: Dr. Dennis Brylow.</div>Jmillerhttps://reu.cs.mu.edu/index.php/Summer_2016_ProjectsSummer 2016 Projects2016-06-03T16:24:22Z<p>Jmiller: </p>
<hr />
<div>SimSys Project. [[Dcronce|Daniel Cronce]] and [[Mjbaker4|Michael Baker]]. Mentors:<br />
<br />
Predicting Relative 'Cleanability' from Geometry. [[User:Asisk|Anna Sisk]]. Mentors: Dr. Stephen Merrill and Casey O'Brien <br />
<br />
[[Sudoku Distances]]. [[User:Jbeilke|Julia Beilke]] and [[User:jmiller|Joel Miller]]. Mentor: Dr. Kim Factor.<br />
<br />
[[Algorithms of CT and SPECT Scans]]. [[kskamp | Kim Sommerkamp]]. Mentor: Dr. Anne Clough<br />
<br />
[[Text Mining in Keywords Extraction | Text Mining in Keywords Extraction]]. Student: [[User:Phucnguyen | Phuc Nguyen]]. Mentor: Dr. Thomas Kaczmarek.<br />
<br />
Applied Probabilistic Forecasting Methods in Energy Consumption. Dr. George Corliss, students Stephen Loew and Alberto Ruiz<br />
<br />
Abstract: In this research we try to find applications for probabilistic forecasting on GasDay energy consumption models. Additionally we will survey literature to find applications of probabilistic forecasting in industry. Furthermore, we will examine forecasting metrics for accuracy including the Brier Score, evaluate strength and weaknesses and consider possible improvements. <br />
<br />
[[Analyzing and Mapping out data of Milwaukee]] . [[ghong|Gina Hong]]. Mentor: Dr. Gary Krenz.<br />
<br />
== Mathematics and Computer Science Education ==<br />
* MUzECS : Really cool things and stuff. David Hunpatin and [[User:Rthomas|Ryan Thomas]]. Mentor: Dr. Dennis Brylow.<br />
<br />
* Embedded Xinu : Really cool things and stuff. David Hunpatin and [[User:Rthomas|Ryan Thomas]]. Mentor: Dr. Dennis Brylow.</div>Jmillerhttps://reu.cs.mu.edu/index.php/JmillerJmiller2016-06-03T16:22:45Z<p>Jmiller: </p>
<hr />
<div>Joel Miller studies Computer Science at Oberlin College in Ohio, and is part of the [[Summer 2016 Projects|2016]] REU at Marquette. He is working on the [[Sudoku Distances]] project with [[jbeilke|Julia Beilke]], advised by Dr. Kim Factor. In his free time, he enjoys rock climbing and making music.<br />
<br />
<br />
== Progress Log ==<br />
<br />
<br />
'''Week 1 (5/31 - 6/3)'''<br />
<br />
*Attended various orientation events to become familiarized with Marquette campus, libraries, etc.<br />
*Began research on the Travelling Salesman Problem, and its application to Sudoku Distances<br />
*With [[jbeilke|Julia]], wrote an algorithm for finding the optimal solution in the [[Sudoku Distances]] project for k = 3, and proved it correct</div>Jmillerhttps://reu.cs.mu.edu/index.php/JmillerJmiller2016-05-31T19:01:20Z<p>Jmiller: </p>
<hr />
<div>Joel Miller studies Computer Science at Oberlin College in Ohio, and is part of the [[Summer 2016 Projects|2016]] REU at 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.<br />
<br />
<br />
== Progress Log ==<br />
<br />
<br />
'''Week 1 (5/31 - 6/3)'''<br />
<br />
*Did stuff<br />
*Did other stuff</div>Jmillerhttps://reu.cs.mu.edu/index.php/JmillerJmiller2016-05-31T19:00:52Z<p>Jmiller: </p>
<hr />
<div><br />
'''Personal Description'''<br />
<br />
Joel Miller studies Computer Science at Oberlin College in Ohio, and is part of the [[Summer 2016 Projects|2016]] REU at 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.<br />
<br />
<br />
== Progress Log ==<br />
<br />
<br />
'''Week 1 (5/31 - 6/3)'''<br />
<br />
*Did stuff<br />
*Did other stuff</div>Jmillerhttps://reu.cs.mu.edu/index.php/JmillerJmiller2016-05-31T18:56:12Z<p>Jmiller: </p>
<hr />
<div><br />
'''Personal Description'''<br />
<br />
Joel Miller studies Computer Science at Oberlin College in Ohio, and is working on the [[Sudoku Project]] with Julia Beilke, advised by Dr. Kim Factor. In his free time, he enjoys rock climbing and making music.</div>Jmillerhttps://reu.cs.mu.edu/index.php/JmillerJmiller2016-05-31T18:55:05Z<p>Jmiller: Created page with " ==== Joel Miller ==== = Personal Description = Joel Miller studies Computer Science at Oberlin College in Ohio, and is working on the Sudoku Project with Julia Beilke, a..."</p>
<hr />
<div><br />
==== Joel Miller ====<br />
<br />
= Personal Description =<br />
Joel Miller studies Computer Science at Oberlin College in Ohio, and is working on the [[Sudoku Project]] with Julia Beilke, advised by Dr. Kim Factor. In his free time, he enjoys rock climbing and making music.</div>Jmillerhttps://reu.cs.mu.edu/index.php/Summer_2016_ProjectsSummer 2016 Projects2016-05-31T18:52:41Z<p>Jmiller: </p>
<hr />
<div>SimSys Project. [[Daniel Cronce]] and Michael Baker. Mentors:<br />
<br />
Relative 'Cleanability' from Geometry. Anna Sisk. Mentors: Dr. Stephen Merrill and Casey O'Brien <br />
<br />
[[Sudoku Distances]]. [[Julia Beilke]] and [[jmiller|Joel Miller]]. Mentor: Dr. Kim Factor.<br />
<br />
== You used to call me on my cell phone ==<br />
o Late night when you need my love</div>Jmiller