Thank you Ryan, I am watching your lectures over and over in order to understand about some notions including to the textbook of Sipser, Papdimitriou and Goldreich.
Sure. You need to fix a system, but one system for encoding in unary is: . encode in binary using your favorite method, getting a string x . let y be the string 1x [we do this in case x begins with 0's] . interpret y as the binary representation of some positive integer z . the final unary encoding is z 1's. The above system is completely generic. An alternative for this specific case of pairs of natural numbers is to use a 'pairing function' (en.wikipedia.org/wiki/Pairing_function). E.g.: . encode the pair of natural numbers (x,y) with a string of 1/2(x+y)(x+y+1)+y 1's. I prefer the first system, because it's clearer, to be honest.
Thank you Ryan, I am watching your lectures over and over in order to understand about some notions including to the textbook of Sipser, Papdimitriou and Goldreich.
This is awesome! Never thought I'd find it on TH-cam.
Unbelievable lectures! So impressive!
Another cool course, thank you.
Is it possible to somehow access the accompanying assignments ?
Thank you! This is great!
Watch on at least 1.5 speed for the screens to line up.
Thanks
Link to panopto? Because i can't fint the lectures there
Great lecture, but the frame rate is killing me.
Did you find any solutions for it?
@@jordankuzmanovik5297 Sadly no.
Can one encode (5,2) in unary (with one string)?
Sure. You need to fix a system, but one system for encoding in unary is:
. encode in binary using your favorite method, getting a string x
. let y be the string 1x [we do this in case x begins with 0's]
. interpret y as the binary representation of some positive integer z
. the final unary encoding is z 1's.
The above system is completely generic. An alternative for this specific case of pairs of natural numbers is to use a 'pairing function' (en.wikipedia.org/wiki/Pairing_function). E.g.:
. encode the pair of natural numbers (x,y) with a string of 1/2(x+y)(x+y+1)+y 1's.
I prefer the first system, because it's clearer, to be honest.
@@RyanODonnellTeaching Wow that's cool. Thank you so much!
It's so funny when one student guesses the answer is "P vs NP".
Even funnier if they presented a [correct] proof in class.