| Date | Date | Date | Date | Date | Date | Date | ||||||
| 08/24/06 | 09/07/06 | 09/21/06 | 10/05/06 | 10/24/06 | 11/07/06 | 11/21/06 | ||||||
| 08/29/06 | 09/12/06 | 09/26/06 | 10/12/06 | 10/26/06 | 11/09/06 | 11/28/06 | ||||||
| 08/31/06 | 09/14/06 | 09/28/06 | 11/17/06 | 10/31/06 | 11/14/06 | 11/30/06 | ||||||
| 09/05/06 | 09/19/06 | 10/03/06 | 10/19/06 | 11/02/06 | 11/16/06 |
On the first day of class, we discussed the Warm Up Problem. Mike came up with the first idea for a solution; he suggested using the StringTokenizer in Java. This allows us to break a string up into individual words. However, we still had to glue the words back together to get the output. Aaron showed us how to do that with string concatenation. His pseudocode was as follows.
String result = "";
while (tokenizer.hasMoreElements()) {
result = token.nextElement()+result;
}
Everyone seemed to be happy with this, and the instructor didn't tell us anything was wrong. However, Aaron immediately noticed a problem with this, namely that the output will not have any spaces in it (because a StringTokenzier drops the spaces when it returns the words). He fixed this with the following pseudocode.
String result = "";
while (tokenizer.hasMoreElements()) {
result = token.nextElement()+" "+result;
}
Afterwares the instructor told us that it was up to us to find errors; he would point out very large errors, or give us some hints, but it was our responsibility to evaluate each other's work. Alex immediately took this advice and pointed out one more mistake in the code above: it puts an extra space at the end. Alex suggested that we fix this by adding a boolean to test if it was the first time going through the loop, and only add spaces after the first time was completed.
At this point, everyone (including the instructor) seemed happy that we had solved the problem. However, we noted that the solution above is very inefficient. Java Strings are immutable, which means they cannot be changed. So string concatentation does not add to an existing string; it makes a new string. How many strings are created? After some discussion, the instructor gave us the String "A B C D E F G H I". He pointed out that this pseudocode will create (at least) the following strings:
A B A C B A D C B A E D C B A F E D C B A G F E D C B A H G F E D C B A I H G F E D C B A
Someone in class noted that, if the string is length n, this is the sum of the first n numbers. So the program uses O(n2) memory (and at least that much time).
At this point the instructor challenged us to solve the problem using linear memory. Aaron suggested that instead of making strings, we make a character array to write the output in. This gets around the fact that Java Strings are immutable; a character array is just a mutable string. The instructor thought this was an interesting idea and challenged us to write a program that does this.
Alex suggested a way to do the program in C. The difference with Alex's suggestion is that string concatenation in C actually adds to the string (because C strings are mutable), and does not create a new string. One of the students pointed out that Alex had really reinvented a tokenizer using C functions. However, Alex's approach is still better because it does not create new strings. The instructor also suggested that it would be nice to see the source code for this.
Finally, the instructor challenged us to do this in place (using constant memory). Mike showed us a clever way to do this.
At this point the class was over. The instructor challenged us to write code for the two linear-space solutions. He also asked us to come up with another way of solving the in-place problem, particularly one that was "closer" to the linear-space solutions.
Today we finished up our discussion of the Warm-up problem. Alex started off the class by showing us her linear-space solution to the problem in C. Her solution was very interesting in that she inserted nulls ('\0') into the string to change its length. Unlike Java, that stores its length as a number at the beginning of a string, C strings determine their length by reading until they reach a null character. As we discussed in class, this means that determining the length of a string is O(n) in C, while it is O(1) in Java.
The instructor also talked about malloc and free. Malloc is the equivalent of "new" in Java; it creates memory for new objects. While we don't have objects per-se in C, we do need them to create arrays and strings, just like in Java. The instructor pointed out that we do not have garbage collection in C, like in Java, so we must always remember to free our objects. There are several tutorials online on how to use malloc and free.
Next Colin Barth showed us an in-place solution. His solution was not the clever "reverse the words, then the string" that we talked about last time. Instead, it was a generalization of the linear solution. While it works, the solution was O(n2).
We ended the class with a new problem. This problem was closer to the style of the competition problems. It has a specified input file that must be used, and requires the user to output the answer in a specific way. We learned that competition problems use this to format to check the solutions; if the output is not exactly correct, then the answer is wrong.
We first talked about how to parse the input line-by-line. For input such as the numbers, we need a way to convert from strings to numbers such as Integer.parseInt() in Java or atoi() in C. We also needed to be able to break the "rules" up into first word, second one. One student suggested that we put these in a hashmap. The first word is the key, while the second word is the value. This allows us to look up what each word should be changed to.
Aaron pointed out that there were way too many ambiguities in this problem. For example, what if we had the following two rules:
"dog" to "cat" "cat" to "mouse"
Should we change "dog" to "mouse"? In this case, the instructor told us that our solution should be "one pass". That is, we should apply each rule to the original document and get a whole new document; we should never replace on an editted document. That way "dog" changes to "cat" only.
Aaron also pointed out that we had to worry about other ambiguities. What if a word appears twice on the left-hand side, or one word is a substring of another, like
"cat" to "mouse" "catch" to "throw"
In this case, how would we process "catcher"? Even worse, suppose we had the rule
"aa" to "bb"
and told to process "aaa". Do we replace the first two "aa"s or the second two. For these problems the instructor promised us that the input would never have these problems, so we can ignore them. In general, that is how we will resolve ambiguities in the future. Either we will make the problem clearer, or we will recognize that they can never happen in the input set.
At this point we ended the class. Tom Wexler will be substitute teaching the next class.
Problem 1 Discussion
Problem 2 Discussion
Discussed the Wiki, uploading code to the internet, and posting solutions to the Wiki.
Review of problem one and what was learned: Brendon mentioned Ambiguities and how to deal with them. Mike mentions the two algorithms that could be used to solve this problem: Searching for every word or checking each start-letter. Also, discussed different ways of storing the key - value pairs for this problem. The two methods mentioned were a Hash Map or a Trie. Mike diagrams how his program used a hash map to check for every word at every starting character. Discussion of the right data structure to use, depending on the algorithm one is using.
"Design is Iterative." When designing a program, we try one way of doing things, and if it doesn't work, try something else. Also, make efficiency changes as we see that they can be made. For example: See that hash map isn't the best way of storing data, so switch to a trie. Then we have to make all the changes to the program to account for the new data structure, which may bring up more complications, until no more changes may need to be made. Went on to discuss ambiguities of Problem two, including how to deal with multiple occurances of the first word and the order used to decide which occurance to use.
George discusses his solution to Problem 2. Briefly discussed 'structs', a way to do OOP with C. He uses a 'struct' to hold 4 numbers defining word position in grid. His program goes through entire grid looking for each word, as opposed to checking each character in grid for all words. Uses recursion to choose direction. Discussion of his use of s simpler 'containing method' that houses the more complex recursive method.
Brendon discusses his solution that uses the Pearl programming language. His program has a different function for checking a word in each direction. One problem we discussed is that this method of checking is hard to debug, but his solution is successful when running with a test input.
Discussion of the next problem: Problem 3 which is to be posted on the web. It involves taking a paragraph that is not nicely formatted and converting it to a formatted paragraph. Example:
This is an Ugly Looking paragraph Should be converted to: This is an ugly Looking paragraph.
Today in class, the instructor started with a few announcements. He announced that there would be a programming contest (with prizes!) sponored by the ACSU on October 22. Unfortunately, this will be too late to use as a run-off for our team to represent us to the regionals, as they have moved the regionals forward this year to October 29th. That means that we will be holding tryouts within the next two weeks. More news will be made available, as necessary.
He also chastized us for not adding to the Wiki.
He started off the class with a new problem. This problem was different from the last couple of ones in that it was not only about string manipulation; it was also about sorting.
As usual, the first thing we needed to do was parse the text. Everyone was pretty comfortable with using a tokenizer by now. The only question was what data structure to use. Mike suggested we create a Person class, with fields for first name, last name, height, and weight. In this case, all we needed to do was to parse the file into an array of these Person objects, which we could then sort.
Given this data structure, Alex came up with the idea:
Stable sorts do not change the order of ties. So if we order the following pairs by first number
| (1,3) | (3,0) | (2,4) | (1,2) |
we would get
| (1,3) | (1,2) | (2,4) | (3,0) |
Otherwise we would have no guarantees on the order of (1,2) and (1,3). Alex pointed out to us that merge sort is stable, so she could write that. At this point the instructor reminded us to "not reinvent the wheel". We should always use libraries when available. The API will tell us if it is stable or not.
The class seemed to be pretty sure that this algorithm would work. Mike did not have a proof that it would work, but he did come up and given an example of the algorithm using three digit numbers, sorting on each digit. Everyone seemed convinced by this argument. The instructor told us that arguing with examples is actually okay in helping us solve a problem, provided that we can be sure that this example accurately captures the "important features" of the problem. After some discussion, everyone felt that was the case here, so we moved on.
Brenden had an alternate idea where he would take Mike's Person class and combine the fields into a single number, which he would use to order the suitors. He would take the height and weights and multiply them by different weights (e.g weight by 1,000,000, height by 10,000) in order to give them different preference. The names would have to be encoded into integers first (using 1 for "A", etc.) and then given lesser weights. People thought this was a good idea in general, but that his weights we not big enough to keep the fields "separate". Everyone was particularly concerned about suitors with really big names, like "Mary Supercalifragilisticexpialidocious"
George suggested that, instead of converting everything to integers, converting everything to strings. If the strings were concatenated in the right order, this would have the same effect. There was some concern that the string "742" comes before "75", but George pointed out that we could solve that by finding the size of the biggest number, and padding everything else with 0s in the front.
At this point, the class felt like it had adequately solved the problem. However, the professor teased the class that there was a much easier way to do the problem. The class was stuck, however, and he moved on.
The instructor introduced us to a variation of the problem. Alex suggested that a solution was to sort the array normally first, and then move all of the "bad" suitors in the end. The class realized that this sounded very similar to moving the zeroes in Warm Up Problem 2. However, in that problem all zeroes are equal. This problem was a little more difficult because we had to remember the information for each suitor.
Colin suggested another solution where we first scan through the information and put people into "good buckets" and "bad buckets". We then sort each bucket and concatenate them together to get the final answer. However, there was still the problem of determining when a suitor went in a bad bucket. A suitor does not automatically go in the bad bucket when he is overweight; there must be another suitor of the same height difference that weighs less.
At this point, the instructor showed us how this problem is similar to "duplicate elimination". Suppose we want to eliminate duplicates in the following array:
| 2 | 1 | 2 | 4 | 1 | 3 | 1 |
This is much easier to do if the array is sorted.
| 1 | 1 | 1 | 2 | 2 | 3 | 4 |
In this case, we read through the array once. At each step we keep track of the current number, and skip ahead until we see a different number.
Finally, near the end of class, Robert realized that the easy way to solve the problem was to use something like a Comparator object. A Comparator is just a means of defining "less than"; compare(x,y) returns
If we want to change the order of objects, we do not need to write a new sorting algorithm. All we need to do is to redefine our less-than. For example, to sort integers in ascending order, we use the comparison function
int compare(int x, int y) {
return x-y;
}
However to sort integers in descending order, we use the comparison function
int compare(int x, int y) {
return y-x;
}
The instructor ended the class telling us that we will almost never need to write a sort algorithm in real life. Instead, we will only need to write "less-than" functions.
Instructor recapped the results of our last class when we came up with ways to sort the list for problem 4. The ideas were: -Ierative stable sorts -String concatenation -Integer coding -Comparators
Mike shows his algorithm for solving problem 4. He created an algorithm that uses four sorts each of which uses a comparator. His comparators had to handle a case insensitive search which was done by comparing characters mod 32.
Another solution was shown by Robert. He created a person class that implements comparable so that there is only one sort necessary.
The instructor then discussed another intricacy of the problem. He showed that there were many different ways to sort pairs of integers. He pointed out that sorting first by the first number then by the second number of the pair is called lexicographical ordering.
(1,0) (2,3) (3,1) (4,2) (2,2) (1,3)
sorts to
(1,0) (1,3) (2,2) (2,3) (3,1) (4,2)
We start discussing problem 5. There is a shoemaker who is given a list of jobs. Each job has a number of days that it takes to finish and a penalty for the number of days he delays before starting. Sample data:
Job Days Penalty 1 3 4 2 1 1000 3 2 2 4 5 5
Supposing he goes in order
days 1-3 job 1 day 4 job 2 days 5-6 job 3 days 7-11 job 4 job 1 no penalty job 2 3 * 1000 = 3000 penalty job 3 4 * 2 = 8 penalty job 4 6 * 5 = 30 penalty
We look at more sample orders to show that they result in different penalties. The idea here is to look at some examples to see what sort of orderings are better than others. The first simple heuristic is to move the highest cost one to the front. We offer a counterexample with the following data:
Job Days Penalty 1 2 100 2 1 99
If we move the 100 first then it will delay the 99 for 2 days costing 198 but the other ordering will only delay the 100 1 days so it will only cost 100. Another idea is presented by Ken. The idea is to get a value by multiplying the penalty by the difference of the days to do it and the current day.
Mike has another suggestion. He divides the days by the penalty for each job and sorts by this in ascending order.
Alex suggests a solution that creates a grid of penalty and days remaining after the current one. Multiplying the two values should order then to minimize the penalty. Solution retracted.
We return to Mike's solution. It seems to work for our example input. The class is given the challenge to find a proof or counterexample for Mike's algorithm.
The instructor explains the idea that we should play with small input sets and build up to larger sets and eventually the arbitrary input.
Problem 6 is handed out. We are given some time to think about it. We start off discussing with a sample of only three inputs.
Intructor's Note: Because my drive died, this is going to be a short journal. I am trying to recover the basic ideas from memory. I know what we covered, but I cannot remember whom exactly to credit for what. For that I apologize.
Today in class, we talked about Problem 6, which the instructor noted is a notoriously hard problem. This lesson that we learned from last time for working on this type of problem is to reason on small inputs. From last class we figured out that 4 people was the first interesting case.
In this case, suppose we have people with crossing times a <= b <= c <= d. We figured out that we always wanted to bring 2 over and send only 1 back (that way we make progress). We focused on two possibilities
We convinced ourselves that the other orders were slower than this. Why? Look at the cost of these two.
We always have to bring d across, so it will cost us at least that much. There is no benefit to bringing it over with b as it is cheaper to shuttle a back with the flashlight. Clearly this is the fastest way to bring it over with c (just enumerate the possibilities). For the other case, we have to bring c over with someone else, and again enumerating the possibilities we see that it is a.
Which one of these do we choose? To use the first strategy, we need the inequality
which simplifies to
If this inequality holds, we use the first strategy. Otherwise we use the second.
We had similar results for the case with 5 people. The hard part, however, is turning this into a general algorithm. There was some consensus that we do it as follows.
We all admitted that the "repeat" step is a bit fuzzy and vague (what do we do with the b?). So the instructor told us to try an solve it outside of class.
After this we talked about how we could even prove that this general algorithm worked. No one had any clue. So the instructor introduced us to the concept of "empirical testing". The idea is such
As the instructor made quite clear, this is definitely not a lesson that you should do in comercial software. However, it is certainly a "Hail Mary" approach that works in competitions.
In order to brute force the answer, we needed to be able to list all possible (or at least all "acceptable") crossings, and search for the correct one. We realized that this is very difficult. So, instead, the instructor gave us a warm-up problem. Given n, he asked us to
This was similar to the listing of crossings as
This warm-up problem and coding the flashlight problem were left for next time.
Professor White's hard drive went belly up and he is trying to get it fixed.
The first topic of the class was working on a previous problem. The goal is to print all the subsets of a set.
George tried to extract an algorithm from a proof.
int factorial (int N)
{
if (N == 0)
return 1;
return factorial(N-1);
}
We talked about a decision tree for case.
{1,2,3,4}
Each of the subsets is a leaft of the tree.
Alex proposed a solution that would use a 2^n elements of an array.
However, Speed is not a problem with today's computers, Memory is. A tree can be bushy and it can be optimized later. If a tree is very deep, it is a much worse scenario.
Use java.util! it is very useful, no use reinventing the wheel.
A BST is not needed to solve this problem. We just need sets.
Reviewed solution finding permutations of a set in place. It is okay that the algorithm is inefficient, as long as it does not take up a lot of space.
It is acceptable to create 1 new array for this problem. However, Creating a new array for each subset is not acceptable.
We started off with a very hard problem to gauge our skill level. Then the problem was broken down and made easier for us step by step. We are learning how to solve problems, how to break them down into simplier problems.
Combinations are Subsets
We received Warm-Up Problem 3 which deals with printing subsets.
Everyone should try to write this code.
We received new Problem 7 which is a substantially easier than the flashlight problem.
ANNOUNCEMENTS
CLASS
George had an interesting solution to subsets problem. In pseudocode:
Subsets(nums, n, bools, startingvar)
{ if(s==n-1)
{ bools[s] = true;
print;
bools[s] = false;
print;
}
else
{
bools[s] = true;
subsets(nums,n,bools,s+1);
bools[s] = false;
subsets(nums,n,bools,s+1);
}
}
Similar to permutations where you swap things and then swap them back. In this case you set it true and then set it false.
Trees are great. Use trees. Trees are big, but you can still use them, because you're only looking at one branch. You can forget about a branch once you look at it and move to the next one without using up much memory. All you ever have to compute is a single branch. The only problem now is time to compute all the branches. But time is much easier to handle than memory. So it's OKAY! Exhaustive Search: goes through all possibilities to determine the answer.
So for the Bridge Problem, we want the best possible crossing sequence. Can we do exhaustive search on the bridge problem?
Check the Clever Algorithm
It's okay to "experiment" like this. Scientists experiment too!
Brenden's Idea:
Q: How many different ways to permutate 1,2,3,...,100?
A: 100!
Suppose we pick a permutation at random.
Q: What's the chance we pick a specific permutation?
A: 1/100!
Q: What's the probability we pick the same permutation twice?
A: 1/100! (WHY? BECAUSE THE FIRST ONE DOESN'T MATTER)
One of the problems with Brendan's Method is that it's possible to miss the minimum (which is what we want). We have to guarantee that we'll hit the minimum.
Q: How much do we have to sample to guarantee we get the minimum with high probability?
A: A lot more than exhaustive search, to ensure that our minimum is the minimum for the problem.
Q: How do we generate a random permutaion?
Randomly pick 2 people on one side. Send them across. Randomly pick 1 person on the other side. Send him/her back.
Suppose we can list all crossings.
We know that some sequences are CLEARLY bad. Shuffling with the slowest guy is clearly worse than shuffling with the fastest guy.
We need to get rid of this sequence. This is called Pruning the Search Space.
Where are we?
Oh wait! Alex has an idea. Use George's method of writing out a binary number representing whether an element is in the subset or not. Except this time randomly select 1 or 0 for each element. Aha, it gives equal weight.
Mike has an idea about permutations. Randomly select one and remove it from all the elements. This however does not create independency between choices.
Bobby says something stupid and refuses to write it up on the wiki.
Alex thinks that Mike's idea is correct however in disguise. If you draw it in tree format you can see that you can randomly pick one of the leaves (which represents a sequence). Is the argument correct?
George demonstrates an idea that involves swapping in an array. It's different because it randomly picks by integers (representing positions). This ensures independency. And so Alex's argument is correct.
George has a possible proof of the Bridge problem using induction.
Bridge problem will be put on hold but it will not be closed.
Hand out Problem 8
Review of past problems and relation to sorting:
Tollbooth Problem
Idea proposed: Sort licence numbers into an array then check for entering and exiting using a comparator. Entering and exiting stored onto a stack.
Amiguity of tollbooth problem:
Solution: use the innermost enter-exit pair.
Alex suggets sorting by licence plate number first then time to reduce the number of passes required through the array.
int compare(ticket t, ticket s){
if(t.licence.compareTo(s.licence) == 0){
return(t.time.compareTo(s.time));
}
else return t.licence.compareTo(s.licence);
}
Speed up this code by caching t.licence.compareTo(s.licence)
So far this method is O(n*log(n))
Worst case: N is very close to M => O(n^2 * log(n))
Knights Problem
Variation: Don't care about direction.
Brenden proposed to solve the original problem:
Mike proposes an idea:
Back to Brenden's idea: Given two strings, how do you test if one is a substring of another?
Comparison of Benden's and Mike's ideas: they are the same basic idea. The last character of the string is not required (In 123123 3 is not required)
Alex proposes a new idea:
Today we will discuss three outstanding problems...
1) Toll Booth Problem - we decided it is solved
2) Knights Problem
3) Queens Problem
Knights Problem
Two solutions submitted. Both are "correct" but not fast enough on big inputs. One test input has 3x9900, and one with 3x99900. Timeout is 2 minutes.
Colin talked about his solution. First he put the chair orderings such that 1 was always in front. Did his comparisons by going through entire thing and comparing with first one and removed all copies, opened a new file, all entries that weren't the same go into a new file. Repeat.
Ken talked about his solution. Ken did the if you have 123 -> 12312 to do comparisons. Load each unique thing into the array. (Find uniqueness by checking against all substrings of each thing in the array).
Differences? Colin is removing duplicates, Ken is not adding duplicates. Sort of a different approach.
Sameness? Both of these algorithms are O(m^2).
Colin has an idea to speed up his solution: sort them. First put all combinations with one in front. Then sort and print all uniques. This is O(mlogm).
Alex suggested read in as an object, remove duplicates, sort by entry number, output to maintain order number.
Queens problem
How many ways can you put n queens on an nxn board so they can't attack each other.
We discussed 2x2 - not possible, 3x3 - not possible (we looked through all possibilities to figure this out). To do this, we placed one queen in all 3x3 = 9 possible places, then reasoned that we were stuck for each.
4x4 - can't put a queen in the corner because then you are reduced to a 3x3 problem which isn't possible. But can't generalize that "no queen in the corner rule" (Mike's 5x5 solution)
X.... ..X.. ....X .X... ...X.
Mike's 4x4 solution (where did it come from?)
.X.. ...X X... ..X.
Start by putting queen in position 1,2. Now there's only one place left in row 2 to put a queen (2,4). Now there's only one place left in row 3 to put a queen (3,1). Now there's only one place to put a queen in row 4 (4,3).
Possible slow algorithm (Mike):
Start at top left square. Put Q in square. Mark off all "impossible" squares (put x's there). Go to next row, in first available square put a queen. If you run into row all marked off, go back up a row and go to next block. Looks like a depth first search.
Other solution to 4x4:
..X. X... ...X .X..
This is symmetric to the other solution. (Mirrored across either axis). This is more advanced in the problem so we're putting it aside for now.
Mike's solution: Depth first search. This is backtracking - all of backtracking is essentially depth first search.
Brendan showed us a way to organize this as a tree. At most, there are n^n possible branches (but a lot are eliminated). Fortunately, there are small inputs (13^13).
n^n comes from put one in each row and check. But the solution currently proposed goes in order. Every time you put a queen somewhere, you kill off squares. This is called pruning. This cuts down on number of depth first searches you have to do.
How slow is it? How it works for professionals - write code that is easy to read but not necessarily fast and run a profiler. A profiler shows you how much time it spent on each function, then you can optimize.
Today's lesson: Do not design a program to be fast from the start. Design it to work from the start and optimize it later.
First to ask ourselves - do we need optimizations? (Like the symmetry).
Let's assume this isn't fast enough. Symmetry: Look at the five solution.
X.... ..X.. ....X .X... ...X.
This flipped vertical
....X ..X.. X.... ...X. .X...
The orginal flipped horizontal
...X. .X... ....X ..X.. X....
This flipped horizontal then vertical
.X... ...X. X.... ..X.. ....X
This gives all four corners.
There is also rotational symmetry. This is rotated 90 degrees clockwise.
....X .X... ...X. X.... ..X..
Mike's conjecture (for proof credit): Rotations and horizontal flips are all you need. (you don't need vertical flips).
Brendan also pointed out you can cut the problem in half (you only need to look at ceil(n/2) rows because the rest are symmetric to the others).
George asked if we can reproduce all solutions by using rotations and horizontal flips.
Brenden showed his solution to the Knights Problem that involved a Hash Table. We discussed the different methods of solving the problem, sorting the list or using hash maps.
Hash maps are very powerful and are your friends.
Mike demonstrated his solution to the Queens Problem
Start:We demonstrated that this works with a 5x5 chessboard. However, the problem was to count the number of possible combinations.
To overcome this, we kept backtracking to find all possible chessboard combinations.
Alex's initial hunch was to use a 2D array
2D arrays are not used in OpenGL/graphics programming because of optmizations.
Instead of using:
a[n][m] a[2*n+m] a[n*m]
1000x1000 Array of Integer (8 Bytes) is only 4 Megabytes
We also were showed a method of representing the chessboard in excel. It is helpful to use computer presentations to aid in solving the problem.
This Bishop problem is an extension of the queens problem. The Rooks question is also a subset of the queens problem. Brenden suggested that on a NxN chessboard, you can put at most N rooks because if you put N+1, there will be 2 rooks on either the same column or row.
However, for a Bishop, you can put more than N bishops on a NxN chessboard.
Used extensively in computer games to help movements and find optimal paths.
Today we spent the class examining the various solutions to the n Queens Problem. The first thing that the instructor talked about was input. Several people had correct solutions, but they were not reading the input files correctly. There should be no reason for this, as the input files are available on the wiki. In general, we should read the data in two ways: either through the standard input (System.in in Java, cin in C++) or from a file. From now, the ability to read the input file will be considered part of the grade (i.e. whether the problem is accepted or not).
With that said, several people had submitted a mostly correct solution using Mike's algorithm. Roughly, this algorithm involved the following steps:
We saw three correct solutions along these lines. They all used the algorithm above but they differed in one very important way: they all used different means to mark off the squares. As we saw in class, this had a sizable affect on performance. In order of performance, the solutions were as follows:
Brenden kept track of "marked-off" squares with an n xn two-dimensional array of booleans. Each position in the array corresponds to a board position, and we cannot place a queen in a square if it is marked true. There is a slight problem with this approach, as we discussed in class. We we backtrack, we need to erase those positions no longer attacked by the queen we just removed. Brenden solved this by recopying his table every time that he placed a queen. That way, when he backtracked, he could go back to the old copy.
The problem is that copying is expensive. For an n x n board, this is O(n2). This really cost Brenden., He took 2m 9s to process a 12x12 board. The instructor gave up on doing much more.
Alex's solution is similar to Brenden's solution except that she used the counting trick that we covered in class. Instead of a two-dimensional array of booleans, she kept a two-dimensional array of integers. When a queen attacked a square, she would increment the value in a square by one; when a queen was removed she would decrement the appropriate squares. That way, a square is free if its value is 0.
Because she did not copy any data, she only had to perform O(n) operations at each step to mark the squares. This was much faster and so her program took only 2s to process a 12x12 board; much faster than Brenden. She was able to go as high as a 14x14 board in 1m 9s.
Ken's solution was the most unusual of them all. He did not bother to keep a two-dimensional array for the board. He only kept a one-dimensional array, representing the rows in the table. Each row would contain the column containing a queen. Hence the board
| Q | |||||||
|---|---|---|---|---|---|---|---|
| Q | |||||||
| Q | |||||||
| Q | |||||||
| Q | |||||||
| Q | |||||||
| Q | |||||||
| Q |
| 6 | 4 | 7 | 1 | 8 | 2 | 5 | 3 |
|---|
In addition, Ken did not actually keep track of the positions being attacked by each queen. Instead, when he placed a queen in row r, he checked each s < r to ensure that
In doing this, Ken was able to process a 14x14 board in 53s. His was clearly the performance winner.
The Queens problem is essentially exponential. It is O(n!), but it is best to think of it as O(2n). That means, each time we increase the size of the board, we essentially the double the amount of time necessary to do the problem. Therefore, the name of the game is to squeak out as much as you can. Brenden stopped around 12. Ken and Alex were able to go to 14. Ken's was faster, but in terms of orders of magnitude, his problem has as much problem with 15 as Alex's does.
However, we did learn that little things can make all the difference in the world in these exponential programs. Each move by Alex required O(n) steps. She had to mark all 4n squares attacked by the queen. She also had to unmark them when done. Ken had to perform roughly 3n/2 checks for each move. While this is still O(n), at this point the constant starts to matter. His program was about 2/3 the speed of Alex.
To find these types of performance enhancements, however, it is best to first write a program that you understand and then optimize later. It seems counterintuitive that keeping a data structure to keep track of attacked squares is slower than checking this directly. The best way to discover counterintuitive things like this is with a profiler. A profiler will run your code and will tell you which parts are taking up the most time. This is particularly useful in loops or backtracking as one function gets called over and over again. Speeding up this function can often improve your performace.
Some examples of (free) profilers are
This essentially ended our discussion of the n Queen's problem. We ended the class by briefly talking about the next variation, the Bishop's problem. However, we did not make any progress, so instead we decided to take it up for next time.
0 0 x 0 0 0 x 0 x 0 x 0 x 0 x 0 x 0 x 0 0 0 x 0 0
The x's represent the diamond matrix.
Realization that bishops on black squares and bishops on white squares are completely separate from each other and so we can split up the board into one with just white squares and one with just black squares:
0 x 0 x 0 x x 0 x 0 x 0 0 x 0 x 0 x x 0 x 0 x 0 0 x 0 x 0 x x 0 x 0 x 0
becomes:
0 0 0 x x x 0 0 0 x x x 0 0 0 and x x x 0 0 0 x x x 0 0 0 x x x 0 0 0 x x x
Solving on black squares: Can place between 0 <= k <= n bishops on black squares where k is the number placed on black squares. Then on white squares, must place n-k bishops.
Using Robert's visualization idea on separate white and black boards and it may be possible to use Rooks problem solutions to solve for bishops in the separate white and black boards.
Robert Solution idea: Number of solutions =
Brief look at 2 ways to solve it: back tracking or converting how we solve as a human being into programmable code.
Idea: Thinking of hole as a piece and moving it until it is in position next to piece we want to move, and continue to do this for each piece. When a leftmost piece must be added and, rotate, add it in, and rotate back.
Contest this Saturday. There will be pizza and prizes!
Wiki has been updated.
The next round of reports will be out on Tuesday.
The Bishops Problem
Brenden ran into the problem of duplicates when trying solving the problem by backtracking.
Can this problem be reduced to a problem we have already solved?
Remember the Queens problem: verticle and horizonal were key and diagonal not so much.
Algorithm:
Review of Mike's algorithm:
Difference between the two: In Mike's algorithm the Queen's attacks are structurally present in the algorithm.
Ken's idea: Graph the lines that the bishops would attack through with the slope equal to -1 only. Each bishop will be paired to only one y intercept. There is a max y-intercept that is equal to the max number of bishops for the given n which is equal to 2n-2. His hopes were to find a mathematical solution like we found in the Rooks problem. By putting the possible number of squares a bishop could occupy into an array of length 2n-2, letting the index of the array represent the y intercept you will get something like the following for a 4 by 4 board:
0 1 2 3 4 5 6
1 2 3 4 3 2 1
Professor's Observation: This idea can be used to generalize information about the odd shaped board that is created by rotating the original board by 45 degrees.
Given N*N board and k bishops
The 15-Puzzle
Two ways:
Try it for small boards? But The 15-Puzzle is The 15-Puzzle It is still possible to try ideas on smaller boards and expand those ideas later onto the actual 15 (4 by 4) board.
Example was shown of a 2 by 2 board (3 moving pieces)
Set<Node> Visited Pick next neighbor not in Visited
How will we represent the 15-Puzzle? An array of integers?
class 15-Puzzle {
int array[4][4];
}
How could we put this into a set?
Equality problem: How is equality defined? This is a language specific problem.
Point p = new Point(1,2); set.add(p); p.setX(0);
This will corrupt your set. If you search for (1,2) or (0,2) neither will be found.
In C/C++ you can overide almsot anything (==, ->, et al.) In Java use .equals()
You must make an object compatable for a set. To do this you need to make things comparable (a compareTo() function)
Very useful: if you redefine equals you must redife hashcode (.equals() and .hashCode() )
How do you create a hash function? (A must know for any programmer)
Point p{
int x;
int y;
}
if o1.equals(o2) returns true o1.hashCode()==o2.hashCode()
boolean equals(Object o){
if !(o isInstanceOf Point)
return false;
return x==o.x ?? y==o.y;
}
Returning x + y will cause a lot of collisions. Collisions: ie. (2,1) and (1,2)
Common hash function: 37*x+y Good because 37 is a prime number and has a relation to the golden ratio.
bignum problem:
Difference between Java and C for characters:
All integer types can be unsigned or signed.
Types of data
How to represent floating point numbers:
Next set of problems will be mathematical style problems. Accuracy is important b/c otherwise you get rounding error.
Longs are not long enough to represent data such as encryption data
Java has built in classes to handle this, but we don't want to use them yet
Think of integer as an array of booleans
To do this however we need to redefine addition, multiplication, etc
Learning to Add 123 + 789
Now binary: 10 + 111
Other ways to represent data
Why not just make an array of ints?
Easier problem (converting numbers into strings):
132 % 10 = 2 132 / 10 = 13 13 % 10 = 3 13 / 10 = 1 1 % 10 = 1 1 / 10 = 0 (done)
2 ways to store numbers in an array
Storing forwards (i.e. ones place at the end) is harder to line up ones place
How to convert into base 256:
Replace all above 10's with 256's Cast all remainers as char's
Alex: mask and shift
Bitwise and = 2 & 4 = 0
myNum & FF is way faster and is the same as myNum % 256
Instead of divide by 256 can do myNum >> 8
Replacement of expensive division with inexpensive binary operations
Other bit operations
The instructor promised one last time that he would have grade reports for us next Tuesday. He really means it this time.
He also brought us up to speed on the state of the problems. He is planning on closing everything up to and including the Queens problem (so that we can move on). Any outstanding code needs to be submitted pronto.
The Bishops Problem and the 15 Puzzle will remain open indefinitely so that people can still work on them (several people noted that they are still working on the 15 puzzle).
We began the class talking about warm-up problem 4 again. We reviewed the problem of taking a large number and expressing it as an array. Alex' algorithm from last time was successful at extracting digits. For example to break 123 into its digits we compute
123 % 10 => 3 (123/10) % 10 => 2 (12/10) % 10 => 1 (1/10) % 10 => Done!
However, if the array is storing the number as a string (i.e. a char holds '0', '1', ..., '9' and not a number 0...255), we overlooked how to convert these digits to strings. As Robert pointed out, we make a string with the right number of digits all containing the character '0'. The ith digit is then
str[i] = (char)(str[i]+digit)
We then reviewed the concept of base 256. Alex's algorithm also works for base 256 by replacing every 10 in the above algorithm with 256. In fact, we can do any base b by replacing 10 with b. However, 256 is particularly nice because it is a power of 2 (256 = 28). This means that we can replace the operations above with bit operations. The operation "% 256" is the same as "& 0xFF" and the operation "/256" is the same as ">> 8".
After this review, we went to the next subproblem of the warm-up problem: adding two numbers. We discovered that adding two numbers is easy; you do it exactly like you do it on paper. There are only two hard parts to worry about. The first hard part is "lining up" the numbers correctly. Suppose we want to add the arrays
| 1 | 255 | 3 |
+
| 2 | 1 |
To do this, we need the ones places to line up. We can do this one of two ways. One is to use the fact that we know a big number can only be an array with 100 elements. We just make every number 100 elements long and move everything to the right, as so
| 0 | 0 | 0 | 1 | 255 | 3 |
+
| 0 | 0 | 0 | 0 | 2 | 1 |
The other alternative is to "reverse" the numbers so that the ones are at the start. This would give us
| 3 | 255 | 1 |
+
| 1 | 2 |
We just add these digit by digit as so
| 3 | 255 | 1 |
+
| 1 | 2 |
=
| 4 | 256 | 1 |
However, now we have our second problem. One of the numbers is over 255. That means that we have to subtract 256 and "carry the 1", just like we do in normal addition. Thus the result is
| 3 | 255 | 1 |
+
| 1 | 2 |
=
| 4 | 0 | 2 |
How do we know the number is over 255? If we add the arrays directly, like
c[i] = a[i]+b[i]
then we will not be able to tell because of overflow; the 256 will be stored as 0. Instead, we need to do everything with a temporary variable that is larger than a char and is capable of storing a number like 256 (say, and int). Indeed, as the instructor pointed out, this is the takeaway message of this warm-up: be clearly aware of the limitations of your variables. Be aware of overflow in integer types and round-off error in floating point types.
At this point the instructor decided that the class looked bored, so he handed out a new problem.
The next problem asked us to find the coffecient of any given mononomial of the polynomial
(x1+x2+...+xk)n
We first tried to understand the problem. We did this by continuing with the basic technique that we have used many times now: reasoning on small inputs. We looked at the polynomials
(x1+x2+x3)3
(x1+x2+x3)2
and
(x1+x2)3
After playing around with these for awhile, Alex conjectured that the answer was the following:
n!/(# of duplicate terms)
How did she come up with that idea? She gave an example with the term x12x2 [for the polynomial (x1+x2)3]. The ways we can get this are the different number of ways that we can permute the terms, namely x1x1x2, x1x2x1, and x2x1x1. There are three ways to do this, which is 6!/2. Of course, she was not able to prove this, but her example was nice.
Mike immediately took exception to this formula, and pointed out that there is a counter example for the term x13x2 [for the polynomial (x1+x2)4]. At this point she amended her formula to
n!/(# of duplicate terms)!
At this point the instructor reminded us about chosing input sets for our programs. We need to do the same thing with mathematical formula. In particular, we want to pick inputs that are "non-representative" of the assumptions made in coming up with the formula. In this case, a perfect non-representative case is the term x12x22 [for the polynomial (x1+x2)4], as two terms are repeated. We saw once again that Alex's formula did not quite work. Alex changed her formula one more time to
n!/(# of x1)!(# of x2)!...(# of xk)!
At this point everyone was happy, even though we had no proof it was correct. However, if this is correct, then this is a trivial problem to code. So the instructor was not interested in people turning in code to this problem. He suggested that everyone either
Alex used the phrase "and so on" when she justified her answer. This suggests that induction is involved.
At this point the instructor distributed another problem. This asked us to count the number of carries in adding two numbers. Mike very quickly pointed out that this was the same as implementing arbitrary addition, which we had talked about earlier. As a result, the class may get credit either the warm-up problem, or this one, but not both.
As the class was going through problems like Kleenex, the instructor pulled out one last problem. This one was much more difficult. Quickly the class discovered what the major problems were. While N is guaranteed to be bounded, E is not. In fact, if E were bounded, Alex and Mike suggested that we just make a hashtable of all the powers of 2 and use that. Alternatively, we could just brute force our answer. That is, we start with 1 and keep doubling our answer until we find the right result.
However, the problem is that we run into the overspill problem very quickly. If we use an int, we cannot get any power of two greater than 31. However, the first power of two that starts with 7 is 246. We can improve things a little bit by using a long instead. Then we could go to 263. However, once again, the first power of two that starts with 73 is 266. All in all, this looks difficult.
The hint that the instructor gave us was as follows: understand what it means (mathematically!) for a number to be a solution to the input. Saying that one number is the initial segment of another uses our eyes. Humans are very good at visual stuff while computers are not. Therefore, we have to learn how to convert our visual ideas into mathematical formula. We had some ideas, but they were not very helpful.
We did however come up with Mike's Conjecture: "Every number is the initial segment of some power of two". We aren't sure whether this is true or not. However, everyone believed that we could use this to our advantage. This is what we will talk about next time.
Cornell University Department of Computer Science
Last Updated: October 26, 2006