Welcome to the Fall 2018 web page for CS196, Honors Section of CS 173

Instructor: Tandy Warnow, Founder Professor of Computer Science

• Please use: cs173a-instructors@lists.illinois.edu (which will also be ready by Prof. Varodayan).
• Warnow's office hours: Tu 11 AM to 12 PM in Siebel 3235

Basic information

• This is the honors section for CS 173. You will have more challenging proofs as homework problems and also the opportunity to do coding that uses the algorithmic techniques you'll be learning in the class.
• At this time, I am not planning on providing any extra lectures, but this could change if we can find a time where we can all meet!
• If you are not registered for CS 196 but still want to do the assignments, you are welcome to do these, and then come to office hours to discuss your solutions and get feedback.
• The homework assignments will be posted here as well as on Moodle. If you are registered for the class, please make sure to submit your solutions in Moodle by the deadline.
• Please submit your homework solutions (when these are proofs rather than code) as a PDF created using LaTeX.
• Your grade will be based entirely on your submitted assignments, and these will be graded by Prof. Warnow (and possibly some of the teaching assistants).
• You are allowed to collaborate on homework as long as you follow the rules about collaborations. In general, these specify that if you work with some other people, you must list everyone you worked with on the submitted homework and you must write up your solutions entirely by yourself. Copying (or copying and then modifying it to make it look like you did it yourself) someone else's solution is not acceptable. The full details are available of this collaboration policy are provided here.
• If you feel that you should have received more points than you got, please come see me during office hours. If there was a mistake in the grading, I will address it!
• One piece of advice: start your homework early! It won't always be easy.

Homework assignments

• Homework 1, due Friday, September 21 at 10 PM: Prove by induction on the number of vertices that every finite simple graph has an even number of odd degree vertices. (This proof was sketched in class)
• Homework 2, due Friday, September 28 at 10 PM: Consider the following statement.
  • Suppose P(n) is a statement that is true or false, depending on n. Now suppose P(0) is true and if k>0 and P(k) is false then there is a non-negative integer k' smaller than k such that P(k') is false. Then it must be that P(n) is true for all non-negative integers n.
  If the statement is true then prove it. Otherwise give a counterexample.
• Homework 3, due Friday, October 5 at 10 PM: Solve the following two-person game. There are two players (player A and player B). Player A starts, and players alternate turns until the game ends. The objective is to take the last rock off. The game begins with two piles of rocks, where the first pile has M rocks and the second pile has N rocks (so that M and N are both non-negative and at least one is positive). When it is a player's turn, they must do one of the following: take one rock off, or take two rocks off (each from a different pile). The question you are asked is to determine for a given starting condition (defined by M and N) who has a winning strategy - player A or player B? For example, if the game begins with M=N=1, then player A has a winning strategy - take one rock off of each pile. However, if the game begins with M=2, N=0, then player B has a winning strategy (no matter what A does, player B wins when it's B's turn). To get started on this, figure out what happens for a bunch of starting conditions. HINT: This particular game can be solved by noticing a particular pattern... which has to do with the parity of M and N. What I'd like you to do is
  • Say who has a winning strategy for the following starting conditions:
    • M=1, N=2
    • M=2, N=2
    • M=2, N=3
    • M=1, N=3
    • M=1, N=4
  • Come up with a rule for who wins (player A or player B) that has to do with the parity of M and N
  • Sketch a proof that your rule is correct using induction. (I say "sketch" because I am expecting that this won't be perfect in your first try, and I'll give you feedback afterwards so that you see how to make it better.)
  • Start thinking about how you'd solve any two-person game (with different rules) using dynamic programming. One of your next assignments will be to develop a dynamic programming algorithm to solve a different two-person game that doesn't have a simple solution based on some properties of the values of M and N!
• Homework 4, due Thursday, October 18, 2018 (10 PM). Consider the following two-person game. You have two piles of rocks, and two players take turns playing. When it is your turn, you can take one or two rocks off, but the choice of where you take rocks off is up to you:
  • one rock off of one pile
  • two rocks off of one pile
  • one rock off of each of the two piles
  The person who gets the last rock off wins. Come up with a Dynamic Programming (DP) algorithm to determine who has a winning strategy when the initial starting condition has M rocks in the first pile and K rocks in the second pile. (So the input is the pair M,K, and the output is "1" if player 1 has a winning strategy and "2" if player 2 has a winning strategy.) Describe your DP algorithm fully. State the variables and their meaning, and show how to calculate them (what are the boundary conditions and what is the order in which you compute the variables). Explain why your dynamic programming algorithm is correct.
• Homework 5, due November 2 at 10 PM. (Note: this homework is preparation for a later homework, where you prove that Minimum Vertex Cover can be solved exactly in polynomial time for any tree.} Prove that for every tree T, with at least 3 nodes, there is a minimum vertex cover that does not have any of the leaves in T. (Hint: Do this as a proof by contradiction. Then, among all the minimum vertex covers, find one that has the smallest number of leaves.)
• Homework 6, due November 6 at 10 PM. Implement the DP algorithm from HW 4 (see Moodle for details).

Additional reading

Other interesting problems

• Aniket Murhekar: (PDF)
• Meghan Shanks: (PDF)

Interested in doing research?