Dude, you are so confused it isn't even funny. The early experiments in nuclear propulsion for flight were done by a company that basically loaded a reactor on board, flew it around, took some radiation readings, then proclaimed that nuclear flight needs "men over birthing age". (A really stupid statement if I ever heard one.)
After that, Project Pluto was commissioned as a nuclear bomber. Since the point was maximum destruction to the target area, the reactor was completely unshielded. It would still drop its bombs, but its unshielded nature would be great for added death and destruction. And since it used air and nuclear fission for fuel, they could fly it around enemy territory for months after the bombs were dropped. The project was dropped after ICBMs were shown to be a better near term solution. There weren't a whole lot of tears shed either, since many considered the project's goals a bit sadistic.
In the 60's, serious uses for nuclear propulsion were considered. The two that received the most funding and research were Orion (which had a built in radiation shield by the nature of its design) and NERVA (which was looked at for the upper stages of a moon mission, where the thrust to weight ratio didn't matter quite as much). While both were tested in a reasonable and safe manner, neither actually flew. The reason was that chemical propulsion was already more advanced and would be ready sooner than nuclear solutions. Thus the Saturn V was built for the moon mission.
After the Saturn V was finished, Von Braun began looking forward to exploring the rest of space. He was shown the "joyrider" experiment (a coffee can sized Orion that used conventional explosives) and became a believer. It was his intention to launch an Orion into LEO on top of a Saturn V. Once in space, the Orion could use its nuclear pulse drive to cruise the solar system.
Unfortunately, the US government had other plans. Since the Russians were defeated in the moon race, the US made quiet plans to decommission our remaining arsenal of super-rockets. The space program was scaled back to only handle comsat and military launches. Von Braun strongly disagreed with the government over this point, and eventually left to found the National Space Institute (later the National Space Society). Sadly, he contracted cancer and died in 1977. And that pretty much ended the golden age of space exploration.
The end result is that we have more designs for nuclear propulsion than we know what to do with. Yet not one of those designs has ever been flown, or will be flown, until someone says, "let's go explore!"
Most people just don't realize that we do have the technology to travel the solar system. "We can barely get to LEO!" they say. Too bad no one told them what we actually have to put in LEO. Space travelers live and die by the amount of energy they have available. Nuclear fission provides plenty.
BTW, check out the multimedia section over at Nuclear Space. They have the footage of the Orion joyrider, and the NERVA engine tests.
I think what Bush has in mind is nuclear propulsion. Various tree hugging organizations will do whatever they can to stop the launch of a nuclear craft from Earth, but they can't say anything if it's launched from the moon. The primary advantage of a nuclear craft is the surplus of energy. No matter your orbital inclination, you still have enough power for a short (3-8 months depending on the craft) flight to Mars. Of course, some types of craft could be lowered into the gravity well and launched on a more normal trajectory. However, if Bush is considering something extremely powerful like an Orion, he's got to launch it from high orbit. Otherwise the EMP could wreak havoc with our orbital infrastructure.
Some excellent engine choices from low to high:
NERVA - 800-1000 Isp Gas Core Nuclear Rocket - 2000-5000 Isp Nuclear Salt Water Rocket - 4500-10000 Isp Orion - 10000-100000 Isp M2P2 Orion - >10000 ???
Orions are particularly interesting because of their ability to scale, and be made of traditional building materials instead of composites. (read: Steel) Since the efficiency of Orions climb as the size of the craft does (Thermonuclear H-Bombs give a better bang for the same mass as an Atomic warhead). The largest Orion calculated possible with 1960's technology is 8 million tons. A moving city in space!
I'm pretty sure that Mandrake is using the wrapper for the NTFS.sys driver. Read and write work because it's real windows code running. I don't think you can format however.
n = number of items in list m = maximum number of collisions
thus:
O(1 + m)
Thus if m = 2:
O(1 + 2) O(3)
Perhaps I'm getting it wrong, but I do believe that's a valid solution.
Doh! I remember, now. O(n) ignores constants. Thus O(n) = f(n) = n + n2 + 1 would equals n2, but O(n) = f(n) = 1 + 2 + 3 would be equivalent to O(1) since none of them grow. Thus the hashtable equation of f(n) = 1 + m = O(1,m) = O(m). What I meant to say is to only allow O(m) to reach 2 or 3 before you rehash.
Okay, I suppose I've said something stupid for today. Time for me to rest.:-)
Thanks for the links, BTW. And no, references and pointers are quite different. If I get the time I'll dig up an old discussion I had on it.
I also think that Java is a first rate language. However, I think his point is that schools today are churning out "programmers" for whatever the popular language of the day is. They started with Visual Basic for awhile, but when Java became popular the market ended up being flooded with people who could supposedly program in it. The trouble is that C/C++ at least had a higher barrier to entry. Not just any fool could write a program without crashing their computer. Java's object model and garbage collection take care of all that making it easier on real programmers, and lowering the barrier to entry for programmer-wanna-bes.
You refer to Dr. Dobbs as a "computer science journal,"
No, I referred to it as a promising place to publish. I don't know any good publications any more. It suddenly occurred to me today, that most of the serious journals have disappeared. There used to be journals for every concievable area of comp-sci. They all seem to have died in the 90s.
you claim to have made a "publication" which actually turns out to be a poorly spelled posting on a programming discussion board
Poorly spelled? A little rough, but I could have sworn I checked my spelling. In any case, what I was doing is what comp sci is about. Solving computational problems. In this case, my algorithm was an attempt to solve an inaccuracy in the computation domain of time. The timer that comes with Java (System.currentTimeMillis()) is only accurate under Windows to within 10-50ms. My solution was to latch onto the leading edge of the square wave, thus giving the program an accurate amount of time to execute. Previous solutions either tried to guess the appropriate timing, or used methods which produced random results and caused the system clock to drift.
That statement just proved that you have no idea what the O() notation means. Please, take off the teaching cap, you're going to hurt somebody.
*chuckle*
Have you ever coded a hash table? Or understand how they work? A hash table is basically a virtual array of all possible hashes for an object or string. Thus if you were using a 16 bit hash, your hash table would be 65,536 items long. Here's the problem: you don't want a 64K array, and you most certainly don't want a 4 Gig array (32 bit). As a result, a smaller array is chosen and the remainder operator is used to scale the item to the actual table size. This has one unwanted side effect: sometimes the hash items will collide.
Unfortunately, the cost of a rehash (create a larger array where they don't collide and reinsert all the hash table items) is extreme, and should only be done if absolutely necessary. This gave rise to most hash tables being designed with the ability to hold more than one item in a slot. If a collision occurs, multiple items will be stored, and multiple items will be searched during retrieval. Generally it's best to only allow 2 to 3 collisions in a hash. If you start having more collisions on a given hash, it's probably time to rehash the table.
And that sir, is how hash tables can have an O(2) or O(3) worse-case lookup time.
Now here's my challenge to you, sir. Explain the difference between a reference and a pointer. Then we'll see how well you were paying attention in your own comp-sci studies.
And my frustration comes from that gross generalization.
Indeed, it is a gross generalization. Unfortunately, it's pretty much true of most comp-sci majors who's resumes land on my desk. I'll grant you that the good ones may be getting filtered out by the powers that be (sometimes I just want to shoot HR departments).
Here's something I want you to consider. People who truly love a field will tend to attempt to congregate with others who love the field. Thus we both have met here. We might have met over at JavaLobby, or on Usenet. But we met because we like this field. Now the only reason we have met is because the Internet allows us to condense distances. In real life, you will often meet very few people in your area who will share your interest and be proficient in that interest.
I graduated last May, and I know the answer to your question is a) Hash table, and I would have known that when I graduated.
Very good. But then again, I wasn't trying to test you.:-)
A properly deployed hash table has a O(1) search time (That is not to say I would necessarily think a hash table was the best choice to store name value pairs, but it is the fastest).
*teaching cap on*
While a hash table can have an O(1) search time, it is sometimes desirable to accept an O(2) or O(3) search time in exchange for delaying a rehash. Rehashing the table is a very expensive operation and should be avoided if possible.
*teaching cap off*
Sorry, you seem to have triggered my automatic, "how to apply comp-sci to software engineering" response.:-)
Even if my answer to your question is incorrect in your estimation, I clearly learned what all three of those things were in my first year of CS. Any institution that gradauated someone who doesn't know these things should be ashamed, and I just don't buy that they do.
Sadly, they don't. I have to run right now, but suffice it to say that I have hired people before based on their apparent understanding and excellent school references. Unfortunately, sometimes they aren't taught well and sometimes they cheat the system. Finding a way to determine that is still something I'm working on.
If I were given the choice between two people, one who had a Master's in CS, and one who "first got an algorithms book at 10, and really learned CS great on his own," the CS graduate is the clear choice.
Sir, you are a student. How many developers have you actually tried to hire? I've given dozens of interviews, and actually hired several I later came to regret. Trust me. Degrees are not worth anything more than the resume they're listed on.
You paint with a pretty broad brush. Perhaps it's your insecurity at having never earned a degree that causes you to attack the methods of teaching used in higher education. Just because people didn't learn CS "the hard way," (your way) that doesn't mean they aren't learning it, and learning it well.
No, it's honest to God real frustration with the market. I *expect* someone with a comp-sci degree to know what they're doing. (Or at least I used to.) But the waters got really muddy with the Internet boom. Suddenly, a lot of people started showing up with degrees that simply couldn't do their jobs. Now I've pretty much always expected to have to train a graduate. While they should understand theory, they're also going to have to understand things like software maintenance and problem analysis. But they need a foundation in theory to do that.
Perhaps things are really getting better. The economy has forced a collapse of the "dot com supplier" market, and it has been awhile since I've seen someone who was trying to trick people into doing their homework. I'll have to keep my eyes open and maybe form a new opinion.
The first assignment was to write a boolean expression parser in C. The second assignement was to do the same in ML. Then Prolog. My Prolog program was 3 lines long. The C program was much, much longer and much more complicated too.
Sounds like the compiler theory classes. Shouldn't be too much longer until they introduced you to sorting the operators and operands into reverse polish notation. Recursion is a much easier solution, but it's also very important to understand RPN.;-)
Personally, I am self taught in most languages I know. I took CS because I like to program, but I knew what the degree really was. I learned a bunch of techniques for analyzing algorithms and various other language-independant techniques.
Good for you! I hope you make the most of your comp-sci degree. If you pay enough attention, you should be able to pass up 90%+ of the existing developers on the market. It will still be very difficult getting a job in the current economy, but once you have your foot in the door you should be able to go far. Just remember: work smarter, not harder!
See, you really don't know what comp-sci actually is.
I think I may be coming across as incorrect because of the various concepts that get mixed up when referring to comp-sci. Comp-sci is, as you say, an extension of mathematics dealing with computation. Programming is the modern equivalent of a computational machine.
However, when a student finishes comp-sci, they should be capable of one of two things:
1. Using the mathematical concepts they have learned to go into software development. In specific, compilers, operating systems, distributed computing, etc. are all covered by comp-sci degrees. Thus I expect that someone who enters software development should be capable of at least applying the data structures they've learned.
2. Go into mathematical research. Get grants to develop new concepts and algorithms that may be useful to software development, or advance current information theory. (Oh the stories I have about battling information theory, let me tell you. Don't you just hate how making information more compact - even if you make it implied information - makes it no longer compress as well?:p)
My frustration comes from the fact that graduates can do neither. All they *really* want to do is make some instructions execute in order. (Some have some serious problems with that.:-/) They have no appreciation for *using* comp-sci to do their development right. Let's say you ask a typical programmer the following question:
A named property is a name that is associated with some type of information. Most often, named properties are used to store settings by name. For example:
screen-res=1024x768
The part before the '=' sign is the name, while the part after is the value of the property. Access to these properties must be as fast as possible. Which of the following data structures would you use?
a) Hash table b) Linked list c) Binary tree
The answer most commonly received form graduates is, "what are those options?"
Follow me so far? Almost as inexcusable are the types who complain that "object references" are really just a fancy name for pointers. Just like methods are actually just functions. If these kids had half a clue that a function is actually a variation of the "mathematical function", they might better understand what they're doing.
"Hey look! I wrote a C program that writes 0xFFFFFFFF to 0xA000 and a pixel appears on the screen! I found it by randomly writing bits to different points in memory!"
Ah. See, that's *just* before comp-sci really started to go downhill. Many schools at the time were already bowing to the the market demand for C and C++ programmers (not necessarily a bad thing), but it wasn't until 98-99 that the big stink about "programmer shortages" caused schools to start rushing through students.
I know it's hard to believe (seems like yesterday), but it's been about seven years since you graduated. I haven't even been married that long! (5 years):-)
FWIW, I'm starting to wonder if programming and comp-sci should be split at schools. Programmer would be more of a "technical degree", allowing computer science schools to produce tomorrows computer architects and researchers.
You know, all of these arguments have gotten me thinking. Does anyone remember the last time a major mathematical concept was introduced to computer science? The most recent paper I can think of that fits the criteria is probably the one on the Burrows-Wheeler Tranform. Other than people tossing around concepts online and research into encryption, I can't think of a single newer paper.
I did have a new compression algo a few years ago, but I decided not to publish it after I found out that it couldn't do as well as gzip.
There's a good attempt at it here. Granted, it's not so much a true proof as it is an argument against. But that's why they're called theorms. Someone might come along and show it to be wrong or find a loophole.
That being said, most real world algorithms focus on best or common case. Worst case can often hurt (sometimes as bad as O(n2)), but data is usually prearranged in such a way as to allow for much faster sorting than a general algorithm.
Take the statement: "engineering is a form of applied science." and change it to "programming is a form of applied mathematics". Does it make sense?
Engineers have to apply science to make their designs work. Engineers who fail to do so invariably fail in their work. However, an engineer without any intuition will never be able to accomplish a revolutionary engineering feat.
Programmers have to apply mathematics. Programmers who fail to do so invariably fail in their work. However, a programmer without any intuition will never be able to accomplish a revolutionary programming feat.
Can you prove that general sorting cannot be less than O(n log n)? This is fundamental. If you can't do it, you do not know computer science
Yes, I can. And that's my point. I learned how when I was given my first book on data structures. It was a little weird at first, but if you're going to do things right, you have to know the math behind them. In fact, modern computers long ago made me give up the desktop calculator. Trying to develop for the processing power of today requires numbers far beyond what my old desktop calculators could do. It's too bad, because it was so convenient to not have to switch windows. And yes, I'm too cheap to get a decent scientific calculator.:-)
Put out a publication comparing your methods with other known methods.
You mean like this one? Looking back at it, I should have taken the time to clean up the english. I was so excited about my algo, that I just pushed it out.:-)
Keep an eye on Java Developers Journal for an article on logging. They wouldn't let me publish a pure research paper, but I was able to squeeze in a dissertation on using ThreadLocals for multiplexing a stream.
Does anyone know any *good* comp-sci journals? Dr. Dobbs looks promising, but I had already promised an article to JDJ.
got my bachelor's in comp sci from UMass, and our first class covered linked lists in Pascal.
1. When? 2. Some good schools still exist. However, they are few and far between. 3. Assuming you received your degree within the last 5 years, let me ask you this: How many people in your class passed even though they couldn't program their way out of a paper bag?
Yes, I'm frustrated. I frustrated that a comp-sci degree today is so meaningless. As a young adult, I had entered the market expecting that those who had completed their degrees would know far more than I did. While some knew more through experience, most would hack at things until they worked. Despite having degrees, none of the knowledge stuck. By working smarter, it was a very short period of time before I was leading teams of programmers. 50% of my time I would spend educating my team, 50% I would spend on core development while they handled the less tricky areas. (e.g.: I would create core business logic, then let my team develop the GUI and interaction with that logic.)
I have to say though, the hardest thing I ever did was my first project where I was required to direct the developers without writing a single line myself. I think they kind of looked at me like one of their professors. "Why does this fuddy-duddy want it done this way? Wouldn't it be faster and easier to just do it this way?" Of course, there was method to my madness, but it was only shown months later when major changes to the system were reduced to minor changes.:-)
But back on topic. I have no problem with comp-sci degrees or those who obtain them. I have a problem with their devaluation.
Actually, it's a bit more like engineering. There's a scientific aspect to it, but also an artistic aspect. The scientific aspect can tell you how well your algorithm works. The artistic aspect is that deep-down human intuition that develops newer and better algorithms. The artistic side obviously becomes even more prominent when you begin real-world development, since real-world development begins to take into account such concepts as maintainability and adaptability.
Hmmm... seems my weblogs say that people have been checking my links. Now it's just a countdown to those who start throwing around slurs like, "you don't know anything about calculating algorithms to execute at O(n), O(log n), O(1), etc.", "game programming is not real comp-sci!" (tell that to my collision algorithms or research into better timing methods), or "that's just programming, comp-sci is REALLY about...". (hint: it's about something that's just a intangible as code)
You're barking up the wrong tree. I tend to comment on Nuclear Sciences and propulsion as an interested amateur. Software architecture, development, programming, and yes, Computer Sciences are all part of my chosen profession.
You think I don't know comp-sci? Oh dear, we seem to have a pickle here. I must have chosen the wrong profession, because I could have sworn I was leading teams of developers, doing my part to change the fact of Java gaming, helping design better database drivers, competing in competitions to pack the most into 4K, building better tools, and generally spending my time trying to knock some sense into these idiots who didn't pay attention when they were getting their degrees.
I didn't get a degree, but I did take the hard way of learning comp-sci. I spent years of my time studying the various texts and papers that students *should* be studying. Some people complain that, "well you can't be a *true* comp-sci professional because you didn't pay for this piece of paper." I just shake my head at their insecurity and offer to help them solve whatever their current problem is.
There are my credentials. Take them or leave them. My only recommendation is that you don't underestimate what I can do, or what I have done.
Then how the heck do you know what the teachers are teaching?
I check in on the various curriculums every now and then. Some still teach data structures and information theory, but the trend is toward "Learn C++/Java in 30 days" type of books disguised as text books. Even more telling is how many people get a passing grade in comp-sci (Some even get Masters Degrees!) and couldn't explain what a linked list is to save their lives. The usual excuse is, "well, we didn't cover that." (Which of course they did, but the student still somehow got a passing grade.)
I personally thought it was really interesting, and as such I am now a graduate student. I love comp-sci for what it actually is, which is not programming.
Comp-Sci is great. I love the concepts of comp-sci. My mother actually gave me my first book on data structures when I was 10. (Old college textbook.) It's just too bad that comp-sci isn't very well taught anymore. 90% of the current crop of comp-sci students should probably be flunked.
Why am I replying to a troll??? Oh well, I feel better now.
You feel better about yourself because you labeled a valid opinion as a troll? Dude, you need to get out more.
Of course, some readers won't know what functional programming is, or what is special about pure data structures.
Truly sad. I never got a Comp-Sci degree myself, and I know more about procedural, functional and OO data structures than pretty much every comp-sci student I've met. What are they teaching kids these days!? Oh, that's right. Teachers are teaching only what you need to get a job, and students are hacking code they don't understand instead of learning.
You wouldn't by any chance be one of those whack-job Nader supporters, would you?
It amazes me how many people think Plutonium is going to kill people. It's an Alpha emitter for crying out loud. That means that you can hold it in your hand and none of the radiation will penetrate your skin. If I were you, I'd be much more worried about the Uranium, Thorium, Arsenic, Mercury and other chemicals (many radioactive) that are released by coal plants. Not to mention that rockets are composed of many chemicals which are far more dangerous than Plutonium.
No, they run on plutonium, not highly-boiled cabbage and Chicken Tonight(TM).
It was a joke! Plutonium has the atomic symbol of "PU". Thus, "PeeUoo". Ok, it's lame. But it's probably lamer that a site full of geeks didn't get it.
Slashdot Mirror
Dude, you are so confused it isn't even funny. The early experiments in nuclear propulsion for flight were done by a company that basically loaded a reactor on board, flew it around, took some radiation readings, then proclaimed that nuclear flight needs "men over birthing age". (A really stupid statement if I ever heard one.)
After that, Project Pluto was commissioned as a nuclear bomber. Since the point was maximum destruction to the target area, the reactor was completely unshielded. It would still drop its bombs, but its unshielded nature would be great for added death and destruction. And since it used air and nuclear fission for fuel, they could fly it around enemy territory for months after the bombs were dropped. The project was dropped after ICBMs were shown to be a better near term solution. There weren't a whole lot of tears shed either, since many considered the project's goals a bit sadistic.
In the 60's, serious uses for nuclear propulsion were considered. The two that received the most funding and research were Orion (which had a built in radiation shield by the nature of its design) and NERVA (which was looked at for the upper stages of a moon mission, where the thrust to weight ratio didn't matter quite as much). While both were tested in a reasonable and safe manner, neither actually flew. The reason was that chemical propulsion was already more advanced and would be ready sooner than nuclear solutions. Thus the Saturn V was built for the moon mission.
After the Saturn V was finished, Von Braun began looking forward to exploring the rest of space. He was shown the "joyrider" experiment (a coffee can sized Orion that used conventional explosives) and became a believer. It was his intention to launch an Orion into LEO on top of a Saturn V. Once in space, the Orion could use its nuclear pulse drive to cruise the solar system.
Unfortunately, the US government had other plans. Since the Russians were defeated in the moon race, the US made quiet plans to decommission our remaining arsenal of super-rockets. The space program was scaled back to only handle comsat and military launches. Von Braun strongly disagreed with the government over this point, and eventually left to found the National Space Institute (later the National Space Society). Sadly, he contracted cancer and died in 1977. And that pretty much ended the golden age of space exploration.
The end result is that we have more designs for nuclear propulsion than we know what to do with. Yet not one of those designs has ever been flown, or will be flown, until someone says, "let's go explore!"
Most people just don't realize that we do have the technology to travel the solar system. "We can barely get to LEO!" they say. Too bad no one told them what we actually have to put in LEO. Space travelers live and die by the amount of energy they have available. Nuclear fission provides plenty.
BTW, check out the multimedia section over at Nuclear Space. They have the footage of the Orion joyrider, and the NERVA engine tests.
I think what Bush has in mind is nuclear propulsion. Various tree hugging organizations will do whatever they can to stop the launch of a nuclear craft from Earth, but they can't say anything if it's launched from the moon. The primary advantage of a nuclear craft is the surplus of energy. No matter your orbital inclination, you still have enough power for a short (3-8 months depending on the craft) flight to Mars. Of course, some types of craft could be lowered into the gravity well and launched on a more normal trajectory. However, if Bush is considering something extremely powerful like an Orion, he's got to launch it from high orbit. Otherwise the EMP could wreak havoc with our orbital infrastructure.
Some excellent engine choices from low to high:
NERVA - 800-1000 Isp
Gas Core Nuclear Rocket - 2000-5000 Isp
Nuclear Salt Water Rocket - 4500-10000 Isp
Orion - 10000-100000 Isp
M2P2 Orion - >10000 ???
Orions are particularly interesting because of their ability to scale, and be made of traditional building materials instead of composites. (read: Steel) Since the efficiency of Orions climb as the size of the craft does (Thermonuclear H-Bombs give a better bang for the same mass as an Atomic warhead). The largest Orion calculated possible with 1960's technology is 8 million tons. A moving city in space!
I'm pretty sure that Mandrake is using the wrapper for the NTFS.sys driver. Read and write work because it's real windows code running. I don't think you can format however.
Ack, my math is rusty. But IIRC:
:-)
Standard hash table:
O(1)
Addition of an array at each hash:
n = number of items in list
m = maximum number of collisions
thus:
O(1 + m)
Thus if m = 2:
O(1 + 2)
O(3)
Perhaps I'm getting it wrong, but I do believe that's a valid solution.
Doh! I remember, now. O(n) ignores constants. Thus O(n) = f(n) = n + n2 + 1 would equals n2, but O(n) = f(n) = 1 + 2 + 3 would be equivalent to O(1) since none of them grow. Thus the hashtable equation of f(n) = 1 + m = O(1,m) = O(m). What I meant to say is to only allow O(m) to reach 2 or 3 before you rehash.
Okay, I suppose I've said something stupid for today. Time for me to rest.
Thanks for the links, BTW. And no, references and pointers are quite different. If I get the time I'll dig up an old discussion I had on it.
I also think that Java is a first rate language. However, I think his point is that schools today are churning out "programmers" for whatever the popular language of the day is. They started with Visual Basic for awhile, but when Java became popular the market ended up being flooded with people who could supposedly program in it. The trouble is that C/C++ at least had a higher barrier to entry. Not just any fool could write a program without crashing their computer. Java's object model and garbage collection take care of all that making it easier on real programmers, and lowering the barrier to entry for programmer-wanna-bes.
You refer to Dr. Dobbs as a "computer science journal,"
No, I referred to it as a promising place to publish. I don't know any good publications any more. It suddenly occurred to me today, that most of the serious journals have disappeared. There used to be journals for every concievable area of comp-sci. They all seem to have died in the 90s.
you claim to have made a "publication" which actually turns out to be a poorly spelled posting on a programming discussion board
Poorly spelled? A little rough, but I could have sworn I checked my spelling. In any case, what I was doing is what comp sci is about. Solving computational problems. In this case, my algorithm was an attempt to solve an inaccuracy in the computation domain of time. The timer that comes with Java (System.currentTimeMillis()) is only accurate under Windows to within 10-50ms. My solution was to latch onto the leading edge of the square wave, thus giving the program an accurate amount of time to execute. Previous solutions either tried to guess the appropriate timing, or used methods which produced random results and caused the system clock to drift.
That statement just proved that you have no idea what the O() notation means. Please, take off the teaching cap, you're going to hurt somebody.
*chuckle*
Have you ever coded a hash table? Or understand how they work? A hash table is basically a virtual array of all possible hashes for an object or string. Thus if you were using a 16 bit hash, your hash table would be 65,536 items long. Here's the problem: you don't want a 64K array, and you most certainly don't want a 4 Gig array (32 bit). As a result, a smaller array is chosen and the remainder operator is used to scale the item to the actual table size. This has one unwanted side effect: sometimes the hash items will collide.
Unfortunately, the cost of a rehash (create a larger array where they don't collide and reinsert all the hash table items) is extreme, and should only be done if absolutely necessary. This gave rise to most hash tables being designed with the ability to hold more than one item in a slot. If a collision occurs, multiple items will be stored, and multiple items will be searched during retrieval. Generally it's best to only allow 2 to 3 collisions in a hash. If you start having more collisions on a given hash, it's probably time to rehash the table.
And that sir, is how hash tables can have an O(2) or O(3) worse-case lookup time.
Now here's my challenge to you, sir. Explain the difference between a reference and a pointer. Then we'll see how well you were paying attention in your own comp-sci studies.
And my frustration comes from that gross generalization.
:-)
:-)
Indeed, it is a gross generalization. Unfortunately, it's pretty much true of most comp-sci majors who's resumes land on my desk. I'll grant you that the good ones may be getting filtered out by the powers that be (sometimes I just want to shoot HR departments).
Here's something I want you to consider. People who truly love a field will tend to attempt to congregate with others who love the field. Thus we both have met here. We might have met over at JavaLobby, or on Usenet. But we met because we like this field. Now the only reason we have met is because the Internet allows us to condense distances. In real life, you will often meet very few people in your area who will share your interest and be proficient in that interest.
I graduated last May, and I know the answer to your question is a) Hash table, and I would have known that when I graduated.
Very good. But then again, I wasn't trying to test you.
A properly deployed hash table has a O(1) search time (That is not to say I would necessarily think a hash table was the best choice to store name value pairs, but it is the fastest).
*teaching cap on*
While a hash table can have an O(1) search time, it is sometimes desirable to accept an O(2) or O(3) search time in exchange for delaying a rehash. Rehashing the table is a very expensive operation and should be avoided if possible.
*teaching cap off*
Sorry, you seem to have triggered my automatic, "how to apply comp-sci to software engineering" response.
Even if my answer to your question is incorrect in your estimation, I clearly learned what all three of those things were in my first year of CS. Any institution that gradauated someone who doesn't know these things should be ashamed, and I just don't buy that they do.
Sadly, they don't. I have to run right now, but suffice it to say that I have hired people before based on their apparent understanding and excellent school references. Unfortunately, sometimes they aren't taught well and sometimes they cheat the system. Finding a way to determine that is still something I'm working on.
If I were given the choice between two people, one who had a Master's in CS, and one who "first got an algorithms book at 10, and really learned CS great on his own," the CS graduate is the clear choice.
Sir, you are a student. How many developers have you actually tried to hire? I've given dozens of interviews, and actually hired several I later came to regret. Trust me. Degrees are not worth anything more than the resume they're listed on.
You paint with a pretty broad brush. Perhaps it's your insecurity at having never earned a degree that causes you to attack the methods of teaching used in higher education. Just because people didn't learn CS "the hard way," (your way) that doesn't mean they aren't learning it, and learning it well.
No, it's honest to God real frustration with the market. I *expect* someone with a comp-sci degree to know what they're doing. (Or at least I used to.) But the waters got really muddy with the Internet boom. Suddenly, a lot of people started showing up with degrees that simply couldn't do their jobs. Now I've pretty much always expected to have to train a graduate. While they should understand theory, they're also going to have to understand things like software maintenance and problem analysis. But they need a foundation in theory to do that.
Perhaps things are really getting better. The economy has forced a collapse of the "dot com supplier" market, and it has been awhile since I've seen someone who was trying to trick people into doing their homework. I'll have to keep my eyes open and maybe form a new opinion.
The first assignment was to write a boolean expression parser in C. The second assignement was to do the same in ML. Then Prolog. My Prolog program was 3 lines long. The C program was much, much longer and much more complicated too.
Sounds like the compiler theory classes. Shouldn't be too much longer until they introduced you to sorting the operators and operands into reverse polish notation. Recursion is a much easier solution, but it's also very important to understand RPN.
Personally, I am self taught in most languages I know. I took CS because I like to program, but I knew what the degree really was. I learned a bunch of techniques for analyzing algorithms and various other language-independant techniques.
Good for you! I hope you make the most of your comp-sci degree. If you pay enough attention, you should be able to pass up 90%+ of the existing developers on the market. It will still be very difficult getting a job in the current economy, but once you have your foot in the door you should be able to go far. Just remember: work smarter, not harder!
See, you really don't know what comp-sci actually is.
:p)
:-/) They have no appreciation for *using* comp-sci to do their development right. Let's say you ask a typical programmer the following question:
I think I may be coming across as incorrect because of the various concepts that get mixed up when referring to comp-sci. Comp-sci is, as you say, an extension of mathematics dealing with computation. Programming is the modern equivalent of a computational machine.
However, when a student finishes comp-sci, they should be capable of one of two things:
1. Using the mathematical concepts they have learned to go into software development. In specific, compilers, operating systems, distributed computing, etc. are all covered by comp-sci degrees. Thus I expect that someone who enters software development should be capable of at least applying the data structures they've learned.
2. Go into mathematical research. Get grants to develop new concepts and algorithms that may be useful to software development, or advance current information theory. (Oh the stories I have about battling information theory, let me tell you. Don't you just hate how making information more compact - even if you make it implied information - makes it no longer compress as well?
My frustration comes from the fact that graduates can do neither. All they *really* want to do is make some instructions execute in order. (Some have some serious problems with that.
A named property is a name that is associated with some type of information. Most often, named properties are used to store settings by name. For example:
screen-res=1024x768
The part before the '=' sign is the name, while the part after is the value of the property. Access to these properties must be as fast as possible. Which of the following data structures would you use?
a) Hash table
b) Linked list
c) Binary tree
The answer most commonly received form graduates is, "what are those options?"
Follow me so far? Almost as inexcusable are the types who complain that "object references" are really just a fancy name for pointers. Just like methods are actually just functions. If these kids had half a clue that a function is actually a variation of the "mathematical function", they might better understand what they're doing.
"Hey look! I wrote a C program that writes 0xFFFFFFFF to 0xA000 and a pixel appears on the screen! I found it by randomly writing bits to different points in memory!"
*sigh*
Graduated '97.
:-)
Ah. See, that's *just* before comp-sci really started to go downhill. Many schools at the time were already bowing to the the market demand for C and C++ programmers (not necessarily a bad thing), but it wasn't until 98-99 that the big stink about "programmer shortages" caused schools to start rushing through students.
I know it's hard to believe (seems like yesterday), but it's been about seven years since you graduated. I haven't even been married that long! (5 years)
FWIW, I'm starting to wonder if programming and comp-sci should be split at schools. Programmer would be more of a "technical degree", allowing computer science schools to produce tomorrows computer architects and researchers.
You know, all of these arguments have gotten me thinking. Does anyone remember the last time a major mathematical concept was introduced to computer science? The most recent paper I can think of that fits the criteria is probably the one on the Burrows-Wheeler Tranform. Other than people tossing around concepts online and research into encryption, I can't think of a single newer paper.
I did have a new compression algo a few years ago, but I decided not to publish it after I found out that it couldn't do as well as gzip.
There's a good attempt at it here. Granted, it's not so much a true proof as it is an argument against. But that's why they're called theorms. Someone might come along and show it to be wrong or find a loophole.
That being said, most real world algorithms focus on best or common case. Worst case can often hurt (sometimes as bad as O(n2)), but data is usually prearranged in such a way as to allow for much faster sorting than a general algorithm.
Take the statement: "engineering is a form of applied science." and change it to "programming is a form of applied mathematics". Does it make sense?
Engineers have to apply science to make their designs work. Engineers who fail to do so invariably fail in their work. However, an engineer without any intuition will never be able to accomplish a revolutionary engineering feat.
Programmers have to apply mathematics. Programmers who fail to do so invariably fail in their work. However, a programmer without any intuition will never be able to accomplish a revolutionary programming feat.
Can you prove that general sorting cannot be less than O(n log n)? This is fundamental. If you can't do it, you do not know computer science
:-)
:-)
Yes, I can. And that's my point. I learned how when I was given my first book on data structures. It was a little weird at first, but if you're going to do things right, you have to know the math behind them. In fact, modern computers long ago made me give up the desktop calculator. Trying to develop for the processing power of today requires numbers far beyond what my old desktop calculators could do. It's too bad, because it was so convenient to not have to switch windows. And yes, I'm too cheap to get a decent scientific calculator.
Put out a publication comparing your methods with other known methods.
You mean like this one? Looking back at it, I should have taken the time to clean up the english. I was so excited about my algo, that I just pushed it out.
Keep an eye on Java Developers Journal for an article on logging. They wouldn't let me publish a pure research paper, but I was able to squeeze in a dissertation on using ThreadLocals for multiplexing a stream.
Does anyone know any *good* comp-sci journals? Dr. Dobbs looks promising, but I had already promised an article to JDJ.
got my bachelor's in comp sci from UMass, and our first class covered linked lists in Pascal.
:-)
1. When?
2. Some good schools still exist. However, they are few and far between.
3. Assuming you received your degree within the last 5 years, let me ask you this: How many people in your class passed even though they couldn't program their way out of a paper bag?
Yes, I'm frustrated. I frustrated that a comp-sci degree today is so meaningless. As a young adult, I had entered the market expecting that those who had completed their degrees would know far more than I did. While some knew more through experience, most would hack at things until they worked. Despite having degrees, none of the knowledge stuck. By working smarter, it was a very short period of time before I was leading teams of programmers. 50% of my time I would spend educating my team, 50% I would spend on core development while they handled the less tricky areas. (e.g.: I would create core business logic, then let my team develop the GUI and interaction with that logic.)
I have to say though, the hardest thing I ever did was my first project where I was required to direct the developers without writing a single line myself. I think they kind of looked at me like one of their professors. "Why does this fuddy-duddy want it done this way? Wouldn't it be faster and easier to just do it this way?" Of course, there was method to my madness, but it was only shown months later when major changes to the system were reduced to minor changes.
But back on topic. I have no problem with comp-sci degrees or those who obtain them. I have a problem with their devaluation.
Actually, it's a bit more like engineering. There's a scientific aspect to it, but also an artistic aspect. The scientific aspect can tell you how well your algorithm works. The artistic aspect is that deep-down human intuition that develops newer and better algorithms. The artistic side obviously becomes even more prominent when you begin real-world development, since real-world development begins to take into account such concepts as maintainability and adaptability.
Hmmm... seems my weblogs say that people have been checking my links. Now it's just a countdown to those who start throwing around slurs like, "you don't know anything about calculating algorithms to execute at O(n), O(log n), O(1), etc.", "game programming is not real comp-sci!" (tell that to my collision algorithms or research into better timing methods), or "that's just programming, comp-sci is REALLY about...". (hint: it's about something that's just a intangible as code)
3... 2... 1...
You're barking up the wrong tree. I tend to comment on Nuclear Sciences and propulsion as an interested amateur. Software architecture, development, programming, and yes, Computer Sciences are all part of my chosen profession.
You think I don't know comp-sci? Oh dear, we seem to have a pickle here. I must have chosen the wrong profession, because I could have sworn I was leading teams of developers, doing my part to change the fact of Java gaming, helping design better database drivers, competing in competitions to pack the most into 4K, building better tools, and generally spending my time trying to knock some sense into these idiots who didn't pay attention when they were getting their degrees.
I didn't get a degree, but I did take the hard way of learning comp-sci. I spent years of my time studying the various texts and papers that students *should* be studying. Some people complain that, "well you can't be a *true* comp-sci professional because you didn't pay for this piece of paper." I just shake my head at their insecurity and offer to help them solve whatever their current problem is.
There are my credentials. Take them or leave them. My only recommendation is that you don't underestimate what I can do, or what I have done.
Then how the heck do you know what the teachers are teaching?
I check in on the various curriculums every now and then. Some still teach data structures and information theory, but the trend is toward "Learn C++/Java in 30 days" type of books disguised as text books. Even more telling is how many people get a passing grade in comp-sci (Some even get Masters Degrees!) and couldn't explain what a linked list is to save their lives. The usual excuse is, "well, we didn't cover that." (Which of course they did, but the student still somehow got a passing grade.)
I personally thought it was really interesting, and as such I am now a graduate student. I love comp-sci for what it actually is, which is not programming.
Comp-Sci is great. I love the concepts of comp-sci. My mother actually gave me my first book on data structures when I was 10. (Old college textbook.) It's just too bad that comp-sci isn't very well taught anymore. 90% of the current crop of comp-sci students should probably be flunked.
Why am I replying to a troll??? Oh well, I feel better now.
You feel better about yourself because you labeled a valid opinion as a troll? Dude, you need to get out more.
Of course, some readers won't know what functional programming is, or what is special about pure data structures.
Truly sad. I never got a Comp-Sci degree myself, and I know more about procedural, functional and OO data structures than pretty much every comp-sci student I've met. What are they teaching kids these days!? Oh, that's right. Teachers are teaching only what you need to get a job, and students are hacking code they don't understand instead of learning.
Disgusting.
You wouldn't by any chance be one of those whack-job Nader supporters, would you?
It amazes me how many people think Plutonium is going to kill people. It's an Alpha emitter for crying out loud. That means that you can hold it in your hand and none of the radiation will penetrate your skin. If I were you, I'd be much more worried about the Uranium, Thorium, Arsenic, Mercury and other chemicals (many radioactive) that are released by coal plants. Not to mention that rockets are composed of many chemicals which are far more dangerous than Plutonium.
No, they run on plutonium, not highly-boiled cabbage and Chicken Tonight(TM).
It was a joke! Plutonium has the atomic symbol of "PU". Thus, "PeeUoo". Ok, it's lame. But it's probably lamer that a site full of geeks didn't get it.
What are you talking about?