Do SDD HSC markers desk check? (1 Viewer)

[Technoash]

2 questions of my Software Design and Development trial paper were algorithm questions in which we had to create an algorithm. I came up with quite elaborate algorithms that did not make use of standard code snippets from our textbooks. The solutions did resemble standard linear searches etc, but were not obvious. The issue is that I received 1/4 and 0/4 for the questions. I was sure that the solutions were worth more than what I got so I asked our teacher to go through those questions again. We manually went through the program and figured out that it works fine. There were a couple of tiny errors but that's it. I received 2/4 and 3/4 (4 extra marks)

Obviously my teacher had not done a desk check of my program and had assumed that it was incorrect because of the deviation from textbook algorithms.
My question is: Will HSC markers actually manually go through the program to determine if the solution works or will they look at features of the program to see if common structures are used?

Thanks
Technoash

 

[seventhroot]

well it is likely that they will look at the main body of it and if it looks good enough they will award you marks according to a criteria. I highly doubt that that markers will take the time to make sure every function, loop, etc was done correctly, remember they are also on a deadline

 

[GoldyOrNugget]

I want to see these solutions now

 

[Technoash]

I want to see these solutions now

Here it is

Question: As part of the operating system of a MP3 player, a module is required to enable a random or shuffle play of all songs stored in the player. Initially it is assumed that there are 500 songs in the playlist. Random(x) is a function that will generate a number between a and x inclusive.

It was discovered that the algorithm above allowed some songs to be repeated while others were not played at all. Rewrite the algorithm adding the necessary logic to ensure that all songs are played in a random order without repeating any of them.

EDIT: Line 2 has a typo. Should be NumberOfSongs-1
I now realise how stupid this algorithm is but that does not take away from the fact that it works

 

[GoldyOrNugget]

Whose trial paper was this? They need a stern talking to. This as a totally inappropriate question for an SDD exam. Random shuffling is a hard problem which requires some intense mathematical analysis to implement correctly. Many 'obvious' solutions to the problem won't lead to a uniform distribution over all permutations. In fact, even nowadays exploits are being discovered in e.g. online poker sites which are caused by bad random shuffles.

Your solution seems to be correct (although it's extremely inefficient). I think it deserves full marks because the question doesn't specify that your algorithm doesn't need to be efficient. What solution were they expecting you to implement?

 

[Technoash]

Whose trial paper was this?

This paper was made by our school from previous years questions but I can't find this question on the Board of Studies archives with a google search
https://www.google.com.au/webhp?sourceid=chrome-instant&ion=1&espv=2&ie=UTF-8#q=site:www.boardofstudies.nsw.edu.au++%22played+in+a+random+order+without+repeating%22

This as a totally inappropriate question for an SDD exam.

To their credit, the question did provide a random int generating function that should provide sufficient "randomness".

Your solution seems to be correct (although it's extremely inefficient).

Yeah, I wasnt worried about efficiency. I just had to get an answer on paper

What solution were they expecting you to implement?

My teacher showed me the suggested answer while going through my program. From what I remember it was fairly similar to my solution. That being said, I don't remember much of the answer


I might have my teacher look at the solution again. It's a bit late as ranks have already been calculated but I'm interested in why I didn't receive full marks

 

[GoldyOrNugget]

The randomness of the random number generator isn't the issue. Rather, the issue is that there are many subtle variations on the basic shuffling algorithm, and the consequences of these variations are not clear from a cursory examination of the algorithms' outputs. The canonical shuffling algorithm is called the Fisher-Yates shuffle, or the Knuth shuffle, and it produces uniformly-distributed permutaitons. By changing ONE character in the code for the Knuth shuffle, you get Sattolo's Algorithm, which also seems to produce random permutations but in fact produces uniformly-distributed cycles over the array elements. There are only (n-1)! possible cycles, whereas there are n! permutations.

Another one-character change to the Knuth shuffle produces an even subtler bug -- the new algorithm can produce all permutations, but it doesn't produce them with equal probability. The reason is that it makes n^n distinct swaps, whereas the number of permutations is n!. n^n is never divisible by n! for n > 2, so some sequences must be produced with greater probability than others. If your test data is large enough (e.g. 500 elements) the difference between the outputs of these algorithms will be almost indistinguishable.

It worries me that an SDD teacher happily puts a question like this on an exam paper without considering these issues :'(

And to answer your question, an HSC marker will perform an informal desk check on your algorithms. If your algorithm is too complex or appears to be wrong on first glance, they might mark it down. Try to make your algorithms as simple and intuitive as possible. Comment your code heavily if you're concerned that it's difficult to understand.

 

[Technoash]

The randomness of the random number generator isn't the issue. Rather, the issue is that there are many subtle variations on the basic shuffling algorithm, and the consequences of these variations are...

Yeah the question is a bit inappropriate
This stuff is cool. Are you doing computer science or software engineering? Or did you learn this shuffling stuff by researching it yourself?

 

[Technoash]

And to answer your question, an HSC marker will perform an informal desk check on your algorithms. If your algorithm is too complex or appears to be wrong on first glance, they might mark it down. Try to make your algorithms as simple and intuitive as possible. Comment your code heavily if you're concerned that it's difficult to understand.

Yeah that's what my issue is. I didn't have comments and the structure of the algorithm wasn't the best.
I need to get used to writing comments.

It's good to hear that they do some sort of desk check
Thanks for the clarification

 

[GoldyOrNugget]

I learnt that stuff myself, but I studied some compsci too. There's plenty of interesting theory behind the treatment of random numbers in programming.