While the article says that the number of Win7 infections have gone up while the number of WinXP infections has gone down, the infection rate on XP is still higher at 14 per 1000 compared to 4 per 1000 in Win7.
Then why is it still a problem 17 years later? Windows 7 easily recognizes a second monitor, but Ubuntu 10.10 completely ignores it. What's worse is I don't even know where to start with fixing it.
I predict not a single update will go into the Linux and Android versions
As far as Skype updates go, they can keep them. In the past, Skype updates simply broke features and added bloat. For example, a couple versions ago Skype removed the option to minimize to the system tray for Windows 7 users. The Skype icon was always in the taskbar. The work around was to run it in Windows Vista compatibility mode. Very annoying.
Further, as I write this, the main Skype process is hogging the second most amount of memory on my system, at 75mb. Not to mention there's a separate process for Skype extras, which I don't even use. It seems with every update it gets worse, when no new features are really added. Why does it need that much memory?
I think you missed where I said this was a graduate level course; I'm in a PhD program. I'm guessing they either figure we've seen this stuff at least briefly once before, or we'll do what we need to do outside of class in order to understand it. I don't know how they treat the undergraduate version.
I guess if you consider rough pen/paper pseudocode outlines of algorithms well above the implementation level to be coding, I guess I did some coding for a few homework assignments. Honestly spent more time on proving complexity and proofs of correctness. As for your concern with my academic development, I appreciate it I guess, but I don't feel I have much to gain from physically implementing quicksort when I'm already coding 12+ hours a day.
I said we didn't write code, not algorithms. I think the distinction is warranted, since algorithms existed well before programming languages. As for computer science graduates needing more programming, I don't know whether that is true or not, but it's not the job of a theoretical algorithms course to teach programming or lend experience in programming. For what it's worth this was a graduate level course; I don't know what they do at the undergraduate level.
You could learn complexity theory without ever learning to code in anything but BASIC.
I recently took two courses, one in algorithms another in theory of computation. I didn't write a single line of code for either. That's the way it should be, because algorithms are language agnostic (as long as they are Turing complete).
That is, given two languages A and B, "A solves B" means that there is a map f from B to A where f(x) is in A if and only if x is in B, for all possible x (not just those in B).
You pretty much just stated the definition for a reduction. I mean, if all you have is a problem with the word then I guess all you risk is confusing people who aren't familiar with your terminology.
I remember being introduced to the concept of reductions with the following analogy: Say I want to go to my friend's house.This is easy if I have his address, otherwise I would need to visit every house until I found his. So the problem of going to my friend's house reduces to knowing his address. But just by knowing his address, I'm not at my friend's house; I still have to do the actual work of walking there. To me, saying that A solves B in this context is like saying knowing my friend's address gets me to his house. Whereas in reality, knowing his address gives me a path for me to walk which when followed will lead me there.
(Actually, if I don't know the area this problem probably further reduces to finding a map.)
I answer questions on the math sub-board of a programming forum sometimes and have gotten a few NP(-complete) problems, though they were all easily recognizable as such even with my poor background in complexity theory.
Right, that's probably reasonable as long as you are well versed in maths, you can probably infer a lot of complexity theory (which in the end is evaluating and comparing asymptotic behavior of functions). Where I think complexity theory would help is in understanding just why the problem is hard, how it relates to other problems, which could lead you do a very nice way to relax or approximate the problem.
My favorite example of this is Shortest Path vs. Longest Path.
Shortest path is in P. The worst algorithm I think is Dijkstra's will solve it in O(V^2) for example. So you would think finding the longest path in the graph can't be much harder, right? Actually it's NP-Complete.
Because saying "solves" removes an important implication of reducibility. When I say "exact cover reduces to knapsack" what I mean is there exists a function f(x) that maps every instance of exact cover to knapsack in polynomial time. The thing is, when we're talking about any theory, it's important to be very precise with language. What exactly does "solve" mean? Can we use knapsack to decide exact cover? Or does can we only use it to recognize exact cover? The difference between these two things in computability theory is drastic.
The GP has probably only been working on problems that are in P, and in fact there are a lot of those. However, there are also a LOT of problem which are in NP we would like to solve.
Scenario 1: The classic example. You work for a presidential political campaign and your candidate asks you to plan the best possible trip to 1000 counties for the next year. The optimal trip will visit the same city only once, and in total take the least distance. This is known as the traveling salesman problem problem is NP Hard.
Scenario 2: Your boss asks you to write a program that, given a boolean formula, determines if there is an assignment of variables that makes it true. This is known as SAT, and is NP Complete.
What's more, there are even HARDER problems than these... things that take more than Polynomial space, so you would need more atoms than are in the entire universe to store the data.
And then there are problems that are IMPOSSIBLE to solve with current computers, given an infinite amount of time and space. Suppose you're writing a compiler, and you would like to warn the user that the program he wrote contains an infinite loop. This program is not Turing recognizable.
Or pretend you're an instructor for a programming course. You would like to write a program that takes in a student's homework, and compares it against a solution program, and determines if the two programs do the same thing. This would be the most amazing program in the world, but it's not even Turing recognizable!
Knowing these facts may seem academic, but if you know your problem reduces to TSP or SAT or CLIQUE, you can tell your boss this is not feasible for our input size, so we either need to relax the problem or approximate the solution. If you don't know this you're going to waste your time writing a program that takes 4 years to calculate the answer.
But it can still be computationally infeasible in the real world.
I think the best example that made me realize this was that O(n^100) is in P technically. But it is intractable. However, O(n^100) is still asymptotically better than O(100^n). However, algorithms that run like this are very rare... it's that large gap that exists between O(n^k) for small k and O(k^n). Always wondered why that was, but I guess if people knew we'd have a better understanding about the relationship between P and NP.
For most practical problems, O(n^3) is often intractable.
Just finished a final exam on Theory of Automata
on
Forty Years of P=NP?
·
· Score: 2
There was a question, in a round about and not obvious way, asked us to prove P = NP. Dirtiest most evil trick question I've ever encountered.
Thing is, you can sell your old one. Macs have a high resale value. I remember pricing out parts for a broken Macbook Pro, and even completely broken systems are absurdly expensive.
Thanks for clarifying. The context of the discussion was so ambiguous, I had no idea he was referring to Apple's desktop computer line. Those capital letters just threw me off completely
Gingerbread was released on December 6, 2010, yet the Nexus One didn't receive an update until almost 3 months later on Feb 23, 2011. The Windows Phone update in question was released On March 22nd. Here we are only a Month later where one manufacturer seems to have trouble with this.
How exactly is this situation worse than Android's?
Slashdot Mirror
While the article says that the number of Win7 infections have gone up while the number of WinXP infections has gone down, the infection rate on XP is still higher at 14 per 1000 compared to 4 per 1000 in Win7.
Then why is it still a problem 17 years later? Windows 7 easily recognizes a second monitor, but Ubuntu 10.10 completely ignores it. What's worse is I don't even know where to start with fixing it.
Isn't that equivalent to security by obscurity? I mean, after all the Linux kernel is open to anyone so Linux should be riddled with viruses, right?
I predict not a single update will go into the Linux and Android versions
As far as Skype updates go, they can keep them. In the past, Skype updates simply broke features and added bloat. For example, a couple versions ago Skype removed the option to minimize to the system tray for Windows 7 users. The Skype icon was always in the taskbar. The work around was to run it in Windows Vista compatibility mode. Very annoying.
Further, as I write this, the main Skype process is hogging the second most amount of memory on my system, at 75mb. Not to mention there's a separate process for Skype extras, which I don't even use. It seems with every update it gets worse, when no new features are really added. Why does it need that much memory?
I think you missed where I said this was a graduate level course; I'm in a PhD program. I'm guessing they either figure we've seen this stuff at least briefly once before, or we'll do what we need to do outside of class in order to understand it. I don't know how they treat the undergraduate version.
I guess if you consider rough pen/paper pseudocode outlines of algorithms well above the implementation level to be coding, I guess I did some coding for a few homework assignments. Honestly spent more time on proving complexity and proofs of correctness. As for your concern with my academic development, I appreciate it I guess, but I don't feel I have much to gain from physically implementing quicksort when I'm already coding 12+ hours a day.
They would get away with it too, because obviously anyone who will not pledge to not commit suicide is suicidal.
I said we didn't write code, not algorithms. I think the distinction is warranted, since algorithms existed well before programming languages. As for computer science graduates needing more programming, I don't know whether that is true or not, but it's not the job of a theoretical algorithms course to teach programming or lend experience in programming. For what it's worth this was a graduate level course; I don't know what they do at the undergraduate level.
You could learn complexity theory without ever learning to code in anything but BASIC.
I recently took two courses, one in algorithms another in theory of computation. I didn't write a single line of code for either. That's the way it should be, because algorithms are language agnostic (as long as they are Turing complete).
That is, given two languages A and B, "A solves B" means that there is a map f from B to A where f(x) is in A if and only if x is in B, for all possible x (not just those in B).
You pretty much just stated the definition for a reduction. I mean, if all you have is a problem with the word then I guess all you risk is confusing people who aren't familiar with your terminology.
I remember being introduced to the concept of reductions with the following analogy: Say I want to go to my friend's house.This is easy if I have his address, otherwise I would need to visit every house until I found his. So the problem of going to my friend's house reduces to knowing his address. But just by knowing his address, I'm not at my friend's house; I still have to do the actual work of walking there. To me, saying that A solves B in this context is like saying knowing my friend's address gets me to his house. Whereas in reality, knowing his address gives me a path for me to walk which when followed will lead me there.
(Actually, if I don't know the area this problem probably further reduces to finding a map.)
I answer questions on the math sub-board of a programming forum sometimes and have gotten a few NP(-complete) problems, though they were all easily recognizable as such even with my poor background in complexity theory.
Right, that's probably reasonable as long as you are well versed in maths, you can probably infer a lot of complexity theory (which in the end is evaluating and comparing asymptotic behavior of functions). Where I think complexity theory would help is in understanding just why the problem is hard, how it relates to other problems, which could lead you do a very nice way to relax or approximate the problem.
My favorite example of this is Shortest Path vs. Longest Path.
Shortest path is in P. The worst algorithm I think is Dijkstra's will solve it in O(V^2) for example. So you would think finding the longest path in the graph can't be much harder, right? Actually it's NP-Complete.
Right, I always get them mixed up.
Because saying "solves" removes an important implication of reducibility. When I say "exact cover reduces to knapsack" what I mean is there exists a function f(x) that maps every instance of exact cover to knapsack in polynomial time. The thing is, when we're talking about any theory, it's important to be very precise with language. What exactly does "solve" mean? Can we use knapsack to decide exact cover? Or does can we only use it to recognize exact cover? The difference between these two things in computability theory is drastic.
Scenario 1: The classic example. You work for a presidential political campaign and your candidate asks you to plan the best possible trip to 1000 counties for the next year. The optimal trip will visit the same city only once, and in total take the least distance. This is known as the traveling salesman problem problem is NP Hard.
Scenario 2: Your boss asks you to write a program that, given a boolean formula, determines if there is an assignment of variables that makes it true. This is known as SAT, and is NP Complete.
What's more, there are even HARDER problems than these... things that take more than Polynomial space, so you would need more atoms than are in the entire universe to store the data.
And then there are problems that are IMPOSSIBLE to solve with current computers, given an infinite amount of time and space. Suppose you're writing a compiler, and you would like to warn the user that the program he wrote contains an infinite loop. This program is not Turing recognizable.
Or pretend you're an instructor for a programming course. You would like to write a program that takes in a student's homework, and compares it against a solution program, and determines if the two programs do the same thing. This would be the most amazing program in the world, but it's not even Turing recognizable!
Knowing these facts may seem academic, but if you know your problem reduces to TSP or SAT or CLIQUE, you can tell your boss this is not feasible for our input size, so we either need to relax the problem or approximate the solution. If you don't know this you're going to waste your time writing a program that takes 4 years to calculate the answer.
B is in NP Complete if B is NP and also, every A in NP is polynomially reducible to A.
And of course I mean "polynomially reducible to B" for anyone confused.
Did it turn out to be a trick question or did he really want a^nb^n? The former is very evil while the latter I guess I can understand.
I think you're using NP, NP Hard, and NP Complete interchangeably, when they are very different.
B is in NP Hard if every A in NP polynomially reduces to B, even if B isn't in NP.
B is in NP Complete if B is NP and also, every A in NP is polynomially reducible to A.
B is in NP if B can be decided in polynomial time by a nondeterministic Turing Machine.
But it can still be computationally infeasible in the real world.
I think the best example that made me realize this was that O(n^100) is in P technically. But it is intractable. However, O(n^100) is still asymptotically better than O(100^n). However, algorithms that run like this are very rare... it's that large gap that exists between O(n^k) for small k and O(k^n). Always wondered why that was, but I guess if people knew we'd have a better understanding about the relationship between P and NP.
For most practical problems, O(n^3) is often intractable.
There was a question, in a round about and not obvious way, asked us to prove P = NP. Dirtiest most evil trick question I've ever encountered.
Thing is, you can sell your old one. Macs have a high resale value. I remember pricing out parts for a broken Macbook Pro, and even completely broken systems are absurdly expensive.
It's an odd world where someone fondles your junk and they can sue you for sexual harassment. I feel a Soviet Russia joke coming on...
Thanks for clarifying. The context of the discussion was so ambiguous, I had no idea he was referring to Apple's desktop computer line. Those capital letters just threw me off completely
I remember reading this before. Talk about Deja Vu.
Oh, now I remember: http://slashdot.org/comments.pl?sid=2096508&cid=35905686
I guess recycling posts is the green thing to do these days.
Gingerbread was released on December 6, 2010, yet the Nexus One didn't receive an update until almost 3 months later on Feb 23, 2011. The Windows Phone update in question was released On March 22nd. Here we are only a Month later where one manufacturer seems to have trouble with this.
How exactly is this situation worse than Android's?