Lecture 5/27: Lecture 22 Q&A
Lecture 22 Questions and Answers (Exported from Zoom Q&A log)
Q: whats the definition of BFS?
A1: breadth first search
Q: did the university guidelines apply just for CS classes?
A1: No, it applies to all spring quarter courses
Q: Is the optional BlueBook exam gonna look like the midterm that we took?
A1: It will look like a traditional CS106B final exam, timed, comprehensive over entire quarter, problem solving in written form (well, typed) using BlueBOok
Q: Will the final be cumulative?
A1: yes it will cover content from the whole quarter
Q: can we do the end quarter meeting if we dont take the exam
A1: Yes!!
Q: best news ive gotten in a long time
A1: Enjoy, you have all been working hard!
Q: “We will provide students with the opportunity to check their current standing in class.” Will this be made explicit, e.g. in an announcement?
A1: Yes
Q: what will exact grading on the exam be? as in what will be looked for by SLs
A1: It will be graded in the same way that a traditional exam would be
Q: are the university guidlines saying that finals are optional or are they something different than that?
A1: They say that a final has to fit into one class period which for us liimted to 50 minutes for which we cannot really test much at all
Q: could chris also tell us when his rescheuled office hours will be?
A1: I will remind him, thanks. My office hours are after class today if you want to stop in!
Q: what are the keys again?
A1: He is speaking of using a BST as the implementation for Map of key-value pairs
Q: what if there is another 6?
A1: It could go to either left or right subtree
Q: can elements appear more than once?
A1: yes
Q: do these always have to be ints? if not, how do we rank other data structures as bigger and smaller?
A1: The elements do have to have ordering, i.e. some form of less than, equal, greater. For strings, it could be alphabetic order, say.
Q: if they repeat would they appear on the left or right?
A1: It could be either.
Q: Awesome, okay!
A1:
Q: Is it a problem that we define the ::findMin() method twice?
A1: It is allowed to do that if the two same name functions have different signatures (i.e. one has no arguments, the second has one Node * parameter)
Q: would it be possible for t=3 to have a left node of 2 or 1 considering that the 3 itself is already to the right of 2, so does everything coming off of it also ahve to be alrger than 2?
A1: The latter — all nodes in right subtree of 2 have to be greater than 2. The BST ordering applies locally (to parent and immediate left/right child) but also globally (to entire subtree)
Q: how do you compare if a string is less than the other
A1: “apple” < “banana” compares in lexicographic order
Q: didn’t mean to type t=3, sorry, i just meant the 3 node
A1:
Q: Why were we using strings in node->string if we were dealing with number comparison in contains?
A1: Contains is using == and <, these operators also work on strings
Q: Will the value you’re adding always be placed in an “empty” spot or is it possible for you to replace the value of a current node?
A1: for add, you are trying to insert a new element, so no, you would not want to replace a node, you want to add a new node. that node will be placed into an “empty” spot, i.e. what was a null subtree will become a new node
Q: if we were to add a 7 would that need to push the 8 down?
A1: No, a new node is always added as a new leaf (replacing what was previously a null subtree)
Q: if we modify a pointer of a list NOT passed in by reference, what are we modifying?
A1: We are only changing the copy, i.e. the parameter pointer variable
Q: why for addArmsLength do we not have to pass the Node* node by reference? Isn’t creating a new Node then only true that the copy will have a new Node?
A1: the addArmsLength doesn’t change the node pointer, it changes the pointer in node->left or node->right. This is tricky to see why this “works” and why assigning to node would not. Come to office hours and we can draw pictures together
Q: How many trees containing the first n natural numbers are possible? That is, how many arrangements are there?
A1: Good question — are you in 103/109? Think how you solve a combinatorics problem!
Q: Where did we define “left” and “right”? How does our program know what these mean?
A1: There is a TreeNode struct (defined last lecture) that two TreeNode * fields, one named left, one named right
Q: if you’re creating a new node, as in the first part of add(), are you giving it a left or right directionality?
A1: By the time we get to the null subtree that we are going to replace with new node, we arrived here via a traverse from left or right of parent
Q: why do we want to do pointer-to-pointer? it looks much more complex than other 2 options
A1: Behind the scenes, this is what a pointer reference is doing, just automatically. Some languages (C being the prominent example) do not have references and thus manual pointer-to-pointer is your only option
Q: How do you physically remove an element from a tree? Like syntactically.
A1: you would re-assign the parent nodes left or right pointer to a new value (i.e. parent->left = nullptr, would excise whatever was previously the left subtee of parent)
Q: isnt o(n) good?
A1: O(N) is ok, but O(logN) is much, much better
Q: Are these 2 things the same?
void replaceNode(string s, Node*& node) { node = new Node(s); }
void replaceNode(string s, Node* node) { (*node) = new Node(s); }</i>
A1: live answered