Hw11: Counting II, FSM

Due 04.Apr.20 (Tue) 22 (Thu) 17:00.

Before you tackle the homework, remind yourself of our general hw policies.

Reading: Lecture covered Rosen Sections 4.5, 6.2 (the homogeneous case), 6.3, 6.5.
Sections 11.2, 11.3 are variants on the finite-state machines given in lecture.
Separately, the hat-check problem (Section 6.6, derangements) is fun and occasionally pops up in problems.

1. (3pts) Section   4.5 #10a,c,f (p.342). (croissants) 4ed: p.294 #10.
2. (2pts) Section   4.5 #40 (p.342). (4d paths) 4ed: #36.
3. (2pts) Section   6.3 #12 (p.434). (f(n)=2f(n/3)+4) 4ed: ???
4. (4pts) Section   6.3 #28 (p.434). (hi-lo with one lie) 4ed: does not exist.
5. (2pts) Section   6.5 #  6 (p.456). (union) 4ed: p.359 #6.
6. (2pts) Section   6.5 #14 (p.456). (avoiding animals) 4ed: p.360 #14.
7. (3pts) Section   6.6 #  6 (p.464). (squarefree) 4ed: p.367, #6.
8. (2pts) Section 11.4 #  2b,d,f,h (p.774). You'll want to read p.766 (Regular Sets, Def'n and Example).
9. (10pts) We'll model the progression of a volleyball game with a finite state machine (as per notes). Our first attempt will be overly simplistic, but we'll add some features to arrive at a slightly less simplistic version.
   1. Let the set of states be
      S = { team1-to-serve, team1-to-return, team2-to-serve, team2-to-return }.
      (You can abbreviate these Srv1,Ret1,Srv2,Ret2.) Let the inputs be the set I = {Succeed,Fail} (you can abbreivate S,F), indicating a ref's call¹ that the current state's action just succeeded or failed, resp. Thus we think of our model proceeding along the lines of:

      state:  team2-to-serve
      input:    Succeed         [indicates team 2 served successfully.]
      state:  team1-to-return2
      input:    Fail            [oops, team 1 failed to return the ball.]
      state:  team-2-to-serve
      ...
      

      Specify the 4-state FSM best modeling a volleyball game. Express your answer in table format.
   2. Give a new FSM which allows for the possibility of a "re-serve": If a team is to serve but fails, they get one further attempt³ before losing possession. You will need to add a little more state.
      Express your answer as a picture of a directed graph with labeled edges (as in lecture, similar to Rosen 11.2). Neatness improves clarity!
   3. Scoring in volleyball is such that only the team which served may score a point⁴. Our FSM won't actually keep track of score, but it will indicate when one team or the other scores a point, via two new states "increment-team1-score" and "increment-team2-score". (After an increment, the referee will always give the input S.)
      This requires quite a few more states. Don't write down the answer for this part -- instead, just include your answer as part of the next subproblem.
   4. Currently, our FSM models a volleyball game that never ends. We'll modify this by letting the referee keep score⁵, and (after a team's score is incremented) they'll give the input "S" to continue the game, and "F" to indicate that that team just won.
      Express your answer as a graph, as before.
10. (0pts, not to be turned in) Check the grade database, to verify all your scores are correct. Scores up through hw09 should be included including exam1-redo, (with the possible exception of the hw06-ec single point, which for some may still be counted in the regular hw06 score). If there is a discrepancy, please bring it to TA/prof office hours, thanks!