We can clarify that "step" means a computer instruction. If you'd like to be extremely formal, we can define it extremely clearly as "instruction for a Turing machine," although that would be rather painful so likely the first thing we would do is show that an Intel processor is identical to a Turing machine for our purposes. Any computer ever invented is identical to a Turing machine for the purpose of counting steps.
The slime machine might be interesting, but (since it's defined as magical) doesn't exist. So for our purposes, we define "computer" to be a Turing machine, because those are the only things that exist in a way that we can study.
If you can think of a way to describe what a magical machine would be like, then even before it's invented we could reason about it. Adding any finite number of cores will not make a difference, though.
Are you saying for all possible chip designs and all possible compiler designs, bubble sort will ALWAYS be slower than merge sort (for non-trivial sort sets of relatively random keys)?
Yes, as long as it's the type of computer that follows a sequence of steps (as opposed to some kind of weird slime computer that is magic). Although if it doesn't follow a sequence of steps, it's not bubble-sort anymore.
If so, can you provide the proof?
Yes, the proof involves counting the number of steps required to complete each algorithm.
According to the article, the employees can go to jail. Presumably you start at the top of the chain of command, go down the stack, and the first person to refuse will go to jail.
. We shouldn't really pass judgement until we see the curriculum, which I doubt anybody commenting here has.
There's a description of the curriculum in the paper (so yeah, maybe you're right, maybe no one here has seen it).
It's basic programming concepts, followed by python, followed by a lot of OOP.
I wrote this incorectly, it should have been: ... So if r = number of cores, then you are going to have a bubble sort RunningTime = c/r*N*N,....
So if you can divide the sort among five cores, you'll get the task done in ~1/5 the time.
btw, there has been research done on the parallelization of sorting, and at best, you can only get a speedup of dividing it by the number of cores. So if r = number of cores, then you are going to have a bubble sort RunningTime = c/5*N*N, which is great, but it means bubble sort is still going to be slower than merge sort, no matter how good the compiler is.
I'm asking for proof of speed, not proof of classification.
The classification tells you how fast it's going to go. Again, we have this equation for the running time of bubble sort:
RunningTime = c*N*N
The compiler can reduce c, which is nice, but it's for large enough N, it will always be slower than an algorithm whose running time is RunningTime = d*N*lg(N)
As mentioned elsewhere, a sophisticated optimizing compiler may find shortcuts.
It doesn't matter. The compiler can reduce c, but it's still going to be an N^2 algorithm.
Whether bubble sort could be automatically parallelized is an interesting question, but that's a question for further research, and if it can, we can include it into the model.
Yes, actually, we can model it anyway. We model the algorithms based on how many steps it will take to solve the problem (we will say running time is equivalent to number of instructions, to simplify for now). Because of the way bubble sort is set up, with a loop inside a loop, we can say (where N is number of items):
RunningTime = c*N*N
Where 'c' is the amount of time it takes to run through one internal loop.
In comparison, for example, with merge sort, we have:
RunningTime = d*N*lg(N)
So, once N gets big enough, the running time of merge sort will always be shorter than the RunningTime of bubble sort, because an N^2 graph will also increase faster than an N*lg(N) graph. Where exactly the cross-over happens depends on the size of c and d. If that didn't make sense, I can try to clarify.
*Note: lg(N) here means log base 2, and is log base 2 because for merge sort, you keep dividing your list in half over and over.
I should change my previous comment, because it wasn't very good. Here is what I meant:
If you look at a web page from the 90s, here's an example so you can remember, it's not going to be acceptable to modern users. It looks ugly. Furthermore, the tools used to build it (like tables) are outdated, and your coworkers will yell at you if you use them now.
Moving forward, in the early 2000s, everything looked really square, so now, if you don't add a radius to the corners of your divs, then people will say, "Oh, your website looks old."
More importantly, in the last two or three years, we've seen the advent of the responsive web. The way the 'responsive web' was designed means that anything built before 2012 looks rather lousy on cell phones.
Now, of course, you are right that the web page from 1997 will probably still render, but it will look really bad everywhere. Compare that to TCL-TK which apps built in 1997 actually look really good right now.
Further, a sufficiently smart compiler could perhaps optimize a bubble sort to be as fast as the more commonly-used algorithms such to say bubble sort is "objectively slower" than the usual algorithms is probably either wrong, contentious, or very complicated to fully prove.
It's wrong. A bubble sort is typically faster when N < ~10
Au contraire, computer science is the best science, and the best way to teach science. You can test your hypotheses almost immediately, eg, "Is sort A faster then sort B?" by merely writing the program. Of course that's settled science now, but I've seen professors teach their students in exactly that way.
It's an important skill to have as a programmer, too. Too many people skip important phases (like the measuring phase, saying, "oh, we'll just replace this algorithm, it'll be faster." In reality, if you don't measure, you don't know). Not long ago, we had to replace a very slow algorithm, and everyone came up with their own algorithm, with their own reasons it was the best. But we didn't know which one was until we tested it.
In short: computer science is the best science because many hypotheses can be easily tested.
Plus, OOP is not the right solution for some parts of systems.
Yeah, teaching OOP at that level is more of indoctrination, because they don't have the tools they need to understand when it is a good choice, and when it isn't.
I'm not sure the trend of 'making programming a game' is the best way to go about it....it works fine at the introductory levels, but how do you move beyond drag-and-drop programming blocks and start using text all the time? Are you going learn about NP-complete with pictures? I think at some point, the students need to develop a passion for solving puzzles, otherwise they will not have the desire to keep going.......
In any case, here is the curriculum they used:
1) programming (bouncing ball, kindergarten picture)
2) functions, variables, basic loops, 2D arrays (image processing)
3) fundamentals, control structures (Andy Wharhol, Green Screen)
4) algorithm development (finding the robots ball)
**At this point, the students are given a four-week introduction to Python**
5) OOP: classes, polymorphism, animation (bouncing ball, sea creature)
6) OOP and design (space invaders)
7) Abstraction Strings (data visualization)
8) OOP: interfaces (swimmable object, paint)
9) OOP: inheritance (sea creature inheritance)
10) Recursion (hanoi tower)
11) algorithm development, OOP: encapsulation (robot maze)
Personally I would rather see less emphasis on OOP, and more emphasis on "the proving mindset" (the proving mindset being, when you write code, try to think of everything that can go wrong, every possibility). It's kind of hard to understand when OOP is a good thing without writing bad code first.....
Yeah, stable, unless you want to have a div that is relatively positioned, clickable, and also has some transparency. Because IE will chop off the bottom of the div (don't ask me why). And a myriad of other instabilities over time.......
I'm not sure that's accurate. My team was using Angular, and there was a lot of Javascript all over the place, to the point that it felt like all Javascript. Maybe other teams use it differently, though.
Stole what idea? The idea of an electronic facebook?
Someone hired him to build their idea into a website, and he told them he was building it, but instead was building his own. That's lies and stealing right there.
I'm not sure what the deal is with that guy he allegedly screwed out of a partnership
So you are ignorant and still defending him? Sounds like your post has a strong basis in rational thought there.........
But other than that I have no issues with the guy.
It doesn't bother you that he stole people's passwords so he could read their email?
Do you think he will ever cooperate with the state authorities again? It will hurt his image
Uh, the general image I see of him is a guy who stole someone else's idea, has no problem stealing passwords to read email, and mainly lucked out. What image do you see of him?
University administration should not be judged on how much money they bring in but on how they have managed to improve the quality of research and teaching which the University does.
They would have to limit tenure, so they can have a way to get rid of the sucky teachers.
Slashdot Mirror
We can clarify that "step" means a computer instruction. If you'd like to be extremely formal, we can define it extremely clearly as "instruction for a Turing machine," although that would be rather painful so likely the first thing we would do is show that an Intel processor is identical to a Turing machine for our purposes. Any computer ever invented is identical to a Turing machine for the purpose of counting steps.
The slime machine might be interesting, but (since it's defined as magical) doesn't exist. So for our purposes, we define "computer" to be a Turing machine, because those are the only things that exist in a way that we can study.
If you can think of a way to describe what a magical machine would be like, then even before it's invented we could reason about it. Adding any finite number of cores will not make a difference, though.
Are you saying for all possible chip designs and all possible compiler designs, bubble sort will ALWAYS be slower than merge sort (for non-trivial sort sets of relatively random keys)?
Yes, as long as it's the type of computer that follows a sequence of steps (as opposed to some kind of weird slime computer that is magic). Although if it doesn't follow a sequence of steps, it's not bubble-sort anymore.
If so, can you provide the proof?
Yes, the proof involves counting the number of steps required to complete each algorithm.
According to the article, the employees can go to jail. Presumably you start at the top of the chain of command, go down the stack, and the first person to refuse will go to jail.
Well the primary problem with this is how are they going to put a company in prison for two years?
You arrest the executives.
. We shouldn't really pass judgement until we see the curriculum, which I doubt anybody commenting here has.
There's a description of the curriculum in the paper (so yeah, maybe you're right, maybe no one here has seen it).
It's basic programming concepts, followed by python, followed by a lot of OOP.
I wrote this incorectly, it should have been:
... So if r = number of cores, then you are going to have a bubble sort RunningTime = c/r*N*N,....
So if you can divide the sort among five cores, you'll get the task done in ~1/5 the time.
I'm asking for proof of speed, not proof of classification.
The classification tells you how fast it's going to go. Again, we have this equation for the running time of bubble sort:
RunningTime = c*N*N
The compiler can reduce c, which is nice, but it's for large enough N, it will always be slower than an algorithm whose running time is RunningTime = d*N*lg(N)
As mentioned elsewhere, a sophisticated optimizing compiler may find shortcuts.
It doesn't matter. The compiler can reduce c, but it's still going to be an N^2 algorithm.
Whether bubble sort could be automatically parallelized is an interesting question, but that's a question for further research, and if it can, we can include it into the model.
Yes, actually, we can model it anyway. We model the algorithms based on how many steps it will take to solve the problem (we will say running time is equivalent to number of instructions, to simplify for now). Because of the way bubble sort is set up, with a loop inside a loop, we can say (where N is number of items):
RunningTime = c*N*N
Where 'c' is the amount of time it takes to run through one internal loop.
In comparison, for example, with merge sort, we have:
RunningTime = d*N*lg(N)
So, once N gets big enough, the running time of merge sort will always be shorter than the RunningTime of bubble sort, because an N^2 graph will also increase faster than an N*lg(N) graph. Where exactly the cross-over happens depends on the size of c and d. If that didn't make sense, I can try to clarify.
*Note: lg(N) here means log base 2, and is log base 2 because for merge sort, you keep dividing your list in half over and over.
I should change my previous comment, because it wasn't very good. Here is what I meant:
If you look at a web page from the 90s, here's an example so you can remember, it's not going to be acceptable to modern users. It looks ugly. Furthermore, the tools used to build it (like tables) are outdated, and your coworkers will yell at you if you use them now.
Moving forward, in the early 2000s, everything looked really square, so now, if you don't add a radius to the corners of your divs, then people will say, "Oh, your website looks old."
More importantly, in the last two or three years, we've seen the advent of the responsive web. The way the 'responsive web' was designed means that anything built before 2012 looks rather lousy on cell phones.
Now, of course, you are right that the web page from 1997 will probably still render, but it will look really bad everywhere. Compare that to TCL-TK which apps built in 1997 actually look really good right now.
Further, a sufficiently smart compiler could perhaps optimize a bubble sort to be as fast as the more commonly-used algorithms such to say bubble sort is "objectively slower" than the usual algorithms is probably either wrong, contentious, or very complicated to fully prove.
It's wrong. A bubble sort is typically faster when N < ~10
Au contraire, computer science is the best science, and the best way to teach science. You can test your hypotheses almost immediately, eg, "Is sort A faster then sort B?" by merely writing the program. Of course that's settled science now, but I've seen professors teach their students in exactly that way.
It's an important skill to have as a programmer, too. Too many people skip important phases (like the measuring phase, saying, "oh, we'll just replace this algorithm, it'll be faster." In reality, if you don't measure, you don't know). Not long ago, we had to replace a very slow algorithm, and everyone came up with their own algorithm, with their own reasons it was the best. But we didn't know which one was until we tested it.
In short: computer science is the best science because many hypotheses can be easily tested.
Plus, OOP is not the right solution for some parts of systems.
Yeah, teaching OOP at that level is more of indoctrination, because they don't have the tools they need to understand when it is a good choice, and when it isn't.
I'm not sure the trend of 'making programming a game' is the best way to go about it....it works fine at the introductory levels, but how do you move beyond drag-and-drop programming blocks and start using text all the time? Are you going learn about NP-complete with pictures? I think at some point, the students need to develop a passion for solving puzzles, otherwise they will not have the desire to keep going.......
In any case, here is the curriculum they used:
1) programming (bouncing ball, kindergarten picture)
2) functions, variables, basic loops, 2D arrays (image processing)
3) fundamentals, control structures (Andy Wharhol, Green Screen)
4) algorithm development (finding the robots ball)
**At this point, the students are given a four-week introduction to Python** 5) OOP: classes, polymorphism, animation (bouncing ball, sea creature)
6) OOP and design (space invaders)
7) Abstraction Strings (data visualization)
8) OOP: interfaces (swimmable object, paint)
9) OOP: inheritance (sea creature inheritance)
10) Recursion (hanoi tower)
11) algorithm development, OOP: encapsulation (robot maze)
Personally I would rather see less emphasis on OOP, and more emphasis on "the proving mindset" (the proving mindset being, when you write code, try to think of everything that can go wrong, every possibility). It's kind of hard to understand when OOP is a good thing without writing bad code first.....
Yeah, stable, unless you want to have a div that is relatively positioned, clickable, and also has some transparency. Because IE will chop off the bottom of the div (don't ask me why). And a myriad of other instabilities over time.......
That's pretty cool. I notice it gets weird when I shrink the screen, might I suggest giving it a "responsive" design?
I'm not sure that's accurate. My team was using Angular, and there was a lot of Javascript all over the place, to the point that it felt like all Javascript. Maybe other teams use it differently, though.
Angular = Google, Microsoft and friends.
React = Facebook and friends.
Both platforms are going to be around for while, like J2EE.
no one values a stable web platform any more?
There has never been a stable web platform for frontend.
Should have taken a screenshot :(
We are not so good at World Wars and Empires.
In fairness, Germanic tribes were the ones who finally took down Rome (and more than once!)
Stole what idea? The idea of an electronic facebook?
Someone hired him to build their idea into a website, and he told them he was building it, but instead was building his own. That's lies and stealing right there.
I'm not sure what the deal is with that guy he allegedly screwed out of a partnership
So you are ignorant and still defending him? Sounds like your post has a strong basis in rational thought there.........
But other than that I have no issues with the guy.
It doesn't bother you that he stole people's passwords so he could read their email?
Do you think he will ever cooperate with the state authorities again? It will hurt his image
Uh, the general image I see of him is a guy who stole someone else's idea, has no problem stealing passwords to read email, and mainly lucked out. What image do you see of him?
University administration should not be judged on how much money they bring in but on how they have managed to improve the quality of research and teaching which the University does.
They would have to limit tenure, so they can have a way to get rid of the sucky teachers.
and probably learned more about the world,
Probably not......