• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Getting better at algorithms and problem solving

 
Ranch Hand
Posts: 546
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hello,

Sorry for the lengthy question but this is something that I've wanted to ask for a long time. I have always been good at Maths and problem solving since I was young. I loved to solve problems related to Algebra and problems to do with numbers. I now have a degree in Computer Science but I really find it hard to solve problems like this and this just to give a couple of examples.

I have to admit I didn't make much use of my time in college and I've definitely learnt way more about data structures and algorithms in the last couple of years than I ever learnt in college. In fact, I didn't even know how a linked list worked until after college when I decided to learn on my own. I am now able to at least think of solutions to problems like this and this, which I couldn't have dreamt of doing 2 years ago. Do I need to have something inherent in me to understand harder algorithms and to solve problems like the one I've listed here? Or, can it be done through practice and sheer hard work? I really want to be very good at algorithms (I don't think I'm bad but I want to go to the next level) and rediscover the joy in solving problems rather than keep staring at walls when faced with problems like these. I know this would be possible through practice and hard work but just looking for reassurance and a nudge in the right direction. I'm 28, if age has any relevance at all here.

Thanks,
Prasanna
 
Sheriff
Posts: 3063
12
Mac IntelliJ IDE Python VI Editor Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Unfortunately, I don't think there are any tricks to this. It's a matter of trying, really trying, to solve problems on your own, then investigating how other people have solve the same problems. Eventually, you start to recognize patterns.

In your "this" examples, I found your Egg Drop problem the most interesting. Brief recap: find the highest floor of a 100 story build that you can drop an egg from without breaking it, but with the fewest number of drops, and breaking a maximum of two eggs. It resembles binary search, except for the two egg limit. There's probably a mathematical solution to this, but I don't know what is, so here's how I approached it:

I could drop one egg from each floor from 1 to 100, but that would take on average 50.5 of trials, and I'm not using the second egg. Instead, I could drop one egg from the 10th floor, then the 20th, etc., until it broke. If I got the break on, say, the 70th floor, I'd then take the second egg to the 61st floor and drop it successively up one floor until it broke. So, if X is the floor I'm looking for, I drop the first egg (X / 10) + 1 times, and the second (X % 10) times. (When I divide by 10 I mean to truncate the part after the decimal point.) I want to know how many drops on average that would take, and that's where programing can help. Ruby is good at these kinds of computations so here it is in Ruby:



I get 10.1 drops on average, so way better than 50.5. How do I know that's the best I can do though? Well, I don't. I don't even know if 10 floors is the right starting interval for this particular algorithm. Let me run it with different starting intervals:



=> [26.5, 18.5, 14.75, 12.7, 11.5, 10.76, 10.34, 10.14, 10.1, 10.1, 10.14, 10.34, 10.55, 10.76, 11.0, 11.5, 11.55, 11.9, 12.55]

Note: interval of 1 would change the algorithm, so I started with 2. As it turns out, 10 or 11 is the right interval to start with. What if there are more stories in the building though. I found for a 200 story building, 14 or 15 is the best starting interval. Now, I can see that the best starting interval may be related to the square root of the number of stories. I wouldn't have guessed that, but with the data to work from, maybe I can figure out why that's true. I could also devise and test alternate algorithms ... maybe changing the interval as I went up floors would help?

Anyway, I went off on a tangent there, but the short version is, if you love solving problems, and you willingly spend your lunch break solving a problem just because it interests you, then you will soon get very good at solving them.

 
Prasanna Raman
Ranch Hand
Posts: 546
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thank you for the detailed response, Greg.
 
Bartender
Posts: 1810
28
jQuery Netbeans IDE Eclipse IDE Firefox Browser MySQL Database Chrome Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Since you like math and want to learn problem solving, check out Project Euler.
 
Prasanna Raman
Ranch Hand
Posts: 546
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thank you very much, Kevin!
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic