Algorithms

Return to List of Lectures

Previous Lecture

Misc

My solutions to the first exam are available through Canvas. See the “Exam 1 Solutions” folder under “Files,” each question is a separate Matlab file.

Please return mid-semester evaluation forms today if you want to turn them in.

Questions?

Algorithms

Example. Make c cents change (0 ≤ c ≤ 99, US currency) using the least number of coins.

Relevant ideas or questions from video.

• An algorithm takes input, has steps, and produces output
• Steps have to be effective (doable) and definite (clear)
• An algorithm also has to be finite, i.e., eventually produce its output. This precludes just guessing at answers until you find one.
• The output has to be correct

Making change as an algorithm

• Input: c, the amount of change to make
• Output: A list of coins to give as change
• Algorithm: “give as many quarters as you can, then move on to dimes, nickels, etc.”
  • This is very high level, but it is in fact fine as an algorithm for people.
  • To express it for a computer, you would refine it into more precise steps, probably involving while loops and/or if statements.
  • This is much of the point of algorithms: you can invent them at a high level where they intuitively make sense and then refine them into something you can write in a programming language.

A comment on the change-making problem and algorithm: the algorithm we came up with makes a great deal of intuitive sense, but it won’t work for all imaginable currencies. For instance, if there was a 4 cent coin and you wanted 8 cents change, this algorithm would use a nickel and 3 pennies whereas using 2 four-cent coins would be better. Algorithm inventors actually have to be careful to prove that their algorithms are correct, and there are ways of using mathematical proof techniques to do this (but they aren’t covered in this course).

More on While Loops

Making Change. Write the change-making algorithm from above using a while loop. Print the coin(s) used.

Relevant ideas or questions from reading.

• Single control structures (while loops, if statements, etc.) generalize to programs with multiple control structures. For example while loops that come after other while loops or if statements nested inside loops.

Here is the first Matlab version, following very closely the high-level English idea of first giving as many quarters as possible, then as many dimes, and so forth:

function [ ] = change( c )
while c >= 25
    fprintf( 'give a quarter\n' )
    c = c - 25;
end
while c >= 10
    fprintf( 'give a dime\n' )
    c = c - 10;
end
while c >= 5
    fprintf( 'give a nickel\n' )
    c = c - 5;
end
while c >= 1
    fprintf( 'give a penny\n' )
    c = c - 1;
end
end

Here are some examples of this algorithm running:

>> change( 83 )
give a quarter
give a quarter
give a quarter
give a nickel
give a penny
give a penny
give a penny
>> change( 98 )
give a quarter
give a quarter
give a quarter
give a dime
give a dime
give a penny
give a penny
give a penny
>> change( 8 )
give a nickel
give a penny
give a penny
give a penny

Here’s another way of writing essentially the same algorithm, demonstrating the ability to nest control structures, i.e., have one (in this case an if) inside another (in this case a while):

function [ ] = change2( c )
while c >= 1
    if c >= 25
        fprintf( 'Give a quarter\n' );
        c = c - 25;
    elseif c >= 10
        fprintf( 'Give a dime\n' );
        c = c - 10;
    elseif c >= 5
        fprintf( 'Give a nickel\n' );
        c = c - 5;
    else
        fprintf( 'Give a penny\n' );
        c = c - 1;
    end
end
end

It also runs well:

>> change2( 87 )
Give a quarter
Give a quarter
Give a quarter
Give a dime
Give a penny
Give a penny

Next

Lab re finding zeros of functions via Newton’s method

• See Handout for details.

Just what is Newton’s method? Watch this video:

You’ll also need to know about a Matlab feature called “function handles”

• Read textbook sections 13.3 - 13.4

Next Lecture