Monthly Archives: March 2013

CodingBat: Java. Array-3, Part II


For further help with Coding Bat (Java), please check out my books. I am also available for tutoring.


squareUp:

public int[] squareUp(int n) {
	int[] result = new int[n * n];
	int pos = 0;

	for (int i = 1; i <= n; i++) {
		for (int k = 1; k <= n - i; k++) result[pos++] = 0;
		for (int j = i; j > 0; j--) result[pos++] = j;
	}
	return result;
}

seriesUp:

public int[] seriesUp(int n) {
	int[] result = new int[n * (n + 1) / 2];
	int pos = 0;
	int i = 1;
	while (i <= n + 1) {
		for (int j = 1; j < i; j++) result[pos++] = j;
		i++;
	}
	return result;
}

maxMirror:

public int maxMirror(int[] nums) {
	int[] numsCopy = new int[nums.length];
	for (int i = nums.length - 1, j = 0; i >= 0; i--, j++)
		numsCopy[j] = nums[i];

	int max = 0;

	for (int i = 0; i < nums.length; i++) {
		int count = 0;
		int pos1 = i;
		int pos2 = 0;
		boolean flag = false;

		while (pos1 < nums.length && pos2 < nums.length) {
			if (!flag) {
				if (nums[pos1] != numsCopy[pos2]) pos2++;
				else {
					flag = true;
					count = 1;
					pos1++;
					pos2++;
				}
			} else {
				if (nums[pos1] == numsCopy[pos2]) {
					count++;
					pos1++;
					pos2++;
				} else {
					if (count > max) max = count;
					pos1 = i;
					flag = false;
				}
			}
			if (count > max) max = count;
		}
	}
	return max;
}

The input array is reversed to make the subsequent steps clearer to follow. This leads to slightly more code, but it should increase comprehensibility.

countClumps:

public int countClumps(int[] nums) {
	int count = 0;
	for (int i = 0; i < nums.length - 1; i++)
		if (nums[i] == nums[i + 1]) {
			count++;
			for (int j = i + 1; j < nums.length; j++)
				if (nums[j] == nums[i]) i++;
				else break;
		}
	return count;
}

At first I was tempted to use only one for loop and operate with a flag variable. Using a second for loop led to a more elegant solution, though. A neat detail is that the running time is linear since the nested for loop only increases i.


For further help with Coding Bat (Java), please check out my books. I am also available for tutoring.


CodingBat: Java. Array-3, Part I


For further help with Coding Bat (Java), please check out my books. I am also available for tutoring.


The Array-3 section on CodingBat only contains 9 exercises, but some of those can be quite intricate. My solutions should be fairly easy to follow. If something is unclear, then take a piece of paper, write down a few sample arrays, and trace the execution by hand. With array-based problems, this can be a good preliminary step before staring to write code.

All solutions were successfully tested on 10 March 2013.

maxSpan:

public int maxSpan(int[] nums) {
	if (nums.length > 0) {
		int maxSpan = 1;
		for (int i = 0; i < nums.length; i++)
			for (int j = nums.length - 1; j > i; j--)
				if (nums[j] == nums[i]) {
					int count = (j - i) + 1;
					if (count > maxSpan) maxSpan = count;
					break;
				}
		return maxSpan;
	} else return 0;
}

In line 7 count gets increased by 1 because the span is inclusive of the last element. If the array is empty, the return value is 0.

fix34:

public int[] fix34(int[] nums) {
	for (int i = 0; i < nums.length; i++)
		if (nums[i] == 3) {
			int temp = nums[i + 1];
			nums[i + 1] = 4;
			for (int j = i + 2; j < nums.length; j++)
				if (nums[j] == 4) nums[j] = temp;
		}
	return nums;
}

fix45:

public int[] fix45(int[] nums) {
	for (int i = 0; i < nums.length; i++)
		if (nums[i] == 5 && i == 0
			|| nums[i] == 5 && nums[i - 1] != 4) {
			int pos5 = i;
			for (int j = 0; j < nums.length; j++)
				if (nums[j] == 4 && nums[j + 1] != 5) {
					int temp = nums[j + 1];
					nums[j + 1] = 5;
					nums[pos5] = temp;
					break;
				}
	}
	return nums;
}

canBalance:

public boolean canBalance(int[] nums) {
	for (int i = 0; i < nums.length; i++) { 
		int sum = 0;
		for (int j = 0; j < i; j++) sum += nums[j];
		for (int j = i; j < nums.length; j++) sum -= nums[j];
		if (sum == 0) return true;
	}
	return false;
}

The variable i indicates where the array is split.

linearIn:

public boolean linearIn(int[] outer, int[] inner) {
	int indexInner = 0;
	int indexOuter = 0;
	while (indexInner < inner.length && indexOuter < outer.length) {
		if (outer[indexOuter] == inner[indexInner]) {
			indexOuter++;
			indexInner++;
		} else indexOuter++;
	}
	return (indexInner == inner.length);
}

For further help with Coding Bat (Java), please check out my books. I am also available for tutoring.


Review: Think Again: How to Reason and Argue — Coursera

Most MOOCs follow a strict schedule with weekly deadlines. I was thus quite surprised when I learnt that Think Again: How to Reason and Argue, which started on 26 November 2012, had just one deadline for all assignments, which happened to be 11 March 2013. Since I had some spare time last week, I decided to go through the entire class in the evenings.

At first, I expected a class that was more similar to Michael Genesereth’s Introduction to Logic, but this wasn’t the case at all. Instead, Walter Sinnott-Armstrong (Duke University) and Ram Neta (University of North Carolina at Chapel Hill) gave a 12 week course on “informal logic”. This isn’t a term I just made up, though, but one I have taken from the subtitle of the recommended textbook.

Compared to a typical course in logic as you might find it on a computer science or philosophy curriculum, Think Again has a much different focus as it attempts to teach how one could evaluate arguments in everyday contexts.

The syllabus structures the course into four distinct parts:

  • Analyzing argument
  • Deductive arguments
  • Inductive arguments
  • Fallacies and refutations

Later on, this review will sound rather critical, therefore let me straight away state that Walter Sinnott-Armstrong and Ram Neta largely succeeded. If you make it through the course, you will be able to more critically analyze the kind of arguments you encounter on your favorite blogs or in mainstream media, and if you watch Fox News, you’ll probably stop doing so by week two or three.

The first part consisted little more than textual analysis. You’ll learn how arguments can be strengthened or weakened, or why it’s not that great of an idea to make unfalsifiable statements. Overall, that part moved very slowly, but the pace picked up in the second part. Ram Neta offered a gentle introduction to propositional and categorical logic. I would have expected some first-order logic, and at least an intro to proofs in propositional logic.

I found Ram Neta’s teaching to be of uneven quality, which was also reflected in many negative comments on the forums. I did enjoy his sometimes whimsical presentation, like his illustration of the logical connective “and” by putting a book between his foot and his hand:

Ram Neta

That’s nothing any of my former philosophy professors would have done.

However, he sadly had a tendency to often ramble on and repeat himself over and over. This was even more bothersome because some concepts which you would have expected to be taught in the lectures were introduced in the quizzes. Out of the blue you were hit with the definition of, say, a conjunction introduction argument, and asked to identify it among the answer choices. I can’t imagine that this is how those two professor teach their course at Duke. I’d assume that to some degree the lectures were ad libbed, and when they later on realized that they forgot to cover some concepts, they simply added them to the quizzes.

The third part was refreshing as it incorporates probability theory and set theory, but nothing that should be unknown if you’ve paid attention in high school. Knowledge about various statistical biases would do a lot of people good. I do believe that those who misinform with statistics do so deliberately, but some very basic knowledge of statistics could at least make some people more skeptical of the kind of flawed reasoning that is all too common in mass media.

In the final part, various logical fallacies were discussed, and in the final week, arguments that were submitted by students were picked apart. Overall, part four was rather weak, and many of the minor issues you were willing to overlook in the previous became quite annoying. I will now proceed with describing what I perceive to be the main problems with “informal logic” ask taught in Think Again, but before I do so, let me reiterate that I thought the course to be pretty good. What follows is therefore a discussion of some of the negative aspects that are in no way representative of the entire course.

One big problem I saw with “informal logic” is that natural languages are inherently vague, and therefore any attempt to precisely reason about language is doomed to failure. I will give one particularly striking example. In one of the lectures, Ram Neta discusses what philosophers call the “sorites paradox”. The two premises are:

