Logo

CS106B Lecture - Shared screen with speaker view
Kenneth Fischer
10:36
Chess
Samuel Lynn Ledden
10:37
chess
Akash Bhargava
10:39
chess
Nate Hedgecock
10:44
Candy Crush
Aadi M Rane
10:47
chess
Kenny Wang
10:47
literally any game
Yukun Yang
10:48
chess
Zachary Alon
10:49
chess
Kyle Thomas Booker
10:49
Chess
Nadia Palar
10:54
chess / sudoku
Liza George
10:54
tic tac tow
Humaid Alzaabi
10:57
Life
Ryan Gabel
10:58
chess
klaus cerny
10:58
chess
kathleen bryan
10:59
Scrabble
Liza George
10:59
toe toops
Matt Presson
10:59
mancala
Evan Baldonado
11:03
suduko
Kenny Wang
11:08
Minecraft
Kyle Thomas Booker
11:11
Magic
Kenneth Fischer
11:15
Mancala!
ian rundle
11:18
Pong
edouard des
11:45
Any type of impartial computational game (though those tend to be pretty easy if you know what you are doing)
Elan Smolar Eisenberg
12:06
chess
Jordan Lin
35:03
Shouldn't i be string::size_type?
kylie jue
35:31
The warning is due to the unlatching types but C++ will still be okay if you use an integer for i instead
kylie jue
35:40
*unmatching
Jordan Lin
35:44
Ah I see
kathleen bryan
37:43
I am a little confused about returning specific values for an individual Stack within recursion and mapping that with what stack it was associated with.How do we keep track of those individual stack values?
kylie jue
38:11
By stack do you mean each stack frame (function call)?
kathleen bryan
38:33
Yes the individual stack frames , sorry so getting the value that was produced at that frame
kathleen bryan
38:49
keeping track of it if that makes sense
kylie jue
38:51
got it - in this case, since the function is void, we’re not actually returning any values for each call
kylie jue
39:02
We’re just printing out our results in our base case
kylie jue
39:21
so that’s our way of outputting our results in this particular problem
kathleen bryan
39:36
got it- But generally, we would do that with a return? How would we keep track of what stack frame
Aadi M Rane
39:53
how do you come up with the specific strategy to store info and creating helper?
kylie jue
41:00
@Kathleen: Yeah that’s a great question. IT depends on the problem – some backtracking problems we’ll want to return our results and in others we just want to print them out. But sometimes we “Return” using parameters that the different calls have access to instead of just returning the value. We’ll see an example of this in a later problem today
kylie jue
41:29
So for example with “keeping track” of what letters you’ve chosen so far for permutations, we use a function parameter
hriday chhabria
41:36
Is the number of branches the main difference between yesterday’s example and today’s example
hriday chhabria
41:38
?
kylie jue
42:08
@Aadi It’s often thinking about what information you need to keep track of at each step that is not already present in the provided function prototype parameters
kathleen bryan
42:26
Ok , thank you. So we’d keep track of the parameter it’s called with. I think that makes sense
kylie jue
42:45
@Hriday Yes exactly. And as a result we use a for loop to determine how many branches based on how many letters are left
kylie jue
42:57
@Kathleen yup that sounds right! It will become a little clearer as we see more examples
Ryan Gabel
43:06
Froze
hriday chhabria
43:12
Great! Thanks so much! That makes a lot of sense:)
kathleen bryan
43:25
It’s frozen
Hemant Chaudhary
43:32
Nick looks frozen to me
ian rundle
43:37
rip
Ryan Gabel
43:48
Nick's frozen for me too
Ryan Gabel
45:04
You're frozen again
Michael M Hu
45:07
Oh no
Hemant Chaudhary
45:08
^
Evan F Davis
45:08
bruh
Rafael Vila
45:09
rip
hriday chhabria
45:10
:(
Kenneth Fischer
45:31
Sounds fine!
rayjohns@stanford.edu
49:31
did you mean any single letter word is NOT shrinkable?
Demi Lei
49:44
^
kylie jue
50:02
Will answer out loud
rayjohns@stanford.edu
50:08
cheers
Elan Smolar Eisenberg
50:18
If a word when shrunk to one letter is still valid, then the overall word is shrinkable, not just the letter
rayjohns@stanford.edu
51:04
but all are valid because letters are words
kylie jue
51:23
we mean a word in the English dictionary when we say "Valid"
edouard des
51:24
So O is a one-letter word but it’s not shrinkable, correct?
Evan F Davis
51:53
Is there a way to view the entire lexicon set of words
rayjohns@stanford.edu
51:56
all letters are in the dictionary, so i guess they are valid, assuming you are using a normal dictionary. but it depends on the file you read in
rayjohns@stanford.edu
52:06
@evan it would depend on the file you read in as the lexicon
Demi Lei
52:06
for the base case, how do we determine if a words is not shrinkable? I thought we need to go through a recursive process to determine if it's shrinkable
rayjohns@stanford.edu
52:17
@demi you'd need an explicit lookup
kylie jue
52:28
Yes it will depend on the lexicon file you use - the file will be under “other files”
kylie jue
53:14
@Demi does the base case here make sense?
Demi Lei
54:06
so basically we need to check it everytime?
kylie jue
54:14
Yes
Demi Lei
54:16
is that why is in the base case
Demi Lei
54:20
ok got it, thx!
kylie jue
54:32
We have to check if the single letter remaining is a valid word
hriday chhabria
55:00
Is that the main function or did we have to create a helper function?
hriday chhabria
56:53
Ohh, since we don’t need to keep track of the removed characters/words essentially?
kylie jue
56:58
exactly
hriday chhabria
57:03
Got it! Thanks!
Kyle Thomas Booker
57:16
If we wanted to return the shrinked word in order could we use a stack?
Aadi M Rane
57:27
so when do you need to store one thing vs to store two things?
kylie jue
57:38
@Kyle yes you could store them in a stack parameter along the way
kylie jue
58:10
@Aadi it depends on what the problem is asking you to output and often if you’re being asked to store the “path” along the way
kylie jue
58:48
if you look at each slide where we define the decision tree, that’s often when you’ll be able to identify whether or not you need to store more things (and use a helper)
Aadi M Rane
59:19
so if you wanted to actually output the shrinking path, you need to store two things?
kylie jue
01:00:06
Yes that would be the cleanest way to store and output the path
Kevin H Fan
01:05:28
Thank you!
Guozhen Miao
01:05:29
thank you
Zachary Alon
01:05:32
Thank you!
julia wang
01:05:32
Thank you!
hriday chhabria
01:05:35
Thank you!
Jennifer Anna Bonello
01:05:36
Thank you
Hanna Mofid
01:05:36
Thank you!
louise marzolf
01:05:36
thank you bye!
Demi Lei
01:05:36
thank you!
Kenneth Fischer
01:05:37
Thank you!
Gautham Rajesh
01:05:38
thanks
Chenlan / Yu
01:05:38
Thank you
Shifeng Hong
01:05:41
Thank you
Tongjun (Albert) Zhang
01:05:42
thank you!
Liza George
01:05:48
bye, thank you~
Lawrence Li
01:05:51
Thank you!
Kenny Wang
01:05:58
*resisting the urge to make a "Tripping up" joke*
Ethan Krish Ramchandani
01:06:44
was the permutation finding algorithm an example of bfs of dfs?
kylie jue
01:06:54
DFS
Ethan Krish Ramchandani
01:07:00
thank you