AP CS Test Takers and Pass Rates Up, Half of Kids Don't Get Sparse Arrays At All

theodp writes: Each June, the College Board tweets out teasers of the fuller breakouts of its Advanced Placement (AP) test results, which aren't made available until the fall. So, here's a roundup of this year's AP Computer Science tweetstorm: 1. "Wow — massive gains in AP Computer Science participation (25% growth) AND scores this year; big increase in % of students earning 4s & 5s!" 2. "2015 AP Computer Science scores: 5: 24.4%; 4: 24.6%; 3: 15.3%; 2: 7.1%; 1: 28.6%." [3 or above is passing] 3."Count them: a whopping 66 AP Computer Science students out of 50,000 worldwide earned all 80 pts possible on this year's exam." 4. "Remember that AP exam standards are equated from year to year, so when scores go up, it's a direct indication of increased student mastery." 5. "Many AP Computer Science students did very well on Q1 (2D array processing–diverse array); >20% earned all 9/9 pts" [2015 AP CS A Free-Response Questions] 6. "The major gap in this year's AP Computer Sci classrooms seems to be array list processing; Q3 (sparse array): 47% of students got 0/9 pts."

Comments

What a confusing summary!

[Anonymous Coward]

What a confusing summary. There are meaningless links that are just numbers. The quotes following the numbers have no context and make no sense. Formatting what appears to be a list into one single paragraph makes it awkward to decipher. The linked-to graph image is missing many labels. The lack of other details doesn't help, either. What the fuck is this submission even supposed to be about?!

Re:What a confusing summary!

[Anonymous Coward]

Kids are passing the AP CS test with higher scores, but nearly 50% of them cannot understand concepts that involve a slight amount of thinking. In other words, it's a shitty test or most taking it are stupid.

Re:What a confusing summary!

[ceoyoyo]

The summary is summarizing a tweet. If releasing results like that in a tweet wasn't dumb enough, summarizing it is.

Re:What a confusing summary!

[JustAnotherOldGuy]

Oh, and BTW you Slashdot 'designers' -- is it possible for you to fix your CSS so the story icons don't sit on top of the fucking headline when my browser window isn't full-screen? Kthxbye.

Dear User,

No. We have a firm policy geared toward fucking shit up and we're not going to stop just because you asked us too.

Signed,
The SlashDice Staff

Re:What a confusing summary!

[Austerity Empowers]

Kids are passing the AP CS test with higher scores, but nearly 50% of them cannot understand concepts that involve a slight amount of thinking. In other words, it's a shitty test or most taking it are stupid.

The more kids that pass the AP CS test, the more colleges that accept AP credits lose funding. It stands to reason the test is designed primarily to throw people off the boat and justify having them retake the class, setting them back between 1 and 2 semesters. In reality, in college, they will learn exactly the same stuff as in high school with probably worse teachers (or grad students).

Now, consider that most people taking AP CS have no interest in "computer science", they have interest in computer programming, specifically the fraction of computer science that will get them the big $$$ in private industry. Very nearly no one has interest in academia (in this or any other field), for very good financial and practical reasons, yet a test is being administered to young kids with inadequate knowledge of what is important/what is not important who have been exposed to the field for, in most cases, exactly one year. The kids probably know how to write a program that will compile or otherwise execute, but have limited idea or perhaps a certain degree of animosity to academic formalism.

Take a combination of predatorial testing, and contrasting motives and hilarity shall inevitably ensue. The best way to appreciate computer science, is similar to the best way to understanding electrical engineering: start with the useful practical things that will get them interested, show them how a bit of education improves the design & function, and get them hooked. It makes all the diffeq a whole lot easier to sit through, or in the case of CS, the algorithms and discrete math.

Kids don't understand sparse arrays

[Culture20]

Duh! I bet it matches up exactly with kids that don't understand pointers and linked lists. Wonder why that might be...

Re:Kids don't understand sparse arrays

[SenatorPerry]

Link for the Lazy