1) One grain of sand does not constitute a heap.
2) Adding one additional grain of sand doesn’t turn a non-heap into a heap.

This might seem plausible enough, but the conclusion is that no matter how many grains of sand you add, you’ll never end up with a heap, which is obviously nonsensical. The problem is simply that “heap” is a vague term. I consider it to be perfectly valid when someone states that he knows what a heap is when he sees one, just as you know when someone is, say, tall, rich, or bald.

We could of course spend many hours debating the problem of vagueness in natural language and feel oh-so-smart when we point out that if losing one hair doesn’t make the difference between being bald or not-bald, then you can never get bald. However, it’s probably more productive to simply formalize the language and move on. Vagueness may be an interesting philosophical problem, but it’s of limited relevance in everyday contexts. Just imagine you were to write a program that determined which number of grain constitute a heap. You’d simply pick a reasonable value and be done with it.

The same is true of another linguistic ambiguity. Consider the following sentence:

Carol went to the bank.

If you now sit back in awe, then you’d fit right into a freshman philosophy class. Of course, “bank” could refer to a financial institution, or it could refer to the bank of a river. However, it’s incredibly difficult to mess this up in normal conversations, and the examples people construct in philosophy classes are more than just a bit tiring. Yes, this is a case of ambiguity, and to get around this, you could either use an artificial language like Lojban, or you point out to your students that there is no equivalence between both words. In a dictionary, there are two entries for “bank” for this very reason. In a philosophy class, you could make it clear to the densest student by using subscripts or variables. Let the bank of a river be P, and the financial institution Q. So, Carol went either to P or Q, and with that there is suddenly no need to waste any time discussing particularities of the English language. All of a sudden, many “philosophical” problems are cleared up.

Logical fallacies are certainly an important topic, yet in this course, the professors went overboard. Instead of discussing, say, the structure of an ad hominem argument, Ram Neta insisted on classifying them as “deniers”, “dismissers”, and “silencers”, and each could be either justified or unjustified. Yet, knowing an arbitrary distinction is not really what matters, given that recognizing an ad hominem in the first place is much more valuable.

Of course, knowing those distinctions was necessary for passing the quizzes. Here is one argument, taken from week 10:

During Senate testimony concerning the BP oil spill in the Gulf of Mexico, BP executives were being questioned about the safety procedures that they implemented on all their oil rigs. An environmental activist who was sitting in the audience stood up during one executive’s testimony and interrupted the testimony, shouting that the executive was lying, and holding up physical evidence that belied the claims that the executive was making. Given the circumstances, we must not consider the activist’s testimony or evidence. Therefore, unless we have any evidence independent of what the activist provided, we must simply assume that the executive was telling the truth.

You then had to choose between the six possible permutations of ad hominem arguments. The supposedly correct answer was that it was a “justified silencer”. Look at this explanation:

[T]he argument is a justified silencer because, in order to have a right to testify in court, one’s testimony has to be presented in accordance with the rules of the courtroom. Since it goes against these rules to merely stand up and start shouting during the testimony of another witness, it follows that, if the activist in (4) presents her testimony by shouting it during a Senator’s testimony, she does not, in fact, have the right to be heard then.

I found this to be a particularly bad example since it relied not on the validity of the argument itself but on circumstances. If the activist did indeed present compelling evidence, then merely being in a court of law does not negate it. You could very well believe that the executive was lying, based on the evidence the activist provided, even though the court (!) would not be in a position to acknowledge the evidence. To spell it out: Yes, the evidence can be inadmissible in court but at the same time prove beyond doubt that the executive has been lying.

Here is another example argument from the course:

A large majority of Americans currently believe that the most effective way for the US Government to grow the economy in the next 3 years is by reducing its spending. In a democracy, the voters decide. Therefore, the most effective way for the US Government to grow the economy in the next 3 years is by reducing its spending.

Sadly, there are too many problems with this argument. First, there is no way to reliably estimate what a “large majority of Americans” currently believe. At best, it’s an extrapolation based on a sample. Second, in a democracy, the voters don’t decide at all. You’ve got the chance to cast a vote every few years, and your choice may, like in the US, be limited to two candidates from a very similar political spectrum. Modern democracy has little to do with the Greek root of the word, and even ancient Greeks democracy wasn’t a democracy, considering that their society was built on a minority exploiting slaves. You’d really wish you’d only see some Ps and Qs on the screen instead of this garbled mess, and if you wanted to discuss this argument, it would best be done in essay form.

This wasn’t all, though. Here is the very next argument from that exercise set:

According to one recent lexicographical study, a large majority of native English speakers in the United States think that ‘chillaxing’ is a synonym of ‘relaxing’. Therefore, it is true that ‘chillaxing’ is a synonym of ‘relaxing’.

(a) justified appeal to popular opinion
(b) unjustified appeal to popular opinion
(c) justified appeal to authority
(d) unjustified appeal to authority
(e) none of the above

Again, you can’t accurately determine what a larger majority of English speakers thinks, but even if we ignore this problem, there is an even larger issue that may be familiar to you if you’ve studied linguistics. The issue is whether linguistics should be descriptive or prescriptive. One one extreme you’ve got people who believe speakers of a language do not have the authority to determine what constitutes acceptable use. Instead, they think they have to set rules for them. A prominent example is the French Academy, which is the authority on the French language. Thus, if 70% of French speakers thought that “chillaxer” was a synonym for “relaxer”, but the French Academy didn’t, then it simply wouldn’t be a synonym. To use an argument by analogy, the French Academy acts as a law maker, and decides what is right or wrong, and they can of course be completely off the mark, just like lawmakers sometimes are as well. Still, the fact that they are an authority means that they can ignore what the majority might think.

The consequence is therefore that you could justify at least three of the answer choices. The third is “none of the above”, which might imply that more than one choice is correct.

An integral part of the MOOC experience are the discussion forums. However, I have rarely seen this part executed well. I saw a few examples in more advanced courses where posts were generally of a high quality, and where moderators had no qualms just deleting inappropriate comments, or quickly pointing out errors in potentially misleading posts. Think Again followed a laissez-faire policy, and the consequence was that you could find staggering amounts of bullshit, which would have made Dunning and Kruger proud.

To provide you with the necessary context, here is an exercise from week 8:

What is the expected financial value of a bet where you will win $2652 if you draw a seven of spades and then a seven of clubs on two consecutive draws (without returning the first card to the deck)?

The correct answer is $0, which is the result of this calculation:
(1/52 * 1/51) * (2652-1) – (1 – (1/52 * 1/51)) * 1).

Let me just walk you through it step by step:

  • There are 52 cards in a deck, and you don’t put the card you first draw back. Thus, the probability of drawing a seven of spades, and then a seven of clubs is 1/52 * 1/51 = 1/2652.
  • If you draw this combination of cards, you win $2652 – $1, since the dollar you initially put in doesn’t get refunded. Considering the probability of this event, the gross gain from winning is therefore 2651/2652.
  • The probability of losing is (1 – 1/2652) = 2651/2652. Multiply this value by the one dollar you put in.
  • Add it all up and you end up with (1/2652) * $2651 – (2651/2652) * $1 = $0

But let’s look at a discussion in the forum. One guy was stumped, and asked for help. Plenty were willing to chime in, including one particular person who wrote:

[Y]ou are not accounting the fact that if the person doesn’t get the right card in the first draw, he wouldn’t pick the second card at all. So to calculate the probability of losing, you actually need to consider two cases:
1. the first card picked is not correct. the probability of this happening is 51/52. Since he doesn’t pick the second card here, we do not multiply this by the probability of picking the wrong card in next draw.
2. the first card picked is correct but the second card picked is incorrect. here the probability of losing is 1/52 * 50/51=50/2652.
now, both these cases are mutually exclusive. so you can add the two probabilities to get the probability of losing overall as 2651/2652, which gives you the correct answer.

This wrong. The question clearly states that two picks are made. There is no room for fantasizing that the bettor would walk away if he picked the wrong card in the first draw. This was bad enough, but then the person who originally asked the question replied:

[EDIT: I made a mistake here. That guy presented an alternative solution that is equally correct. I made the wrong evaluation after reading the first point. Please see the comment by Ed McCardell below if my error isn’t obvious to you.]

Thank you.

I have given up and have left this exercise (only because of Q7 and Q8) in a backburner until a deadline, but your post helped me to think over it again. In my post above I complicated the solution and confused myself (hopefully, not other forum readers!). Thanks again.

It’s a case of the blind leading the blind, and you can witness the same over and over. There is a good reason why universities don’t just put students in a room and tell them to figure everything out by themselves.

Lastly, there were some platform-related issues. Coursera is growing rapidly, and some technical difficulties are therefore to be expected. I did notice prolonged loading times when navigating course content. This refers both to waiting for a video to load as well as simply navigating the site. In addition, there was a particular problem with the videos, and it’s a bug I find quite easy to reproduce: whenever you pause a video, and too much time passes before you continue, then the remainder of it won’t get streamed. After a few moments the video freezes, and you’ll have to reload the page to continue.

I don’t want to end this review with just a lengthy discussion of the flaws I found, though. Overall, I did enjoy Think Again: How to Reason and Argue. It provided me with many enjoyable hours often filled with interesting problems. If you are looking for a gentle introduction into logic and enjoy abstract reasoning, then this course might be for you, provided you can look past some of the issues and won’t require much feedback from the forum. Expecting a flawless experience from a MOOC is probably too much to ask. I have taken dozens of courses in brick-and-mortar universities, and quite a few of those had issues far greater than any of the MOOCs I have taken since.

CodingBat: Java. Array-2, Part III


For further help with Coding Bat (Java), please check out my books. I am also available for tutoring.


tripleUp:

public boolean tripleUp(int[] nums) {
	for (int i = 0; i <= nums.length - 3; i++)
		if (nums[i + 1] == nums[i] + 1 && nums[i + 2] == nums[i] + 2)
			return true;
	return false;
}

shiftLeft:

public int[] shiftLeft(int[] nums) {
	if (nums.length > 0) {
		int first = nums[0];
		for (int i = 0; i < nums.length - 1; i++)
			nums[i] = nums[i + 1];
		nums[nums.length - 1] = first;
	}
	return nums;
}

tenRun:

public int[] tenRun(int[] nums) {
	boolean replace = false;
	int multiple = 0;

	for (int i = 0; i < nums.length; i++) {
		if (nums[i] % 10 == 0) {
			if (!replace) {
				replace = true;
				multiple = nums[i];
			} else
				multiple = nums[i];
		}
		if (nums[i] % 10 != 0 && replace) nums[i] = multiple;
	}
	return nums;
}

pre4:

public int[] pre4(int[] nums) {
		int count = 0;
		for (int i = 0; i < nums.length; i++) {
			if (nums[i] != 4) count++;
			else break;
		}
		int[] result = new int[count];
		for (int i = 0; i < result.length; i++)
			result[i] = nums[i];
		return result;
}

post4:

public int[] post4(int[] nums) {
	int last4 = 0;
	for (int i = 0; i < nums.length; i++)
		if (nums[i] == 4) last4 = i;
	
	int[] res = new int[nums.length - (last4 + 1)];
	for (int i = last4 + 1, j = 0; i < nums.length; i++, j++)
		res[j] = nums[i];
	
	return res;
}

notAlone:

public int[] notAlone(int[] nums, int val) {
	for (int i = 1; i < nums.length - 1; i++)
		if (nums[i] == val && nums[i - 1] != val
			&& nums[i + 1] != val)
			nums[i] = Math.max(nums[i - 1], nums[i + 1]);
	return nums;
}

zeroFront:

public int[] zeroFront(int[] nums) {
	int[] res      = new int[nums.length];
	int zeroPos    = 0;
	int nonZeroPos = res.length - 1;

	for (int i = 0; i < nums.length; i++)
		if (nums[i] == 0)
			res[zeroPos++]    = 0;
		else
			res[nonZeroPos--] = nums[i];

	return res;
}

Note that the order of the non-zero numbers does not matter. For an alternative solution that modifies the given array, please see the comment by ‘aaaaaaaa’ below.

withoutTen:

public int[] withoutTen(int[] nums) {
	int[] copy = new int[nums.length];
	int index = 0;

	for (int i = 0; i < nums.length; i++)
		if (nums[i] != 10) {
			copy[index] = nums[i];
			index++;
		}
	return copy;
}

zeroMax:

public int[] zeroMax(int[] nums) {
	int largestOdd = 0;
	for (int i = nums.length - 1; i >= 0; i--) {
		if (nums[i] % 2 == 1 && nums[i] > largestOdd)
			largestOdd = nums[i];
		if (nums[i] == 0)
			nums[i] = largestOdd;
	}
	return nums;
}

