Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

wctjerry Group Title

For ps4 in mit 6.00 SC: When I was trying the provided solution, I found it slow to run 'decrypt_fable()'. Does anybody know why?

  • 2 years ago
  • 2 years ago

  • This Question is Closed
  1. Constantine Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Hi, It is very slow because of "brute force", exhaustive key search! Let's say 5 keys have been used! This means five tuples of 2 elements : (position, shift)! You are using brute force, say you are trying all the possibilities to find the good keys. If the plaintext had 100 words, you will need (in the worst case) to try 100 positions for one value of the shift!!!! We have 27 possible values for shift! This means that, just for the first (position, shift) pair, you will decipher the text (in the worst case) 27*100 = 2700 times!!!!!!!!!! this is huge! For all the text, for discovering all the five keys, you could need something like 2700^5 deciphering operations!!!!!! This effectively takes a lot of time!!!!!!!!!! cheers!

    • 2 years ago
  2. wctjerry Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Thanks, Constantine. I am trying to use str.split to make it faster, avoiding testing eash of the letters. But something wrong is in my code I can't figure out. Could u give me a favor? I just change the find_best_shifts_rec function.

    • 2 years ago
  3. wctjerry Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I pasted my codes here: http://pastebin.com/9nPkvwMr

    • 2 years ago
  4. Constantine Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Ok Jerry! I saw your code! Look carefully to the split function! It cannot make the job here! Let's say you have a partial decrypted text like this : "my-friend--xtrtyiop". Note that I'am using '-' instead of the space character! Of course, the "xtrtyiop" stuff is the remaining ciphertext! Now, if you use split, you end up with the list ['my', 'friend', 'xtrtyiop']! There is a VERY BIG problem there! The space character just before the "xtrtyiop" IS NOT a space character! It is a very part of the remaining ciphertext!!!!! Some letter has been turned into it by the cipher procedure!!! But our split function doesn't know about that. Thus, your algorithm will fail since it will never find a valid decryption for "xtrtyiop". The good spliting function has to give this ['my', 'friend', '-xtrtyiop'] instead of this ['my', 'friend', 'xtrtyiop']. You can't use the split function! You have to cut the text by yourself (letter by letter ?). Oh oh, It seems that there is no escape here my friend! Cheers!!!

    • 2 years ago
  5. wctjerry Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Thanks, friend. I got that.

    • 2 years ago
  6. ComputerAbuser Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I ran into this problem as well. Thought I was all crafty using split, but as you know, you run into problems with leading spaces being dropped. It wouldn't be a problem if you could tell split to include leading spaces and stop once it hits a space after the word.

    • one year ago
  7. ComputerAbuser Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Actually, I just realized how you can use split. After applying the shift, you need to verify that the first character is not a space. If it is, then you can skip that shift, otherwise you can use split to grab all of the characters before the next space.

    • one year ago
    • Attachments:

See more questions >>>

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.