1

My Greedy Algorithm works, but I'd like to know if it's too inefficient. I looked at some others' codes and they looked more sophisticated and I'm just wondering if my way is too inefficient or limited in some way.

[EDIT: Code reduced to relevant section for discussion for Honor Code compliance]

    //counter start
    int c = 0;

    //quarters
    while (b > 24)
    {
        b = b - 25;
        c++;
    }    
2

Yes, there are more efficient ways to do this. Your way isn't wrong, it gets the job done, but there can be better ways to do a given programming task.

Let's look at the efficiency of your code. To make it really clear, let's say that the input is $1000.00. Also, we'll only look at counting quarters.

If you use a while loop, you have to execute at least three steps - 1) test that you're over a quarter in the while loop control statement and 2) subtract a quarter from the running total, and 3) increment the coin count. That means that you have to execute 4000 loops x 3 = 12,000 steps to calculate how many quarters you have. When the running total is under a quarter, that gives you the change, so it's included in the 4000 steps.

Now, if instead, you do an integer division to determine the quarters, followed by a modulo to determine the remainder, then you have accomplished the same goal in 2 steps. The execution in computer time is 6k times more efficient! Given today's hardware speed, it may not seem to be a significant time difference for the single task of the pset, program efficiency becomes critical when writing practical programs that must run the same task millions of times.

For example, I was recently asked to help with a program to confirm that a 1 million word file contained all unique words. The current solution was estimated to take 11 days to execute. We wrote another program to do the same check that took 0.61 seconds to do the same task. This shows how easy it can be to write a very inefficient program and how important it can be to write efficient code.

If this sounds familiar, it's because I posted it as a comment on a related question a while back. Since so many people do this, I thought it better to add here as a response to the specific question.

If this answers your question, please click on the check to accept. Let's keep up on forum housekeeping. ;-)

1
  • Yeah, I think I did the PSET at the wrong time. I did it after I finished Week 1, but apparently your supposed to be doing the PSETs during the following week. I actually didn't get to modulo's until after I tried to do the PSET. Now I know! But thanks for the response and the insight. Although I just started CS50 I have a pretty good feel for when something is efficient or not. When I looked at my code I definitely felt it was both inefficient and limited (in that it would not be easily changed to accommodate a different scenario, hence the post. Thanks again! – CS50_on_the_go Oct 23 '15 at 13:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .