Q: Would it be too late to join 106M?
A1: live answered
Q: can submissoins be submitted after the on-time period?
A1: Yes, late submissions are permitted during grace period
Q: I have a question about the homework! For the soundex search, do we have to write tests, or is the test “included” in just checking the output
A1: No, you can’t really write tests for the soundex search consoel program. You can still “test” the code by trying lots of inputs and checking the output is reaosnable.
Q: In assignment 1, since we are allowed to copy paste some of the pre written functions as a basis. Are we allowed to copy paste from the pre written comments as a basis too or do those need to be entirely self written?
A1: Good practice to use your own words, please!
Q: I meant extensions
A1: We don’t recommend submitting extensions during the grace period, because the whole submission will be treated as ineligible for the on-time bonus
Q: does implementing the extensions for the soundex code give extra credit?
A1: Yes, the extensions are treated as bonus
Q: Can the test time_operation ever return false?
A1: Generally not, but if an error were raised during the operation it would be treated as failure
Q: for division and subtraction, which number popped off goes first?
A1: 8 4 - will subtract 4 from 8
Q: how do we translate a order of operations eqaution to this form?
A1: The point is that you don’t have to explicitly worry about order of operations when you process an expression in postfix notation.
Q: Why use stacks to do simple math operations?
A1: The stack is not for the math, but for tracking the operands
A2: The stack here is acting here as effective manner of organiznig the data processing in order to provide correct results without having to explicitly code the logic fo order of operastions
Q: How is this less complicated than simply using parenthases? Are there other benefits?
A1: This is just a learning exercise to understand stacks
Q: how do you separate when you are using postfix with numbers that have more than one digit?
A1: There are spaces between tokens (i.e. 1 2 3 is different than 123)
A2: Numebers and operastors are separated by spaces so numbers can be of arbitrary length
Q: '== string::npos what does this mean
A1: That is a special constant that indicates the desired thing you were looking for in the string does not exist
Q: Is there any exception to the postfix? Maybe there is an expression or operation that can’t be expressed this way
A1: postfix is equal in expressive power to infix and just has a more regular form (i.e. no need for parens in any situation to disambiguate)
Q: Will we have a YEAH session for every assignment?
A1: live answered
A2: Yes, there will be a YEAH session for every assignment
Q: what is the recorded section?
A1: live answered
Q: will assignment 2 be posted at a certain time tomorrow?
A1: Noon-ish
Q: Can we use knowledge that we learn in this lecture to implement in our Assignment 1 or is it supposed to only previous knowledge from last week?
A1: live answered
Q: we can find it on the cs106b website right?
A1: Yes
A2: The recorded section is posted on Canvas where all other recorded course videos are
Q: If we want duplicates, what type should we use? which is very similar to set.
A1: The closest thing is probably a vector
A2: But vector’s aren’t as efficient as sets
Q: do sets have a type? like string or int?
A1: just like a vector you choose when you initialize it
A2: Yes, sets must contain elements of all the same type, declared when you create the set
Q: Is there indexing in Sets?
A1: No
A2: no, they are unordered
Q: so if you want to remove something from a set you have to call it by name?
A1: Yes
Q: so sets can only contain one data type right?
A1: Correct
A2: yes
Q: Does set.h have a set.count method?
A1: live answered
Q: How are capital letters ordered by sets?
A1: Using string <, in ASCII uppercase is “less than” lowercase
Q: Can you change the ordering of the set?
A1: No, a set uses hashing (you’ll learn about this later in the quarter)
Q: Sorry to ask, but what does (string person: friends) do?
A1: It is a “for-each” loop over the elements in the set. Every element is visited and made available via the person variable once
Q: Are there unordered sets in the Stanford C++ Library?
A1: Yes, there is a HashSet type for that
A2: Yes
Q: can we take advantage of that set order other than print somehow? like is there any way to "cheat" and basically index
A1: No, you sould never be trying to index into a set
Q: Since this set is ordered, is it implemented as a binary tree (or ordered list) instead of a hash set? Is the complexity of any operation then O(log(n)) instead of O(1)?
A1: live answered
Q: so if you want to take one specific value out of a set how would you do that?
A1: You can use set.remove(element)
Q: why does a set have a sorted order but no index?
A1: That will become more clear when we learn about binary search trees later in the quarter
A2: Keep in mind that the order is controlled internally. Not externally visible of manipulable — cannot determine the index for a element, no way to insert at index, remove at index, etc.
Q: Are both HashSet and Set included in the set.h header?
A1: yes
A2: No, Set coems from set.h and Hash Set comes from hashset.h
A3: No, there is a second include file “hashset.h”
Q: Does unordered_set in STL also use structures similar to hashset here?
A1: Yes it does (in fact our classes use the stl under the hood)
Q: So we could only use "for type currElem:set" to access elements in set?
A1: Exactly, you would need to for-each loop over a set since you can’t use a “nromal” for loop with indexing
Q: Is the O(1) absolutely the best one that we can get or is there something even faster?
A1: O(1) is instantaneous
A2: In practice, there can be variation in the actual elapsed time for O(1) but there is no better big-o growth class (wait for Monday’s lecture for more on that)
Q: Is there a symmetric diffrence operand
A1: No, but you could construct one :-)
A2: Not explicitly, but you could implement it pretty easily using the given primitives (a + b - (a * b))
Q: Does the order of the elements matter for the == comparison?
A1: No, internal order doesn’t matter for msot operations (it only becomes a fact or when you print out contents of set)
Q: Can a set hold multiple types?
A1: no
A2: No, a set must hold elements all o fthe same type
Q: When you do these operations, will the new set be sorted alphabetically?
A1: Yes, Sets are always ordered
Q: wouldnt s1-s2 = -1?
A1: s1 - s2 evaulates to a Set containing all elements from s1 that are not contained in s1
Q: how do you zoom in on the code in qt?
A1: On Mac, you can use command-plus
A2: you can also use command and then scroll the scroll wheel in to zoom in
Q: are the sets case sensitive? The vs the
A1: yes, those are different strings
A2: Yes, those would be two different strings in a set
Q: Would the runtime of this read-in be nlog(n)?
A1: Correct
Q: Where if we used a hash just n?
A1: Also correct
Q: It seems to slow down as more words are added to the uniqueWords (is that because it runs in O(N^2) time?)
A1: Not quite, it is running O(NlogN)
A2: The Set version, I mean
Q: So in summary:
Q: vector N^2
Q: tree -nlogn, and hash n?
A1: Correct
Q: Is the set faster than the vector because it does not have to check to see if the word is already in the data structure?
A1: live answered
Q: What is definition of hashset?
A1: live answered
A2: A set that is built on top of a hash table instead of a binary search tree. We’ll talk about hashing and hash tables at the end of the quarter
Q: why is a binary search faster?
A1: Because the data is sorted, it is able to quickly narrow in on where a value would have to be, rather than look through every single element
Q: Would there ever be a time when we would choose a set instead of hashset when we don’t care about order?
A1: live answered
A2: In the end, performance differences in most use cases will be negliglible so choosing either one is fine
Q: How are maps and vectors different?
A1: Maps store key-value pairs, Vector stores single element
Q: Just to clarify, normal sets are ordered but but hash sets are not?
A1: Correct!
Q: What is the big O of the look up for map? What data structure does the map use to store the keys?
A1: live answered
Q: so maps don’t have a type?
A1: Maps have two types, the type of the key and the type of the value
A2: You have to set the type of the key and the type of the values upon initialization
Q: If we used a std::map instead of a Map for Assn 1, do we need to change that and resubmit?
A1: live answered
Q: so then is it still possible to traverse a map?
A1: Yes! You can iterate through a map
A2: Yes, you can traverse the keys in a map by using a for-each loop
Map<int, int> m; for (int key: m) // do something
Q: map is essentially the same as dictionary in python right?
A1: Correct
A2: yes
Q: can keys be collections (such as vectors)
A1: No, generally not because they cannot be effectively comapred
A2: Yes, the second example on the previous slide showed the syntax
Q: on slide 13, why did it say the second Map say "map from double keys"? why double?
A1: Ooops, typo in the comment, I will fix
Q: Is there an extra LAIR today or over the weekend?
A1: I have office hours right after class. Lair is open Sun-Thu evenings
Q: if you add a key that isn't in a map, does it return the default value too?
A1: you set the value when you add the key to the map
Q: What order are the keys in the vector from m.keys()?
A1: Same order you would get the keys if you traversed the map using a for-each loop
Q: Since map.keys() returns a vector of keys does this mean that we need to #include “vector.h” along with #include “map.h”?
A1: If you plan on calling map.keys()
Q: is there a keySet() function in c++?
A1: no but you can cast the vector of keys to a set
Q: if you remove the value does the key get removed too
A1: You can’t call remove on a value, you have to cal it on a key (which removes the key-value pair)
Q: Does the HashMap use a HashSet to store keys? Does that also mean that HashMap can only use specific data types that are hashable for keys?
A1: Correct, for a type to be usable as element in HashSet or key for HashMap requires that the type be hashable
Q: why is the map given as map<char, int>?
A1: live answered
Q: are most data structures in C++ initialized to default values? or is it just ones that include ints?
A1: C++ has mechanism that allows you to control the default value for a user-defined type
Q: but how are you specifying with person to add the vote for? its just saying add 1 vote for the v key right?
A1: v is the character representing the person to add a vote for so accing the map at v correctly adds one vote for the current person we’re considering
Q: which*
Q: How does it recognize different letter? (M,R,S)
A1: live answered
Q: What happens if you keep the reference around after the map is destroyed? Is that possible?
A0: What happens if you keep the reference around after the map is destroyed? Is that possible?
A1: Sad times, don’t do that!
Q: so input » word returns true?
A1: live answered
Q: What if the word isn't in the map? What will it print?
A1: You will get an error unless you check for the word in the map first
Q: would while(cin » word) return false for an input that only includes spaces? or does it only return false for blank lines?
A1: It only returns false when the input fails to read anything into word (which happens at end of file or on error)
Q: Tally[word]++ would only work if the value is a number, right?
A1: yes
Q: ahab
Q: Is nested functions better or declaring multiple varibles and assigning each variable with the result of each function?
A1: live answered
Q: Is map equivalent to objects in javascript?
A1: live answered
Q: small q: where do we find lecture recordings?
A1: Course Canvas page > Panopto Course Videos
Q: is #include “math.h” or #include
A1: live answered
A2: #include
Q: if you can do vectors in maps, can you do vectors in vector?
A1: Yup!
Q: So are sets initialized inside main?
A1: Sets can be initialized naywhere, not restricted to main
Q: Do you know what datastructure is underlying the python map? If it sorts by order something is entered, how can it efficiently query a key?
A1: live answered
Q: If you declare a set or map of type object, then canyou input anything to the map as long as all of the elements are the same?
A1: live answered
Q: do the + and * operators used to find union/intersection of sets also work for hashsets?
A1: Yes
Q: In the TIME_OPERATION function I don’t understand what the first argument is supposed to mean
A1: live answered
Q: If you try using “put” with a key that’s already in the map, will that cause an error, or would it change the value for that key?
A1: it will overwrite the ecisting value associated witht hat key
A2: It will override the value
Q: ok thanks
Q: '@julie have office hours been bustling?
A1: live answered