Description
This project focuses on practical usage of hash tables in C++. Rather than implementing a hash table from scratch, we’ll make use of std::unordered_map, a templated hash table implementation that is provided by the C++ Standard Template Library. We’ll show you the syntax and a few points of caution. We’ll also discuss the std::pair type and how STL handles hashing of key types for std::unordered_map. Lastly, we’ll give an example of “memoization,” an important optimization technique that can make good use of the expected constant-time lookups that a hash table can offer. (There is relatively more reading than coding required in this project.) 2 Getting Started 2.1 C++ Environment Setup If you are new to C++, we recommend checking out the first MOOC in this course sequence, which has more information on getting your C++ programming environment set up. In particular, we show how to set up AWS Cloud9 to do your coding entirely through your browser, but it’s also possible to do this assignment on your own computer in Windows (with WSL Bash), in macOS (with some additional tools installed for the terminal), or in Linux natively. Cloud9 itself hosts a version of a Linux. In the Week 1 Programming Assignment item on Coursera, where you found this PDF, there is a download link for the starter files: UnorderedMap_starter_files.zip. If you are using a web IDE like Cloud9, you should still download the zip file locally to your computer first, then upload it to your Cloud9 workspace. With the default Cloud9 workspace configuration, make sure you’ve updated the compiler first, by typing this command in the terminal: sudo yum install -y gcc72 gcc72-c++ (If you forget to do that, you may see a compiler error message that C++14 is not supported.) Now, in the Cloud9 interface, click File > Upload Local Files, and select your local copy of the starter zip file to upload it to your workspace. After that, you’ll see that the zip file appears in the environment file listing on the left of the screen. Fig. 1: Updating the compiler in the Cloud9 terminal as described above. Next, you’ll want to extract the contents of the zip file to a new directory. Your terminal on Cloud9 already has some commands for this, zip and unzip. First, type ls in the terminal and make sure you Unordered Map Project Unordered Data Structures — Week 1 see the zip file in the current directory listing. If not, then as described in the earlier readings, you should use the cd command to change directory until you see the file in the same directory. You can use the file listing on the left side of the window to help you see where you are. The pwd command (“print working directory”) also reports where your terminal is currently browsing in the file system. Once in the same directory as the zip file, enter the following command to extract the contents of the file, which contains a subdirectory named UnorderedMap: (Be careful, because if you already have a subdirectory called UnorderedMap, this may overwrite files in that directory!) unzip UnorderedMap_starter_files.zip After you extract the code files, you should be able to see the filenames in the file list pane on the left, and double-clicking a filename will load that file in the code editor. 2.2 Provided Files Below we describe which files you are meant to edit and which ones you should read through for examples and hints. 2.2.1 Files that will be graded This time there’s only one file you must edit, and the autograder on Coursera will discard changes that you make to any other files. (You can add unit tests to the other files mentioned in the next section, but the autograder will discard those changes.) • UnorderedMapExercises.cpp: There are three exercises to complete, which are described in the code file (as well as in this document you are reading now). 2.2.2 Files you should study Among the other code files provided, some of them are meant for you to read through, even though you don’t need to edit them. They contain examples of syntax, hints, and comments about how things work. • through_the_looking_glass.txt: This text file contains the full text of the book Through the Looking-Glass by Lewis Carroll, published in 1871. (It’s the sequel to Alice’s Adventures in Wonderland.) You don’t have to read the book, but one of the helper functions we provide will load this text as a collection of individual words. • main.cpp: This defines the main program, which you can compile just by typing make at the terminal, as described later in this document. The program is set up by default to run some tests on your code and show some example output. You should read the provided code and try compiling and running the main program. Be sure to look through the terminal output for any warnings or errors. If you want, you can edit this file to add more tests and experiments of your own. • UnorderedMapCommon.h: This header declares or defines some of the types and helper functions that are used in the assignment. • UnorderedMapCommon.cpp: This file has additional implementation for the helper functions we provide. 2 Unordered Map Project Unordered Data Structures — Week 1 • IntPair.h: This uses a customized STL type to represent a pair of ints. It shows how we can add hashing support for this type using STL. • tests/week1_tests.cpp: This configures the test program you can compile with make test at the terminal, as described later in this document. This program runs some unit tests that have been defined with the Catch library. You don’t need to learn how to use the Catch library syntax, but this file shows more information about what exactly the test program will check on your code, and the autograder on Coursera will also run the same correctness tests. If you are interested in Catch, the documentation is here: https://github.com/catchorg/Catch2 2.2.3 Other files There are some additional files in the provided package, although you don’t need to look at them. They’re part of the mechanical inner workings of the assignment. For example, there are files containing Makefile definitions for the GNU Make program to use when it launches the compiler, and there is the source code for the Catch unit testing library. You are welcome to look at this code, but we won’t discuss how it works. 2.3 Compiling and Testing Your Code To compile the code, you must use the terminal to enter the same directory where the Makefile is stored; it’s in the same directory where main.cpp is located. As explained in the readings, use cd to change to the appropriate directory, use ls to view the file list in that directory (just to make sure that you’re in the right place), and then type make to automatically start the compilation. If you need to clear out the files you’ve previously built, type make clean. If you encounter any warnings or errors during compilation, study the messages in the terminal carefully to figure out what might be wrong with your code. If your compilation is successful, you’ll get an executable file simply called main in the same directory as main.cpp. You can try running it by typing ./main while you’re in that directory. As the compilation message suggests, you should also run the unit tests included in the test program. To compile the test program, just type make test at the same prompt. If this compilation is also successful, you’ll see a file named test appear in the directory. Then, you can run it by typing ./test similarly to before. As you work on your code, recompilation is faster if you don’t do make clean, but cleaning the previously-generated files can help to resolve some compilation errors, so we’ll show you some one-liner commands that will clean, recompile, and run. • To recompile and run the main program: make clean && make && ./main It’s faster to recompile by just doing “make” without “make clean”, but using “make clean” can help ensure correct compilation if you’ve been getting errors, since it clears all of the generated files that are remaining from your last compilation. • To recompile and run the unit testing suite: make clean && make test && ./test For this assignment, you can run the same test suite that the autograder will use on Coursera. 3 Unordered Map Project Unordered Data Structures — Week 1 2.4 Submitting Your Work When you’re ready to submit your work for final grading on Coursera, you’ll need to bundle it into a zip file in a specific way. To do that, you can type this command from your main subdirectory, where the Makefile is located: make zip This will automatically package the files to be graded into a new zip file, UnorderedMap_submission.zip, which will appear in the same directory. You can download the created zip file to your own computer from Cloud9 by right-clicking on the zip file in your Cloud9 file list and choosing “Download.” Once you’ve got the zip file on your local computer, you can log into Coursera and submit the zip file for this assignment. (If you need a reminder about how to use Cloud9 or how to submit work on Coursera, the first MOOC in this course sequence on Coursera has more detailed information about these topics in the lessons and homework assignments.) 3 Background Information Here we discuss some of the topics, concepts, and syntax that the project touches upon. Much of this information is supplementary rather than essential, but please read to get the best understanding of what’s going on in the project code. 3.1 Overview of std::unordered_map The Standard Template Library in C++ offers a hash table implementation with std::unordered_map. It has this name because a hash table is a more specific implementation of the abstract data type generally called a “map,” which associates each unique lookup key with an assigned value. It is called “unordered” in C++ to distinguish it from another map implementation, std::map. We will focus on std::unordered_map below, but let’s briefly summarize how it’s different from std::map. The implementation of std::map uses some kind of balanced tree (the specifics may vary from system to system). It maintains keys in a sorted order as a result, which is desirable sometimes, such as when you want to iterate over the keys in the same order repeatedly. It offers O(log n) lookup times. In order for classes to be compatible as key types, they need to have an equality operation defined, as well as a “less than” operation defined for sorting. By contrast, std::unordered_map is implemented as a hash table, and the keys are not arranged in any predictable order, but instead are placed in hashing buckets as described in the lectures on hash tables. It offers very fast O(1) lookup times on average (that is, constant-time). For a class type to be compatible as a key, it must have an equality operation defined, and it also must have a hashing function defined. We’ll talk more about that later in this document. Although lookups on std::unordered_map are very efficient, after inserting many items, the table will be automatically “re-hashed” and resized, and that can periodically lead to temporary slowdown. In the future, if that is an issue you can do additional work to specify optimal sizes beforehand, but we will trust in the system defaults to balance the load factor and maintain the table organization. We may refer to objects of type std::unordered_map simply as “maps” sometimes for shorthand, so in the future, please take note about what kind of map is being used. For this assignment, we will only use std::unordered_map. 4 Unordered Map Project Unordered Data Structures — Week 1 3.2 Syntax for std::unordered_map We import the necessary headers with: #include To declare an instance of the class, we need to specify template parameters for the key type and the value type, like this: // Create a single map instance where each string is mapped to one int std::unordered_map<std::string, int> myMap; In this case, the key type is std::string, and the value type is int. Note that STL already offers built-in hashing support for std::string and several other of the basic numeric types. (However, things will get a bit complicated later on when we need to specify our own class types as keys.) We can do both lookups and assignments on our map using the [] operator: myMap[“five”] = 5; std::cout << myMap[“five”] << std::endl; // output: 5 It’s very important to note that [] can only be used on non-const instances of a map, because it returns a direct reference to the mapped value item that it found (and that could be used to modify the entry). In addition, if the key item doesn’t exist, it will be created as soon as you refer to it with [], and initialized with some default value. Therefore, if you don’t want to carelessly insert meaningless keys to your hash table, you should probably do something else to query whether a key exists before you look up its contents! The count member function will tell you if a key exists already or not. The name is somewhat misleading; it only returns 0 (not found) or 1 (found). However, in conditional statements, C++ can treat those integers implicitly as “false” and “true.” This is not to be confused with the size function, which tells you how many different keys there are total. Here is an example: // Check how many keys there are before our query: std::cout << “Map size: ” << myMap.size() << std::endl; if (myMap.count(“five”)) { std::cout << “Found \”five\” in the map. Value: ” << myMap[“five”] << std::endl; } else { // In this conditional branch, no lookup operation with [] happens at all! std::cout << “Did not find \”five\” in the map. The map is unchanged.” << std::endl; } // Check how many keys there are at the end: std::cout << “Map size: ” << myMap.size() << std::endl; Experiment with this to see whether the size changes or not after the check, depending on what you insert to the map beforehand! Note that although this example avoids bloating the map with new entries for keys not found, it is not optimally fast, because in those situations where the key does exist in the map, doing [] after count is essentially performing the same search a second time. In practice, if the hash table has few collisions, this shouldn’t matter very much. It’s also worth noting that there are some other alternatives for performing lookups on std::unordered_map, 5 Unordered Map Project Unordered Data Structures — Week 1 but they are a bit more advanced. For example, the at function will search for a given key and return a reference like [], but at will throw an exception if the key is not found, instead of modifying the map. For this reason, at can be used on const map objects when [] cannot. There is also the find function, which actually returns an iterator type, which is like a special pointer. The iterator points to a key-value pair found, or otherwise to the map’s end iterator given by end(). This is probably more cumbersome than using at, but it depends on how good you are at avoiding exceptions. If you do iterate over a std::unordered_map (keeping in mind that there is no particular order to the items), the individual items are the key-value pairs themselves. C++ has a special representation of a pair, which we’ll discuss next. You can see an example where we iterated over the pairs in UnorderedMapCommon.cpp, in the definition of the function sortWordCounts. Lastly, the erase function can eliminate a key and its mapped value entirely. 3.3 Pairs In C++, a special template allows you to pair one type with any other type as a single object. In many cases this is more convenient than creating an entire custom class just to bundle two things together. First, we should include this standard header: #include // for std::pair You may forget to do that sometimes because it is included along with certain other STL headers (like ), but pairs are also useful on their own. You can explicitly create a particular type of pair, and a particular instance of that type, like this: std::pair<std::string, int> myPair; myPair.first = “Hello, this is the string element.”; myPair.second = 42; As you can see, the std::pair template implicitly has members first and second that correspond to the elements. There is another way to construct a new pair, using the helper function std::make_pair: std::pair<std::string, int> anotherPair = std::make_pair(“sevens”, 777); Since C++11, you can use a generic initializer list in brackets {…} to initialize a pair. (You can actually use this kind of generic syntax to initialize many STL types besides pairs. For that reason, it’s not really compatible with the inferred auto type.) std::pair<std::string, int> anotherPair = {“sevens”, 777}; For convenience, we can make an alias to a particular type of pair we use a lot. You’ll see some aliases like this defined in UnorderedMapCommon.h, and we use them in the project code. using StringIntPair = std::pair<std::string, int>; StringIntPair anotherPair = {“sevens”, 777}; Some implementations of std::unordered_map actually uses std::pair internally for each key-value pair, and so some of the advanced helper functions of std::unordered_map directly deal with pairs. You can even initialize a map as a list of pairs: 6 Unordered Map Project Unordered Data Structures — Week 1 std::unordered_map<int, int> lookupTable = {{1, 10}, {2, 20}, {3, 30}}; std::cout << lookupTable[2] << std::endl; // output: 20 3.4 Issues with Hashing Since hashing is required for key types to be compatible with std::unordered_map, in those cases where we want to use something elaborate as the key, such as a pair of items, we need to define a custom hashing function. The Standard Template Library provides hashing support for many of the primitive types you would want to use as keys, but it won’t initially hash a custom class type you define yourself (not even a generic pair type that you’ve instantiated—but that may change in future versions of C++). As Prof. Fagen-Ulmschneider explains in the lectures, it is not easy to make a good hashing function by yourself! There is a lot of advanced analysis in designing hashing functions for specific purposes, to ensure a low number of collisions, or to provide some other desirable guarantee. For example, “locality-sensitive hashing” is the idea that similar values should be hashed into the same, or nearly the same, bucket. (That can be useful for geometric applications. Points in 2D space are just pairs of coordinates, for example; and it’s good to know when points are nearby.) The field of cryptography relies on hashing functions that have very strong theoretical guarantees about collisions. If you make a mistake in designing your hashing function, you may not only get very bad performance with your hash table, but you potentially could be creating a security risk. (In practice, the best way to avoid this particular danger is to never try to implement cryptography by yourself.) For the sake of discussion, let’s talk about a few practical and reasonable ways we can add hashing support for a custom type. The general principle will be to avoid literally defining our own hashing function, and instead rely on a known hashing function we already have access to. If you are strictly dealing with integers, there are known ways to map a grouping of several integers uniquely to another integer. This is nice because in theory, it shouldn’t have any collisions at all. However, in practice, our machine implementations of integers have finite precision, so we can still get collisions this way. (This concept is still useful as a basis for locality-sensitive hashing and some spatial algorithms. If you are interested, you might want to read about these topics: the Cantor pairing function, Morton code, Z-order curves.) We won’t use any of these methods for now. Instead, let’s work with reliable hashing functions that STL already gives us. Next we’ll discuss a trick that can apply these to new types. 3.5 String-Based Hashing Instead of trying to come up with a mathematical solution ourselves, then, we can at least try this: We know that STL provides hashing support for std::string already, so we know it can hash an arbitrarily long sequence of bytes, and let us assume that it does this reasonably well for common applications—not cryptographic or security applications, but just for use with hash tables. Then we should be able to hash objects in general by doing this: 1. Convert the custom object type to a string representation. First, convert the separate parts of the object to strings. 2. Combine the partial strings in a unique, non-ambiguous way. Distinct objects should not coincidentally generate the same string after combination; an example is shown below. Any two unique objects must turn into different strings. 7 Unordered Map Project Unordered Data Structures — Week 1 3. If the object is made up of sub-objects that contain more sub-objects, then the above steps might have to be applied recursively. 4. Take the overall combined string. Apply a known safe hashing function to the string. For the sake of this project, we have already provided you the file IntPair.h which implements this for the type std::pair<int, int>. The standard include gives us the default conversion function std::to_string, which can convert an int to a string. We convert both of the two ints to strings. Then, we combine them with the string “##” in the middle; this matters to ensure point 2 above, because otherwise string pairs like (1, 21) and (12, 1) would have the same representation: • With simple concatenation: (1, 21) and (12, 1) both become “121”. • With “##” as a separator: (1, 21) becomes “1##21”, while (12, 1) becomes “12##1”. If you want to use this separator trick for things other than integers, you need to make sure that the separator you insert cannot be anything that would appear in one of the component strings by itself. For example, if we were dealing with a pair of strings instead of ints, it is challenging to think of a separator sequence that would definitely not appear in one of the input strings. 3.6 STL Hashing Support In the provided file IntPair.h, you can see how we defined the pair type IntPair and how we added hashing support for it based on std::string. There are quite a few comments in that file, but to summarize: In , STL provides std::hash, which is the basis for how types like int and std::string are hashed. Technically, the type std::hash is a “function object,” which means it’s an object type that is intended to be applied just as if it were a function, by overriding the () syntax. So, this is a class type that represents a hashing function. By default, STL containers like std::unordered_map that require a hashing function use std::hash internally to hash the key type. So, when we create a map, we don’t have to tell it what hashing function to use, provided that std::hash already supports the key type we need. The issue is that std::hash is templated to support some types by default, but not all. So, we need to extend the template to support our custom type. This is called template specialization in C++, and it has a special syntax beginning with a strange-looking, empty template argument list: template <>. If you are interested, for the rest of the details, please look over the source code in IntPair.h. We won’t ask you to do this in the assignment, but you may want to do this yourself in the future as you use C++! You may be wondering: What happens if we don’t do this, and we try do declare our custom std::unordered_map anyway, even with an unsupported key type? Well, that just generates a compilation error, because std::unordered_map will try to instantiate std::hash in the necessary way, and it won’t be able to find any definition for your key type. This seems to be a big point of confusion for beginners who want to experiment with hash tables. Just remember: you can’t make a hash table until you have a hashing function. 3.7 Memoization Here we’ll briefly discuss a motivating example of how fast lookups with a hash table can accelerate an algorithm. We would like to cache any partial calculation results that could be reused efficiently while solving the same overall problem. This is one of the reasons why, at large scale, it is so important to have O(1) lookups (as with a hash table) instead of O(log n) (as with a balanced tree structure). This is 8 Unordered Map Project Unordered Data Structures — Week 1 just scratching the surface of a much broader topic, and it’s somewhat beyond the scope of this course, so we only introduce the topic for enrichment. First, observe that it’s a common problem-solving technique to break larger problems into smaller ones. This is one of the fundamental principles involved in recursion: the process must eventually reach a base case or recursion will never end, therefore making progress requires that the problem keep getting broken up into smaller problems. It’s also implicit in iteration: When you iterate through a list and perform work on each item, you are essentially using a recursive approach, even if you are only writing a loop. You could state the logic like this: Iterating over a list recursively: 1. If you are considering an empty list, stop. 2. Process the first item on the list. 3. Now, consider the rest of the list: all the items after the first. This is also a list itself, just smaller than before. 4. Run this same algorithm on the smaller list. To recurse on the smaller list is basically the same thing as to “repeat from step 1.” Hopefully you’re beginning to see intuitively that there are only superficial differences between recursion and iteration. When we try to solve a new problem, regardless of whether we use loops or recursion, the important thing to focus on is breaking the problem down into smaller problems. The recurrence isn’t always as simple as the linear relationship suggested in the example above. Sometimes, a problem breaks down in such a way that identical “subproblems” appear multiple times in its structure. There may be a way to index the distinct problems so that when the same essential problem comes up again, its previous result can simply be looked up from memory. When we systematically label and record partial results, making sure to never recalculate anything needlessly, this is popularly called memoization (not “memorization,” but memo-ization, as in “writing a memo” to oneself). In particular, this could be described as implicit memoization, since we can do this somewhat automatically just by adding a few hash table lookups and insertions to our code. One of the exercises in this project contains an interesting recursive problem that has already been solved for you. You’ll get the opportunity to insert the hash table operations that accelerate it, and see the impact on the runtime. In practice, it is sometimes possible to identify ahead of time the order of dependency among the subproblems in the overall structural pattern. In those situations, you could also potentially preallocate a static amount of memory for the partial results, and then explicitly calculate the subproblems in the order that maximizes the reuse of information. This analysis and problem-solving strategy in general is called dynamic programming. Learning how to identify the structural dependencies is more complicated than we can discuss here, but if you’re interested, we recommend the book Algorithms, written by Prof. Jeff Erickson at the University of Illinois. You can find it here: http://jeffe.cs.illinois.edu/teaching/ algorithms/ 4 Exercises Before you begin the exercises, please make sure you’ve read this PDF and examined the code in the provided files. It’s always best to begin by reading through the code that you are given. There are comments throughout and many hints about how to do the exercises. Some of the helper functions, examples, and tests show coding techniques that are directly applicable to the exercises. (However, the code you need to write for the exercises is usually much simpler than any of the examples we provide.) 9 Unordered Map Project Unordered Data Structures — Week 1 This week, there are three exercises to complete, located in UnorderedMapExercises.cpp. The exercises are clearly marked in the file with some additional instructions in code comments. Here we’ll describe the problems as well. When you are working, be sure to compile and run both the main and test programs separately to make sure everything is correct. 4.1 Exercise 1: makeWordCounts First, notice that this type alias is defined for convenience in UnorderedMapCommon.h: using StringIntMap = std::unordered_map<std::string, int>; You need to finish implementing the function makeWordCounts in UnorderedMapExercises.cpp, which has this function prototype: StringIntMap makeWordCounts(const StringVec& words); makeWordCounts takes a vector of strings, which are in no particular order and which may contain duplicates. You can assume that such a vector has already been created properly and passed to your function. (The main program tests this on the text of Through the Looking-Glass.) You need to make sure to prepare an empty StringIntMap on the stack in function scope, which should be returned from the function when you’re done. You need to iterate over the vector words that has been passed in, using whatever form of iteration you choose, and for each unique string encountered in the vector, a entry for that string should be inserted in the map (the string itself is the key). The mapped value for each key should be the number of occurrences of that exact string. Example: If the input is a vector containing {“dog,” “cat,” “dog”}, then the map should have these mappings: Key: “cat” maps to value: 1 Key: “dog” maps to value: 2 You do not need to perform any string operations on the strings. For example, you do not need to change the strings to lowercase or parse the strings in any further way. You can handle each string exactly as it appears in the input. 4.2 Exercise 2: lookupWithFallback You need to finish implementing the function lookupWithFallback in UnorderedMapExercises.cpp, which has this function prototype: int lookupWithFallback(const StringIntMap& wordcount_map, const std::string& key, int fallbackVal); As described earlier in this document, sometimes it’s not the best practice to use [] in situations where lookups would add undesired keys to your map. Moreover, you can’t use [] with a const map object at all. This is a wrapper function for safely performing lookups on a read-only std::unordered_map object. The function should not modify the original map that is passed in. It should search for the key in the map, and if the key exists, then the corresponding value should be returned. If the key sought is not found, then the provided fallback value argument should be returned instead. (In some other programming languages, there is a standard library function that behaves this way.) 10 Unordered Map Project Unordered Data Structures — Week 1 4.3 Exercise 3: Memoizing a Function This exercise is mostly a conceptual illustration of the memoization topic introduced earlier in this document. There is not that much you need to change in the code. But, the small changes you’ll make to the provided code will have a drastic impact on the performance of the provided main example program. A palindrome is a word that remains the same if its spelling is reversed. For example, dad and mom are palindromes. In the provided code file UnorderedMapCommon.cpp, there is a definition of a function called longestPalindromeLength, which is a very slow function. Given a string and two integer indices representing left and right limits for our search, we want to find the length of the longest palindrome substring anywhere between the left and right limit indices. (A substring needs to be made of contiguous characters, so we can’t skip any characters to form a substring. Using the initial string “abcd” as an example, “bc” is a substring, but “bd” is not a substring.) We can understand the problem recursively by realizing that for any palindrome, these cases are true: • An empty string is a palindrome. • A single-character string is a palindrome. • For other strings, if the first and last characters match, and the substring contained in between those is a palindrome, then the entire string is a palindrome. (For example, in the string DAD, since D = D, and the middle part A is a palindrome, then the entire string DAD is a palindrome.) Since our function returns the length of the longest palindrome found anywhere between the limits, as an example, given this string: “xyzwDADxyzw,” and these limits: 0 and 10 (which are the first and last character indices), we can calculate that the longest palindrome length is 3, because “DAD” is the longest palindrome substring to be found. This calculation can be very slow because a naive program may exhaustively re-check the same internal substrings many times, and indeed, longestPalindromeLength will run very slow on large input strings. In Exercise 3, there is an edited version of the palindrome finding function, which is called memoizedLongestPalindromeLength. This version of the function takes an extra parameter, LengthMemo& memo, which is the “memoization table,” that is, a hash table to be used for caching calculation results. The LengthMemo type is defined in UnorderedMapCommon.h like this: using LengthMemo = std::unordered_map<IntPair, int>; Therefore, LengthMemo is an unordered_map where each key is an IntPair (using the custom hashing scheme we discussed earlier in this document), and each mapped value is an int. The IntPair key is a pair of left and right index limits, and the mapped int value is the recorded calculation result. So for the same “xyzwDADxyzw” example given above, one entry in the map would be this, which signifies the result for the entire length of the string: Key: the pair (0, 10) Mapped value: 3 Here is your task: In order to make use of the memo object for caching purposes, you need to edit the memoized function in two different, very specific places, which we have clearly marked with comments as “PART A” and “PART B.” There are also other hints given in the function’s comments, clearly marked “EXAMPLE.” If you examine the source code in main.cpp, you’ll see that there are several sizes of test case strings that you can enable. Some of those will run extremely slow without memoization, and comparatively 11 Unordered Map Project Unordered Data Structures — Week 1 extremely quickly after memoization is enabled. To prevent confusion, we’ve added a mechanism that passes the running time into the palindrome-finding function, and it will time out and stop if things take more than a few seconds. However, even on the small examples, after you have completed this exercise, you’ll be able to see a measurable difference, which the main program output will report to you in the terminal. The unit testing suite will check your code for correctness another way, by verifying that you have filled the memoization hash table accurately. When the table is correctly filled, the provided reconstructPalindrome function will be able to identify the actual palindrome substring based on the lengths recorded in the table. You can study that function’s comments to see how it works too. In practice, it’s common to use such a reconstruction method with dynamic programming algorithms.
