1.
 a) 2^12 Bytes = 4KB
 b) 2^36 Pages
 c) 32MB / 2^12 = 2^13 (Frames)
 d) 2^36 * 64 = 2^42 (bits) = 2^39 (Bytes)

---

2.
 a) 1 frame: (^ indicates a page fault)
    1 2 3 4 1 2 5 6 1 3 1 2 7 6 3 2 1 2 3 6
    ---------------------------------------
    1 2 3 4 1 2 5 6 1 3 1 2 7 6 3 2 1 2 3 6
    ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
    3 frames:
    1 2 3 4 1 2 5 6 1 3 1 2 7 6 3 2 1 2 3 6
    ---------------------------------------
    1 1 1 4 4 4 5 5 5 3   3 7 7 7 2 2     2
      2 2 2 1 1 1 6 6 6   2 2 2 3 3 3     3
        3 3 3 2 2 2 1 1   1 1 6 6 6 1     6
    ^ ^ ^ ^ ^ ^ ^ ^ ^ ^   ^ ^ ^ ^ ^ ^     ^
    5 frames:
    1 2 3 4 1 2 5 6 1 3 1 2 7 6 3 2 1 2 3 6
    ---------------------------------------
    1 1 1 1     1 1   1     1
      2 2 2     2 2   2     2
        3 3     3 6   6     6
          4     4 4   3     3
                5 5   5     7
    ^ ^ ^ ^     ^ ^   ^     ^
    7 frames:
    1 2 3 4 1 2 5 6 1 3 1 2 7 6 3 2 1 2 3 6
    ---------------------------------------
    1 1 1 1     1 1         1 
      2 2 2     2 2         2
        3 3     3 3         3
          4     4 4         4
                5 5         5
                  6         6
                            7
    ^ ^ ^ ^     ^ ^         ^
 b) 1 frame:
    Same as a)

    3 frames:
    1 2 3 4 1 2 5 6 1 3 1 2 7 6 3 2 1 2 3 6
    ---------------------------------------
    1 1 1 2 3 4 1 2 5 6   1 3 2 7 6 3     2
      2 2 3 4 1 2 5 6 1   3 2 7 6 3 2     1
        3 4 1 2 5 6 1 3   2 7 6 3 2 1     6
    ^ ^ ^ ^ ^ ^ ^ ^ ^ ^   ^ ^ ^ ^ ^ ^     ^
    5 frames:
    1 2 3 4 1 2 5 6 1 3 1 2 7 6 3 2 1 2 3 6
    ---------------------------------------
    1 1 1 1     1 2 3     4 5   6 
      2 2 2     2 3 4     5 6   1
        3 3     3 4 5     6 1   2
          4     4 5 6     1 2   7
                5 6 1     2 7   3
    ^ ^ ^ ^     ^ ^ ^     ^ ^   ^
    7 frames:
    Same as a)

 c) 1 frame:
    Same as a)

    3 frames:
    1 2 3 4 1 2 5 6 1 3 1 2 7 6 3 2 1 2 3 6
    ---------------------------------------
    1 1 1 1     1 1   1     7 6     1     6
      2 2 2     2 2   2     2 2     2     2
        3 4     5 6   3     3 3     3     3
    ^ ^ ^ ^     ^ ^   ^     ^ ^     ^     ^
    5 frames:
    1 2 3 4 1 2 5 6 1 3 1 2 7 6 3 2 1 2 3 6
    ---------------------------------------
    1 1 1 1     1 1         1
      2 2 2     2 2         2
        3 3     3 3         3
          4     4 6         6
                5 5         5
    ^ ^ ^ ^     ^ ^         ^
    7 frames:
    Same as a)

 No cases exhibited Belady's anomaly for this sequence of virtual address references.
 All cases with only 1 frame exhibited thrashing. Cases a) and b) with 3 frames did, too. (My criteria for thrashing is more than 80% of address references cause page faults. Thrashing is an imprecise notion, and you could use your criteria, as long as it's reasonable.)

---

3.
 a) To minimize the seek time when accessing entries in the single directory.
 b) For some disk access patterns, e.g. compiling all the .c files in one directory, we could get better performance by putting the directory inode AND the inodes of those files close to each other, instead of putting all the directory inodes together.

---

4.
 a) 2(N - K) / N^2 when K != 0, 1 / N when K == 0.

    When K != 0, possible combinations are
      0         -> K
      1         -> K + 1
      ...
      N - K - 1 -> N - 1
      (Lower track # to higher track #)
    And also
      N - 1 -> N - K - 1
      N - 2 -> N - K - 2
      ...
      K     -> 0
      (Higher track # to lower track #)

    When K == 0, possible combinations are only
      0     -> 0
      1     -> 1
      ...
      N - 1 -> N - 1
    
    The seek can be from any of the N track to any of the N track (including the current track). So there are N^2 combinations overall.

 b)              N - 1
    0 * (1 / N) + SUM  i * 2(N - i) / N^2 = (N^2 - 1) / 3N (Use the hints!)
                 i = 1