tag:blogger.com,1999:blog-8890204.post1345966453168012833..comments2023-01-24T11:41:07.927-05:00Comments on My Biased Coin: Algorithms and Data Structures : Course GoalsMichael Mitzenmacherhttp://www.blogger.com/profile/06738274256402616703noreply@blogger.comBlogger13125tag:blogger.com,1999:blog-8890204.post-18126081599072818562010-01-14T00:49:15.176-05:002010-01-14T00:49:15.176-05:00One could add something similar to 9:
9.5 Student...One could add something similar to 9:<br /><br />9.5 Students should learn the basics of exact algorithms (with worst case exponential running time), so that if asked in practice to solve an NP-hard problem (in the sense of coming up with an optimal solution), they have some idea of what approaches might solve small-ish instances. Or at least when they hear of a 100,000 city TSP instance being solved, or of SAT solvers, they have some idea of what's going on.<br /><br />At the other extreme, one could add<br />- Students should (really)understand the difference between an nlog n algorithm and an n^3 algorithm, by implementing say Dijkstra and Floyd-Warshall, and running them on instances of slowly increasing sizes.Kunalnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-61885757162438056242010-01-13T17:12:04.998-05:002010-01-13T17:12:04.998-05:00Nice list. I would be interested in hearing more ...Nice list. I would be interested in hearing more of what you think about item 4 (formal and rigorous arguments). I don't know that CS departments are handling this correctly.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-47541623401780395222010-01-13T15:35:22.839-05:002010-01-13T15:35:22.839-05:00OK, as an exercise I’ve transformed Michael’s list...OK, as an exercise I’ve transformed Michael’s list into intended learning outcomes. Some of the items benefit a lot (it’s a lot clearer exactly where the line is drawn — did we mean 3a or 3b? 4a or 4b), others become awkward.<br /><br />After Algorithms and Data Structures A-113 the student can<br /><br />1. state the asymptotic running time of a given algorithm, including recursive algorithms, possibly using amortised analysis<br /><br />2. model a computational problem in terms of graphs or linear programmes<br /><br />3a. classify an algorithm by technique: greedy, divide and conquer, dynamic programming, linear programming, or<br /><br />3b. solve a given problem using algorithmic paradigms such as greedy, divide and conquer, dynamic programming, linear programming,<br /><br />4a. recognise a formal correctness proof, or<br /><br />4b. decorate an given algorithm with assertions and invariants to establish its correctness<br /><br />5. solve a problem by reducing it to another problem, and argue for the hardness of a problem by reducing it from another problem<br /><br />6. analyse a randomised algorithms, including finding the expected running time using — (fill in whatever you want here: expectation as sum of indicator random variables, bound stuff using concentration of measure… model something as a markov chain… derandomise using the method of conditional … this is a whole blog post in itself)<br /><br />7. implement and run an algorithm given as pseudocode<br /><br />8. bound a performance guarantee of a simple approximation algorithm<br /><br />9. find a (nonoptimal) solution to a hard computational problem instance using local and exhaustive search methods <br /><br />10. nod in recognition at three really cool, unusual, interesting algorithms and data structures, and brag about having being forced to work on some really hard, challenging problems, to challenge their thinking and demonstrate the power of theory. <br /><br />--<br /><br />I’ll add my own:<br /><br />11. prove an algorithm incorrect by constructing a counterexample<br /><br />12. refactor an implementation by separating abstract data types from data structure implementations<br /><br />13. say “I think I’d use a hash function” during an oral examThore Husfeldthttps://www.blogger.com/profile/14937584058954877153noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-17296496039295604972010-01-13T12:57:44.905-05:002010-01-13T12:57:44.905-05:00It's easy to test whether the objective that a...It's easy to test whether the objective that a student has merely seen a certain topic is met: just use attendance-based grading.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-58054655142960890202010-01-13T12:24:24.694-05:002010-01-13T12:24:24.694-05:00"“After Computational Complexity A–113, the s..."“After Computational Complexity A–113, the student can———” What?"<br /><br />Computational Complexity is theory still under construction. Although the target is taxonomic, i.e. to obtain robust complexity classes (by definitions) and means to classify problems in these classes (trough theorems about the algorithms that solve the problems) IMO we are not yet at this stage. What we have is provisional classes, conditional theorems based on conjetures and the hope to be able to prove these conjetures in the near future (and this makes the whole thing very appealing). <br /><br />The list in the post seems hard to improve. Maybe iwould include that "find the counterexample" suggestion...proaonuiqnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-13942773902489727302010-01-13T11:07:46.090-05:002010-01-13T11:07:46.090-05:00DE -- As I said at the end of the post, perhaps an...DE -- As I said at the end of the post, perhaps another post will focus on the issue of how the objectives are met -- which is, I think, the answers to your questions.Michael Mitzenmacherhttps://www.blogger.com/profile/02161161032642563814noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-65632885387964192042010-01-13T10:56:12.407-05:002010-01-13T10:56:12.407-05:00Daniel --
Interestingly, the idea that correctnes...Daniel --<br /><br />Interestingly, the idea that correctness, like time and memory, can be traded off, seems to really shock students when they first hear it. It's one of those things you don't naturally think of -- but once you get used it to it, it's hard to remember what is was like not to think in those terms.<br /><br />I actually consider it a major philosophical contribution of the class, more important than most people realize.Michael Mitzenmacherhttps://www.blogger.com/profile/02161161032642563814noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-38454729533581279372010-01-13T10:54:31.648-05:002010-01-13T10:54:31.648-05:00To me what stands out for its omission is not any ...To me what stands out for its omission is not any particular topic. Rather, what I see in most of this list are very passive verbs, "students should see" and "students should understand". What I don't see is any kind of learning outcome: what specific things should the students be able to do to demonstrate their understanding? How are their abilities changed for having seen what they've seen in the class?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-17391463972190682282010-01-13T10:45:07.424-05:002010-01-13T10:45:07.424-05:00Mihai -- I think we agree on your goal, though per...Mihai -- I think we agree on your goal, though perhaps we're just wording it slightly differently. (Numbers 7 and 10 line up with your goal pretty well...)Michael Mitzenmacherhttps://www.blogger.com/profile/02161161032642563814noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-83327737754910428732010-01-13T10:26:55.181-05:002010-01-13T10:26:55.181-05:00My answer as a blog post:
http://www.daniel-lemir...My answer as a blog post:<br /><br />http://www.daniel-lemire.com/blog/archives/2010/01/13/the-fundamental-properties-of-computing/Daniel Lemirehttps://www.blogger.com/profile/01566622051558391310noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-48459884895925720722010-01-13T08:53:55.165-05:002010-01-13T08:53:55.165-05:00I would assume that at least 50% of your students ...I would assume that at least 50% of your students will ultimately work in software, without becoming theorists. So I think the most important goal of the class is to educate such students that there exist highly non-obvious algorithms that work very well, and they don't know all of them :) <br /><br />If you manage to convince them of this fact (which is not easy), when they will face a hard problem, they won't just hack something and hope it usually works. They will hopefully start by looking at some literature or just asking somebody.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-82671717333533123522010-01-13T08:30:10.949-05:002010-01-13T08:30:10.949-05:00Good addition, Thore! In fact in my exams I usual...Good addition, Thore! In fact in my exams I usually have a section of the form: "Show the following statement is not true with an example", and I do think finding counter-examples is a useful skill.Michael Mitzenmacherhttps://www.blogger.com/profile/02161161032642563814noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-14983631126847369242010-01-13T08:21:04.818-05:002010-01-13T08:21:04.818-05:00A reason to prefer your list to Lipton’s is that y...A reason to prefer your list to Lipton’s is that you are able to formulate the course goals in terms of skills. <br /><br />Most of your items could be given in the form “After the course, the student can ———”, where ——— preferably is something they couldn’t do before they took the course. A notable exception is your last point. Maybe, “After the course, the student can nod in recognition at up to three, cool recent algorithms.”<br /><br />The real challenge for a complexity course, especially if you teach at a department where course goals have to be formulated in terms of Intended Learning Outcomes rather than facts or topics, is indeed to finish that sentence. “After Computational Complexity A–113, the student can———” What?<br /><br />--<br /><br />As to the algorithms and data structures outcomes, here’s another good, testable skill: “Construct a counterexample to the correctness of a given algorithm.” Proving stuff incorrect is much more useful than proving stuff correct. It’s also more fun, creative (rather than formal), and can be taught (and examined) with a broader student population.Thore Husfeldthttps://www.blogger.com/profile/14937584058954877153noreply@blogger.com