I changed up a few things in my undergraduate algorithms course this year.\u00a0 I probably wouldn’t have if I wasn’t charged with designing an online version of the same course, one that would be static for at least three years, so far as I understand it.<\/p>\n
One major thing that I changed was the assignment component.\u00a0 This course has always (officially, by way of ABET-geared course learning objectives) included programming assignments.\u00a0 Something that I abhored.\u00a0 There was a post by Michael Mitzenmacher that changed my opinion (a bit) on this front. But mostly the thought that non-students would be looking closely at the various components of my course convinced me to take things a bit more seriously.<\/p>\n
In previous iterations, I would completely separate “programming” assignments from “non-programming” assignments which is really terrible<\/em> I know.\u00a0 So this year I took a 180 and had 4 projects, each geared toward a major topic of the course with design, analysis and implementation\/experimental analysis components.\u00a0 Much better.\u00a0 (Except for group unfairness woes as mentioned in my previous post.)<\/p>\n For the final project, I left things very open ended.\u00a0 Design an algorithm to solve (2D Euclidean instances of) TSP.\u00a0 In class, this allowed me to talk about verifiers (how else would I trust their solutions?), NP, give them a taste of a difficult problem, etc.\u00a0 The assignment would culminate with a two-step competition. One to solve instances over a period of 24 hours and one to solve instances — live in class — in 4 minutes.\u00a0 Before the assignment was even released I realized how competitive the students would get, requiring me (a.k.a. our amazing IT guy, Todd Shechter) to set up virtual machines for the competition to ensure fairness.\u00a0 It was definitely convenient that DIMACS has a large set of instances available with optimal tour lengths listed.\u00a0 Thank you, experimental algorithms community!<\/p>\n I have to say, I was impressed.\u00a0 In a stroke of genius, I enforced a 2-page report limit so that I was actually able to easily discern their main techniques.\u00a0 There were several equivalence classes of algorithms.\u00a0 Two groups implemented Christofides’ algorithm, and, true to form, it got within 50% of optimal.\u00a0 I tried hard to keep my impartiality in reading the reports on algorithms by biological metaphor and was pleased to see that my abhorrence played out in algorithms that didn’t do so well.\u00a0 Several groups that did very well started with some sort of greedily generated tour and then made local changes that improved the tour.\u00a0 I’d like to highlight the algorithm by Francis Vo and Soo Hyun Yoo, who were the only team to take advantage of the 2D Euclidean-ess of the problem and had an algorithm that outperformed all the others (almost all of the time), solved one of the 4-minute instances to optimality and added fuel to my “take advantage of the domain” banner I love to wave.\u00a0 They started with a(n almost) convex hull of the points, iteratively added the remaining points to this tour greedily, and cleaned up with local search.\u00a0 They even animated their algorithm to aid in design:<\/p>\n\n I will definitely make improvements (the in class competition was a little chaotic and not super interesting for the students who didn’t make into later rounds) but I enjoyed it and I think many of the students did.<\/p>\n","protected":false},"excerpt":{"rendered":" I changed up a few things in my undergraduate algorithms course this year.\u00a0 I probably wouldn’t have if I wasn’t charged with designing an online version of the same course, one that would be static for at least three years, so far as I understand it. One major thing that I changed was the assignment […]<\/p>\n","protected":false},"author":3747,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[1000,117603,3514],"class_list":["post-990","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-teaching","tag-tsp","tag-undergraduate"],"_links":{"self":[{"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/posts\/990","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/users\/3747"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/comments?post=990"}],"version-history":[{"count":3,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/posts\/990\/revisions"}],"predecessor-version":[{"id":993,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/posts\/990\/revisions\/993"}],"wp:attachment":[{"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/media?parent=990"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/categories?post=990"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/tags?post=990"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}