MATH 1120 Quiz: MATH 1120 Cornell WARMUP2018 Quiz4 26 18
Document Summary
20 april 2004: environment model [27 pts] (parts a d) Suppose we want to implement a game of n-by-n tic-tac-toe using a mutable data abstraction for the board. Consider the following representation: type board = { size: int, Using this rep, here is how we might implement the function create so that it takes only o(1) time in the board size: 1 fun create(n: int) = { size = n, x"s = ref nil, o"s = ref nil } However, some of the other operations are not so easy to implement. (c) [15 pts] give an appropriate representation invariant for this representation. Think about what will be needed to implement all of the functions in the interface above. (d) [6 pts] Suggest a different representation that would permit all of the operations except create to be implemented in time o(1) in the board size. type board : recurrences [20 pts] (parts a b)
