What's more concerning, if anything, is that all of the illustrative solutions are basically brute force approaches.
Really? For practical programming, when I need an algorithm to solve a problem like these, I go in order of preference:
1. Find a library that does it.
2. Steal some source code that does it.
3. Implement obvious algorithm (greedy/exhaustive)
4. Look in CLR
5. Ask a friend
Last resort. Think up clever algorithm.
I'd guess that most coders spend 1-10% of their work time doing the type of programming in this contest. But I'd bet the contest winners are pretty smart and I think most of them would make great programmers after a year of work experience.
That hard problem is more interesting. Isn't it NP-hard? If you can solve this problem, I think I can solve MAX-CLIQUE. Use the graph as the animal incompatibility graph, set all animal weights to 1 and the boat capacity really big. The solution to the animals problem is the solution to MAX-CLIQUE.
I read the problem too quickly so I just thought, "Oh, Huffmann encoding."
The key to this problem is that in the optimal tree, the subtrees of the root are optimal. To solve, you can consider each element in turn as a candidate root, and then compute the optimal left and right subtrees. Pick the best candidate.
To turn it into dynamic programming, start by computing all N optimal 1-element trees, then all N-1 2-adjacent-element trees, and so on: O(N^2). The solution in the article is a bit different because the problem only wants the optimal cost.
Yes, that's a problem. For the reasons you give, List is not a subtype of List. They included a feature called "raw types" to allow interfacing with legacy code. The raw type would be List, so you can do this:
List<Foo> list = new List<Foo>; List haha = list; haha.add("haha!");// unchecked warning
The compiler will generate an "unchecked warning" because List.add and List.add have different argument types. GJ also has a way of retrofitting existing classes to make them work like generics, which they've done for the standard library, but I'm not sure this is going to be in Java 1.5.
I love python myself, but it's not the best language for every project. Python progs are 10-20x slower than equivalent C++ progs. Java is only 2-5x slower. Also, in a medium or bigger project, I find type checking to be pretty helpful in catching bugs.
Pretty close. For "list.add(myFoo)", it won't add a cast, because the type checker verifies that myFoo is-a Foo. The compiler will also add "bridge methods" for classes that implement a parameterized interface:
class Byte implements Comparable<Byte> { ... public int compareTo(Byte obj) { return this.value - obj.value); } }
The method compareTo is supposed to override the method in Comparable, which takes an object. So they create a bridge method that overrides it normally:
class Byte implements Comparable<Byte> { ... public int compareTo(Byte obj) { return this.value - obj.value); } public int compareTo(Object obj) { return this.compareTo((Byte) obj); } }
Of course the Free Market Fairy won't wave her magic wand and put broadband in every home. She's too smart for that. She puts broadband in just the "right" number of homes to maximize overall welfare. I get the idea that the internet is more popular in Korea, which is part of the reason they have more and cheaper (economies of scale?). Btw, the internet is a consumer product in Korea, although the govt built the first networks (same as US), and in the US, companies develop new consumer products all the time expecting profits to be a few years off (same as Korea). And all modern, democratized nations that aren't named Luxembourg have sucky economies compared to the US, so I don't see any reason to imitate them.
We could be suffering from a market failure, though. There is competition between DSL, Cable, and satellite (do those still exist?) but maybe there isn't enough. Or, maybe a big network upgrade is worth it in terms of expected profits, but the risk is too big for all existing companies. OTOH, maybe there are regulations blocking growth in this area. I'd like to read some analyses of these issues before forming an opinion, myself.
If OTS business software takes over the world, I predict IS programmers will split into two groups. One will work to install and maintain OTS software. They won't spend too much time coding, some of them will write extension modules and customizations. The other group will have the job of integrating disparate OTS systems. There are, of course, commercial vendors working on that problem, but I think it will be a while before they solve it.
Until something entirely new and different comes around, computing needs are well understood....a lot of those retail versions are feature complete - what could MS Word 2010 possibly offer us in terms of features? In reality, is there anything you need from a word processor that WordStar in 1985 didn't offer?
Interesting. My attitude is completely the opposite. "All software sucks." People gripe about PowerPoint all the time. Word sucks too. I'd like to be able to use it, but it doesn't work with CVS and the equation editor doesn't typeset things very well. I think the problem is not that applications work too well, but that it's too expensive to develop better ones. If development costs go down, we could see a lot of growth in specialized software.
Also, I think there's still a lot of growth in embedded computers, which will really take off once people figure out what to do with deck- and dime-sized distributed devices.
Because it's research. Researchers need to be able to implement exactly the features they want to study, not what the developers and user base of an OSS project want. It's about the ideas, not the code. But I'm sure the authors would be pleased if JLint used their ideas.
The paper explains the rationale for each check. For "read of uninitialized field in constructor", the idea is that since the field has the default value, it makes no sense to read it, so the code is at best useless. In another post I think you said it was a static field, so it looks like you've discovered a bug in FindBugs.
Isn't the real difference that ML uses type inference while Eiffel uses declarations? If you wrote ML with type declarations for everything, would it be pretty much like Eiffel?
Diamond wondered what might have been going through the mind of the Easter Islander who felled the last tree on the island. He guessed that it might just have been thoughts that would resonate today: "Hey, keeping my job is more important than preserving the environment".
Bah. The guy probably hadn't eaten in 3 days and was thinking "If I don't cut down this tree for a fishing boat, I'll surely die."
Keep in mind that academic researchers create ideas, algorithms, and prototypes, but products only occasionally. Someone still has to write the code for new products. And one of the reasons computer technology is advancing so quickly is that you can put out a low-quality piece of software, and thousands of people will willingly download it and test it for you. Regulation will absolutely kill innovation.
Slashdot Mirror
Really? For practical programming, when I need an algorithm to solve a problem like these, I go in order of preference:
1. Find a library that does it.
2. Steal some source code that does it.
3. Implement obvious algorithm (greedy/exhaustive)
4. Look in CLR
5. Ask a friend
Last resort. Think up clever algorithm.
I'd guess that most coders spend 1-10% of their work time doing the type of programming in this contest. But I'd bet the contest winners are pretty smart and I think most of them would make great programmers after a year of work experience.
That hard problem is more interesting. Isn't it NP-hard? If you can solve this problem, I think I can solve MAX-CLIQUE. Use the graph as the animal incompatibility graph, set all animal weights to 1 and the boat capacity really big. The solution to the animals problem is the solution to MAX-CLIQUE.
The key to this problem is that in the optimal tree, the subtrees of the root are optimal. To solve, you can consider each element in turn as a candidate root, and then compute the optimal left and right subtrees. Pick the best candidate.
To turn it into dynamic programming, start by computing all N optimal 1-element trees, then all N-1 2-adjacent-element trees, and so on: O(N^2). The solution in the article is a bit different because the problem only wants the optimal cost.
The compiler will generate an "unchecked warning" because List.add and List.add have different argument types. GJ also has a way of retrofitting existing classes to make them work like generics, which they've done for the standard library, but I'm not sure this is going to be in Java 1.5.
I love python myself, but it's not the best language for every project. Python progs are 10-20x slower than equivalent C++ progs. Java is only 2-5x slower. Also, in a medium or bigger project, I find type checking to be pretty helpful in catching bugs.
The method compareTo is supposed to override the method in Comparable, which takes an object. So they create a bridge method that overrides it normally:
We could be suffering from a market failure, though. There is competition between DSL, Cable, and satellite (do those still exist?) but maybe there isn't enough. Or, maybe a big network upgrade is worth it in terms of expected profits, but the risk is too big for all existing companies. OTOH, maybe there are regulations blocking growth in this area. I'd like to read some analyses of these issues before forming an opinion, myself.
If OTS business software takes over the world, I predict IS programmers will split into two groups. One will work to install and maintain OTS software. They won't spend too much time coding, some of them will write extension modules and customizations. The other group will have the job of integrating disparate OTS systems. There are, of course, commercial vendors working on that problem, but I think it will be a while before they solve it.
Interesting. My attitude is completely the opposite. "All software sucks." People gripe about PowerPoint all the time. Word sucks too. I'd like to be able to use it, but it doesn't work with CVS and the equation editor doesn't typeset things very well. I think the problem is not that applications work too well, but that it's too expensive to develop better ones. If development costs go down, we could see a lot of growth in specialized software.
Also, I think there's still a lot of growth in embedded computers, which will really take off once people figure out what to do with deck- and dime-sized distributed devices.
Because it's research. Researchers need to be able to implement exactly the features they want to study, not what the developers and user base of an OSS project want. It's about the ideas, not the code. But I'm sure the authors would be pleased if JLint used their ideas.
The paper explains the rationale for each check. For "read of uninitialized field in constructor", the idea is that since the field has the default value, it makes no sense to read it, so the code is at best useless. In another post I think you said it was a static field, so it looks like you've discovered a bug in FindBugs.
Isn't the real difference that ML uses type inference while Eiffel uses declarations? If you wrote ML with type declarations for everything, would it be pretty much like Eiffel?
Diamond wondered what might have been going through the mind of the Easter Islander who felled the last tree on the island. He guessed that it might just have been thoughts that would resonate today: "Hey, keeping my job is more important than preserving the environment". Bah. The guy probably hadn't eaten in 3 days and was thinking "If I don't cut down this tree for a fishing boat, I'll surely die."
Keep in mind that academic researchers create ideas, algorithms, and prototypes, but products only occasionally. Someone still has to write the code for new products. And one of the reasons computer technology is advancing so quickly is that you can put out a low-quality piece of software, and thousands of people will willingly download it and test it for you. Regulation will absolutely kill innovation.