Lecture 4/27: Lecture 10 Q&A
Lecture 10 Questions and Answers (Exported from Zoom Q&A log)
Q: Play a taylor swift song please!
A1: live answered
Q: does recursion have a smaller big O time than the other methods we’ve learned up to this point?
A1: The bigO of a recursive algorithm varies based on how many recursive calls, how deep, etc.
Q: what's A3?
A1: assignment 3
Q: can YEAH be recorded & uploaded?
A1: live answered
Q: will yeah sessions be recorded?
A1: live answered
Q: what happens in the YEAH?
A1: Group help session to assist getting you started on assignment
Q: will YEAH be lecture setting or classroom setting? (just the prof is speaking or everyone has camera view)
A1: live answered
Q: Will we have assignments during the weeks of the exams
A1: No
Q: will we get the same amount of content from this course as we would in a normal quarter with 10 weeks + finals ?
A1: Close, but there is some trimming to fit into 9.5 weeks total
Q: also can we get a video or something of Chris going over the recursion examples that were skipped on Friday
A1: Will discuss with Chris and see what we can do
Q: will we revisit maze and apply recursion?
A1: The textbook has a nice application of recursive depth-first search to maze in Ch 9 — check it out!
Q: are there any iterative problems that cannot be solved recursively?
A1: In general, recursion is superset of iteration, so if you could do with a loop, you could transform to recursion. It may not be the most efficient way to do it, but it will work
Q: what exactly are we trying to find here / do with this program?
A1: trying to enumerate all the possible coin flip sequences of length N
Q: why do we need extra information for recursive function to run now while we didn't need that last week?
A1: For this problem we need infomration in the recursive call to know where we are in the decision tree, we did not need for previous problems
Q: So for this example are we generating ALL combinations or just one path of the tree?
A1: we are generating all possible sequences of length N
Q: Why is it length -1?
A1: We are “flipping” one coin in this recursive call and adding it to sofar, in recursive calls the N-1 other flips are added
Q: When we add to sofar in the else statement, does sofar still start as an empty string, similar to the base case?
A1: It is appending to the value of sofar parameter that came into this call — started as empty string at outset, but as we go deeper in the recursive, sofar gets longer with each recursive call
Q: so the program operates in a 50/50 chance inside the else statement?
A1: It only goes into the base case when we have a full sequence of length N in the sofar paramater
Q: why wouldn’t the program just skip over the second line every time it runs (the + T line)?
A1: Not sure what you mean, it runs the code sequentially no skipping allowed…
Q: can you explain more about length -1 please?
A1: In order to generate a sequence of length 4, you would choose a coin flip and add to soFar, you then make a recursive call passing sofar and asking for 3 additional coin flips to be added., that is, that a length 4 sequences comes from making one choice and then recursively generating the length 3 rest of sequence
Q: I feel like its more useful to call the "Base case" the "end case" since it finishes the recursion. Why do we call it "base case"?
A1: I think the idea is “base” as in “simple”
Q: Are we allowed to use a for loop within a recursive function in Assignment 3?
A1: Where needed, yes!
Q: does the for loop finish before the recursive call?
A1: Each iteration of the for loop makes a recursive call and the for loop only completes after all iterations complete, so after all recursive calls complete
Q: 🤯🤯🤯🤯
A1: I hear that!!
Q: Little Chris is inspirational
A1: yes!
Q: ok thanks
A1: live answered
Q: can you reexplain line 81
A1: That is extracting the parts of the string before the ith character and after the ith character and adding them together. (so effectively the string without the ith character)
Q: What is the big O here in the function permute?
A1: O(n!)
Q: can we use rest.erase(i, 1) to write line 81?
A1: almost — since erase would permanently modify s, you need to have a copy of s unmodified as you will need it for subsequent iterations of the for loop.
Q: Is the big O of the "loop version" of permute() and the "recurse version" of permute() the same?
A1: Yes!
Q: is it normal to understand absolutely none of this?
A1: live answered
Q: permute(string S = “”, string rest) default for S works too?
A1: Yep!
Q: So are there any advantages of recursion vs. loops in terms of computing efficiency? Or are they typically gonna be the same Big O?
A1: Generally going to be the same — it is the size of the entire decision tree that determines how many sequences/permutations/choices you have to explore, that count is the Big O, whether you work your way to them iteratively versus recursively doesn’t change the amount of work you have to do
Q: so does the base case run for every “abcd”, “abdc”, etc etc (ie the end branch of the search tree?
A1: Yes, it does!
Q: is decision trees the best way to understand recursion?
A1: I think so. Looking horizontal across the tree shows you the options at each decision point, looking downward indicates how many decisions you have to make in total
Q: this stuff scares me…
A1: Stay strong! Let your brain mull it over in the background and the little flashes of insight will come — it doesn’t happen immediately, patience, my padawan
Q: what was the purpose of the second permute helper function?
A1: It makes for slightly cleaner way to make the first call — just pass the string to permute, don’t have to pass the empty string to soFar since that will always be what is needed
Q: when you are wroking through these probelms, shoud you make a decision tree?
A1: Yes, I think it really helps you to understand what’s going on
Q: what if our program started with the “crt” though? would it take longer to find a solution since that’s not a valid path?
Q: can we do something like the reducible code as an additional helper in the predict algorithm for assignment three?
Q: can you do a decision tree for the 3 head flip case please??
Q: Awesome thanks!