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

tomaspkr

I would need to check my answers for the 7th problem set, course 2008. Can I get solutions somewhere? Without them I can't know whether I understood the topic properly or not. Thank you

  • 10 months ago
  • 10 months ago

  • This Question is Closed
  1. tomaspkr
    Best Response
    You've already chosen the best response.
    Medals 0

    Only for first 4 functions. I believe it should be linear, linear, linear and quadratic

    • 10 months ago
  2. bwCA
    Best Response
    You've already chosen the best response.
    Medals 0

    i can show you mine if you'ld like. or you could use a code pasting site to post yours for comment. There are solutions from individuals (students) available online - I think if you google MIT OCW ps7 or pset 7.... you would find them. There are no 'official' solutions for the 2008 course. Some of the 2008 topics are in the 2011 course and there are solutions for the 2011 course - but the pset numbers don't match up. Which one is pset 7?

    • 10 months ago
  3. tomaspkr
    Best Response
    You've already chosen the best response.
    Medals 0

    It is pset7 from 2008. You only need to determine the rate of growth for the first 4 functions. As i said I got linear, linear, linear and quadratic for the forth. However, I found answers on the web which says that all of them are linear. I have attached the PDF file of the assignment. I would need confirmation/explanation for the 4th function. Why quadratic for the fourth function? My logic is that to make s1 it takes linear time and then we have to loop through each element in s1 so it is again linear. Two linear times should give quadratic.

    • 10 months ago
    1 Attachment
  4. bwCA
    Best Response
    You've already chosen the best response.
    Medals 0

    you would think 4 is n-squared but maybe because s1 and s2 can change independently then it is linear s1 --> O(len(s1)) or linear with s2 --> O(len(s2) when you change s1 s2 doesn't have to change and vice versa. so it is not the same as for i in xrange(n): for j in xrange(n) pass which would be O(n-squared) check out the set intersection complexity here : http://wiki.python.org/moin/TimeComplexity

    • 10 months ago
  5. bwCA
    Best Response
    You've already chosen the best response.
    Medals 0

    you end up getting a scaling effect, not an exponential effect - if len(s2) is four then for len(s1) = 1-4 you get 4, 8, 12, 16 inner loops which is linear same thing if you vary s2 length and hold s1 constant

    • 10 months ago
  6. tomaspkr
    Best Response
    You've already chosen the best response.
    Medals 0

    Thank you, I corrected my answer, because I saw my silly mistake. Could you have a quick look at the attachment? I might still be wrong.

    • 10 months ago
    1 Attachment
  7. bwCA
    Best Response
    You've already chosen the best response.
    Medals 0

    pretty sure this statement is incorrect: '...it searches through the string s2 using hashing..." the in operator is linear for a sequence. strings are sequence data types. Python does not use hash tables to find things in sequences http://wiki.python.org/moin/TimeComplexity

    • 10 months 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.