7 Bonus Part For extra bonus point, you can implement a data structure that is more efficient than (double) linked lists. Linked lists have terrible performances: when searching for an element that is no in the dictionary you need to go through all pairs key/value. Tweaking your dict_put to ensure that the list is always sorted by keys does provide a speedup, but of only 30%, which is still much too slow. By sorted here, we mean according to the return value of strcmp(3). Indeed, this function does more than just checking whether two strings are equal: • If strcmp (a, b) < 0, then a would appear before b in a real-life dictionary; • If strcmp (a, b) > 0, then a would appear after b in a real-life dictionary. You can score most bonus points with a simple binary search tree based on this order. The idea is to have a binary tree where each node stores a pair key/value. The nodes to the left of a given node contain keys that are smaller, while the nodes to the right contain keys that are greater (according to the order given by strcmp(3)). To search for a key, we start at the root, and check the return value of strcmp: if it is e, we found the key; if it is negative, the key may be in the left subtree but not the right; if it is positive, the key may be in the right subtree but not the left. To insert a new pair, one would go down the tree as if to search for the pair's key and insert the new pair at a leaf. To delete a pair, one would for instance replace the pair with its left subtree, and put its right subtree as the leftmost child of the right subtree of its parent. Refer to your data structures textbook for more details. Implementing binary search trees provides a speedup of around 82% (what takes 60 seconds with a linked list takes about 1 second with a binary search tree). Since the benchmark files are random, binary search trees perform nearly as well as more complex balanced version that you may have seen in Data Structures II. Activate Windows

7 Bonus Part For extra bonus point, you can implement a data structure that is more efficient than (double) linked lists. Linked lists have terrible performances: when searching for an element that is no in the dictionary you need to go through all pairs key/value. Tweaking your dict_put to ensure that the list is always sorted by keys does provide a speedup, but of only 30%, which is still much too slow. By sorted here, we mean according to the return value of strcmp(3). Indeed, this function does more than just checking whether two strings are equal: • If strcmp (a, b) < 0, then a would appear before b in a real-life dictionary; • If strcmp (a, b) > 0, then a would appear after b in a real-life dictionary. You can score most bonus points with a simple binary search tree based on this order. The idea is to have a binary tree where each node stores a pair key/value. The nodes to the left of a given node contain keys that are smaller, while the nodes to the right contain keys that are greater (according to the order given by strcmp(3)). To search for a key, we start at the root, and check the return value of strcmp: if it is e, we found the key; if it is negative, the key may be in the left subtree but not the right; if it is positive, the key may be in the right subtree but not the left. To insert a new pair, one would go down the tree as if to search for the pair's key and insert the new pair at a leaf. To delete a pair, one would for instance replace the pair with its left subtree, and put its right subtree as the leftmost child of the right subtree of its parent. Refer to your data structures textbook for more details. Implementing binary search trees provides a speedup of around 82% (what takes 60 seconds with a linked list takes about 1 second with a binary search tree). Since the benchmark files are random, binary search trees perform nearly as well as more complex balanced version that you may have seen in Data Structures II. Activate Windows