For discrete structures class:

$3.$ Prove that the set of all computer programs is countable.

Hint: Since computers encode data in binary, think of a computer program as a finite

bitstring.

$4.$ Modify the bubble sort algorithm so that it stops early if no more interchanges are

required. Express this more efficient version in pseudocode.

Hint: Note that if the inner for$-$loop completes in full without making any interchanges,

then the data must be in sorted order, and additional iterations of the outer for$-$loop

will be unnecessary.

$5.$ Use the cashier$$s algorithm to make change using quarters, dimes, nickels, and pennies

for the following amounts:

$($a$)51$ cents

$($b$)69$ cents

$($c$)76$ cents

$($d$)60$ cents