| CPSC 327 | Data Structures and Algorithms | Spring 2024 |
About level of detail in describing data structures and algorithms —
Details tend to obscure the idea — start with an overview of the idea, then include further detail only as necessary to understand the algorithm and its correctness.
Code is nearly always too detailed to explain the idea. Pseudocode likely is too, unless it is very high level.
Use as high a level of abstraction as possible. If you can use a common ADT or data structure as a black box, do it — it is far easier to understand a description in terms of push and pop in a stack or inserting into an AVL tree or an array than when those operations are described at a lower level.
You don't need to describe how to carry out well-known ADT and data structure operations. Just say "push on the stack" or "remove from a sorted array" or "insert into a balanced search tree".
Provide specific implementation details only when they matter for running times. It is well-known that there's an implementation for Stack that achieves Θ(1) time for push, pop, and top so there's no need to identify whether an array or linked list is used to store the elements of the stack. For Map, there are several possible implementations with different running times so it is necessary to identify whether a hashtable or a balanced search tree is being used. It is not necessary to identify the specific flavor of balanced search tree unless something in your algorithm depends on that.
Be careful with assuming that something is Θ(1) because you can write it down without loops for a particular value of n. For example, it's possible to check for a win by player X in the traditional 3x3 tic-tac-toe as follows:
if ( board[0][0] == 'x' && board[0][1] == 'x' && board[0][2] == 'x' ) {
return true;
} else if ( board[1][0] == 'x' && board[1][1] == 'x' && board[1][2] == 'x' ) {
return true;
} else if ( board[2][0] == 'x' && board[2][1] == 'x' && board[2][2] == 'x' ) {
return true;
} else if ( board[0][0] == 'x' && board[1][0] == 'x' && board[2][0] == 'x' ) {
return true;
} else if ( board[0][1] == 'x' && board[1][1] == 'x' && board[2][1] == 'x' ) {
return true;
} else if ( board[0][2] == 'x' && board[1][2] == 'x' && board[2][2] == 'x' ) {
return true;
} else if ( board[0][0] == 'x' && board[1][1] == 'x' && board[2][2] == 'x' ) {
return true;
} else if ( board[0][2] == 'x' && board[1][1] == 'x' && board[0][2] == 'x' ) {
return true;
} else {
return false;
}
This might look like a fixed number of steps because there aren't any loops, but what happens as n increases? There will be 2n+2 cases in the if and each case involves n conditions — the number of simple steps is Θ(n2).