evenOdd:

public int[] evenOdd(int[] nums) {
	int[] res   = new int[nums.length];
	int evenPos = 0;
	int oddPos  = res.length - 1;

	for (int i = 0; i < nums.length; i++)
		if (nums[i] % 2 == 0)
			res[evenPos++] = nums[i];
		else
			res[oddPos--]  = nums[i];
	return res;
}

The solution is similar to “zeroFront”, which is given above.


For further help with Coding Bat (Java), please check out my books. I am also available for tutoring.


CodingBat: Java. Array-2, Part II


For further help with Coding Bat (Java), please check out my books. I am also available for tutoring.


no14:

public boolean no14(int[] nums) {
	int ones = 0;
	int fours = 0;
	for (int i = 0; i < nums.length; i++) {
		if (nums[i] == 1) ones++;
		if (nums[i] == 4) fours++;
	}
	return ones == 0 || fours == 0;
}

isEverywhere:

public boolean isEverywhere(int[] nums, int val) {
	boolean flag1 = true;
	boolean flag2 = true;

	for (int i = 0; i < nums.length; i += 2)
		if (nums[i] != val) flag1 = false;

	for (int i = 0; i < nums.length - 1; i += 2)
		if (nums[i + 1] != val) flag2 = false;

	return flag1 || flag2;
}

either24:

public boolean either24(int[] nums) {
	Boolean twos = false;
	Boolean fours = false;

	for (int i = 0; i < nums.length - 1; i++) {
		if (nums[i] == 2 && nums[i + 1] == 2) twos = true;
		if (nums[i] == 4 && nums[i + 1] == 4) fours = true;
	}
	return twos ^ fours;
}

The caret (^) in the return statement represents the logical XOR operator.

matchUp:

public int matchUp(int[] nums1, int[] nums2) {
	int count = 0;
	for (int i = 0; i < nums1.length; i++)
		if (nums1[i] != nums2[i]
			&& Math.abs(nums1[i] - nums2[i]) <= 2)
				count++;
	return count;
}

has77:

public boolean has77(int[] nums) {
	for (int i = 0; i < nums.length - 1; i++)
		if (nums[i] == 7 && nums[i + 1] == 7) return true;

	for (int i = 0; i < nums.length - 2; i++)
		if (nums[i] == 7 && nums[i + 2] == 7) return true;

	return false;
}

has12:

public boolean has12(int[] nums) {
	int one = 0;
	int two = 0;
	for (int i = 0; i < nums.length; i++) {
		if (nums[i] == 1) one = i;
		if (nums[i] == 2) two = i;
	}
	return two > one;
}

The two variables keep track of the position of the number 1 and 2, respectively. After the for loop has finished, they will contain the position of the last 1 and last 2 in the array.

modThree:

public boolean modThree(int[] nums) {
	for (int i = 0; i <= nums.length - 3; i++) {
		boolean cond1 = nums[i] % 2 == 0 && nums[i + 1] % 2 == 0
				&& nums[i + 2] % 2 == 0;
		boolean cond2 = nums[i] % 2 == 1 && nums[i + 1] % 2 == 1
				&& nums[i + 2] % 2 == 1;
		if (cond1 || cond2) return true;
	}
	return false;
}

haveThree:

public boolean haveThree(int[] nums) {
	int count = 0;
	int pos = -2; // in case nums[0] == 3

	for (int i = 0; i < nums.length; i++) {
		if (nums[i] == 3) {
			count++;
			if (i - pos == 1) return false;
			pos = i;
		}
	}

	return count == 3;
}

twoTwo:

public boolean twoTwo(int[] nums) {
	for (int i = 0; i < nums.length; i++)
		if (nums[i] == 2) {
			int count = 0;
			for (int j = i; j < nums.length; j++)
				if (nums[j] == 2) count++;
				else break;
			i += count;
			if (count < 2) return false;
		}
	return true;
}

sameEnds:

public boolean sameEnds(int[] nums, int len) {
	for (int i = 0, j = nums.length - len; i < len; i++, j++)
		if (nums[i] != nums[j]) return false;
	return true;
}

The for loop traverses the array from back to front and front to back simultaneously.


For further help with Coding Bat (Java), please check out my books. I am also available for tutoring.