New host! http://www.acmsolver.org

Check us at:  New host! http://www.acmsolver.org

Are you a Programmer? Contribute here! get a mail address, yourname@acmsolver.org

Some Programming Books.. (from NTNU)

 

Including “Art of Programming Contest”! Check: http://www.csie.ntnu.edu.tw/~u91029/book.html

Can Johnny still program? (Interesting..article)

If David Patterson had his way, the president of the United States would congratulate top code jockeys just like the commander-in-chief applauds the Super Bowl champs.

That would send a message about the importance of technology smarts and skills, argues Patterson, a computer science professor at the University of California, Berkeley, and president of the Association for Computing Machinery, a group that runs a major student coding contest.

“(Our presidents) meet the winners of the football championship, right?” Patterson says. “Gee, wouldn’t it be wonderful if the presidents would meet the winners of the programming contest? Wouldn’t that be a better world?”

After U.S. students earlier this month made their worst showing in the 29-year history of the ACM International Collegiate Programming Contest, Patterson and others are wondering whether the United States does enough to encourage programming talent. The top U.S. school finished in a tie for 17th place. Students from China’s Shanghai Jiao Tong University took the top honors, continuing a gradual ascendance of Asian and Eastern European schools during the past decade or so. The last time a U.S. institution won the world championship was in 1997.

Some argue the results don’t necessarily mean much, given the way foreign schools may put more emphasis on the contest. What’s more, the number of entrants has mushroomed, from fewer than 650 teams in 1994 to more than 4,100 this year.

Patterson, though, thinks there’s more to the U.S. decline–viewed by some as a sign the country’s tech leadership is in trouble.

ACM’s leader knows a thing or two about creating important technology: He played a key role in the development of so-called reduced instruction set computers, or RISC, and was involved in a Berkeley networking project that led to technology used by Internet companies such as Inktomi.

CNET News.com recently spoke with Patterson about ACM’s contest, the state of student tech talent in the United States, and how outsourcing is affecting the field.

What’s measured in the ACM programming contest?
Patterson: The problems are not simply, as the title sounds like, ‘Write a program to do factorial fast.’ It’s more problem-solving than that. One of them had to do with a cell phone tower. You had to cover this many people, so where would you place your cell phone tower, or something like that.

 

Gee, wouldn’t it be wonderful if the presidents would meet the winners of the programming contest?

 

What are the origins of the contest?
Patterson: Since ACM has been around so long, it started off as a local programming contest and then it expanded to be nationwide and then international. Education was a big part of the ACM mission. Since computers were brand new, one of the big challenges was going to be to teach people how these use them. So this was kind of a natural thing to do for this volunteer organization. Somebody thought it would be nice to have a programming contest.

What’s happened in the last 10 or 15 years is information technology has been spreading through a bunch of these countries, many of which do not have great economies and find information technology very attractive. It’s not capital intensive. It’s a nonpolluting technology. And nations think of themselves as good at things. If you think you’re good at math and science–like the Russians, I think, do, and Indians and Chinese–if they think, ‘Gee this is something we’re good at,’ IT becomes a target.

As result of your story, I’ve gotten feedback about how seriously this is taken. I’m told in Russia…the contest couldn’t be taken more seriously.

National Computer Programming Contest 2008 (Bangladesh)

You would be pleased to hear that University of Liberal Arts Bangladesh is hosting the National Computer Programming Contest named ULABNCPC 2008 on Friday, 17 October 2008. This NCPC has been the platform for the young talents to come together from all over the country to compete for problem solving skills for
last 11 years and through this event these young talented minds would contribute for the next generation ICT developments.

Separating Programming Sheep from Non-Programming Goats

A bunch of people have linked to this academic paper, which proposes a way to separate programming sheep from non-programming goats in computer science classes– long before the students have ever touched a program or a programming language:

 

All teachers of programming find that their results display a ‘double hump’. It is as if there are two populations: those who can [program], and those who cannot [program], each with its own independent bell curve. Almost all research into programming teaching and learning have concentrated on teaching: change the language, change the application area, use an IDE and work on motivation. None of it works, and the double hump persists. We have a test which picks out the population that can program, before the course begins. We can pick apart the double hump. You probably don’t believe this, but you will after you hear the talk. We don’t know exactly how/why it works, but we have some good theories.

I wasn’t aware that the dichotomy between programmers and non-programmers was so pronounced at this early stage. Dan Bricklin touched on this topic in his essay, Why Johnny Can’t Program. But evidently it’s common knowledge amongst those who teach computer science:

 

Despite the enormous changes which have taken place since electronic computing was invented in the 1950s, some things remain stubbornly the same. In particular, most people can’t learn to program: between 30% and 60% of every university computer science department’s intake fail the first programming course. Experienced teachers are weary but never oblivious of this fact; brighteyed beginners who believe that the old ones must have been doing it wrong learn the truth from bitter experience; and so it has been for almost two generations, ever since the subject began in the 1960s.

You may think the test they’re proposing to determine programming aptitude is complex, but it’s not. Here’s question one, verbatim:

 

