News Quiz!

Now it's time for a new feature on this blog: the News Quiz! These are some questions about local (and some not-so-local) news events - whatever I find interesting.

1. So-called "Castle Doctrine" laws give citizens the right to do what?

A. Participate in medieval re-enactment.
B. Use lethal force to defend their homes.
C. Engage in collective bargaining over rent payments.
D. Build moats around their property.

2. Which of the following companies have been recently praised by gay-rights advocates, and why?

A. Verizon, for canceling a planned ad campaign that featured two characters getting "stuck" in a same-sex relationship due to a competitor's poor cell-phone service.
B. Bioware, a video game company, for announcing that the highly anticipated space-adventure video game sequel "Mass Effect 3" will provide the option to have the player's character engage in same-sex relationships with aliens.
C. Facebook, for giving users the option to set their Facebook status to "in a civil union" or "in a domestic partnership."
D. Wizards of the Coast, for printing a series of "Magic: The Gathering" cards that feature pairs of same-sex characters that get bonuses if you have both of them on the field at the same time.

3. A new iPhone app is designed to make it easier for religious believers to do what?

A. Pray
B. Confess
C. Proselytize
D. Find churches

4. The University of Illinois computer science department took it as praise recently when a report came out showing that the department is number one in what?

A. Academic integrity violations
B. Nobel Prize winners
C. Percentage of students using alcohol
D. Average number of Facebook friends

==========================

Answers:

Question 1
Question 2
Question 3
Question 4

Gaming Math - Problem 16:

Problem 16: "Fall Out Pick Up"

