| CPSC 327 | Data Structures and Algorithms | Spring 2024 |
ADM 3-4, page 103.
ADM 3-8, page 103. "...accepts a sequence of moves, and reports in constant time whether the last move won the game" means that the data structure should support "make a move" and "game over?" operations.
About "design/create a data structure" problems: describe what is stored and how, and explain how the desired operations are carried out and how the desired running time is achieved. "What is stored and how" includes the data structure containing the elements, how the elements are arranged in the data structure, and any other information stored. For "how the desired operations are carried out", you don't need to explain how standard data structure operations are done (like inserting an element at a particular position in an array), but you do need to explain how the operations of your data structure are carried out in terms of the "what is stored and how" structure and variables. Similarly, you don't need to explain the running time of standard data structure operations, but you do need to explain the running time of how your data structure's operations are carried out.
For example, consider how to implement an O(1)-time array-based queue:
Use an array elements to store the elements in the queue, with the beginning of the array corresponding to the head of the queue. Also store head, tail, and size, the positions of the head and the tail of the queue and the number of elements, respectively. tail is the first spot past the elements of the queue.
For enqueue(x), assuming there is room in the array, store the new element at elements[tail], then increment tail, wrapping to position 0 if tail is at the end of the array. Increment size. For dequeue(), increment head, wrapping to position 0 if head is at the end of the array, returning the element at head before it was incremented. Decrement size. For size(), return size.
Each operation involves only simple steps, so the running time of each is O(1).
At times, such as with the queue example above, it may be clearer and easier to use pseudocode to express some or all of the operations. That's fine. The key thing is to be aware that more detail is not necessarily beneficial — you need to express the algorithm with sufficient detail to be understood and to assess running time and correctness, but too many details overwhelms the ideas and obscures understanding. Review your writeup with an eye as to whether the detail you've included is necessary or if things could be expressed at a higher level of abstraction.