Tor multiply encrypts all traffic passing inside of it (see "onion routing"). The only Tor router that sees your data without encryption is the last one you bounce it through, and an evil router only has a 1/400 chance of being this router.
Anyway, this probably isn't any worse than regular Internet use, where every router from you to the recipient can read the content of the traffic. It might be worse if you expect the Tor routers to be less trustworthy than the random Internet routers your traffic gets routed thrtough. I am of the opinion that it's probably better, since with Tor at least they don't know who the sender and recipient are. This may be more damaging information for some applications (indulging your tentacle porn fetish) than for others (webmail login).
Hear, hear! Scientists, mathematicians and engineers are the true engines of progress. An army of lawyers, politicians, financiers, athletes, musicians, and artists is not worth one of these individuals in the long run.
Firewalls are such a band-aid solution to the problem of unknown processes running on your own computers. The right way to solve the problem of rejecting incoming and outgoing requests is to make it easy to see which processes are accepting and making connections on which port.s
If the game had to be modified to unlock this, how is this different from nudie mods? Do vulgar variable names left in debugging information also constitute offensive material?
DFS would work alright if it was implimented iteratively, using stacks that replaced the recursion but only stored the relevant information, but this requires tracked visited marked vertices by making an boolean array named visited of size n WTF, mate? You don't need to mark nodes when traversing a tree via DFS. That's only when you are exploring a general graph. With trees, you just need to keep the path to the root on the stack. Simply push the current node with some index to the child being visited onto the stack. Then when you return from that child, move that index to point to the next child (a simple increment with constant number of children, following the pointer if children are a linked list), and push that back onto the stack.
but this requires tracked visited marked vertices by making an boolean array named visited of size n, where n are the numbers of nodes in the tree, and flagging each vertex as marked as you visit them (it takes size n because of the case when the tree is a line) You are correct that the stack will be O(n) in a tree with a branching factor of one. In this case BFS indeed uses less memory (asymptotically) than DFS. If each, or even most, nodes have a larger branching factor and the tree is somewhat balanced, which you see far more often in practice and is the expected case of a random tree, you store exponentially more nodes in a BFS than a DFS.
He was wrong for using recursion on a basic graph program that can be solved iteratively using methods from CS II. There are two issues here - iteration vs. recursion and BFS vs. DFS. Recursion is really not that expensive in general. It's some register pushes, a few register and memory copies to create the new stack frame, a CALL instruction, a RET and some register pops. And you can even implement BFS recursively if you like! I suppose asking the applicant to show a non-recursive solution is valid, but without more information about the environment recursion is a perfectively fine solution. As far as BFS vs. DFS, without more knowledge about the types of trees, I would certainly go with a DFS for a depth-limited traversal. It is just as fast (measuring number of nodes visited), and for most trees uses less memory.
We do seem to agree on the reasonableness of MS technical interviews. They probably do help keep people like you out.
With a depth-first search (DFS), you need O(d) memory, where d is the depth of the tree. A balanced tree with any constant branching factor has depth O(log(n)), n the total number of nodes. With a breadth-first search (BFS) you need O(w) memory, where w is the of the tree (the largest number of nodes on the same level). For a balanced tree with any constant branching factor this is O(n). Unless you have an extraordinarily narrow tree, the recursive BFS uses much less memory. This big advantage of BFS is the whole reason iterative deepening is a desirable method for traversing infinite or extremely large trees.
If I understand the problem correctly, we are to list all nodes at a given depth. This is the same as considering the input tree to be cut off after the given depth d, traversing this [virtual] tree, and outputting only the leaves at depth d. Then both methods visit the same total number of nodes, so runtime is asymptotically the same. I don't see why the small difference between a stack PUSH/POP and heap allocation/deallocation (assuming the queue is implemented as a linked list) would affect performance that much and in any case this is highly compiler/architecture/OS dependent.
This _is_ basic algorithms material. Seeing you so completely screw up this simple analysis with such confidence is simply breathtaking.
Close. A problem is NP-hard if every language in NP has a polynomial-time reduction to it. If the problem is also itself in NP then it is called NP-Complete.
The problem as they describe it (find the shortest possible route through all the locations) is, as far as I know, NOT easy checkable in the way they describe.
You are right that polynomial verification of the TSP decision problem exists, and that such verification of the optimization problem doesn't. Interestingly, polynomial solution of the decision problem would imply polynomial solution of the optimization problem (just use binary search).
If I recall correctly, NP actually describes a set of decision problems for which a positive answer is very easily checkable, but a negative answer might or might not be.
Right. Problems (aka languages) for which membership certificates exist are in NP. Problems for which proofs of non-membership exist are in a class called co-NP. If P=NP then NP=co-NP, or conversely if NP != co-NP then P != NP. Obviously, the only problems which are currently known to have both YES and NO certificates are in P. Since TSP is NP-Complete, if certificates of non-membership exist then P=NP. This is unlikely to be true.
"Conventional computing" probably means all formal models of computation that are polynomially related to Turing machines. That is, any function which can be computed in a conventional computing model can be computed by a Turing machine in P(n)*K steps, where n is the size of the input, P is some polynomial that is depends only on the function, and K is the number of steps it takes for the other model to compute it on the input.
The set of conventional models includes everything that we can currently build, including the lambda calculus, cellular automata, the RAM machine, etc. This includes your home computer. It does not include quantum computers.
Avi Silberschatz also recently left Bell Labs (2003). You may know him from his operating systems and databases books. Lucky for me, he joined my department!
I'll give you that America has trained and supplied people and groups that have gone on to commit atrocities. Maybe we even supported them while they were doing these things. Maybe some people in government even knew about them as they were happening.
Your conclusion seems to be that these things are cause for recent terrorist actions against us. I don't think this is exactly correct. From what I've read many Arabs dislike the American government because of our military and monetary support for Israel, as well as the fact the we have troop stationed on their land (ie Saudi Arabia).
Even if all of these things are true, however, it doesn't follow that the American government has acted irresponsibly in the past and continues to do so now. The real world is full of hard choices, and maybe the best decision in the 1980's was to support the mujahadeen against the communists, even if there was a risk they would later turn against us. Is the world a better place without the Cold War but with Islamic terrorism? Are we a better country for having picked that battle and (arguably) won it?
You also seem to suggest that our responsibility for terrorism means we need a more pacifist, compromising, multilateral foreign policy. This doesn't sound like a recipe for success to me. Maybe you could provide more details on what exactly you would do differently from this administration.
BTW, nobody has found credible evidence of election fraud that would have turned the election. I have to wonder if the Democrats had done better, but with the same election abnormalities as have been reported, you would still consider the election "illegal". I somehow doubt it.
What's disgusting is seeing people misuse generously offered open WiFi to commit illegal acts. Maybe the journalist/editor/paper came into this story with a pro-corporate bias. Maybe they are exaggerating the misuse of wireless networks and the difficulty they pose to law enforcement. Maybe, however, you are refusing to believe these things because of your own bias.
It seems wholly possible, even likely, that open WiFis pose opportunities for people to commit crimes while making it harder for law enforcement to stop them. Is this worth the benefit of free, widely available Internet access? Are there technical or legal steps we can take to tighten the holes these networks open to maximize their potential? These are real questions that deserve thoughtful consideration, rather than just screaming "FUD!".
Lets all be reasonable and not spread FUD but support the urgently needed free WiFi access.
Yes, let's be reasonable. Cheap AIDS medication in the third world is "urgently needed". Cheap Internet access in the US is not "urgently needed".
I'm not overwhelmed by Knuth's contributions either. Two things come to mind that are probably important, though:
Knuth created the pushdown automata algorithm for LR Parsing. I'm not sure exactly what most modern compilers and parser generators are using, but I remember hearing that Yacc parses LALR(1) grammars, most likely using an algorithm based on his.
"Concrete Mathematics", a book Knuth coauthored with Patashnik and Graham, is a great book for reference and instruction in combinatorics. Things like generating functions, binomial coefficients, Stirling numbers, and finite calculus are probably not of intense interest to most computer scientists. As a graduate student in theory, though, I regularly deal with problems involving recurrences and series, and the techniques I learned from that book are invaluable.
How ironic that in discussing Knuth's errors in his books, the reporter makes a mistake. 256 = 2^8, which is one followed by eight zeros, not seven, and hence looks like one hundred million, not ten million.
I also find it amusing how he describes the "binary language" of computers. So different from that "decimal language" we humans use.
Slashdot Mirror
Tor multiply encrypts all traffic passing inside of it (see "onion routing"). The only Tor router that sees your data without encryption is the last one you bounce it through, and an evil router only has a 1/400 chance of being this router.
Anyway, this probably isn't any worse than regular Internet use, where every router from you to the recipient can read the content of the traffic. It might be worse if you expect the Tor routers to be less trustworthy than the random Internet routers your traffic gets routed thrtough. I am of the opinion that it's probably better, since with Tor at least they don't know who the sender and recipient are. This may be more damaging information for some applications (indulging your tentacle porn fetish) than for others (webmail login).
Hear, hear! Scientists, mathematicians and engineers are the true engines of progress. An army of lawyers, politicians, financiers, athletes, musicians, and artists is not worth one of these individuals in the long run.
.0001% = 1/10E6. You are predicting at least one million posts on this topic. You're lucky the mods are as bad with numbers as you are.
Firewalls are such a band-aid solution to the problem of unknown processes running on your own computers. The right way to solve the problem of rejecting incoming and outgoing requests is to make it easy to see which processes are accepting and making connections on which port.s
Either way, one hell of an Easter egg!
WTF, mate? You don't need to mark nodes when traversing a tree via DFS. That's only when you are exploring a general graph. With trees, you just need to keep the path to the root on the stack. Simply push the current node with some index to the child being visited onto the stack. Then when you return from that child, move that index to point to the next child (a simple increment with constant number of children, following the pointer if children are a linked list), and push that back onto the stack.
but this requires tracked visited marked vertices by making an boolean array named visited of size n, where n are the numbers of nodes in the tree, and flagging each vertex as marked as you visit them (it takes size n because of the case when the tree is a line)
You are correct that the stack will be O(n) in a tree with a branching factor of one. In this case BFS indeed uses less memory (asymptotically) than DFS. If each, or even most, nodes have a larger branching factor and the tree is somewhat balanced, which you see far more often in practice and is the expected case of a random tree, you store exponentially more nodes in a BFS than a DFS.
He was wrong for using recursion on a basic graph program that can be solved iteratively using methods from CS II.
There are two issues here - iteration vs. recursion and BFS vs. DFS. Recursion is really not that expensive in general. It's some register pushes, a few register and memory copies to create the new stack frame, a CALL instruction, a RET and some register pops. And you can even implement BFS recursively if you like! I suppose asking the applicant to show a non-recursive solution is valid, but without more information about the environment recursion is a perfectively fine solution. As far as BFS vs. DFS, without more knowledge about the types of trees, I would certainly go with a DFS for a depth-limited traversal. It is just as fast (measuring number of nodes visited), and for most trees uses less memory.
We do seem to agree on the reasonableness of MS technical interviews. They probably do help keep people like you out.
(I saw some attempts but didn't care much for them)..
Hahahaaaaaaaaaaa
Thanks, I needed that.
With a depth-first search (DFS), you need O(d) memory, where d is the depth of the tree. A balanced tree with any constant branching factor has depth O(log(n)), n the total number of nodes. With a breadth-first search (BFS) you need O(w) memory, where w is the of the tree (the largest number of nodes on the same level). For a balanced tree with any constant branching factor this is O(n). Unless you have an extraordinarily narrow tree, the recursive BFS uses much less memory. This big advantage of BFS is the whole reason iterative deepening is a desirable method for traversing infinite or extremely large trees.
If I understand the problem correctly, we are to list all nodes at a given depth. This is the same as considering the input tree to be cut off after the given depth d, traversing this [virtual] tree, and outputting only the leaves at depth d. Then both methods visit the same total number of nodes, so runtime is asymptotically the same. I don't see why the small difference between a stack PUSH/POP and heap allocation/deallocation (assuming the queue is implemented as a linked list) would affect performance that much and in any case this is highly compiler/architecture/OS dependent.
This _is_ basic algorithms material. Seeing you so completely screw up this simple analysis with such confidence is simply breathtaking.
Close. A problem is NP-hard if every language in NP has a polynomial-time reduction to it. If the problem is also itself in NP then it is called NP-Complete.
You are right that polynomial verification of the TSP decision problem exists, and that such verification of the optimization problem doesn't. Interestingly, polynomial solution of the decision problem would imply polynomial solution of the optimization problem (just use binary search).
If I recall correctly, NP actually describes a set of decision problems for which a positive answer is very easily checkable, but a negative answer might or might not be.
Right. Problems (aka languages) for which membership certificates exist are in NP. Problems for which proofs of non-membership exist are in a class called co-NP. If P=NP then NP=co-NP, or conversely if NP != co-NP then P != NP. Obviously, the only problems which are currently known to have both YES and NO certificates are in P. Since TSP is NP-Complete, if certificates of non-membership exist then P=NP. This is unlikely to be true.
... and it's P(K), not P(n)*K. I am an idiot.
Sorry, the polynomial P depends only on the other formal model.
The set of conventional models includes everything that we can currently build, including the lambda calculus, cellular automata, the RAM machine, etc. This includes your home computer. It does not include quantum computers.
Avi Silberschatz also recently left Bell Labs (2003). You may know him from his operating systems and databases books. Lucky for me, he joined my department!
Your conclusion seems to be that these things are cause for recent terrorist actions against us. I don't think this is exactly correct. From what I've read many Arabs dislike the American government because of our military and monetary support for Israel, as well as the fact the we have troop stationed on their land (ie Saudi Arabia).
Even if all of these things are true, however, it doesn't follow that the American government has acted irresponsibly in the past and continues to do so now. The real world is full of hard choices, and maybe the best decision in the 1980's was to support the mujahadeen against the communists, even if there was a risk they would later turn against us. Is the world a better place without the Cold War but with Islamic terrorism? Are we a better country for having picked that battle and (arguably) won it?
You also seem to suggest that our responsibility for terrorism means we need a more pacifist, compromising, multilateral foreign policy. This doesn't sound like a recipe for success to me. Maybe you could provide more details on what exactly you would do differently from this administration.
BTW, nobody has found credible evidence of election fraud that would have turned the election. I have to wonder if the Democrats had done better, but with the same election abnormalities as have been reported, you would still consider the election "illegal". I somehow doubt it.
It seems wholly possible, even likely, that open WiFis pose opportunities for people to commit crimes while making it harder for law enforcement to stop them. Is this worth the benefit of free, widely available Internet access? Are there technical or legal steps we can take to tighten the holes these networks open to maximize their potential? These are real questions that deserve thoughtful consideration, rather than just screaming "FUD!".
Lets all be reasonable and not spread FUD but support the urgently needed free WiFi access. Yes, let's be reasonable. Cheap AIDS medication in the third world is "urgently needed". Cheap Internet access in the US is not "urgently needed".
Knuth created TeX, not LaTeX. Leslie Lamport created LaTeX, basically a set of macros to automate the most common usages of TeX.
How ironic that in discussing Knuth's errors in his books, the reporter makes a mistake. 256 = 2^8, which is one followed by eight zeros, not seven, and hence looks like one hundred million, not ten million. I also find it amusing how he describes the "binary language" of computers. So different from that "decimal language" we humans use.