The video game "Fallout 3", and its sequel, "Fallout: New Vegas", are set in a post-nuclear-war world where most civilization has been destroyed and the few people remaining alive must scavenge for supplies to stay alive. Each piece of loot that you can pick up has a weight and value. There is a limit to how much weight you can carry, and when you get to a town you can sell your loot for bottle caps (the game's currency) based on its value. The problem of maximizing the total value of items you can pick up while staying within your weight capacity is known as the "knapsack problem" and is a well-known NP-complete problem.

In the game, however, there is an additional complication. You only observe each item one at a time, and because of the dangers and rival scavengers it is impossible to go back and pick up an item that you dropped or left behind. So you have to make a decision about whether to pick up each item, as well as which items to drop in order to make room, as you see each item.

(a) Is there an algorithm that gives the optimal result in all situations? (There is no limit on the running time of the algorithm.)

(b) The "competitive ratio" of an algorithm is the worst-case ratio of the value of the solution found by the algorithm to the optimal solution. For instance, if an algorithm always gives you a set of items with value at least equal to half the value of the optimal solution, then its competitive ratio is 0.5. Does there exist an algorithm for this problem with competitive ratio greater than 0? If so, give one; if not, prove it is impossible.

(Hint: Imagine there was an "adversary" controlling the capacity and sequence of items, and it gets to observe which items the algorithm selects before deciding which new items to present.)

(c) Suppose that the capacity is C, and the highest weight of any one item is M. Give an algorithm for this problem with competitive ratio 1-(M/C).

The solution is here.

Breaking News: Solution To Illinois Budget Crisis!

As you may know, the State of Illinois has been facing a severe budget shortfall and has recently been forced into massive tax hikes. Also, in the 2008 election, then-candidate Mitt Romney accused then-candidate Rudy Giuliani of turning New York City into a "sanctuary city" for illegal immigrants in order to get more workers and tax revenue. Recently, it appears that Illinois is following this plan, becoming a "sanctuary state" for Democratic politicians who want to avoid voting on bills. Lawmakers have referred to themselves as "refugees", and have been stimulating the Illinois economy by purchasing essential items. There has been speculation about whether police would be able to arrest the rogue legislators and extradite them back to their home states to stand trial. As for me, I am just waiting to see what the Capitol Steps song about it will be like.

More on Echo360

Because I posted on my blog about Echo360, I have been contacted by a marketing person from Echo360 who is interested in what I have to say. Here is what I told her about my experiences so far.

I think Echo360 is a very useful tool, but there are some other features that would help. One thing I think would be useful is to integrate a discussion forum with the lecture capture. The way I would envision this working is that when a student is watching the lecture online, if he has a question he can click a button and type his question in, then the question would be tagged with a timestamp indicating what point in the lecture he asked that. And there would be a way to link to a particular timestamp in the lecture. Then the instructors/TAs can log on and look at the questions, and when you looked at a given question you would have a link to the associated point in the lecture. Or an instructor could answer by pointing the student toward a particular place in the lecture. This would be useful to me because oftentimes when I talk to students, they say the instructor told them something which doesn't sound right to me, but it's hard to clear up the confusion without the lecture in front of me.

Another problem, which is a little more technical, has to do with the sound. The way our setup works is that there are two microphones, one worn by the instructor and one "shotgun" microphone. The one the instructor wears has much better sound quality but only captures what the instructor says, while the shotgun microphone can capture everything in the room. So one of the things I have to do is when the instructor pauses for students to ask questions, switch to the shotgun microphone, and then switch back when the instructor starts talking. This often isn't very reliable and you don't get all the questions. So a useful tool would be to have two or more audio channels going into the system, and it would automatically switch between them depending on who is talking.

I'm also taking a TA training seminar where we are reading the book "Teaching At Its Best: A Research-Based Resource for College Instructors" by Linda B. Nilson. That book talks a lot about how traditional lectures aren't very good at promoting student understanding, and has lots of suggestions for how to improve lectures. For instance, one way of improving lectures is to periodically stop and give students a question to answer and discuss in order to keep them engaged. Something like this could be incorporated into Echo360 - if you had a system like the one I described in the first paragraph, then the instructor could put a question on the whiteboard and ask students to answer it by posting something. It might even be possible to set up a system where the instructor can set the lecture to automatically pause and ask the student a question, and not to continue until the student gives an answer.

More Belegarth Action

Also this weekend I went to Wolfpack Opener, a large Belegarth event. We had to squish in the back seat of a truck because we were low on space in cars, but we got there fine. The battles were exciting, and especially since I am an archer it was fun because it's inside, so everyone bunches up and there are lots of easy targets. There are different types of battles including "line battles" wher everyone lines up in two lines and you fight each other, and also "four corners" battles where each player gets a different color wristband, each color has a corner associated with it, you are fighting against anyone who is not your color, and the referees will periodically call out a color and anyone who is dead with that color comes back alive.

Another thing is they're in the process of voting to see whether I get to become a full member of House Valdemar. So far the vote is going in my favor, but not all the votes are in and several of the key members who are supposed to vote haven't been out to practices in a while and we haven't been able to get ahold of them to get their votes. Maybe they're hiding in Wisconsin.

The qual is finally done!

I had my qual exams this Thursday and Friday. According to the qual web site, normally the qual has 8 questions on it, and a passing score requires "nearly perfect" answers to about 3 of the questions and partial answers to 3 more. This time there were 10 questions on the qual, and I was able to get complete answers to 5 of them and partial answers to 4 more of them. So I think I passed, though I won't know for sure until the results come in, probably next week.

One thing that this does mean for the blog is that you will get to see more of my "Gaming Math" problems. The main reason I haven't been able to put up more of those problems recently is not because I haven't played any games with interesting math or computer science problems in them, but rather because most of the time I can't actually solve the problems I come up with. But preparing for the qual has helped me get better at solving those kinds of problems so that means that you will see more of them.

Here is a problem:

Gaming Math - Problem 15: "For Science!"

In the board game "Battlestations," players control crew members aboard a spacecraft, and they are sent on dangerous missions. In one of the missions, the players are trapped in a region of space containing N wormholes, and the only way to get out is to go through the wormholes in a specified sequence. The only way of finding out what that sequence is is by using the ship's Science Bay, which allows the player to ask any yes-or-no question about the sequence.

1. In the scenario described in the game, N=4. What is the minimum number of questions required to guarantee figuring out the correct sequence?
2. For an arbitrary N, what is the minimum number of questions required? Find an algorithm that achieves this minimum number, and prove its optimality.

(Hint: Don't forget that you can ask any yes-or-no question about the sequence.)

The answer is here.

More school stuff

- I have just finished creating, assigning, collecting, and grading the first homework assignment of the year as a TA. This homeowrk was about formal logic, including propositional and first-order logic. (Propositional logic just has variables which can be either true or false, while first-order logic allows variables to be arbitrary objects, there are "predicates" that are basically functions which take objects as arguments and return a boolean variable, and there are "quantifiers" which allow you to say things like "for any X, P(X) is true" or "there exists an X such that Q(X) is true". We thought this part would just be review (these are Masters students in computer science, so we thought they would already know about logic) but some of them had trouble with simple things like the difference between validity (statement is true all the time regardless of the values of the variables) and satisfiability (statement is true for some assignment of values to the variables.) In fact one of the problems we had to "cancel" and make it an extra credit problem because it had to do with proofs in first-order logic, a topic we didn't cover (I didn't realize that we weren't going to cover it when I wrote the homework, and the professor didn't notice when he was looking at the homework before posting it)

- I have my Ph.D. qualifying examination this Thursday and Friday. I have looked at most of the previous quals and it seems like I pretty well prepared for it. Another thing is even if I do decide to only get a Masters degree, passing the qual is a good idea because if I pass the qual I am exempt from the distributional requirements for a Masters (there are still two distributional requirements, hardware and systems, that I haven't taken courses in so I would need to do that if I were to go that route).

Gaming Convention Season, Part 2

Here are some more games I played:

Space Hulk:
In this game, there are two sides: the Space Marines and the Genestealers. The Space Marines are invading a spaceship that has been taken over by the evil alien Genestealers, and the goal of the Space Marines is to complete their mission before getting killed. The Space Marines have the advantage of ranged attacks and special abilities, but the Genestealers have the advantage of improved melee capability as well as numbers (new Genestealers come in every turn, but the starting Space Marines are all the Space Marines get). So the Space Marines have to be aggressive in getting to the objective, because they are going to lose a war of attrition. This tendency was even more pronounced given that we were playing by the wrong rules: we were spawning 50% more Genestealers per turn than we were supposed to, but we also made a mistake in how the Genestealers move that was equivalent to giving the Space Marines a one-turn head start. We played two rounds, once where my team was the Space Marines and once where my team was the Genestealers. As the Space Marines, we didn't realize this strategy and tried to advance carefully, but were soon overwhelmed. As the Genestealers, our opponents rusjed forward, taking advantage of their head start, and we managed to sneak in from the side and kill them but not until after they had destroyed one of the two objectives.

Rating: 8 out of 10. This game has significant strategy, and it is also fast-paced and exciting, and is designed to reward aggressive play. The one thing that isn't so good about this game is the pieces: some of the pieces break easily, often fall over, and are hard to fit on the board spaces.

Goblin Supremacy:
This is a card game in which players form a goblin army from cards that have goblins on them. There are three "ranks" of goblins, and the higher level goblins are worth more points but you have to have lower level goblins of the same type in order to play them. You can only have five goblins of each rank, but if your row is full you can "mutate" goblins by discarding cards, that transforms them into another goblin from your hand. The carsd have abilities that go off when they are played, when they get mutated, or when they are "activated" by spending "activation tokens." A significant element of the game is figuring out how to "combo" different abilities together and in what order to do things to maximize your cards - creating a sort of "Magic: The Gathering" like gameplay.

Rating: 7 out of 10. I liked the "Magic-like" gameplay, but the main problem with the game was that there were just *too many* decisions at each step - for instance, a typical turn might have you with 6 cards in hand, then deciding which 3 of them you want the least so you can discard them to activate a "zombie mutation" which lets you search through a 30+ card discard pile to decide which one card you want to mutate your guy into. This sometimes makes the game take a long time - I think we started playing this one at about 9:30 or 10:00 and had to end early when the room closed at midnight. Especially near the end of the game it gets slow, because what often ends up happening is that you keep finding ways to discard cards to draw cards so you can cycle through the deck to find the one card that fits in the few spots you have left.

More from the Daily Illini

In reference to a FOIA request from a student environmental group for information about coal disposal at the University power plant:
"The letter also said the University has seven days to submit the unredacted documents. Hardy said the University received the request Jan. 30 and plans to respond by the Feb. 9 deadline."
[Again, this actually makes more sense than it sounds. The "seven days" is seven business days.]

Gaming Convention Season, Part 1

Here are some of the games I played at Winter War:

Dungeon Lord:
In this game, players play as lords of minions in a dungeon with lots of rooms. Each player selects a starting room, and then during each turn there are several phases. First, players get gold depending on how many rooms they control. Next, there is an auction where cards are turned up that represent minions to bid on, and players bid gold on the minions. After hiring minions players place them on the board, then they move the minions, then there is an action phase where minions can fight or bribe other players' minions to gain control of the rooms. At the end of the game whoever controls the most rooms wins.

Rating: 8 out of 10. The auction mechanics, where players can spend money on things like hiring minions, bidding for initiative order, buying extra actions, and bribing enemies, add significant strategy to each turn even when you are not in direct conflict with another player, and encourages players to pay attention to what everyone else is doing even if they are on the other side of the board.

Race for the White House:
In this game, players play the role of candidates in a presidential primary. They travel around the country, stopping in cities to pick up votes. There are event cards that turn up that do things like make certain issues (like defense, health care, etc.) "active issues", which means that candidates who have strong positions on those issues become able to pick up more votes, and give a chance for players to receive campaign contributions. By the time you get to election time, you figure out who has the most popular vote in each state, count up electoral votes using a ballot system similar to that used by the Democratic and Republican parties, and whoever gets 270 or more wins.

Rating: 4 out of 10. While I originally thought this game would be good because I have had good experiences with other election-based games like Campaign Manager 2008, I found that this game had a lot of unnecessary complexity. Having complex rules can be fun if it adds to the strategy, but in this case it didn't. For instance, some of the event cards make it so you have to cross-reference the issue on the card with your character's position rankings to find out whether you gain or lose votes and then you adjust the vote totals in the state you're in and each adjacent state. This is a complex process that takes several minutes to resolve each card, and dozens of cards come up over the course of the game. But the event cards are completely random and your positions on issues are fixed, so there's no way to plan for the event cards or respond to affect the outcome. And the parts that aren't random are largely non-interactive, with the main challenge being to remember how many votes your opponents have in each state.

Gaming Convention Season

Last weekend I went to Winter War, a 2-day gaming convention held in the Hawthorn Suites (they had this last year as well.) This weekend there was Metacon, a gaming convention held by the University of Illinois gaming club. Tomorrow I will post about what happened (It's really late tonight).