Read the following statements and tick the box next to the correct answer.

int a = 10;
int b = 20;
a = b;

The new values of a and b are:
[ ] a = 20  b = 0
[ ] a = 20  b = 20
[ ] a = 0   b = 10
[ ] a = 10  b = 10
[ ] a = 30  b = 20
[ ] a = 30  b = 0
[ ] a = 10  b = 30
[ ] a = 0   b = 30
[ ] a = 10  b = 20
[ ] a = 20  b = 10

This test seems trivial to professional programmers, but remember, it’s intended for students who have never looked at a line of code in their lives. The other 12 questions are all variations on the same assignment theme.

The authors of the paper posit that the primary hurdles in computer science are..

1. assignment and sequence
2. recursion / iteration
3. concurrency*

.. in that order. Thus, we start by testing the very first hurdle novice programmers will encounter: assignment. The test results divided the students cleanly into three groups:

 

• 44% of students formed a consistent mental model of how assignment works (even if incorrect!)
• 39% students never formed a consistent model of how assignment works.
• 8% of students didn’t give a damn and left the answers blank.

The test was administered twice; once at the beginning, before any instruction at all, and again after three weeks of class. The striking thing is that there was virtually no movement at all between the groups from the first to second test. Either you had a consistent model in your mind immediately upon first exposure to assignment, the first hurdle in programming– or else you never developed one!

The authors found an extremely high level of correlation between success at programming and forming a consistent mental model:

 

Clearly, Dehnahdi’s test is not a perfect divider of programming sheep from non-programming goats. Nevertheless, if it were used as an admissions barrier, and only those who scored consistently were admitted, the pass/fail statistics would be transformed. In the total population 32 out of 61 (52%) failed; in the first-test consistent group only 6 out of 27 (22%). We believe that we can claim that we have a predictive test which can be taken prior to the course to determine, with a very high degree of accuracy, which students will be successful. This is, so far as we are aware, the first test to be able to claim any degree of predictive success.

I highly recommend reading through the draft paper (pdf), which was remarkably entertaining for what I thought was going to be a dry, academic paper. Instead, it reads like a blog entry. It’s filled with interesting insights like this one:

 

It has taken us some time to dare to believe in our own results. It now seems to us, although we are aware that at this point we do not have sufficient data, and so it must remain a speculation, that what distinguishes the three groups in the first test is their different attitudes to meaninglessness.Formal logical proofs, and therefore programs – formal logical proofs that particular computations are possible, expressed in a formal system called a programming language – are utterly meaningless. To write a computer program you have to come to terms with this, to accept that whatever you might want the program to mean, the machine will blindly follow its meaningless rules and come to some meaningless conclusion. In the test the consistent group showed a pre-acceptance of this fact: they are capable of seeing mathematical calculation problems in terms of rules, and can follow those rules wheresoever they may lead. The inconsistent group, on the other hand, looks for meaning where it is not. The blank group knows that it is looking at meaninglessness, and refuses to deal with it.

Everyone should know how to use a computer, but not everyone needs to be a programmer. But it’s still a little disturbing that the act of programming seems literally unteachable to a sizable subset of incoming computer science students. Evidently not everyone is as fascinated by meaningless rules and meaningless conclusions as we are; I can’t imagine why not.

* which I hope to master sometime between now and my death

by http://www.codinghorror.com/blog/archives/000635.html

Programming sites to look at

http://editor.altervista.org/ for Algorithm Collection

http://c4swimmers.net/ India;s largest C Programming Portal!

Links..

Online judges

ACM Live Archive, has many problems from past ACM/ICPC regional contests and world finals.
Arbiter, online judge at Sharif University in Iran.
FZU Online Judge, about 500 problems.
Harbin Online Judge
HDU Online Judge, has virtual contest features and quite a lot of problems.
Hunan University ACM/ICPC Online Judge, seems to have a lot of problems from regional contests. Unfortunately a lot of the material is in Chinese.
Google Code Jam, here you can practise on problems from previous competitions. They allow you to code in whichever language you want, which is really nice. The interface is excellent compared to most similar sites.
Jilin Online Judge
Lviv Online Judge, over 100 problems and expanding. Unfortunately it is only in Ukrainian.
Moscow Online Judge, few problems, but all of are of a high quality.
Peking University Online Judge, more than 2220 problems.
Programming Challenges, a judge that contains all the problems in the book of the same title (by Steven Skiena). The problems are a selected subset of the problems from the UVA judge.
Saratov Online Judge, over 200 problems, most problems are also rather challenging.
Sphere Online Judge, over 500 problems, this judge supports over 25 different programming languages. It excels in this area. This is a widely used online judge.
TJU Online Judge, over 3000 problems. Most are from old regionals or similar. A cool feature on their judge is the ability to have virtual contests, and since they have a lot of old regionals, this is a very useful feature for team practice for upcoming ACM/ICPC contests.
TopCoder, TopCoder is not actually an online judge. TopCoder is an organization that arranges programming contests. They have their own arena with practice rooms and a lot of problems from previous SRM’s (single round matches). Moreover TopCoder arranges matches almost weekly, often with prizes to the best scoring contestants. Many people practice at TopCoder, and it is also highly encouraged.
Ural Online Judge, over 500 problems, in general most problems are quite difficult.
USACO Training Program Gateway, this site is intended for high school students, but is in fact used by many others. They have a nice training program with tutorials, and reference solutions that you can see once you have solved a problem. Their training program is highly recommended.
UVA Online Judge, more than 2000 problems available. All problems on this site are from this judge.
ZJU Online Judge, over 1800 problems. Note that this judge supports only C and C++.

