Homework 11: Counting, FSMs

Due 05.Apr.26 (Tue)

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

Reading: Rosen §§ 4.1-4.4
You may want to look at some q&a on this hw.

1. (0pts, not to be turned in) Check the grade database, to verify all your scores are correct. Scores up through hw08 should be recorded, including the exam1-redo-ec. You need to bring your graded hw09 by class or a labby/TA office hour, to have that score recorded, on or by Apr.26. If there is a discrepancy, please bring it to TA/prof office hours, thanks!
2. (3pts) Consider strings of length ≤ n over the alphabet Σ = {a,…,z}. What fraction of these strings are length exactly n? Give your answer as a constant plus a big-Oh error term that goes to zero (e.g., "1/2 + O(1/log(n))".) Show your work.
3. (4pts) Counting passwords.
   We will consider a few various passwords schemes. Let a "common word" be an English word 6-8 letters, found in a reasonable dictionary. As an estimate, we'll guess that there are 12,000 common words¹, and that there are an equal number of 6-, 7-, and 8-letter common words. Here are some password schemes that we'll compare:
   1. Common words.
   2. A common word, but with one letter's capitalization changed.
   3. A common word, with but with two letters' capitalization changed, and one other letter replaced by a digit.

      I originally had used ``insert a digit'' then re-wrote the problem as ``replace a letter by a digit'', but I was too glib about this revision:
      A student points out that ``table'' and ``fable'' could each lead to ``5able''. So, either:

      1. instead of replacing a digit by a letter, insert a digit,
      or
      2. assume that all common words differ by at least two letters (so if ``table'' were common, then: ``fable'' wouldn't also be common, but ``title'' would still be okay.)
      State which you use for your solution.

   4. A hyphenated pair². of common words e.g. ``frolic-meridian''.
   5. For reference: all possible strings of length 6-8, of 80 possible characters (which is roughly the number of letters, digits, and common punctuation).
   Supppose you're trying to find somebody's password by brute-force checking all possible combinations, and that you can check 10³ passwords/sec (over a web connection, say). For each of the above schemes, how long is needed to try all possibilities? Give your answer to two significant figures³, using the most appropriate unit from {seconds, minutes, hours, days, years}. Full credit for answers within 2% of the exact answer. (No real accuracy lost there — we're already making quite a few assumptions/estimates anyway.)
4. (2pts) Section   4.1, #54 (p.312). (|{n-var boolean functions}|)
5. (3pts) Section   4.3, #18 (p.325). (flipping outcomes).
6. (4pts) Section   4.3, #26 (p.325). (softball teams).
7. (3pts) Section   4.5 #10a,c,f (p.342). (croissants)
8. (2pts) Section   6.5 #  6 (p.456). (union)
9. (2pts) Section   6.5 #14 (p.456). (avoiding animals)
10. (2pts) Section 11.4 #  2b,d,f,h (p.774).
    You'll want to read p.766 (Regular Sets, Def'n and Example).
11. (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-return5
       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 interesting: 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.