Another handicapped lab, due to the fact that there are a bunch of students who didn’t learn matrix operation before. Add and multiply namely.

Arrays, and what are they? I also dunno the exact defination. *loL* It is simply a variable that can hold multiple instances of a particular data type / object.

when I declare it as

int[] nD = new int[5];

I just create a var that can store 5 instances of int data type and it runs from nD[0] to nD[4]; Basically 5 placeholders
to store your stuffs.

|_| |_| |_| |_| |_|

when declared as

int[][] nD = new int[5][5];

It is 5 rows of 5 placeholders each to store stuffs. cool rite?

|@| |@| |@| |@| |@|
|@| |@| |@| |@| |@|
|@| |@| |@| |@| |@|
|@| |@| |@| |@| |@|
|@| |@| |@| |@| |@|

And thus this is used to store matrix, with black representing the rows and purple representing the column. The one is green is represented by nD[2][2].

of cos I made that first [] represents rows and the second [] represents column. can be the other way round too.

Awww, got full marks for dynamic tests. Yay. Time spent:3+ hours. Majority of the time trying to find out how multiplication works for matrices.

A stunning no-array-allowed lab exercise:

Write a program ListFractions.java to read in 2 positive integers n (1 < n <= 1000) and k from System.in, and pick the kth fraction from a list of fractions composed as follows:

• A list of fractions is generated from the given n, where the denominator ranges from 2 to n, and the numerator is a positive integer smaller than the denominator, as shown below:

  1/2, 1/3, 2/3, 1/4, 2/4, 3/4, …, (n-2)/n, (n-1)/n

• The list is rearranged such that the fractions are in increasing magnitude, with duplicate values removed, retaining only the one in the simplest form among the duplicates.

  For example, if n is 5, then the list in the required order is:
  1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5
  (2/4 is removed as it is equivalent to 1/2)

If n = 5 and k = 4, then the answer is 2/5 which is the 4th fraction in the list.

Well, if you dunno this sequence like me, bruteforce is the way to go. Yeah. I went by the bruteforce way. For those who know this Farey sequence, good for you too. You are simply looking for the easy way out instead of using your brain to code a algorithm, you rely on maths to help you solve it.

Well using the bruteforce method has got its cons, that is execution time. A sample bruteforce baseline has been set by the professor. His execution time is as follow.

$ java ListFractions
Enter n and k: 1000 2000
6/901
Elapsed time: 300.755 sec.

Well, below is my first and second try.

$ java ListFractions
Enter n and k: 1000 2000
6/901
Elapsed time: 220.124 sec.

$ javac ListFractions.java
$ java ListFractions
Enter n and k: 1000 2000
6/901
Elapsed time: 18.721 sec.

Aw, don’t mistake the 2nd one as using Maths approach. It is still bruteforce method. Just some tweaking and minus out unnecessary steps and the time taken to compute it drops 200 secs! How cool is that? I bet if i limit the range to search for, it would probably be 10s flat. Well, that’s another time.

Oh if you are interested, I bruteforced it by using the following approach.

let n = number of terms
let k = kth term of the series
set smallest to be 1 / n [first term]

loop thru from 1 / n to (n – 1) / n [practically generating the sequence]
look for the term just slightly greater than smallest
set smallest to be this new term

by doing this (k – 1) times, you can find the kth term as 1st term no need to find

Well hand was itchy so tried out Farey formula

$ javac FareyMethod.java
$ java FareyMethod
Enter n and k: 1000 2000
6/901
Elapsed time: 3.422 sec

Dumbfounded. Fast. I am amazed with Maths! Wonder which smart Alec derived this formula. Farey?

Update Decided to optimize the code further, shaved a few seconds off again. No change to logic but change coding style slightly

We permit and encourage healthy discussion among students. However, students must draw the line between discussion and plagiarism (copying of other’s work or taking credit for a piece of work that is not original).

The university does not condone plagiarism. If detected, both the party who copied and the party who had permitted the copying will be penalised equally.

For first-time offenders, they will be given zero mark for that assignment/assessment. In addition, their final grade will be reduced by one grade point (for example, from a B+ grade to a B- grade, from C grade to D grade). The plagiarism record will be kept in the undergraduate office of the school.

For repeat offenders, their final grade will be F

Since the prof told us (during lecture) that a group has been found copying and had been award 0 marks for their labs. This sets me thinking, for small codes. The similarity will certainly be there, especially if the CourseMarker restricts you to using certain stuffs. For example, no arrays, no loops or sort. Everybody will fall back to using individual variables and control structures like if-then-else.

How do they determine you plagiarised? If I wanted to I would change variables to another name add in unnecessary spaces and line breaks, change method names and such.

Headache. Thinking of which, somebody used my code before in poly days. I was dozing off in lecture theatre then I noticed the person was holding on to his printed out codes. I had a quick browse of the codes then I realised the coding style is similar to mine. Methods declared as similar but of different name. Have the liking of using arrays and controlled loops to create User Interface rather than typing out one by one for each objects.

I approached the person and asked where he got the code from but he insisted that he did it himself. Then I pointed to one line that left him dumbfounded.

public static void main(String[] shadowandy)
..

Then I told him, I didn’t know that your screenname is also shadowandy. Well, he lifted the whole code of mine, use search and replace option to replace strings. And yet he failed to notice at the very start of the whole program, my screenname is there. Only then he started to say the truth. Baaa…

So to people who intends to copy codes, do take note that some programmers like to leave their footprint / signature in their works; and I am one of them. Instead of hiding them, I made them so obvious in JAVA that people overlooked it.

Wow! Lab is getting tougher. More mathematical thinking required. Read the full post to look at the question. This actually took me around 5 hours to code and troubleshoot and conform to the test data. Although I still failed 4 sub test data.

Well, limiting where the triangle should rotate need some thinking. Playing around with mathematical rules and functions. >.< Read the rest of this entry »

It didn’t occur to me that computer cannot store floating points accurately.

float a = 1.0;
float b = 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1;

a != b

The value of b is infact 0.999999999999999

Pretty weird. That is why I failed one of the test data sets for my latest lab #3. Due to the inprecision of floating point calculation.

Workaround? Easy. Include a tolerance value / epsilon.

e.g
(Math.abs(a – b) < 0.00001) this will be true
whereas
(a == b) this will be false

Don’t know if this happens to ASP. Erik wanna try it out and tell me about the floating point computation of ASP and PHP?

for tomorrow’s CS1105 lecture, for I have done the latest Programming Lab #3. XD

Failed for one for the test data. Test data are unknown to us so dunno which is the test data I failed to compute correctly. Heck. See if others have the same problem.

Seems like people are still struggling with Lab #2