Useful sites

Algorithmist, here you can find explanations of many problems and also classifications. There are also nice tutorials about different subjects. Also they have a calendar of different programming contests. You should really check this page out!
Felix Halim – Hunting UVA problems, Felix Halim has a great site where you can Hunt UVA problems. One great feature is that you can view “the next 20 easiest problems for you”. This is of an immense aid in helping you find problems that you are able to solve. You can also find a graph that shows your problem solving progress. He also keeps ranklists for all countries in the world. All in all his site is greatly recommended.
GMU ACM ICPC Code Repository, solutions for different problems on the UVa online judge, ACM/ICPC regionals, and also explanations of various techniques such as dynamic programming.
Steven Halim – World of Seven, at this site you can find hints for many of the problems. There are also some nice tutorials that will help you learn new algorithms and problem solving skills. It is also a good site to visit if you are stuck on a problem and need a hint. He has hints for around 530 problems from the UVA judge.
Igor Naverniouk’s site, Igor has a lot of experience in solving problems at the UVA judge. At his site you can see how he has has classified his solved problems, and in some cases you can also get hints. His problem classification list is often very useful. His library of algorithms (in C++) is very useful, and is definitely worth a look.
Waterloo Programming Contests, this is the local page for contests held at the University of Waterloo in Canada. Here you will find a lot of great problems (most of them are also on the UVA judge), including solutions, input and output. Most solutions are of a very high quality. If you are stuck on one of their problems, it may be a good idea to take a look here.
Mesmay’s ACM-ICPC Resources page, here you can find hints for many of the problems of Volume I at the UVA judge. You can also find extra input and output for these problems. Furthermore there is a section concerning many of the standard algorithms. This site is mainly useful if you are stuck on one of the problems of Volume I at UVA

TopCoder tools

otinn.com, has myriads of different statistics from TopCoder competitions such as “country statistics”, and various interesting features such as “TopCoder duel”. If you are bored, there is always something to look at there.
Micromatch scores, compares the performance of two competitors using the problems that both have faced.
Division summary, Felix Halim has made a very nice overview of division summaries from TopCoder algorithm competitions.
Division summary, same as above but with a different interface.
Algorithm rating graph comparison, can be used to compare algorithm rating graphs of any number of competitors.
Random Coder Stats, shows random but still very interesting statistics about a coder
TC Utilities, here you can calculate predicted ratings, expected value of prizes and various other things.
Country Statistics, has ratings of countries in terms of their performance in TopCoder algorithm competitions.

Google Code Jam statistics

GCJ 2008 Statistics, a lot of different useful statistics over GCJ 2008.
GCJ Round 2 scoreboard, an unofficial scoreboard relating contestants to their TC handles (by the topcoder zibada).
GCJ Round 3 scoreboard, as above but for round 3.

DataStructures- Maxiumum subsequence problem

Problem:
Given (possibly negative) integers A1,A2,…An, find the maxiumum value of the sub array.

Solution:

#include <stdio.h>

#define SIZEOF(arr) (sizeof(arr)/sizeof(arr[0]))

int arr[] = { 2, -3, 4, -1, 5, -1, -3, 6, -1, -1, -4, 2, -1};

void MaxSum(int arr[],int length)
{
       int max,sum;
       int i = 0 ;

       max = sum = arr[0];

       for(i=1;i<length;i++)
       {
               sum += arr[i];
               if(sum > max)
               {
                       max = sum;
               }

               if(sum < 0)
               {
                       sum = 0;
               }
       }
       printf("The max sum is : %d\n",max);
}

void PrintArray(int arr[],int size)
{
       int i;
       for(i=0;i<size;i++)
               printf("%d ",arr[i]);
       printf("\n");
}

int main()
{
       PrintArray(arr,SIZEOF(arr));
       MaxSum(arr,SIZEOF(arr));
       return 0;
}

 

Top 100 Universities in the world 2008 : ARWU by Shanghai Jiao Tong University, China

1. Harvard University, USA
2. Stanford University, USA
3. University of California, Berkeley, USA
4. University of Cambridge, UK
5. Massachusetts Institute of Technology (MIT), USA
6. California Institute of Technology, USA
7. Columbia University, USA
8. Princeton University, USA
9. University of Chicago, USA
10. Oxford University, U.K
11. Yale University, USA
12. Cornell University, USA
13. University of California, Los Angeles, USA
14. University of California, San Diego, USA
15. University of Pennsylvania, USA

Aah..Let’s take a break for vacation!

Photography by http://www.kristupa.com/foto.php?id=419794