AP CS Test Takers and Pass Rates Up, Half of Kids Don't Get Sparse Arrays At All 128
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."
What a confusing summary! (Score:5, Insightful)
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: (Score:1)
Ask an editor, if you can find one around here. It all seems to be about flashy front-end redesign instead of content now.
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.
Re: (Score:3, Funny)
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: (Score:2)
Artificial stupidity hasn't progressed that far.
Re: (Score:2, Informative)
Re: What a confusing summary! (Score:2)
TRWTF: List is used instead of Map (Score:2)
I'm on the autism spectrum, and I see "private member variables with no setters" as more than likely a class representing an immutable value, such as a decimal floating point value, a big integer value, a date, a string, or whatever. An immutable class sets its fields in its constructors, and then various getters return various transformations of these fields.
Then I read the article, and I was right: sparse array entries are immutable. But the real WTF is that sparse array entries are stored in a List, not
Re: (Score:2)
Re: (Score:2)
I should have read the linked questions before replying...
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.
And this is how we teach computer science?
Sigh.
Re: (Score:3)
Easy. How do you test that you're handling boundaries correctly?
I mean, yeah, your bignum goes from negative infinity to positive i
Re: (Score:2)
How the heck was I supposed to know that a 64 bit flat architecture (pointer range compare across arrays = flat arch) would someday come along that still set int to 32 bits?
How the heck were you supposed to know that your code would run on a flat architecture? Pointer range comparison across unrelated C arrays has been undefined behavior as long as I can remember. Besides, even among flat architectures, the common ABI for the 65816 has 24-bit pointers and 16-bit ints, and the common ABI for the 68000 has 32-bit pointers and 16-bit ints.
Re: (Score:2)
How the heck was I supposed to know that a 64 bit flat architecture would someday come along that still set int to 32 bits?
By reading the standard, which explicitly states that only a long is guaranteed to hold a pointer. Or by running "lint" which is designed to catch silly newbie errors like this. Or by not using casts when you don't understand how they work.
Re: (Score:2)
Sparse array entries, in general, are not necessarily immutable, although they may be so in this case.
The interface in the PDF describes a mutable sparse array with immutable entries. To assign a new value, you'd delete the entry and then add a new one.
Re: (Score:2)
Re: (Score:2)
Re: What a confusing summary! (Score:1)
I've not gone back as a student, but I have taught labs and worked as a tutor. When confronted with a particularly painful examples of allegedly intelligent students acting incredibly dumb I just try to remember how I was in first year: lazy, not stupid; suffering from sever culture shock from the high-school to uni transition; severely hungover most mornings; and still getting used to being required to think about things rather than blindly recalling trigonometric identities, recipes for solving quadratic
Re: (Score:3)
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
Re: (Score:2)
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).
Actually, at least with the AP subject tests in the fields I'm used to dealing with, it's not predatory testing but the sheer lousiness of the AP system. My Gen Chem I class outright treated AP chemistry as a recommended prerequisite--it wasn't a replacement for anything you'd be taking for credit, and regular old high school chemistry was pretty much just as good. (I got through pretty happily without either.)
Basically, at this point AP courses are designed to have a high number of people taking them and
Re:What a confusing summary! (Score:5, Insightful)
The summary is summarizing a tweet. If releasing results like that in a tweet wasn't dumb enough, summarizing it is.
Re: (Score:2)
Re: (Score:1)
An indicator of your test results possibly... (Score:2)
Normally I agree with complaints abut summaries, but this time I found the summary somewhat terse but pretty clear. I guess you were looking for definitions of some of the terms used?
Re: (Score:2)
It would appear that the submitter thinks all that is required to construct an article summary is to string tweets together in a single paragraph.
It's all just words and numbers, isn't it? No suitable effort or consideration for the communication medium required. Consider yourself lucky it isn't written in emojis.
Re: (Score:2)
Re: (Score:2)
Formatting what appears to be a list into one single paragraph makes it awkward to decipher.
Maybe it's a sparse list.
Kids don't understand sparse arrays (Score:4, Insightful)
Re:Kids don't understand sparse arrays (Score:4, Informative)
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: (Score:2)
This might be because in most places you will call them map/dictionaries (int->whatever) if they are single dimensional and sparse _matrices_ when having more dimensions.
One in the test is sparse matrix. Calling it sparse array requires a bit of mental exercise (by having said array indexed by tuples of (x,y) instead of integers). But this probably comes from concept of 2d arrays, which are neither...
Re:Kids don't understand sparse arrays (Score:4, Informative)
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: (Score:1)
Re: (Score:2)
Re: (Score:2)
It all depends on what you want to do with your matrices. Various operations have various costs in different sparse matrix formats. The standard ones are COO or coordinate format: a list of triples (i, j, val); DOK or dictionary of keys format: the hashmap you are thinking of; LIL or list of lists format: a list for each row and a list if pairs (j, val) in each list entry; CSR/CSC or compact sparse row/column: an array of indices where each row starts, an array of column indices and an array of values.
COO a
Re: (Score:3)
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. T
Re: (Score:2)
Thank you.
You put it better than I did.
Re: (Score:2)
You know the nice thing about Wikipedia? When you find poorly written or factually incorrect articles you can actually do something about it instead of just whining about it on an unrelated website.
Re: (Score:2)
You know the nice thing about Wikipedia? When you find poorly written or factually incorrect articles you can actually do something about it instead of just whining about it on an unrelated website.
The other nice thing about Wikipedia is that the original author can be notified via RSS/ATOM that someone has changed their factually incorrect page and they can revert it in moments. A lot of people whine about that on unrelated sites because they're done spending their own free time fighting over fiefdoms when they can say "screw it" and just not hire people that come to an interview armed with whatever they read on Wikipedia.
What I'm saying is, while your solution absolutely makes sense in theory, m
Re: (Score:2)
For a degree in computer science you need to know sparse arrays.
As a working programer you will almost never write one. You will use STL or some other library to handle it.
Re: (Score:3)
Re:Kids don't understand sparse arrays (Score:5, Insightful)
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: (Score:1)
Yes, lack of knowledge does not prevent you from getting a job. But it does prevent you from doing that job well.
Re: (Score:3)
Re: (Score:2, Insightful)
"Working programmers" don't need degrees in computer science. They need diplomas or certificates in programming.
Even so, it's not a bad idea to know something about the tools you're using. Perhaps knowing something about how those vertices are stored might help write efficient code for manipulating them?
HR is part of the problem (Score:2)
"Working programmers" don't need degrees in computer science. They need diplomas or certificates in programming.
If there are 90 people with a certificate in programming applying to a position and 10 with a B.Sc. in computer science, which resumes will HR prefer?
Re: (Score:2)
If there are 90 people with a certificate in programming applying to a position and 10 with a B.Sc. in computer science, which resumes will HR prefer?
The resumes asking for the lowest wage.
Re: (Score:2)
The EE, if they have any sense.
Re: (Score:2)
I said need. You might want one because apparently hiring is done by people who don't know anything about the requirements of the jobs they're hiring for.
What counts in a GitHub folio? (Score:2)
But what defines a "decent GitHub folio"? Does work in other programming languages count? Does work in other subfields of software engineering, such as video games vs. accounting software, count?
Re: (Score:2)
They need diplomas or certificates in programming.
If they don't understand mathematics or computer systems design then their code will be useless
Re: (Score:2)
They need diplomas or certificates in programming.
If they don't understand mathematics or computer systems design then their code will be useless
But note that the question wasn't about understand mathematics or computer systems design; it was about diplomas or certificates in programming. It's fairly well understood that those are orthogonal quantities. ;-)
Re: (Score:2)
Not necessarily. It doesn't take much math to be able to do probably 99% of the programming the world demands today. System design should probably be (and probably is) left to systems architects who have a better understanding of it than the rank and file code monkeys.
If you want to be a system designer/architect/whatever, you maybe should have a degree in software engineering. If you want to be a code monkey a diploma where they ensure that you can write Java, C, add, subtract and multiply is handy. Co
Re: (Score:1, Informative)
Do you think they would've gotten it if the question had called it a database of values instead of a sparse array? There wasn't even a need to know what a sparse array is in advance, as the data structure is fully explained in the question. The actual task only requires a single loop over the linked list, comparing each element to the requested row and column number, returning the value if found and 0 if the element isn't in the list. The second half of question three is just a little bit more difficult, bu
Jeez, sparse arrays, really? (Score:2, Informative)
That is like the second easiest pointer-driven data structure...
Re: (Score:2)
It's a map, with its keys constrained to numbers.
JavaScript arrays are actually sparse arrays. Under the covers, they are implemented as maps.
Apparently, Wikipedia editors don't get sparse arrays either...because they define them as arrays where almost all of the values are 0 or null.
Re: (Score:2)
Re: (Score:2)
Well that is the way I learned it, one way to implement them is using a linked list for each row (or column) of the array (skipping the null/0 values each element storing its index). It was a footnote on my data structures class, maybe that is why students failed the test, the professors did not bother teaching sparse arrays.
For example
0 0 1 0
0 0 0 0
3 0 4 0
0 0 0 5
in a sparse array implemented with linked lists would be:
L0 -> (2: 1) -> null
L1 -> null
L2 -> (0: 3) -> (2: 4) -> null
L3 -> (3
Yeah, well... (Score:2)
Perhaps the kids' teachers taught them the other things and not sparse arrays. It's pretty hard to program something when you have no experience and the only clue you have to program is the title of the data structure.
Re: (Score:2)
I had a look at the question. It explains exactly what a sparse array is and even tells you how it wants you to implement one (essentially as a linked list). The question involves writing the functions to access elements of the sparse array. Given the details provided, I'd be really disappointed if any programmer familiar with the concept of a linked list failed to complete the exercise satisfactorily.
Re: (Score:2)
I just had a look as well. The proposed solution is a linked list of linked lists isn't it? Perhaps this is the bit the kids are stumbling over.
Re: (Score:2)
That's not a particularly efficient sparse array implementation. Although I guess the question doesn't require efficiency.
Re: Here's your chance Slashdot (Score:1)
Yeah, the instant a test has to be in JAVA, sorry, check please.
I can answer that question in Assembly for three processors, Python, ECMAScript (AKA Node), C (note the lack of trailing symbols), bash, awk, and FORTH, or muddle through it in LISP, F, PHP, PERL, five or six other processors in assembly, C++, C#, Go, and Modula-2/3, but seriously... The test requires answers written in JAVA, the least instinctually writable and overly verbose programming language ever invented? O.O
- WolfWings, too lazy to log
Re: (Score:2)
yeah here's the C++ implementation:
#include "my_header.h"
int main(int argc, char *argv[]) {
DO_IT();
}
My solution is best because it is the most readable and easiest to understand. There is only one line of actual code. All of the details are handled by the preprocessor.
Re: (Score:2)
I think you've been watching a bit too much Shia LeBeouf...
Re: (Score:2)
Compilation failed: my_header.h: no such file or directory
Let's go sparse on the "Tweetstorms" (Score:2)
This mash-up of digit-heavy tweets is a crappy SlashDot summary of a sort we haven't seen before.
Doesn't Dice pay editors for this kind of stuff?
I had to look up sparse array (Score:2)
Now my curiosity is demanding a sample copy of the test that I can take. Beyond not having memorized many of the terms I wonder how I would do after 20+ years of programming.
With these sort of tests I often worry that it is just Bulimia Learning where you have to memorize esoterica while never learning to actually program. For instance for you C++ wizzards
Re: (Score:2)
Implement it as a k-d tree and see if any of the examiners can follow your solution.
Re: (Score:2)
Re: (Score:1)
If anything I was a bit slow taking it as I was looking for trick questions that weren't there. But I would say that someone who could pass that test would have at least the basic tools to go fourth and program.
Plus it is in Java which I haven't touched since 2000.
Re: (Score:2)
Would you really expect more? This test isn't a test for college grads- its a test for high school seniors to get them out of 1-2 semesters of bottom level CS courses, by proving they already know the basics. The point isn't to trick them or to expect them to know everything, its to see if they can save some time/money on intro level topics.
Re: (Score:2)
If anything the main problem that I have is that I have met CS grads who might not do so well on that exam. I am not saying it is too hard but that the aforementioned CS grads sucked.
Re: (Score:2)
Yes. Previous years scores are contained in a linked list. All you have to do is ...
Sorry about that.
oh goodie slashdot tradition continues (Score:1)
How many years has slashdot been around, and how many years spent arguing about silly little things like this?
Yes, CS was harder when you were in college. Yes, people were smarter back then too. There are 2 orders of magnitude higher enrollment in Computer Science programs than there was 20 years ago. You're bound to get a lot of people who haven't quite figured out if this is the place for them yet.
Also, the readability of the summary is approaching zero as well. If I wanted a recap of tweets, I would have
Why Java? (Score:2)
Why is the entire test in Java? Not Javascript but actual Java. I mean, at least it's not .NET or C# (aka, platform specific).
Why Not Java? (Score:3)
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,
Re: (Score:2)
Re: (Score:2)
When I took it in 2002, it was C++ at the time. I think they switched to Java a year or two later.
You're close. I took the AP test the last year it was C++. I was also taking Java with the same instructor, same room, the next period, so I kind of had the best and worst of both worlds. But the instructor was top notch and is regionally well known - I'm very sure he was the primary factor in nearly all of his AP students both passing the AP test and having a job in the industry. Those two classes got me through my first two years of college and put me in a unique position for learning low/high level l
Re: (Score:2)
...because teachers need to be able to decipher the code afterwards.
Re: (Score:2)
Why is the entire test in Java? Not Javascript but actual Java. I mean, at least it's not .NET or C# (aka, platform specific).
Well, I tried turning in my answers in Whitespace [wikipedia.org], but I got a zero.
Craptastic Summary (Score:2)
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: (Score:2)
Read the article? There is no article. There are six tweets (numbered and linked individually), a graph with data sets helpfully labeled "1", "2", "3", "4", and "5" but no other description, and a PDF of the test questions. And some comment about students not understanding the concept of "sparse arrays", but since the term is completely defined in the test materials I can only assume the real concern is that students can't be bothered to read the "unimportant" introductory material before trying to answer
This is AP? (Score:2)