Lecture 4/29: Lecture 11 Q&A
Lecture 11 Questions and Answers (Exported from Zoom Q&A log)
Q: I accidentally showed up early but i love this song
A1: live answered
A2: glad to hear you’re enjoying it!
Q: Chris’ sound is a bit wonky
A1: live answered
Q: the sound quality on chris’ end isn’t great for me, pretty fuzzy
A1: live answered
Q: does chris sound muffled for anyone else?
A1: live answered
Q: sounds aweful to me to.
A1: live answered
Q: do we use a decision tree for predict?
A1: Yes! A decision tree is a great way to think about any form of branching recursion
Q: maybe check your zoom audio settings
A1:
Q: way better!
A1:
Q: much better
A1:
Q: what is the difference between Lexicon and a dictionary?
A1: A lexicon is just the word list, a dictionary has an associated value/definition for each word
Q: Is “lexicon” a new data type? If so, what do its “innards” look like? Like, is it a vector of strings . . . ?
A1: Great question — there are lots of possible options for how it is implemented, with various tradeoffs, we will look into it later during course
Q: is the font on QT different?
A1: I believe Chris said he is using his wife’s computer (his went into shop because of keyboard) so this is now a Windows system, fonts are different
Q: isnt it word.length() - 1?
A1: you want to consider deleting every possibel character, including the last one, so looping < word.length() si the way to go
Q: whats the difference between .size and .length
A1:
Q: for the homework should we also be making copies when handinling our strings?
A1: Maybe? It depends on what operations you are using. Some operations (like erase) modify the string, others create a new string (such as concat using +)
Q: on the pasting of the code on the handout, why is there
(int)word.length(); in the for loop. specifically why is the (int) there?
A1: To suppress warning about comparing signed versus unsigned (see pinned post on Ed about this)
Q: why do we return true and not the shortened word
A1: we are just trying to figure out whether the word is reducible or not, so a true/false result is all we want to determine
Q: why did we need the string copy = word line?
A1: live answered
Q: Does the lex contain proper names?
A1: It contains whatever words are in the data file. This particular data file EnglishWords.txt does not have proper names
Q: is the only reason for the copy string that wprd.length() is in the for loop?
A1: live answered
Q: A follow-up on the lexicon question, I know that we have to access a txt file of English words. Is this a “Lexicon” data type? I’m just worried that we’ll run into some exceptions or weird data type operator rules. Does “Lexicon” have its own operands? Built-in functions?
A1: The input file is just plain text listing of words. Those words are loaded into the Lexicon. The key operations on Lexicon are contains and containsPrefix
Q: for reducable, does it delete the letters from the center outward?
A1: The for loop tries deleting each letter starting from first to last
Q: does order in a power set matter?
A1: No, the elements in a set are not ordered. {a, b} is same set as {b, a}
Q: what does exploring with/without mean?
A1: The decision at this point in tree is whether to include first in the current subset (soFar) or to not include first
Q: what does substr(1) do when there is only one char in the string?
A1: it returns an empty string!
Q: where is the backtracking in our code?
A1: After fully exploring the “with” path, the algorithm backtracks to this point and then explores the “without” path
Q: if you would have reversed the order of the two recursive calls, would we get the same output, just in exact opposite order?
A1: Yes!
Q: walking through the debugger is super helpful!
A1: Yay! We love the debugger! your BFF
Q: so the entire tree gives the powerset?
A1: Yes!
Q: does it end on the bottom right or does it go back to the first node?
A1: It goes all the way back up to the top (root node of decision tree) Nothing more is printed after the bottom right though
Q: when we do these problems on our own for HW is it helpful to handdraw our own decisions trees and trace them?
A1: yes, absolutely! It is one of the most helpful things you can do to understand the recursion :)
Q: if the entire tree is the powerset, why did we return 2 different lists when we used listSubsets? Do we combine those lists to get the powerset? Or, why did we not have an empty set in the beginning to add those subsets into the powerset?
A1: The listSubsets printed the first half of the power set during the first call, and the second half in the second call.
Q: does predict on A3 use backtracking?
A1: it does an exhaustive recursion
Q: is the "choose" line a recursive call or are only explore and unchoose recursive calls?
A1: The explore is the recursive call, the choose/unchoose are updating the state before and after the recursive call
Q: {1,4} and {5} is the same sum?
A1: Yes, 1+4 = 5
Q: why can’t yous plit {1, 4, 5, 6} into, for example, {1, 5} and {6}
A1: For this particular problem, all elements from the original set have to be included in one set or the other (e.g. “partition”)
Q: Then how come chris said the vector 1,4,5,6 cant be split?
A1: In the partition problem, all elements from the original set have to belong to either set1 or set2, cannot ignore some elements
Q: Do we need to use all values? So the above example wouldn’t work?
A1: If you could ask non-anonymous, I would be able to know what former example you are referring to, but I’m kind of at a loss
Q: oh! thanks!
A1:
Q: can you zoom your code out just a little bit please
A1: live answered
Q: what is “rest”?
A1: It is the collection of elements that have not yet been partitioned into either sum1 or sum2
Q: will the base case always come before the recursive case?
A1: Most typically, yes.
Q: is removing from the back faster because there are larger numbers at the back of rest, and it’s more likely for larger numbers to equal the sum of the other numbers?
A1: No. It has to do with how a Vector stores elements. Removing an element at low-numbered index has to move all the later elements down one index. If you remove at highest-numbered index, no other element has to move
Q: if they both return false, is that the empty set
A1: If both return false, it indicates there was no possible way to partition the elements into 2 groups that sum to same value
Q: what is n here again?
A1: rest[0] (basically element chosen from remaining)
Q: what does the || mean?
| A1: Logic or -> a | Â | b is true if either a is true or b is true or both |
Q: what does reinserting the first number do for the function if the recursive functions have already been called?
A1: it restores the vector to hold the contents that it did before the initial call
Q: I'm still confused about why we have to insert the number we took out at the front. Why doesn't this start an infinite recursion where we keep checking the front?
A1: live answered
Q: If we did not use for loop, how are we iterating over the elements?
A1: Each level of the recursion considers one element from vector, so if there were N elements to start, the recursion wil go to depth N, and each level is considering one element
Q: wouldn't the lefthalf partitionable function returns bool value first and then the righthalf returns right after that? then how can the rest.insert function add the removed value back to the vector
A1: live answered
Q: when do we not use the insert?
A1: Hang out after lecture with Chris and ask in person!
Q: Oh, does that mean recursion is doing the loop?
A1: Effectively, yes
Q: why did we do sum1 + n ?
Q: can you explain the subset code again?
Q: back to the sums one again, how does it get to the final value of {1,2,3} and {1,5} does it split it by recusion?
Q: can you dive a little deeper into those last two lines?
Q: yes
Q: thank you