Q: what is the answer? true : false thing?
A1: That is the C++ “ternary” expression, it is like a compact if-else
A2: It’s called a terinary operator if answer is true you it is set to true, if answer is false it is set to false
Q: wait he meant log 2 of 128 right
A1: Correct!
Q: Is O(log (n)) always assuming log base 2?
A1: Yes. Conventionally computer scientist will assume log base 2
A2: Changing the base of logaritmn changes calculation by constant factor, so it’s a generalization of how we ignore constant factors in Big O
Q: How do people mess up the binary search?
A1: Lots of ways! Wrong stopping condition, wrong advance when cutting range in half (should remove the mid point, not retain it), overflow on computing mid point index. I posted some materials on binary search for 106M last week, see web.stanford.edu/class/cs106m to check them out!
Q: I am a bit confused, isn’t the best case Ω(1)?
A1: live answered
Q: Is the best case for most search algorithms generally 0(1)?
A1: Yes, you can’t really get better than O(1)
Q: is the amount of total poles always 3 in this problem regardless of how many rings?
A1: Yes, the game is defined to always have 3 pegs/poles.
A2: Yes, that is the traditional setup for the Towers problem
Q: sorry, slightly unrelated, but is cs103 the feeder for cs106b or is it cs107
A1: live answered
Q: When we do homeworks on recursion will there be a lot of testing to make sure there are no infinite loops?
A1: Yes, an important test case(s) for a recursive function is to ensure it arrives at its stopping condition!
Q: What is a stack overflow?
A1: It’s like wikianswers for coding
A2: The stack that holds the sequence of function calls has a fixed upper limit on size, when you go back that, you have an overflow (error) condition
A3: back -> past (typo)
Q: how is this different from a while(true) loop?
A1: live answered
Q: So multiple return statements are allowed?
A1: live answered
Q: Are multiple returns good style?
A1: If done in good taste, yes. :-)
A2: A typical good use case is where there is a code path (such as base case) that quickly does something simple and is ready to return right away. The recursive case likely has more complicated work to do and has its own separate return. Although you could try to reunite both paths into one combined return at function end, that’s actually more awkward than just having two distinct returns
A3: (Try rewriting one of the simple recursive examples count people, factorial, raise to power. into a form with combined return and you’ll see what I mean)
Q: why do we need the + 1 in the recursive statement?
A1: live answered
A2: live answered
Q: For these simpler problems, would the code run faster because we’re using recursion
A1: Not really, in fact in some cases recursion can slow down code if you go down too far
A2: No, in general, a recursive solution will run slightly slower than comparable iterative approach
Q: when doing operations with multiplication, is it good to have a base case of 1 and when adding, have a base case of 0?
A1: Ideally you are going for the simplest, most primitive base case
Q: cant you just have the if loop stop the recursion when n reaches 1? return x. Would save a tiiiiny bit of time
A1: But then you would need an additional case for power = 0 if you wanted to get the correct result for power(x, 0)….
A2: We would rather have one simple base case that can be the stopping condition for everything than divide into additional special cases to stop a little bit early
Q: why do we not use an else statement in this example?
A1: You don’t have to use an eles statement because if you enter the if the function “returns” asnd execution stops, so it won’t fall through to the later code.
Q: Are there any problems we can only do with recursion (i.e. not iteratively)?
A1: I don’t believe so, but some problems are MUCH easier using recursion than loops
A2: Well, to be nitpicky about it, we can always simulate one with the other, but as Chase says, certain problems are much easier to express in one form than other
Q: Is the variable x irrelevant to Big O complexity discussion because it’s a stand-in for any number within an operation?
A1: live answered
Q: Does this run in parallel?
A1: No.
Q: Would there be a way to implement concurrency for fastPower in c++? Not super familiar with this language
A1: Yes, you can use threading which is discussed in CS110
A2: The C++ language facility does not have facilities for concurrent execution, you have to use library/os features
Q: Can you break it into one thirds or one fourths?
A1: Yes
Q: If n is odd can we do power(x, (n-1)/2)*power(x,(n+1)/2)? Would that be even faster?
A1: A little bit, yes!
Q: Wait so this is kinda the same approach as the binary search right? Like we split it into half? Is this splitting into half common in algorithms?
A1: live answered
Q: Can you go over why it’s now log n?
A1: live answered
Q: If I use a parameter for the first time inside an if statement, how can I reuse it outside of the statement later in the code? Should I define it in the main part of the code instead of inside the if statement?
A1: A parameter is visible throughout the entire body of the function
Q: which algorithm does the built in c++ power use? Like when we use **
A1: live answered
Q: Does recursion ever lead to issues with memory constraints because of all the recursive calls (even when there is no infinite loop)?
A1: Yes, absolutely! You will explore this on future assignments :)
A2: Yes!
Q: Is there a simple (but mathematically rigorous) general way to prove the complexity of a recursive function?
A1: live answered
Q: in recursion, you have to keep calling the function over and over so you have to keep making copies of paramters. Therefore, is recursion inefficient, or bad for saving memory space compared to other methods?
A1: live answered
Q: Will our section this week dedicated to recursion?
A1: Yes, you will cover big-O + recursion in section this week
Q: Going off of Sarah’s question, can you pass things in by reference during recursion
A1: Yes, definitely
A2: yes
Q: It seems like you can implement the mystery function with a second parameter (int) log_{10} n to find the sum of the digits of n, with the second parameter decreasing by 1 at each recursive call? Sorry, this is hard to express in words.
A1: live answered
Q: What would happen if the final line was return a + mystery(a+b) because a keeps changing?
A1: It would use the value of a at the current stack frame (its value at the time the recursive function is called)