tag:blogger.com,1999:blog-8890204.post1042159991124639436..comments2024-05-04T06:30:02.754-04:00Comments on My Biased Coin: Algorithms for Newbies: Static or Dynamic?Michael Mitzenmacherhttp://www.blogger.com/profile/06738274256402616703noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-8890204.post-14028880391131233342008-02-14T18:24:00.000-05:002008-02-14T18:24:00.000-05:00Commonly used concepts, e.g. "big-Oh" notation and...<EM>Commonly used concepts, e.g. "big-Oh" notation and recurrences, could be taught beforehand...</EM><BR/><BR/>This sort of material is very often taught in a "Discrete Math" course that is a prerequisite of algorithms.<BR/><BR/>Some schools may also have a course on Data Structures before a course on algorithms, or a two-semester algorithms sequence.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-23422087382653031852008-02-14T10:24:00.000-05:002008-02-14T10:24:00.000-05:00Perhaps we've reached a level of specialization wh...Perhaps we've reached a level of specialization where any course entitled "Introduction to Algorithms" is too broadly titled. For example, how often do you see a course called "Introduction to Math"? Now we have separate intro courses for algebra, analysis, etc. Maybe the same should be true for algorithms. Commonly used concepts, e.g. "big-Oh" notation and recurrences, could be taught beforehand in a separate "Math for algorithmists" course (maybe not the best name), and then there could be separate intro courses for different algorithm subfields.Jelani Nelsonhttps://www.blogger.com/profile/00216475103758212305noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-13002157993008052892008-02-02T12:49:00.000-05:002008-02-02T12:49:00.000-05:00The "Static" algorithms are too important to be sk...The "Static" algorithms are too important to be skipped over. But the students need to understand what dynamic algorithms actually are.<BR/><BR/>Ideally, you would find 2 simple dynamic algorithms to teach. It wouldn't take much time and 2 is the beginning of seeing a pattern. <BR/><BR/>I don't actually know if 2 such algorithms exist that are worth teaching, though.Your Correspondent https://www.blogger.com/profile/17440467058108985654noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-72497342203436928222008-02-01T21:53:00.000-05:002008-02-01T21:53:00.000-05:00Anon 5 : I think we hint at "dynamic" algorithms w...Anon 5 : I think we hint at "dynamic" algorithms when we consider data structures responding to a sequence of operations [though usually that can be thought of as an offline finite sequence of operations -- or an input], and hint more strongly when we consider online algorithms. Though somehow the "always on" aspect isn't quite captured. (Also, while I do some approximation algorithms in my undergrad class, I don't really cover on-line algorithms in any detail. Not enough time, and some unwillingness on my part to try to justify why the competitive ratio would be the "right" thing to aim for algorithmically...)Michael Mitzenmacherhttps://www.blogger.com/profile/02161161032642563814noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-21012896312466907032008-02-01T21:38:00.000-05:002008-02-01T21:38:00.000-05:00A sequence of insertions, deletions and lookups in...A sequence of insertions, deletions and lookups in a binary search tree are a dynamic algorithm, aren't they? So are on-line algorithms such as paging.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-51830942000366670452008-02-01T14:39:00.000-05:002008-02-01T14:39:00.000-05:00To me, distributed algorithms are very different f...To me, distributed algorithms are very different from "classic" ones. Designing a DA is much like solving a puzzle about three wise men. In fact, you design a FSA that, being deployed on network nodes, will strive towards some "common aim".<BR/><BR/>So, static and dynamic algorithms can be studied in any order.Mikhailhttps://www.blogger.com/profile/03247181793198240403noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-72252069122334681012008-02-01T08:22:00.000-05:002008-02-01T08:22:00.000-05:00My guess is that the teaching of only static algor...My guess is that the teaching of only <BR/>static algorithms in algorithms courses will look old fashioned at some point in the not too distant future. At the very least, it seems that standard texts such as CLRS should at least have one chapter devoted dynamic/online/streaming/etc algorithms.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-50078181995896344642008-02-01T06:42:00.000-05:002008-02-01T06:42:00.000-05:00"Dynamic" algorithms could perhaps also include on..."Dynamic" algorithms could perhaps also include on-line algorithms, and issues like competitive ratio; they don't have to be distributed.<BR/><BR/>When we move to distributed algorithms, the business of proving desirable properties becomes less dominated by identification of bounds on their runtime. In the context of teaching, maybe this is a good thing (arguably the proofs are more diverse and interesting.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-85999919697896716672008-02-01T01:49:00.000-05:002008-02-01T01:49:00.000-05:00(1) I agree that implementation of an algorithm is...(1) I agree that implementation of an algorithm is very important. There are often many details to work through during implementation that make the students really "learn" and appreciate the algorithm.<BR/><BR/>Often times, there's a disconnect between those who do "theory" and those that implement. I've heard this from a NASA engineer: "Just because some clown told you Turbo codes are good, doesn't mean you should use it." He was very bitter because in th past, he had to deal with many "clowns" who couldn't see the difficulties during implementation.<BR/><BR/>(2) I would imagine that if people thought hard enough (say, put in the same effort they do to a STOC/FOCS problem), they could think of some very innovative ways to teach both static and dynamic algorithms.... but I digress...Anonymousnoreply@blogger.com