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
Monday, February 28, 2011
Thursday, February 24, 2011
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.
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.
Wednesday, February 23, 2011
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.
Tuesday, February 22, 2011
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.
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.
Saturday, February 19, 2011
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.
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.
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.
Monday, February 14, 2011
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).
- 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).
Subscribe to:
Posts (Atom)