Q: What make backtrack unique from other types of recursion
A1: live answered
Q: is struct similar to class?
A1: Yes, very much so
Q: why do we have to add a ; at the end of the closing brace when making a struct?
A1: It is required in C++ syntax
A2: When you forget it, you be punished with an inscutable mess of complaints from compiler :-)
Q: do we need a helper function to solve this if we just adjust “target” based on how much weight an object adds?
A1: You can
A2: No, you’re exactly right. We can either count up in currentScore and compare to original target, or decrement remaining as we consume and compare to 0
Q: when would you want to use a return statement to pass info b/w calls and when would you want to use a parameter?
A1: Usually we use parameters to build up data structures and return values for “simple” pieces of infromation (int, bool, etc.)
Q: quick side question: is the information we learn about data types in this class applicable to other programming languages? i.e. are sets always faster than vectors in java too?
A1: Yes, typically the data structure information transferrs to different languages as well
A2: Yes! In this class we are generally learning about “abstract data types” in the sense that we describe large classes of data structures that show up in all kinds of different programming languages.
Q: why return 0 twice in base case 1?
A1: live answered
A2: live answered
Q: Why did you use a vector instead of a Queue for the objects?
A1: live answered
A2: We need to be able to both insert and remove the object from the frnt of the data structure (can’t do the former with a queue)
Q: Could one do this function without the currentscore parameter as the score is what is getting returned, or is it necessary?
A1: live answered
Q: Can't we be destructive with an input vector like in this case if it's passed by value?
A1: Yes, we could. But then we would be making copies of vector all over the place which could be inefficienct.
Q: why is it important to pass the vectors through reference?
A1: live answered
A2: We pass data structures by reference in order to avoid having to make copies of the data structure at every point of the recursion.
Q: does it because we pass in reference so we need to add object back
A1: Yes, exactly.
Q: would a stack have worked in place of a vector to keep track of the objects?
A1: live answered
A2: live answered
A3: Sure, you could probably make it work that way.
Q: Could the combination change based on the order in the vector or will this always guarantee the maximum score?
A1: The order items are added to the backpack doesn’t matter, they add to same weight/score
A2: This will always try all combinations of objects, so order in the original vector doesn’t matter.
A3: It will always garuntee the maximum score, you may just visit the numbers for this solution in a different order
Q: generally speaking, does it make sense to first find the solution, then modify your function to return the actual values
A1: Surprisingly, I would say no. For example, it is easier to confirm that you have moved to the maze edit than to also have tracked the path that lead here
Q: Are we going to use structs in Assignment 4?
A1: No
Q: Can you use a global vector for the best solution?
A1: No, we really try to avoid use of global variables.
Q: where in the code it removes the non related solution
A1: I am not sure I understand the question. Can you clarify?
Q: is recursive backtracking used for finding combinations?
A1: It can, yes
Q: If you changed the function to return the optimal vector instead of the optimal score, could you possibly do away with passing in both bestsolution and currentsolution vectors?
A1: You will still need the current objects in the knapsack, but the return value of best could take the place of the best parameter
Q: Though I don’t think it matters for functionality, does it matter style wise if we used else if for base case 2 and else for the recrisive case?
A1: Not really (see https://us.edstem.org/courses/2537/discussion/143264 for more)
Q: why we remove from current solution?
A1: We are now testing out a new solution where we don’t consider the current object
A2: Same reason that we add back to the list of objects – we need to make sure that any data structures that are passed around by reference are returned to their original starting state beofore the recursive call returns.
Q: How can we find all solutions that are the best? In other words, if there are multiple best solutions how can we find all?
A1: live answered
Q: what is the big(O) of the algorithim?
A1: live answered
Q: could we potentially extend this function to find solutions that exactly fit in the bag, i.e. weight == 0 for all solutions? .
A1: live answered
A2: live answered
Q: In this week's assignment I've done everything but the function operators are matches. In all of the given examples of exploring a string with recursion the functions either return a string so the original function can use the altered string or the original string is supposed to have a consistent structure like symmetry allowing you to work inward. It seems like when testing operators whenever you remove a pair in the middle of the string there's no way to pass back the new string to the old function and there's no way to send the cut out operators to the new functions for continued analysis. Is there something I'm missing?
A1: Come to my office hours after lecture!
Q: why u do currentSolutionObjects.remove(currentSolutionObjects.size() - 1);
A1: live answered
Q: Could you trace through an example with the second way?
A1: live answered
Q: The second method of solving it
A1: live answered
Q: To find big-O of a recursive function, is it just how many branches are created? Then if there is a loop in the recursion that goes to n, it would be n * branches_created_each_time^n?
A1: It may very from probelm to problem depending on the specifics of the work you do at each point, but that is a good general approach. Big O is driven by the branching factor of the recursive calls and the number of “leaves” at the bottom of the recursive tree.
A2: Generaly the two things you need to know is how many branches (how many recursive calls are fired off) and how deep the tree gets. Together this gives you the shape of the entire tree and you can read the big O off of that shape
Q: That makes sense!
A1: live answered
Q: how would subracting the objects be represented in the decision tree
A1: Think of that as the set of available objects at every level of the tree shrinking (the number of choices you have available decreases)
Q: that was helpful, please post that tree on ed
Q: Wait where can I find the office hour links
A1: https://web.stanford.edu/class/cs106b/restricted/zoom_info
Q: thanks!
A2: live answered