CS 106B: Programming Abstractions (C++)
Spring 2015

Pre-section problems: Due to an error on our web site, the section did not appear until late Wednesday. Therefore, pre-section problems are optional this week. Merely attending and participating during your section will earn you full points.

If you want to solve the optional pre-section problems for practice, they are:

1. Review question 18.10 (p814) - Write a representation of the given graph as a pair of sets, V and E.
2. Review question 18.11 (p814) - Draw the adjacency list representation of the graph. Also draw an adjacency matrix representation of the graph.

Pre-section problem: Solve the following review problem on paper (hand-written or printed) and bring your sheet of paper to your section:

1. Review Question 16.9 (p724). Draw a picture of the binary search tree (BST) that would result after adding the strings listed in the problem. Assume that the BST orders the strings based on alphabetical order, with names earlier in the alphabet being considered "less than" ones that come later in the alphabet.

Pre-section problem: Solve the following two (2) review problems on paper (hand-written or printed) and bring your sheet of paper to your section:

1. Review Question 11.18 (p509). The problem asks you to evaluate the result of performing some pointer operations on integers. Trace through the statements given and list the values of all variables after each step. Draw arrows to represent pointer targets if you like.

2. Linked node question. (This problem does not come from the textbook.) Suppose we have a chain of linked nodes that looks like the following:

   ListNode* list = new ListNode(10);
   list->next = new ListNode(20);
   ...
             +----+     +----+    +----+     +----+
   list  --> | 10 | --> | 20 | -->| 30 | --> | 40 | /
             +----+     +----+    +----+     +----+
   

   What statements are necessary to turn it into the following new picture? You should not allocate any new ListNode objects using the new keyword, but you may create up to two pointers to existing objects if you like.

             +----+     +----+    +----+     +----+
   list  --> | 20 | --> | 40 | -->| 30 | --> | 10 | /
             +----+     +----+    +----+     +----+
   

Pre-section problem: Solve the following exercise problem on paper (hand-written or printed) and bring your sheet of paper to your section:

1. Exercise: diceSum modified. (This problem does not come from the textbook.) Modify the diceSum function we wrote in lecture so that it does not print duplicate combinations that are just rearrangements of each other. The idea of this exercise is described on slide 10 of the "11-backtracking2" lecture slides. You might need to add/modify the parameters of the helper function to implement this. For example, the call of diceSum(3, 7) should now print:

   {1, 1, 5}
   {1, 2, 4}
   {1, 3, 3}
   {2, 2, 3}
   

You can just write the answer by hand and make your best attempt to solve the problem. If you want to actually code them up in Qt Creator, you can do so using our starter project ZIP below, but you don't have to do so. If you type in your solution, you'll need to print it out or rewrite it by hand so that you can turn it in on paper at your section. We do not accept them digitally such as by email. Note that you do not need to write a complete program; just the relevant lines of code to answer the question. (See detailed information below about pre-section problems.)

• section04-code.zip

Pre-section problem: Solve the following exercise problem on paper (hand-written or printed) and bring your sheet of paper to your section:

1. Exercise 7.7: digitSum (p346). Make the function handle negative numbers by returning the negation of the value that a positive number would return. For example, digitSum(-123) returns -6.

You can just write the answer(s) by hand and make your best attempt to solve them. If you want to actually code them up in Qt Creator, you can do so using our starter project ZIP below, but you don't have to do so. If you type them in, you'll need to print them out or rewrite them out by hand so that you can turn them in on paper at your section. We do not accept them digitally such as by email. Note that you do not need to write a complete program; just the relevant lines of code to answer the question. (See detailed information below about pre-section problems.)

• section03-code.zip

Pre-section problem: Solve the following book exercise problem on paper (hand-written or printed) and bring your sheet of paper to your section:

1. Exercise 5.19: morse code (p258)

   Assume that there already exists a function named readMorseCodeMap that reads an input file of Morse code mappings and produces a Map<char, string> from text characters to their Morse code equivalents. For example, the key 'A' maps to ".-" .

   You should write the following function:

   void toMorseCode(Map<char, string>& codeMap, string text)
   

   Your function accepts the Map described above, and a string to be converted, and should print out the Morse code equivalent of the given string to the console. For example, if the string is "SOS TITANIC", you should print "... --- ... - .. - .- -. .. -.-." (without the quotes). Note that the string might contain some characters that are not uppercase A-Z letters (like spaces); just skip those characters. For reference, our solution to this problem has 6 lines in the function body.

You can just write the answer(s) by hand and make your best attempt to solve them. If you want to actually code them up in Qt Creator, you can do so using our starter project ZIP below, but you don't have to do so. If you type them in, you'll need to print them out or rewrite them out by hand so that you can turn them in on paper at your section. We do not accept them digitally such as by email. Note that you do not need to write a complete program; just the relevant lines of code to answer the question. (See detailed information below about pre-section problems.)

• section02-code.zip

Pre-section problems: Solve at least one of the following two (2) book exercise problems on paper (hand-written or printed) and bring your sheet of paper to your section:

1. Exercise 5.2: mean (p247)
2. Exercise 5.11: reshape (p253)

You can just write the answer(s) by hand and make your best attempt to solve them. If you want to actually code them up in Qt Creator, you can do so using our starter project ZIP below, but you don't have to do so. If you type them in, you'll need to print them out or rewrite them out by hand so that you can turn them in on paper at your section. We do not accept them digitally such as by email. Note that you do not need to write a complete program; just the relevant lines of code to answer the question. (See detailed information below about pre-section problems.)

• section01-code.zip