This is where I will archive all messages
If your first bit is a 0, return 1. Otherwise, generate two more bits, and then assign each length 2 bitstring to each of {2,3,4,5}. Generate two values from rand5, x and y. Take (x - 1) * 5 + (y - 1) (this will be random in {1, 2, …, 25}) If it is less than 22, divide by 3 to get a value in {1, 2, …, 7}, otherwise, generate two more samples and try again. Drop an egg from the 14th floor. If it breaks, then start at floor 1 and walk up. If it doesn't break, go to the 14 + 13 = 27th floor. If the egg breaks, start at floor 15 and walk up. If it doesn't, go to the 14 + 13 + 12 = 39th floor, etc… One person counts the number of black hats (s)he sees, then guesses black if this number is odd and white if this number is even. The others then can each look at the other 98 victims and deduce their color accordingly. p^2 - 1 = (p - 1)(p + 1), so the number is divisible by (p - 1) and (p + 1). Consider any three consecutive numbers (x - 1), x, and (x + 1). One of them must be divisible by three, so as p is not prime, one of (p - 1) or (p + 1) is divisible by three. As p is odd, (p - 1) and (p + 1) must be even, and one of them must be divisible by four. This means we have a 2, 3, and 4 amongst the divisors of (p - 1) and (p + 1), which multiply to 24. By the pigeonhole principle, two of the five cards must share a suit, so Alice will hand back one of these two cards. More on which one in a second. Alice places the other card with the shared suit in the first position of the four held out cards, indicating to Bob the suit of the secret card. As long as we have a total order on the cards (e.g. spades > clubs so 4S > 4C), with the three remaining cards we can create 6 different permutations. We need 12 though! Ah, now we can go back to the fact that we have two cards of the same suit. If you arrange all cards of the same suit in an ordered circle, picking any two, one is always at most 6 cards ahead of the other. For example, 2H and JH - the JH is eight cards ahead of the 2H, but the 2H is 4 ahead of the JH. As long as Alice sets aside the 2H in this scenario, she can then put the JH on top of the four card stack, then arrange the remaining three cards in the fourth permutation. This fully communicates to Bob which card was left out! We work backwards. Imagine if only two pirates are left. The older of the two can simply allocate all of the coins for her/himself, knowing that the split vote will go in her/his favor. Knowing this, when only three pirates are left, the oldest can give her/himself 99 coins, appeasing the youngest pirate with a single coin, and spurning the middle pirate with no booty! In the four pirate case, the oldest gives himself 99 coins and the second youngest 1 coin, ensuring a split vote. Finally, the fifth pirate gives himself 98 coins, and the middle and youngest pirates each 1 coin: #1 #2 #3 #4 #5 1 0 1 0 98 0 1 0 99 1 0 99 0 100 Ugh, more math stuff. The solution is actually the Catalan numbers. If you want to give the closed form, you might try this - envision an n x n grid, then consider paths along the grid from the bottom left (0, 0) to the top right (n, n) taking only steps up and to the right. Each path can be described by an arbitrary sequence of n open parens and n closed parens, in any order, where we allow open parens to indicate steps up and closed parens to be steps to the right. Note that there are 2n choose n of these paths. If the string of parens is balanced, then the corresponding path never crosses the diagonal from start to finish. Now here's the tricky part: consider what happens when the path does cross the diagonal. We take the rest of the path, so all steps after the step that crosses the diagonal, and swap up steps for right steps and vice versa. This gives us a path to (n+1, n-1). This is because at the point at which we cross the diagonal, we must have made a step right, so, if we cross the diagonal at (k, k), we have k steps up and k+1 steps right. The n - k steps up remaining become steps to the right, then the n - k - 1 steps to the right become steps up. Thus, we land at (n+1, n-1). Each one of these paths, of which there are 2n choose n+1, corresponds directly to a path on the square grid that does not cross the diagonal, or in other words to an unbalanced string of parens. This leaves (2n choose n) - (2n choose n+1) total balanced parens. Draw a 3 circle venn diagram, with circles A, B, and C. If you put the four information bits in the four intersection regions, AB, BC, AC, ABC, then you have three extra regions that are empty, A, B, and C. In each of them, put the sum mod 2 of all the bits in the same circle (e.g. in the A region, put AB + AC + ABC mode 2). If at most one bit has been flipped, the sums will no longer be correct, and the origin values can be inferred. The answer is six! Start with one person, X, at the party. By the pigeonhole principle, this person has, amongst the five other guests, either three mutual friends or three mutual strangers. Say, without loss of generality, that they have three mutual friends. Call them A, B, and C. If any of A, B, and C are friends, then together with X, they have a set of three mutual friends. If none are friends, then they form a trio of mutual strangers. Tada! If you represent a 5-simplex with vertices in 6 dimensions, (1, 0, 0, 0, 0, 0), (0, 1, 0, 0, 0, 0), …, (0, 0, 0, 0, 0, 1), then they have edge length of √2. The inscribed simplex has vertices at points (.2, .2, .2, .2, .2, 0), (.2, .2, .2, .2, 0, .2), …, (0, .2, .2, .2, .2, .2, .2). These edges have length √2/5, so our ratio is 5, and in general, for an n-simplex, this ratio is n The solution, and the puzzle, are straight off of wikipedia: This is general induction plus a leap of logic. Leap of logic: Every colour must appear at least twice around the circle. This is because the Master stated that it would not be impossible for any Logician to solve the puzzle. If any colour existed only once around the circle, the Logician who bore it would have no way of knowing that the colour even existed in the problem, and it would be impossible for them to answer. Each of the Logicians can look around the circle and count the number of times they see each colour. Suppose that you are one of the Logicians and you see another colour only once. Since you know each colour must exist at least twice around the circle, the only explanation for a singleton colour is that it is the colour of your own band. For the same reason, there can only be one such singleton colour, and so you would leave on the first bell. Likewise any Logicians who see another colour only once should be able to determine their own colour, and will either leave with dignity or be thrown out as an infiltrator. Equivalently, any colour for which there are only two bands of that colour will be eliminated after the first bell has rung. Thereafter there must be at least three bands of any remaining colour. Suppose you do not see any colour once, but you do see a colour twice. If these were the only bands of this colour, then these two Logicians ought to have left at the first bell. Since they didn't, that can only be because your own band is the same colour, so you can leave at the second bell.
Student evals please:
ok, i will let the students out early like Ben, but I will try to get a bus to pick up at Arillaga at 12:15.
Actually, Brian, I'm putting you in charge of figuring out what is best. I will give you the phone number for the buses, so you can tell them where to pick up. If you think it's better for them to go to Lakeside, then do that– This is for NEXT week.
If i remember correctly, one of the three classes will be split between the two buses
Man, that was a lot of material covered in one day.
Hopefully, they enjoyed TSP. It's an example of something that seems sort of easy, but isn't so for a computer.
The 1:1 meetings went well.
My notes for tomorrow:
Continue taking notes on the eval sheet here:
https://docs.google.com/spreadsheet/ccc?key=0AiBY_Q7S7qNqdHJ0UTRHVHRtUzJYdzdaUzBoRmlZSUE#gid=1
Lay Kuan will give a 15 minute LateX talk and +5 on the field trip wednesday.
http://users.soe.ucsc.edu/~sherol/teaching/doku.php?id=epgy:ai13:assignment_5
Please take a look at Assignment 5.
Lay Kuan!.. Would you like to teach Latex on Tuesday? If you take a look at Lab 4, I have them doing some simple proofs.
Probably I won't have much more to say about tomorrow.
The lock activity went well. The field trip for Wed is set.
Check out my Lab 4 in Assignment 4…lol.
http://users.soe.ucsc.edu/~sherol/teaching/doku.php?id=epgy:ai13:day_4
I suppose tomorrow is seen as a catchup day.
I may not be able to make it to lab, b/c I want to beat rush hour traffic back home.
The combo lock activity will be during Lab time.
Take a look at day 3 stuff. I also fleshed out the syllabus.
http://users.soe.ucsc.edu/~sherol/teaching/doku.php?id=epgy:ai13:index
The assignment 3 MySorts is only the first half of what I want them to do.
I've now finished the majority of the historical material, although I might go into specializations later.
I need to remember to grab my old AI book from Santa Cruz and all my AI and Game Developer Magazines.
I think the approach I'm going to take with this class is on polishing quality projects, now that we are done reviewing programming concepts. I'd also like them to continue documenting their work like they have been. In the student evals, I care most about the progress that students are making. This will help me know whether I can move on or I should stay on a topic.
https://docs.google.com/spreadsheet/ccc?key=0AiBY_Q7S7qNqdHJ0UTRHVHRtUzJYdzdaUzBoRmlZSUE#gid=1
I'm still debating on how deep I want to go with the next assignment, but I think I'm going to have them make a SIMPLE version of: http://visualsort.appspot.com/
I'd still like them to complete EPGY Draw, so that will be part of Assignment 3.
Tomorrow will have a lot more on data structures and algorithms.
Student evals go here:
https://docs.google.com/spreadsheet/ccc?key=0AiBY_Q7S7qNqdHJ0UTRHVHRtUzJYdzdaUzBoRmlZSUE#gid=1
Here are the solutions to Lab 2 part 1:
Take a look at the students site and leave them comments.
Day 1 went great! Thanks for getting me in the loop.
In google drive, I put folders with you names on them. Feel free to switch students if you think it's necessary. Also, feel free to give me any feedback about what I should do or how things should be done :)
Tonight I'm going to put up Assignment 2 and go buy an audio cable. I'll also get to submitting all field trip forms tonight. Stay tuned for notes for day 2.
The objective of the afternoon is:
So, the difference between Ben's day 1 and mine are the following:
Here's the course website: epgy.sherolchen.com
See Journal 1 and Assignment 1 under Day 1: http://users.soe.ucsc.edu/~sherol/teaching/doku.php?id=epgy:ai13:day_1