DS test3 6:55-8:45pmCSCI-1200 Data Structures Test 3 — Practice Problems Note: This packet contains...

Question

DS test3 6:55-8:45pmCSCI-1200 Data Structures Test 3 — Practice Problems Note: This packet contains selected practice problems from Test 3 from three previous years. Your test will contain approximately one third as many problems (totalling ∼100 pts). 1 Order Up! [ / 48 ] Alyssa P. Hacker is consulting for a restaurant to build a customer and order tracking system. Below is a small sample of the data structure she’s designed. She explains that it uses 5 different STL data structures, but it does NOT use STL vector, or the C-style array, or any custom classes. Jacob,1 apple_pie happy_meal fanta nuggets salad tea burger coke fries burger fries sprite coke fries salad Victoria,1 Herta,1Ben,2 Ben,1 Jacob,1 Ben,3 Herta,2Victoria,1 Jacob,1 Victoria,1Herta,1 Victoria,1 Jacob,1 The design allows us to study the frequency of meals (combinations of items on the menu) ordered by customers, and who has ordered the meal most recently. For example, 3 different customers have ordered the meal “salad & tea”. Herta has ordered that meal twice and Jacob has ordered it most recently. To record a customer order in the structure above, we typically use the following 3 argument function: placeOrder( data , "Jacob" , meal with burger, fries, and coke ); Where data is the complete structure diagrammed above. This call will update the fifth row of the structure to record that Jacob has now ordered that meal twice, and furthermore, the sequence will be changed so that Jacob is last (swapping places with Victoria) because he has now ordered that meal most recently. 1.1 Fast Food typedefs [ / 6 ] After looking ahead through the rest of this problem, let’s define a few helpful typedefs. You will be graded on the convenience and efficiency of the overall structure. Also remember that Alyssa said she used 5 different STL types, but NOT vector. typedef Meal; typedef Orders; typedef Data; 1 1.2 Organizing the Meals [ / 6 ] On the previous page we can see the restaurant’s desired organization for the meals. We should start with the simple (1 item) meals and progress to more complicated meals. Meals of the same complexity are organized alphabetically. Write the necessary helper function so this happens automatically. sample solution: 13 line(s) of code 1.3 Complexity Analysis [ / 6 ] Let’s assume that the restaurant has i items on the menu and c unique customers. Customers have created m different meals (each with at most k menu items). Any one meal has been ordered by at most d different customers, and at most t times by one customer. What is the Big ’O’ Notation for the following functions? placeOrder Note: We don’t ask you to implement this. namelessOrder You will implement this on the next page (page 4). orderMyFavorite You will implement this in a couple of pages (page 5). 2 1.4 Convenience for Our Most Loyal Customers: namelessOrder [ / 16 ] This structure allows us to streamline ordering for the most frequent customers. They don’t even need to leave their name when they place an order. For example: namelessOrder( data , meal with nuggets and fanta ); prints “Welcome back, Ben!” and places his order (because Ben has ordered that meal more often than anyone else!) However, attempts to use this function can fail and result in error messages: namelessOrder( data , meal with salad, fries, and coke ); will print to STDERR: “ERROR: What name should we put on this order?” (because two different people, Herta and Victoria, are tied for most times ordering that meal). And namelessOrder( data , meal with happy meal and coke ); will print to STDERR: “ERROR: No one’s ordered this meal before!” sample solution: ∼ 30 line(s) of code 3 1.5 We Know What You Want! orderMyFavorite [ / 14 ] Alternately, customers may re-order their personal favorite (most frequently ordered) meal: orderMyFavorite( data , "Herta" ); which will respond with the success message: “Placing your order for salad & tea.” However, orderMyFavorite( data , "Victoria" ); prints the error message “ERROR: You have multiple, equally-favorite meals.” (because Victoria has ordered four different meals, one time each). And orderMyFavorite( data , "Louis"); prints “ERROR: We don’t have any prior orders for you.” sample solution: ∼ 30 line(s) of code 4 2 Each Level, All Pairs [ / 16 ] Write a function named each_level_all_pairs that takes in a pointer to the root Node of a binary tree and prints all pairs of values from each “level” of the tree. For example, the function will print the following 10 pairs for the tree on the right, which has 4 levels: (2,3) (4,5)(4,6)(5,6) (7,8)(7,9)(7,10)(8,9)(8,10)(9,10) There are no pairs from the top level (because there’s only 1 value). There’s 1 pair from the second level. We have 3 values and 3 pairs from the third level, and 4 values and 6 pairs from the lowest level. Note: The extra space between pairs of different levels is optional. template  class Node { public: T value; Node* left; Node* right; }; 10 1 2 3 4 5 6 7 8 9 sample solution: 18 line(s) of code 5 3 tREeVISION (Tree Revision) [ / 20 ] foo Q D b c F A G bar d e b c a Write a function named treevision that takes in two Node pointers and modifies the first tree to match the second tree in shape and values. The function returns a Trio of three numbers, indicating how many nodes were edited, how many nodes were added, and how many nodes were removed. For example treevision(foo,bar) will return the values 2 3 1 because 2 nodes were edited (’a’→’A’ and ’d’→’D’), 3 nodes were added (’Q’, ’F’, and ’G’) and 1 node was removed (’e’). class Node { public: Node(char v):value(v){left=right=NULL;} char value; Node* left; Node* right; }; class Trio { public: Trio(int e,int a,int r):edit(e),add(a),remove(r){} int edit; int add; int remove; }; sample solution: 25 line(s) of code 6 4 Treeslinger Quick Draw! [ / 13 ] Draw a balanced binary tree with in-order traversal: the fox jumped over the lazy dogs Draw a binary search tree with leaves: 210, 10, 102, and √ 10. Draw a balanced ternary tree with pre-order traversal: 13 12 11 10 9 8 7 6 5 4 3 2 1 Draw a red-black tree with values ’a’-’g’, with root ’e’ and 3 red nodes: ’b’, ’d’, and ’g’. 7 5 Intensely Overloading on TA Office Hours [ / 41 ] Cameron (who helped develop YACS) is thinking about an extension to assist students in maximizing use of TA office hours for their registered classes. He has access to the following tables of data from the registrar using STL maps and vectors (shown here with sample data): Thursday 4pm, Folsom Abby Eric Milo Ryan Sinclair Tim Wendy ds physics1 cs1 bio ds calc1 cs1 bio ds psychcalc1 calc2 cs1 econ physics1 Ben Louis Wendy Thursday 4pm, Folsom Milo Thursday 4pm, Folsom Wednesday 6pm, Folsom Eric Tuesday 5pm, J−Rowl Cameron Friday 4pm, Sage Abby Monday 3pm, AE Thursday 2pm, Folsom students ta_assignments office_hours Ryan Thursday 4pm, Folsom Sinclair Cameron proposes we write a function GetHelp that takes in these 3 tables of data, and the name of a student, and returns an STL set of strings with the day, time, and location of all relevant office hours. For example, by printing the output of: GetHelp(ta_assignments,students,office_hours,"Ben"); We will learn that Ben should attend the following office hours: Thursday 4pm, Folsom Tuesday 5pm, J-Rowl Wednesday 6pm, Folsom 5.1 Just the typedefs, Ma’am [ / 3 ] After looking ahead through the rest of this problem, let’s define a few helpful typedefs: typedef type_t; typedef type_s; typedef type_o; 5.2 Let’s get Ben some help in Office Hours! [ / 13 ] Write the GetHelp function below. Perform some basic error checking. We suggest you use assert to verify any assumptions as you work through the implementation. std::set GetHelp(const type_t &ta_assignments, 8 const type_s &students, const type_o &office_hours, const std::string &student) { sample solution: 18 line(s) of code } 9 5.3 What Would Milo Do? [ / 12 ] Milo notices someone forgot their laptop charger in office hours. In addition to posting a message on the Submitty Discussion Forum, Milo would like to message students in the other courses that share his assigned office hour times and locations. Let’s write another function, GetShared, that returns an STL set of the names of other courses that share an office hour time and location with the specified TA. For example, if we print the return value of: GetShared(ta_assignments,office_hours,"Milo"); We will learn that Milo’s Data Structures office hours overlap with these other courses: bio cs1 std::set GetShared(const type_t &ta_assignments, const type_o &office_hours, const std::string &ta) { sample solution: 19 line(s) of code } 10 5.4 Who’s Afraid of the Big Bad ’O’ Notation? [ / 7 ] What is the running time for each of the functions you wrote? Let’s say that we have s students, each student takes on average k courses, the university has t TAs, each TA is assigned on average to h office hour slots per week, the university has c total courses, and the output contains x values. Justify your answers. GetHelp GetShared 5.5 Making some Mappy Improvements [ / 3 ] Is this the best organization of data to accomplish these tasks? Describe a minor change to one of these tables (still sticking with STL maps and vectors) that will simplify the algorithm(s) you wrote above and/or improve the big ’O’ notation. Write 2-3 sentences describing the change and why it’s an improvement. 5.6 Are Hash Tables always better than Binary Search Trees? [ / 3 ] If we switched the maps and sets in this problem to be hash tables, what would be one advantage/improve- ment? What would be one disadvantage/loss? Write 2 concise, technical, and well-written sentences. 11 6 I am the Lorax, I speak for the Trees [ / 36 ] In this problem we will inspect the structure of a memory diagram composed of Node objects, as declared on the right. We will decide if the current arrangement, contents, and coloring of nodes is a valid, well-balanced, binary search tree. Note: “red” nodes are visualized white. On the next two pages you will complete the implementation of the recursive functions used in the fragment of code below: template  class Node { public: T value; bool is_black; std::vector children; }; if (!is_tree(root)) std::cout

CSCI-1200 Data Structures Test 3 — Practice Problems Note: This packet contains selected practice problems from Test 3 from three previous years. Your test will contain approximately one third as many...

Get Answer To This Question

Related Questions & Answers

Submit New Assignment