I had never heard of sparse array as a term, but we discussed the concept nearly two decades ago as a normal design process.

Re:Kids don't understand sparse arrays

[skovnymfe]

In other words you don't need a CS degree to be a programmer.

Re:Kids don't understand sparse arrays

[LWATCDR]

No you don't but their is value in knowing how to write one when you use one.
It usually means you know better than reinventing the wheel.

Re:Kids don't understand sparse arrays

[Cassini2]

Sparse arrays is a mathematical abstraction that completely ignores the implementation details. Formally, they are any matrix that has "many" zeros (or null) values. The practical problem is that most useful optimizations around sparse arrays require closely matching implementation details against the problem to be solved. With sparse arrays, implementation details are killers.

For instance, suppose the standard solution is adopted. The sparse array will be organized as an array of linked lists representing the rows, with each row containing another linked list that contains the individual data values. What happens if you want to do a matrix multiply? A matrix multiply requires a column by row lookup and a row by column lookup. One will be an O(1) lookup, and the other will be a O(n^2) lookup. This makes a full matrix multiply an O(n^5) operation, and memory is the least of everyone's worries.

To optimize the code, it is necessary to look closely at how the matrix will be built and used. However, as soon as that starts happening, the matrix multiply decomposes into a bunch of specialized matrix operations. At this point, the abstraction starts falling apart.

For example:
a) Assume the multiplication involves a diagonal matrix. Then the optimum solution is to store the diagonal matrix as a 1xn matrix, and specialize the matrix code. This was the favoured approach from numerical methods in C and Fortran.
b) Assume the multiplication involves a tridiagonal matrix. Then the optimum solution is to store the tridiagonal matrix as a 3xn matrix, and specialize the matrix code. Again, see numerical methods in C and Fortran, or just about any good matrix library.
c) Assume the matrix operation involves a "control-systems" style matrix. One populated row, followed by a diagonal series of rows with one or two elements. The optimum solution is to develop specialized code. For most control systems problems, this matrix never changes.
d) Control systems often have a compact matrix representation involving a series of matrix multiplies. However, if the matrix multiplies are analysed, they become a much simpler sequence of equations that can often be executed in O(n^2) time instead of the longer O(n^3) time of the matrix multiplies. As such, develop specialized code. Both MatLab and Mathematica have functions where numerical operations can be broken down into there constituent formulas and saved as "C" code.
e) Assume we really need to frequently multiply a truly sparse array. Then build two sets of linked lists, one organized by row/column and another organized by column/row. Then both the row and column lookups can be done as an O(1) operation. The matrix multiply is a O(n^3) operation.
f) Just because the inputs to a matrix operation are sparse, doesn't mean the output array is sparse. I'm thinking of Singular Value Decomposition, some matrix multiplies, matrix inverses, matrix pseudo-inverses, and covariance matrices. Also, some matrices that appear in Quantum physics. In this case, matrix operations need to be further specialized to deal with creating non-sparse matrices from sparse-matrices. Additionally, some matrices may need to be rounded to sparse, even though they may be fully populated, like some covariance matrices.

In the end, sparse matrices are simply a descriptive term for a bunch of application-specific optimizations. Sparse matrices devolve into numerical optimizations that no-one cares about unless they are looking at an application that requires the specific numerical optimization. I'm not surprised high-school CS coders don't "understand" them.

Re:Kids don't understand sparse arrays

[jandrese]

No, but you will need the CS degree to be a good programmer. If you know what is going on under the hood you can avoid those O(N^5) operations that make your code inefficient. If you just blindly use whatever looks vaguely correct in the standard library you'll never know why your code is so slow.

Re:Kids don't understand sparse arrays

[mbkennel]

I think the poster above clearly understood the problem domain, in that the most common uses for "sparse array" is a "sparse matrix" for numerical computations.

And moreover, as is the case, the problem domain of matrix computations is known to be deep and problem-dependent, with a wide variety of representations and solution categories.

