Give specific description of an algorithm that provides enough detail for CS students to implement the algorithm.

As an example of how to describe an algorithm, consider the following data type for implementing a least recently used (LRU) cache.1 An LRU cache is a data type that stores up to N distinct keys. If the data type is full when adding a new key to the cache, the LRU cache first removes the key that was least recently cached. cache(key key): If there are N keys in the cache and the given key is not already in the cache, remove the key that was least recently used as an argument to cache and add the given key to the LRU cache. inCache (Key key) : Returns true if and only if the key is in the LRU cache. Suppose we want to design an LRU cache implementation where both operations usually complete in constant time, with the assumption of a good hash function that distributes keys evenly. It's not sufficient just to say, "Use a hash table and a linked list." While this hints at a high-level approach, it's not clear how the reader could implement the operations in the given time requirements. A better description explains how the data structures can be applied to solve the problem. We use two data structures: a doubly-linked list and a separate-chaining hash table. A doubly-linked list containing the N keys in the cache, with the most-recently cached key at the front and the least-recently cached key at the end. A separate-chaining hash table containing the N keys in the cache, where the value is a reference to the node in the doubly-linked list containing that key. To implement inCache (Key key), use the hash table to determine whether the key is in the cache. Implement cache (Key key) in three cases. 1 If the key is already in the cache, move the corresponding linked list node from its current position to the front of the list. 2 If the LRU cache is not yet full, add a new linked list node at the front of the list and create a corresponding entry in the hash table. 3 Otherwise, remove the last node from the linked list and the corresponding entry from the hash table. Then, add a new node to the front of the linked list with the given key and a corresponding entry in the hash table. Note that the complete case-by-case breakdown for cache isn't entirely necessary. The reader can infer the second case from the description of the invariants defining the relationship between the two data structures. It can also be inferred that removing an item from the linked list should also remove the corresponding entry from the hash table, though here we choose to include it for clarity. If this clause is needed in many places, we can mention it once at the beginning when declaring the data structure invariants. As an example of how to describe an algorithm, consider the following data type for implementing a least recently used (LRU) cache.1 An LRU cache is a data type that stores up to N distinct keys. If the data type is full when adding a new key to the cache, the LRU cache first removes the key that was least recently cached. cache(key key): If there are N keys in the cache and the given key is not already in the cache, remove the key that was least recently used as an argument to cache and add the given key to the LRU cache. inCache (Key key) : Returns true if and only if the key is in the LRU cache. Suppose we want to design an LRU cache implementation where both operations usually complete in constant time, with the assumption of a good hash function that distributes keys evenly. It's not sufficient just to say, "Use a hash table and a linked list." While this hints at a high-level approach, it's not clear how the reader could implement the operations in the given time requirements. A better description explains how the data structures can be applied to solve the problem. We use two data structures: a doubly-linked list and a separate-chaining hash table. A doubly-linked list containing the N keys in the cache, with the most-recently cached key at the front and the least-recently cached key at the end. A separate-chaining hash table containing the N keys in the cache, where the value is a reference to the node in the doubly-linked list containing that key. To implement inCache (Key key), use the hash table to determine whether the key is in the cache. Implement cache (Key key) in three cases. 1 If the key is already in the cache, move the corresponding linked list node from its current position to the front of the list. 2 If the LRU cache is not yet full, add a new linked list node at the front of the list and create a corresponding entry in the hash table. 3 Otherwise, remove the last node from the linked list and the corresponding entry from the hash table. Then, add a new node to the front of the linked list with the given key and a corresponding entry in the hash table. Note that the complete case-by-case breakdown for cache isn't entirely necessary. The reader can infer the second case from the description of the invariants defining the relationship between the two data structures. It can also be inferred that removing an item from the linked list should also remove the corresponding entry from the hash table, though here we choose to include it for clarity. If this clause is needed in many places, we can mention it once at the beginning when declaring the data structure invariants