The tags match... when you are in the story. I think each paragraph should have its own HTML tags. You want italics, fine, just do it for each paragraph. Then, when only the first bits make it to the front page, they have their own matching HTML tags.
Living near and working in Hershey, PA (technically Derry Township, but there was a vote to change... different tangent) for a while means I get to smell chocolate all the time. I've gotten so I don't notice it any more, and I have never heard anyone "ewww, that town smells like chocolate" or "I had to move away, the chocolate smell just got to me after a while." Now, getting near the West plant (where they pasturize milk) and you get this odor of stale milk - not bad evil sour milk - just stale. It's not "I gotsta build a 3-bedroom here because of the lovely odor" but it's not "roll up the windows and drive fast" kind of thing either - it's just something that's there. I don't live that close to that plant to have grown used to it, but I don't see many For Sale signs in that area either.
I think they are trying to receive communications from deep space and begin their plans for place travel. This is just to compete with the humans at the Arecibo radio telescope.
choose banks based on their... customer service...
But to this dood, browser support IS customer service. He's a customer, he wants service, and he probably wants it in a comfortable manner. Just as you would probably not pick a brick and morter bank that had the heat set to 110 (degrees or celsius, your pick) and was blaring [insert your most dispised band/group/genre] music and had that "Service With A Drunk" kind of attitude, this guy seems to hold browser type in high regard. Although it might not be a popular restriction (to you or many others right now for that matter) don't knock someone's own reasoning, maybe he'd rather give up better interest rates just to have a "better" user experience - maybe that premium is worthwhile for some people - maybe money is not a concern* and interface is!
* - if money is no object... let me hold it and I sware I'll support your browser!
Re:Correct me if I'm wrong
on
10.2.2 Is Coming
·
· Score: 4, Informative
I don't know about MAC-land, but I do know linux land. You can boot a cleanly unmounted ext3 under ext2 (if it's not clean, do e2fsck).
To mount something as ext3 you need to run:
tune2fs -j/dev/hdaX
on it first. This can be done on an unmounted or on a mounted filesystem. If you create the journal on a mounted filesystem you will see a.journal file. Don't try to delete this and don't back this up or restore it from backup! If you run tune2fs -j on an unmounted partition an unvisible journal file will be created. Now you can mount the filesystem as ext3 using:
the common computer science usage of 'an O(log n) algorithm' is wrong, I don't know.
Well, we tend to often wave our hands at things. One of the common things is the reading of the input. These things do come back and bite us. I remember a proof a few years back getting for pimality and things were great except the author didn't properly take into account the loading/encoding of the input. It's not something that creeps into every discussion, nor have I ever seen any two people go on at length as we have about this (thanfully your responces have been both inteligent and interesting), but I think it's something that we mustn't over look.
Well, I think you went into the ivory tower of CS as I tend to:
So the data will always take O(n) time to copy. Transfers from the hard disk to main memory will be O(n).
We can do better than O(n) to transfer from hard disk to main memory due to the width of a word. We can transfer a word in one clock cycle. I am not saying we can transfer data in constant time, it must still be based on the length of the data, but we can create instances where we do not need to go character by character to transfer. I think this is a minor point of little debate value, but consider lossless compressed data (Huffman for instnace) and we are clearly transfering less amount of data, but the computational over head negates the decrease in data transfer size so it's meaningless, but parallel transfers on a data bus mean that we can transfer several portions of our data at the same time. In the worst case we get back to character by character, but just like your example of head vs. tail we can create specific instances where things indicate a certain behavior. Now, on to:
The point is that not every algorithm requires the data to be fully copied in and out again.
I think we're getting back to the semantics debate again. An algorithm (this is my definition and I could have sworn a commonly accepted one... but who knows) is a definition of a step-by-step problem-solving procedure. I think you'll agree to that version, but I extend that to talk about the problem definition and include that the problem must specify the input in its entirity.
Here, I think we're both starting to get tongue tied on the semantics. Take this analogy.
For me to right now bake a cake would require a trip to the store for (among other things) sugar. I have a recipie (an algorith) for the cake, but I don't have the ingerdients. The recipie (including mixing and baking) would require 40 minutes. However, the trip to the store (and back) would require 10 minutes. If my SO asked me to bake a cake and asked how long it would take, she would be annoyed if I replied "40 minutes" and it really took me 50 minutes.
Now, to relate this to your senario of the input being done once and then algs. running on this many times, if I were asked to bake a pie I would also need to run to the store (again 10 minutes) before I could begin the algorithm that for arguement sake takes 30 minutes. I could run to the store once thus getting the needed input for both algorithms, and each one (once they have the needed input) would take their alloted times. But that doesn't make either alg. quicker since they were dependant on the prep work. In my baking the actual creation of a pie is an operation in the entire process, the reading (buying) and encoding (opening/measuring) of the input needed time as well.
Now, before you point it out, I realize that baking time is not dependant on running-to-the-store time, but you get the point about prep work being done before the alg. is even brought into the CPU.
Back to your specific example about using binary search. Do not forget that for binary search to work we need to have the elements aligned so that searches can run in O(log n) and that alignment doesn't happen over night. Even in non-deterministic approaches we always at least verify that the input was formatted the way we would like. Those searches are each an operation in the overall algorithm.
And I will concede that data can be copied in less than O(n) time. It doesn't always go that way, but if you are talking about data that lives on your hard disk that is then sent in O(log n) time to memory (pretend the CPU can deal with things in memory directly and it does not need to be copied to cache/registers) due to data being represented in binary. And yes, these aren't things that are usually discussed and are just assumed away. But, doing pass by value and assuming things happen quickly is not good - being apreciative of these issues is helpful.
I guess it's mostly a semantics debate. I don't think it's acceptable to talk about algorithms which take O(log n) time or even less. But I do think it's accepable to talk about operations (portions of algorithsm) that take O(log n) time or even less.
As for 'seq 0 1000000000 | head -1' and tail -1 I argue that head once the head is satisfied then the input is stopped. Piping into wc has a similar effect of tail -1 due to having to generate all of the input. To me this is like a special case using some OS trickery. Here, the entire input stream did not need to finish since the reciever has some control over the sender. The pipe operation is not a serial "do this then do that" operation. Rather things occur in parallel, input is generated and send to the reciever. If at any time in the chain a reciever no longer requires input the senders up the chain cascadingly halt. Receivers being so tightly coupled with senders is not always this easy. I'll be the first to say that your point is supported by that execution, however a proof by lack of counter example is not a sufficient proof. We can't take your example and state that input is unnessary. I guess we can't say that input timing is entirely necessary either, but that's why I try to seperate things into algorithms and operations. An algorithm encountering the entire life of data while an operation may deal with data on only a portion of its life.
As a side note, data clean up also takes time. In your example of the command line execution the data was no stored so removal is not applicable. But what about your previous example about data that was easily obtainable from disk or other randomly accessible media? At some point (assuming the system is bounded by storage and won't destroy itself, and I'm talking outside the ivory tower of computer since here) the data is no longer needed and must be destroyed. This garabe collection is often not cheap, especially for dynamically allocated memory. Here, in this phase of the data life (the death) many people overlook the time spent for cleanup. I think debate about garbage colletion is a more common one than data creation, but the two are highly related.
See my argument here for my responce to the AC with a similar point of view, but I'll address some of your specifics here.
if you take something like an ordinary computer, and have the input already in memory
Wait, stop right there.... how did the stuff get into the computer in the first place? If you are dealing with things you have in the sytem already then you are talking strictly about operations performed on them - not talking about a completel algorithm which takes input, does something, and returns.
Even if you take a computing device that must read its input one character at a time, and doesn't have a random-access memory
Side note: I argue that at some point in the life of the data, at the inception of this data, it was trasmitted one character at a time. I can take data into my system and store it on a floppy. Then make 1,000 copies of the floopy and distribute them. Now that the data has been put into a randomly acessible form and I wish to do operations on this data (read the first block for example) I can't argue that this took O(constant) time solely because my data is randomly accessible. I must ask myself how the data got to me in the first place - the true honest read.
, then there are still some algorithms that take less time than reading the whole input. Returning the first element of a list, for example.
And just how did the data get to you? Probably one character at a time. And the system that is sending this data is taking O(n) time to send it to you. If you are disregarding data being sent or not - it's still in the stream. If you think you are simply going to ask the sender to send you a portion of the input then you must take into account the sender's time to find this portion of the input (again, constant time in your example) but then how did the sender get the input in the first place?
One must always trace the input back to an originating point. Operations on data/input that are already on a sytem are operations on data partway through its life. A true algorithmic discussion is on the entirity of the data's life - beginning, middle, and end.
Say you want to return the first element in an array of length N, and you're given the entire array... well, your "input" (as I'm defining it) is of length N, but obviously the worst your algorithm can do is run in constant time (assuming you don't do anything monumentally stupid).
You must state that you are using pass by reference, otherwise getting the input to the algorithm takes O(n). Think a tad more in the realm of theory - Turing Machines and such. Specifically deterministic TMs, since non-deterministic ones run uber fast (1. Read Input and verify it is of the correct type 2. Ask an oracle for an answer 3. Decide what that answer means and return). Be careful with step one, it's often written off, but checking input for validity sometimes takes a little time.
Ok, then you go on about how the term input is sometimes loose. Then ending with:
"Input" is what you're given, whether you need it or not.
Ok, stop right there. Input is everything... For example the whole array in your example. To read that data in it takes O(n). You can't do things any faster. If you are asked to return the first element of the array so you "read" that and just ignore the rest of the input, fine... but that input still needs to be sent to you.
And then it's easy to think of problems whose algorithms run in time smaller than O(n).
Huh? I could have sworn you had the idea and were restating mine back with the last quote - you get all of the input. Keep in mind, pass by reference is just a neat coding trick, somewhere at somepoint in time the input had to be fed into the system - you can't get around that. Sure, it might have been passed to a particular portion using pass by reference, but if you wish to talk about the running time of that portion of code (disregarding the other algorithms you so skillfully coded in the remaining code) you must still take into account the reading of the data into your system. To ignore how the data got onto the system is to not completely discuss the algorithm.
This is a crucial thing, and is often over looked. This is fine for little things like talking about finding the head of a list or something. There we often say the "operation" runs in constant time. But a true algorithm that takes an array as input and returns the head takes O(n) due to the read. It's not too big of an issue here, but when you get into things that need to be encoded in certain ways for the remainder of the algorithm to work, and you think that just encoding into unary takes O(1) time, then you're in for trouble.
Don't confuse operations (portions of an algorithm) and the actual algorithms themselves. An operation can take less than O(n) time, but if you intend to promote that operation to being a stand alone algorithm you need to incorporate reading the input AND if there were previous operations that got the input turned into a particularly useful form. Consider this argument:
Johnny wishes to read find the largest element in an array. He decides to sort the array in desending order and then read the first element. He knows that reading the first element takes O(1) time so he says his algorithm runs in constant time. Bzzzzt, wrong. He only looked at an operation and then scaled that to the entire algorithm. Ignoring the fact that it's faster to do this without sorting and continue with Johnny's plan we need to look at previous sub-algorithmic operations and account for the reading in of the entire array. The reading alone took O(n) and the sorting took more (hopefully he's smart enough to use a decent sorting algorithm, but that's not the point - we don't need to be tight about the bounds of his sort for this discussion). Disregarding the sorting but keeping the reading we are already up to O(n).
Similar to analysis algorithms (sorting, finding stuff, etc...) we have generation algorithms such as producing n Fibonacci numbers. Here I hope we have less things to argue about since how can you possibly generate n numbers without at least "touching" those n numbers?
I don't think this quite gets the point across that you want it to, "I'm just a theta(n) person in a theta(log n) world." would work better;)
I'm not so sure you get the point I'm trying to make... Can you ever have an alg. that runs in less time than it takes to read in the entire input? I'm trying to make a statment about difficult demands placed by the world and what I think of my own abilities to keep going at the real physical limit, but it just doesn't match the expectations of the world.
I'm not saying I'm asymptotically similar to something - I'm just talking in the worst case that I'm bounded. I feel the world wants things done in an unrealistic time (in the worst case) and that I just can't seem to provide that...
You can set the messages allow/not allow per each journal. You can set the default option in your preferences... should you ever want to actually go and let everyone talk about it.
You know... your write a lot of interesting things in your journal - why don't you ever allow comments so we could have a discussion about the topics you present?
If you are going to learn to program (and in today's economy, I actually don't recommend that) please steer clear of MIT.
Maybe I'm unique in my feelings about SE and programming, but I feel software engineering and programming to be quite different. I feel they are similar to a mechanical engineer and a machinist. The ME designs things, uses their knowledge of how things work (limitations of physical media [strength, size, weight/mass], timing of things, etc...) to design something. This design is then turned over to machinst, who although is skilled in their trade at making designs reality, does not (IMHO) add much to the product other than just making it. Don't get me wrong coders and machinists are highly skilled people and don't just walk in off the street. But, machinists who design do not always get the greatest of results - they are approaching the system from a completely different angle. Similarly coders who design (without formal design input, i.e. they were just young code monkeys) do not always make the best design of a system. Granted, with experience a coder will get to see many different designs and (through the likely maintainence phase) see how these designs worked - then this coder would work well as an engineer.
So, to take my approach and your input and put them together and that just makes the MIT course on software engineering sound better. If you want to have a good designer do not corrupt their mind too much with code (they do need to experience it to see how their cog fits into the system), and if you want a great coder do not bog them down with waterfall model, OO message passing, and other fundamental SE things (they do need to experience it to see how their cog fits into the system).
Nothing better than "Ernest goes to camp" on an IMAX screen.
If there are three lines:
1. Ernest goest to camp IMAX Movie 2. Dude, where's my car IMAX Movie 3. Slow painful death involving hideous torture locked in a room with Martha Stewart, Carrot Top, and Anna Nicole Smith.
I wonder if I'll have the same credit card numbers in 15 years.
My CC company tends to send me a new one every few years (right before the old one expires) with a new number. When does your card expire? What does your CC company do around that time if it doesn't send you a new number?
Here here!! I'm with you all the way on that vote. But, if you can't jump right in with heavy Knuth, start with Weiss' Data Structures book (in general form and specific coding languages, I reccomend the general) and CLR (Cormen, Leiserson, and Rivest [as in RSA]) book Introduction to Algorithms.
By default the Access Point broadcasts the SSID every few seconds...
Can someone then explain to me what is the reason for choosing a secure SSID?
Well, if you name yours "company name" and you happen to work for Company Name then it's kind of obvious whose network you have. Now, this issue isn't so important when you have a large corporate campus and you have to be in the parking lot just to get reception "gee, I wonder whose network this is???" But it makes a lot of sense in a shared environment or in office space in urban environments. Chances are by doing some range poking you can narrow down the broadcast field where you're catching an SSID and possibly locate the physical location of the box, but it's just another layer to security. As is often promoted, layering security is better than just one this-had-better-hold form of security -- it often means you can detect intrusions at less vital areas and it often means those inside with proper access aren't working in some soft gooy center where it's easy to gain access throughout.
With the lack of security people working for the government, the cons serve as a recruitment rich environment. Problem is, they won't hire people with a record usually.
Their other problem is they pay so low. I don't have a record, I have a MS degree in CS focusing on crypto and other security items and the best pay from the NSA would still force me to live out of my car.
Could you please elaborate on that for me? I always though NTM's (non-determinstic Turing Machines) were so powerful since they always made the "right" decision and didn't need luck or a specific rule set, they just non-determinstically chose the right path.
If you have a network that is just sending packets correctly with out decisions then all the better and we should take it on tour. Maybe, however you're refering to the complete broadcast mentality that packets aren't sent to specific hosts as required but to all hosts since this is how non-determinism is typically simulated, but simulated non-determinism and true non-determinism are a tad different.
Maybe it's just that I don't really know a lot of networking theory, but that term just sort of jumped out at me. I've often equated non-determinism with magic...
Slashdot Mirror
The tags match... when you are in the story. I think each paragraph should have its own HTML tags. You want italics, fine, just do it for each paragraph. Then, when only the first bits make it to the front page, they have their own matching HTML tags.
Ah, and don't forget:
- Enjoy your job
- Make lots of money
- Work within the law
Pick any two.
"into the empty space in the wall" but that's only about 16" X 3 1/2" by about 6' (some construction techniques differ)
6 foot celings? Remind me never to come over to your place... My doorways are taller than that...
This seems like the way that shows like Insomniac get started.
Perhaps you should watch that show a few times and see where he goes. Nothing like a good tour of a brothel to add to your church group tour plan.
Living near and working in Hershey, PA (technically Derry Township, but there was a vote to change... different tangent) for a while means I get to smell chocolate all the time. I've gotten so I don't notice it any more, and I have never heard anyone "ewww, that town smells like chocolate" or "I had to move away, the chocolate smell just got to me after a while." Now, getting near the West plant (where they pasturize milk) and you get this odor of stale milk - not bad evil sour milk - just stale. It's not "I gotsta build a 3-bedroom here because of the lovely odor" but it's not "roll up the windows and drive fast" kind of thing either - it's just something that's there. I don't live that close to that plant to have grown used to it, but I don't see many For Sale signs in that area either.
I think they are trying to receive communications from deep space and begin their plans for place travel. This is just to compete with the humans at the Arecibo radio telescope.
choose banks based on their ... customer service...
But to this dood, browser support IS customer service. He's a customer, he wants service, and he probably wants it in a comfortable manner. Just as you would probably not pick a brick and morter bank that had the heat set to 110 (degrees or celsius, your pick) and was blaring [insert your most dispised band/group/genre] music and had that "Service With A Drunk" kind of attitude, this guy seems to hold browser type in high regard. Although it might not be a popular restriction (to you or many others right now for that matter) don't knock someone's own reasoning, maybe he'd rather give up better interest rates just to have a "better" user experience - maybe that premium is worthwhile for some people - maybe money is not a concern* and interface is!
* - if money is no object... let me hold it and I sware I'll support your browser!
I don't know about MAC-land, but I do know linux land. You can boot a cleanly unmounted ext3 under ext2 (if it's not clean, do e2fsck).
/dev/hdaX
.journal file. Don't try to delete this and don't back this up or restore it from backup! If you run tune2fs -j on an unmounted partition an unvisible journal file will be created.
/dev/hdaX /mnt/somewhere
3 -faq.html and is a good FAQ for those who are not down and jiggy with ext3.
To mount something as ext3 you need to run:
tune2fs -j
on it first. This can be done on an unmounted or on a mounted filesystem. If you create the journal on a mounted filesystem you will see a
Now you can mount the filesystem as ext3 using:
mount -t ext3
Of note, this info was shamlessly stolen from http://batleth.sapienti-sat.org/projects/FAQs/ext
the common computer science usage of 'an O(log n) algorithm' is wrong, I don't know.
Well, we tend to often wave our hands at things. One of the common things is the reading of the input. These things do come back and bite us. I remember a proof a few years back getting for pimality and things were great except the author didn't properly take into account the loading/encoding of the input. It's not something that creeps into every discussion, nor have I ever seen any two people go on at length as we have about this (thanfully your responces have been both inteligent and interesting), but I think it's something that we mustn't over look.
Well, I think you went into the ivory tower of CS as I tend to:
So the data will always take O(n) time to copy. Transfers from the hard disk to main memory will be O(n).
We can do better than O(n) to transfer from hard disk to main memory due to the width of a word. We can transfer a word in one clock cycle. I am not saying we can transfer data in constant time, it must still be based on the length of the data, but we can create instances where we do not need to go character by character to transfer. I think this is a minor point of little debate value, but consider lossless compressed data (Huffman for instnace) and we are clearly transfering less amount of data, but the computational over head negates the decrease in data transfer size so it's meaningless, but parallel transfers on a data bus mean that we can transfer several portions of our data at the same time. In the worst case we get back to character by character, but just like your example of head vs. tail we can create specific instances where things indicate a certain behavior. Now, on to:
The point is that not every algorithm requires the data to be fully copied in and out again.
I think we're getting back to the semantics debate again. An algorithm (this is my definition and I could have sworn a commonly accepted one... but who knows) is a definition of a step-by-step problem-solving procedure. I think you'll agree to that version, but I extend that to talk about the problem definition and include that the problem must specify the input in its entirity.
Here, I think we're both starting to get tongue tied on the semantics. Take this analogy.
For me to right now bake a cake would require a trip to the store for (among other things) sugar. I have a recipie (an algorith) for the cake, but I don't have the ingerdients. The recipie (including mixing and baking) would require 40 minutes. However, the trip to the store (and back) would require 10 minutes. If my SO asked me to bake a cake and asked how long it would take, she would be annoyed if I replied "40 minutes" and it really took me 50 minutes.
Now, to relate this to your senario of the input being done once and then algs. running on this many times, if I were asked to bake a pie I would also need to run to the store (again 10 minutes) before I could begin the algorithm that for arguement sake takes 30 minutes. I could run to the store once thus getting the needed input for both algorithms, and each one (once they have the needed input) would take their alloted times. But that doesn't make either alg. quicker since they were dependant on the prep work. In my baking the actual creation of a pie is an operation in the entire process, the reading (buying) and encoding (opening/measuring) of the input needed time as well.
Now, before you point it out, I realize that baking time is not dependant on running-to-the-store time, but you get the point about prep work being done before the alg. is even brought into the CPU.
Back to your specific example about using binary search. Do not forget that for binary search to work we need to have the elements aligned so that searches can run in O(log n) and that alignment doesn't happen over night. Even in non-deterministic approaches we always at least verify that the input was formatted the way we would like. Those searches are each an operation in the overall algorithm.
And I will concede that data can be copied in less than O(n) time. It doesn't always go that way, but if you are talking about data that lives on your hard disk that is then sent in O(log n) time to memory (pretend the CPU can deal with things in memory directly and it does not need to be copied to cache/registers) due to data being represented in binary. And yes, these aren't things that are usually discussed and are just assumed away. But, doing pass by value and assuming things happen quickly is not good - being apreciative of these issues is helpful.
I guess it's mostly a semantics debate. I don't think it's acceptable to talk about algorithms which take O(log n) time or even less. But I do think it's accepable to talk about operations (portions of algorithsm) that take O(log n) time or even less.
As for 'seq 0 1000000000 | head -1' and tail -1 I argue that head once the head is satisfied then the input is stopped. Piping into wc has a similar effect of tail -1 due to having to generate all of the input. To me this is like a special case using some OS trickery. Here, the entire input stream did not need to finish since the reciever has some control over the sender. The pipe operation is not a serial "do this then do that" operation. Rather things occur in parallel, input is generated and send to the reciever. If at any time in the chain a reciever no longer requires input the senders up the chain cascadingly halt. Receivers being so tightly coupled with senders is not always this easy. I'll be the first to say that your point is supported by that execution, however a proof by lack of counter example is not a sufficient proof. We can't take your example and state that input is unnessary. I guess we can't say that input timing is entirely necessary either, but that's why I try to seperate things into algorithms and operations. An algorithm encountering the entire life of data while an operation may deal with data on only a portion of its life.
As a side note, data clean up also takes time. In your example of the command line execution the data was no stored so removal is not applicable. But what about your previous example about data that was easily obtainable from disk or other randomly accessible media? At some point (assuming the system is bounded by storage and won't destroy itself, and I'm talking outside the ivory tower of computer since here) the data is no longer needed and must be destroyed. This garabe collection is often not cheap, especially for dynamically allocated memory. Here, in this phase of the data life (the death) many people overlook the time spent for cleanup. I think debate about garbage colletion is a more common one than data creation, but the two are highly related.
See my argument here for my responce to the AC with a similar point of view, but I'll address some of your specifics here.
if you take something like an ordinary computer, and have the input already in memory
Wait, stop right there.... how did the stuff get into the computer in the first place? If you are dealing with things you have in the sytem already then you are talking strictly about operations performed on them - not talking about a completel algorithm which takes input, does something, and returns.
Even if you take a computing device that must read its input one character at a time, and doesn't have a random-access memory
Side note: I argue that at some point in the life of the data, at the inception of this data, it was trasmitted one character at a time. I can take data into my system and store it on a floppy. Then make 1,000 copies of the floopy and distribute them. Now that the data has been put into a randomly acessible form and I wish to do operations on this data (read the first block for example) I can't argue that this took O(constant) time solely because my data is randomly accessible. I must ask myself how the data got to me in the first place - the true honest read.
, then there are still some algorithms that take less time than reading the whole input. Returning the first element of a list, for example.
And just how did the data get to you? Probably one character at a time. And the system that is sending this data is taking O(n) time to send it to you. If you are disregarding data being sent or not - it's still in the stream. If you think you are simply going to ask the sender to send you a portion of the input then you must take into account the sender's time to find this portion of the input (again, constant time in your example) but then how did the sender get the input in the first place?
One must always trace the input back to an originating point. Operations on data/input that are already on a sytem are operations on data partway through its life. A true algorithmic discussion is on the entirity of the data's life - beginning, middle, and end.
Say you want to return the first element in an array of length N, and you're given the entire array... well, your "input" (as I'm defining it) is of length N, but obviously the worst your algorithm can do is run in constant time (assuming you don't do anything monumentally stupid).
You must state that you are using pass by reference, otherwise getting the input to the algorithm takes O(n). Think a tad more in the realm of theory - Turing Machines and such. Specifically deterministic TMs, since non-deterministic ones run uber fast (1. Read Input and verify it is of the correct type 2. Ask an oracle for an answer 3. Decide what that answer means and return). Be careful with step one, it's often written off, but checking input for validity sometimes takes a little time.
Ok, then you go on about how the term input is sometimes loose. Then ending with:
"Input" is what you're given, whether you need it or not.
Ok, stop right there. Input is everything... For example the whole array in your example. To read that data in it takes O(n). You can't do things any faster. If you are asked to return the first element of the array so you "read" that and just ignore the rest of the input, fine... but that input still needs to be sent to you.
And then it's easy to think of problems whose algorithms run in time smaller than O(n).
Huh? I could have sworn you had the idea and were restating mine back with the last quote - you get all of the input. Keep in mind, pass by reference is just a neat coding trick, somewhere at somepoint in time the input had to be fed into the system - you can't get around that. Sure, it might have been passed to a particular portion using pass by reference, but if you wish to talk about the running time of that portion of code (disregarding the other algorithms you so skillfully coded in the remaining code) you must still take into account the reading of the data into your system. To ignore how the data got onto the system is to not completely discuss the algorithm.
This is a crucial thing, and is often over looked. This is fine for little things like talking about finding the head of a list or something. There we often say the "operation" runs in constant time. But a true algorithm that takes an array as input and returns the head takes O(n) due to the read. It's not too big of an issue here, but when you get into things that need to be encoded in certain ways for the remainder of the algorithm to work, and you think that just encoding into unary takes O(1) time, then you're in for trouble.
Don't confuse operations (portions of an algorithm) and the actual algorithms themselves. An operation can take less than O(n) time, but if you intend to promote that operation to being a stand alone algorithm you need to incorporate reading the input AND if there were previous operations that got the input turned into a particularly useful form. Consider this argument:
Johnny wishes to read find the largest element in an array. He decides to sort the array in desending order and then read the first element. He knows that reading the first element takes O(1) time so he says his algorithm runs in constant time. Bzzzzt, wrong. He only looked at an operation and then scaled that to the entire algorithm. Ignoring the fact that it's faster to do this without sorting and continue with Johnny's plan we need to look at previous sub-algorithmic operations and account for the reading in of the entire array. The reading alone took O(n) and the sorting took more (hopefully he's smart enough to use a decent sorting algorithm, but that's not the point - we don't need to be tight about the bounds of his sort for this discussion). Disregarding the sorting but keeping the reading we are already up to O(n).
Similar to analysis algorithms (sorting, finding stuff, etc...) we have generation algorithms such as producing n Fibonacci numbers. Here I hope we have less things to argue about since how can you possibly generate n numbers without at least "touching" those n numbers?
I don't think this quite gets the point across that you want it to, "I'm just a theta(n) person in a theta(log n) world." would work better;)
I'm not so sure you get the point I'm trying to make... Can you ever have an alg. that runs in less time than it takes to read in the entire input? I'm trying to make a statment about difficult demands placed by the world and what I think of my own abilities to keep going at the real physical limit, but it just doesn't match the expectations of the world.
I'm not saying I'm asymptotically similar to something - I'm just talking in the worst case that I'm bounded. I feel the world wants things done in an unrealistic time (in the worst case) and that I just can't seem to provide that...
Isn't it more like steganography? I mean, ok, so we can encrypt the message you store using steg. but are we confusing the two?
You can set the messages allow/not allow per each journal. You can set the default option in your preferences... should you ever want to actually go and let everyone talk about it.
You know... your write a lot of interesting things in your journal - why don't you ever allow comments so we could have a discussion about the topics you present?
If you are going to learn to program (and in today's economy, I actually don't recommend that) please steer clear of MIT.
Maybe I'm unique in my feelings about SE and programming, but I feel software engineering and programming to be quite different. I feel they are similar to a mechanical engineer and a machinist. The ME designs things, uses their knowledge of how things work (limitations of physical media [strength, size, weight/mass], timing of things, etc...) to design something. This design is then turned over to machinst, who although is skilled in their trade at making designs reality, does not (IMHO) add much to the product other than just making it. Don't get me wrong coders and machinists are highly skilled people and don't just walk in off the street. But, machinists who design do not always get the greatest of results - they are approaching the system from a completely different angle. Similarly coders who design (without formal design input, i.e. they were just young code monkeys) do not always make the best design of a system. Granted, with experience a coder will get to see many different designs and (through the likely maintainence phase) see how these designs worked - then this coder would work well as an engineer.
So, to take my approach and your input and put them together and that just makes the MIT course on software engineering sound better. If you want to have a good designer do not corrupt their mind too much with code (they do need to experience it to see how their cog fits into the system), and if you want a great coder do not bog them down with waterfall model, OO message passing, and other fundamental SE things (they do need to experience it to see how their cog fits into the system).
Nothing better than "Ernest goes to camp" on an IMAX screen.
If there are three lines:
1. Ernest goest to camp IMAX Movie
2. Dude, where's my car IMAX Movie
3. Slow painful death involving hideous torture locked in a room with Martha Stewart, Carrot Top, and Anna Nicole Smith.
Which would you choose?
I wonder if I'll have the same credit card numbers in 15 years.
My CC company tends to send me a new one every few years (right before the old one expires) with a new number. When does your card expire? What does your CC company do around that time if it doesn't send you a new number?
Start with _The Art of Computer Programming_.
Here here!! I'm with you all the way on that vote. But, if you can't jump right in with heavy Knuth, start with Weiss' Data Structures book (in general form and specific coding languages, I reccomend the general) and CLR (Cormen, Leiserson, and Rivest [as in RSA]) book Introduction to Algorithms.
standard Prisoner's Dilemma tests...
I am not a number, I am a free man!
I will not be pushed, filed, stamped, indexed, debriefed or numbered!
By default the Access Point broadcasts the SSID every few seconds...
Can someone then explain to me what is the reason for choosing a secure SSID?
Well, if you name yours "company name" and you happen to work for Company Name then it's kind of obvious whose network you have. Now, this issue isn't so important when you have a large corporate campus and you have to be in the parking lot just to get reception "gee, I wonder whose network this is???" But it makes a lot of sense in a shared environment or in office space in urban environments. Chances are by doing some range poking you can narrow down the broadcast field where you're catching an SSID and possibly locate the physical location of the box, but it's just another layer to security. As is often promoted, layering security is better than just one this-had-better-hold form of security -- it often means you can detect intrusions at less vital areas and it often means those inside with proper access aren't working in some soft gooy center where it's easy to gain access throughout.
With the lack of security people working for the government, the cons serve as a recruitment rich environment. Problem is, they won't hire people with a record usually.
Their other problem is they pay so low. I don't have a record, I have a MS degree in CS focusing on crypto and other security items and the best pay from the NSA would still force me to live out of my car.
Could you please elaborate on that for me? I always though NTM's (non-determinstic Turing Machines) were so powerful since they always made the "right" decision and didn't need luck or a specific rule set, they just non-determinstically chose the right path.
If you have a network that is just sending packets correctly with out decisions then all the better and we should take it on tour. Maybe, however you're refering to the complete broadcast mentality that packets aren't sent to specific hosts as required but to all hosts since this is how non-determinism is typically simulated, but simulated non-determinism and true non-determinism are a tad different.
Maybe it's just that I don't really know a lot of networking theory, but that term just sort of jumped out at me. I've often equated non-determinism with magic...