| But by all means, go ahead and implement your own formats for each of the various types of sparse matrices you are likely to encounter. Then optimize operations for each. Then implement complex algebra (eigenvalues, svd, QR, the works). In the end, hope that your brand spanking new wheel has no corners and works for enough use cases to justify not employing a standardized wheel. A smarter person than me said something along the lines of premature optimization and evils, but I suppose it does not apply to your brand of genius.

I see an unjustified insult against the previous poster.

The various cases and solvers have already been implemented in many important software packages for different domains, and given the centrality of matrix operations in high performance computing, this is not a premature optimization but rather the essential, core implementation and algorithmic optimization flowing from the proper mathematical treatment of the problem.

And his point was not at all to re-do everything yourself, but to be aware that there are in fact many varieties of sparse matrices in various settings and that this is not just a software-abstraction problem but a key mathematical problem, and there is no simple over-arching software abstraction that works well universally. The post described well-established problem domains with high-quality solutions.

Simply being aware of this not-always obvious fact is an example of scientific maturity.

Why Not Java?

[sirwired]

Why not Java? They have to pick some language, and Java has a wide array of IDE's, many of which will run just great on whatever ancient Windows boxen a school can scrape up, an extensive textbook infrastructure, a decent number of people that know it, and the ability to implement (in a straightforward manner) most of the concepts you need to teach in a high-school CS class. It has it's quirks, but I'd prefer it to C++.

Yes, a full CS curriculum uses several languages in order to teach different concepts, but that's just not possible within the confines of a couple High School courses.

When I did AP CS in the early 90's, it was Pascal all the way... it had a very easy to learn syntax, but didn't have enough modern language features (like OOP) that the folks in my college's CS program that had passed the AP test were really hurt when their follow-on classes assumed they both knew C++ already and that they had some familiarity with OOP. (I didn't pass the AP CS test due to my brain being fried from a brutal AP US History test that morning.)

Craptastic Summary

[JustAnotherOldGuy]

No offense, but this is a shit summary.

I'm not even going to bother to parse it out or read the article, I have all the word-salad I need at the moment.

Re:TRWTF: List is used instead of Map

[tlhIngan]

Stupid, stupid, STUPID! Why have numRows and numCols in a sparse array? Things with unnecessary, arbitrary bounds annoy me. My implementation of Conway's Game of Life runs on a sparse array precisely because that allows the world to stretch arbitrarily in any direction a glider goes, limited only by the capacity of the bignum library and the total store available to the program.

Easy. How do you test that you're handling boundaries correctly?

I mean, yeah, your bignum goes from negative infinity to positive infinity. But what happens as you approach those numbers?

Also, how do you test that you're not arbitrarily limiting the results? More than one program has been caught in the 32-to-64 bit transition because they cast pointers to uint32's. (Enough that there's "uintptr_t" which is an int type big enough to cast a pointer to).

So why not have a way to arbitrarily limit the size? Even better, add in the ability to adjust the boundaries. That way you can do testing on small, easily testable and quickly reproducible array sizes and nail down the most common bugs you'll encounter (especially ones that require wrap around handling), before you run more extensive tests.

Plus, constants can be changed. One common test would be to change numRows and numCols and rebuild/re-run the test and make sure it handles the new value successfully and that it still works. You know, to make sure values like that aren't hard coded. (You may laugh, but enough people code "C:\Windows", or "C:\Program Files", to matter. It's basically assuming a constant will stay, well, constant, instead of checking. Apple threw Square Enix for a loop because Apple renamed the documents folder for storing volatile per-app content. Square Enix hardcoded their paths (despite Apple telling people HOW to do it properly), resulting in app breakage. Even worse, Square Enix's solution was "do not upgrade your phone/tablet". Apple threatened to withdraw their apps because of complaints, and within a week, new versions were released).

So yeah, you may use bignums, but maybe someone internally decided 32 bit ints were good enough, because well, it's a test app and no one was going to actually run it long enough to verify. (Funny, in production, how often people hit limits we think are "too big"... see IPv4. Windows' 49 day bug, etc).