Monday, November 08, 2021

Money is Hard in Programming

Last week I wrote about the making change for a dollar project. It got me thinking about how hard dealing with money in programming really is. The problem with money is that 1/10 is an infinitely repeating fraction in Binary.If one adds 1/10

Take the following C$ code.

double penny = 1.0 / 10.0;
double dime = 0.0;
Console.WriteLine(penny);  
for (int I = 0; I < 100; I++)
{
     dime += penny;
}
if (dime == 10.0) Console.WriteLine("Dime");
Console.WriteLine(dime);

One might expect that the word “dime” would be printed but it’s not. What this code actually prints is the following.

0.1
9.99999999999998

The 0.1 is expected but as you can see, adding the 0.1 100 times doesn’t give exactly 10.0. The problem often doesn’t show up right away. This sort of thing often confuses beginners because the programming language “helpfully” hides the issue. When I had the program display the value of “dime” after every addition the discrepancy don’t show up until around 6.0.

5.8
5.9
5.99999999999999

It’s not only beginners who struggle with this issue. It’s a pretty common issue and some languages support a currency data type for that reason. The currency data type adds some overhead to operations and not everyone is a fan of using it. A different alternative is to use integers and insert a decimal point on display.

One of the first programming languages I used for business related software, called DIBOL, didn’t support floating point numbers at all. It supported 18 digits of integer accuracy. It was an interesting language. Using it did make it easier for me to think about using integers for money later in my career though. Most beginners don’t have that sort of a helpful start. They are used to thinking in digital rather than binary. To my way of thinking this reinforces my thinking that learning binary is an important part of computer science education.

Thursday, November 04, 2021

How Many Ways to Make a Dollar

I ran into a reminder of an interesting programming problem the other day. One I meant to use with students but never did. Other teachers I know do use it. Simply pot, how many possible combinations of coins are there that add up to a dollar. It’s easily solved with a set of nested loops like the ones below.

int count = 0;

for (int halves = 0; halves <= 2; halves++)
{
     for (int quarter = 0; quarter <= 4; quarter++)
     {
         for (int dimes = 0; dimes <= 10; dimes++)
         {
             for (int nickels = 0; nickels <= 20; nickels++)
             {
                 for (int penny = 0; penny <= 100; penny++)
                 {
                     int value = halves * 50 + quarter * 25 + dimes * 10 + nickels * 5 + penny;
                     if (value == 100)
                     {
                         count++;
                     }
                 }
             }
         }
     }
}
Console.WriteLine(count);

It’s pretty straight forward. The key thing is understanding what coins there are and what their value it. The code above doesn’t include a dollar coin. Should it? Probably but it depends on the way the problem is specified. Also these are the coins currently being minted. Over the history of the country there have been a number of other coins in circulation

US TREASURY: What denominations of coins are no longer being produced?

There are quite a few denominations of coins that the United States Mint does not produce any longer for general circulation. They are the half-cent coin, the two-cent coin, the three-cent coin, the half-dime coin (although it was replaced by the five-cent coin), a twenty-cent coins, and the various denominations of gold coins. Although the Mint does produce a series of gold bullion coins, these are not intended for circulation.

The problem would be more interesting if some of these were allowed. I keep thinking that there must be another way to solve the problem though. I just can’t think of what it might be.

[Edit] Jeremiah Simmons shared information about solving this problem using Dynamic Programming. It's more complicated but scales better. Take a look. Understanding The Coin Change Problem With Dynamic Programming

It is so sawesome when educators share ideas with each other.

Thursday, September 30, 2021

Define Learn To Code

I saw an interesting question today on Twitter:

My first response is that there is no definitive answer to that question. I thought about it for a while. One can learn to program by hooking a Raspberry Pi to a monitor, keyboard, and mouse and firing up Thonny and learn Python. One can use any number of online IDEs and a Chrome book. The last classes I taught had a mix of students running Eclipse and Processing on Mac and PC laptops with no appreciable difference. In short, does the computer even matter?

Maybe there is a question that has to be asked and answered before discussing the right or best laptop to use. That question is “what does it mean to “learn how to code?” I suspect we could have quite a long discussion on that question alone.

To me it boils down to:

  • What problem are you trying to solve – how do you define “learning to code”
  • What software helps you best learn to code by your definition
  • What hardware runs the software you want to run

Picking the hardware should almost always be the last thing one picks. Now I have to go think about what it means to “learn how to code.”

Sunday, September 26, 2021

Phun With Phone Numbers

Among the programming projects I ran into recently was one to calculate all of the combinations of letters one could make from a phone number. Companies do this sort of thing all the time. They generate the combinations and then look for words related to their business so they can use it as a mnemonic and help people remember their phone number. Probably a bigger deal before domain names than now but still useful.

How many possible combinations are there? Well, that depends. It can be a low or 2187 (3 to the 7th power) and a high of 16384 (4 to the 7th power). The highest number is for phone numbers with all 7s and/or 9s.

I’m trying to write small bits of code to keep my mind active and solving interesting (to me) little programs. Initially I didn’t care to write this program (though eventually I did) so was thinking around the problem from other directions. What if I took a word and had a program generate a phone number? That was fun. And pretty easy. So I thought about the logical (to me anyway) next step. What if I had a list of 7 letter words and generated a file with the phone numbers that matched each word?

It turns out I have a small word list with just under 114,000 words in it. Step one was building a new file with only the seven letter words in it. A nice little project that is simple even for beginners.

I borrowed the code from the earlier program that turned a word into a number. A handy thing that shows the value of methods and reusable code. I used that to create the file with a list of seven letter words and phone numbers. A list of just over 22,000 for what its worth.

When I did write the program to create all the possible combinations of characters for a phone number I had a nice data file to use to check my work. That was surprisingly helpful.

Anyone out there assigning the program to create all the combinations of letters for a phone number? What interesting solutions are students coming up with?

Friday, September 24, 2021

An AI Tutor for CS Education

Recently I came across a Microsoft Research project called AI for Programming Education. The project “goal is to build a personalized and autonomous intelligent teaching assistant (an AI Tutor) for programming education, enabling on-demand education.”

It’s an intriguing and I think ambiguous idea. I tend to be skeptical of AI tutors as a general idea. A half dozen years or so ago I attended a workshop at Microsoft Research dealing with hinting systems. In other words, how can the computer give hints to beginners. I wrote about hinting systems and the workshop here.

The tl;dr is that it is a hard problem. No surprise to teachers of course. Knowing when to hint and how much to hint is a tough problem for human teachers. For a computer AI it is going to be harder still. That’s just one part of what an AI tutor would have to be able to do.

I don’t know any more about the project than what I read on the web page (link above) and that they are looking for a CS Education researcher to help with pedagogy. CS Education/Pedagogy Research Internship Opportunity at Microsoft (AI-driven Program Synthesis in the PROSE team) That is an encouraging move.

With more and more of education moving to the cloud, more and more online curriculum being developed, and systems that are getting smarter about helping programmers to write code (IntelliCode Completion In Visual Studio (Preview) 2022), creating an AI tutor seems like a logical project to take on. I assume papers will be published. I look forward to reading more about this project over time.

Monday, September 20, 2021

Book Review–System Error: Where Big Tech Went Wrong and How We Can Reboot

System Error: Where Big Tech Went Wrong and How We Can Reboot is what you get when a top philosopher, a top political scientist, and a top computer scientist get together to think deeply about technology and society and write a book.  It’s not a book for just one group. It’s not a dry textbook or academic paper but a clearly written explanation of the issues. It’s a book for everyone.

The book talks a lot about both artificial intelligence and social computing which are more connected to each other than may be obvious at times. The social and political impacts of these topics and others are covered in a clear and understandable way without hyperbola, scaremongering, or blatant cheerleading. This is one more thing that makes it stand out from many other books on these topics.

Yes, there are parts that are scary. Yes, there are parts that are optimistic. All in all though it is as fair and open minded a book as one can get. The book askes questions that have to be asked. There is enough data and sets of facts to give one a lot to think about. In fact, I found several times that I had to put the book down to think about what I had read. It’s that sort of book.

Were I teaching Advanced Placement Computer Science today, especially Principles but also APCS A, I would assign reading from it and have class discussions. If I could not get a class set I would at least have some copies in the library put on reserve. But I’d really like my students to read it all.

This is a book that should be on some required reading lists. Computer scientists really do need to think about the “should we do this” question as much as the “can we do this” question. This is the book to start thinking that way. But policymakers need this books as well. So do business people. So give it to the polysci and business majors you know.  A lot of social scientists should read it as well – sociology, psychology, social work. Probably more. It will help one understand what people are dealing with in today’s world.

Technology is impacting society, and our democracy, in many ways. Some are obvious and some are not. If we want to have a civil society we need to think deeply about the impact of technology on individuals and organizations This book is a great way to start.

Friday, September 17, 2021

Debugging–Slow is Smooth and Smooth is Fast

Mike Zamansky had an interesting post called  What They Used To Know that got me thinking about the old days. Now Mike is a youngster and didn’t really start in computers until the 1980s.  I started in the 1970s with punch cards and batch processing. That meant that there was no instant gratification seeing your program run.

With batch, one handed their cards to an operator and some time later, hours or maybe a day, one got their cards back with a listing that showed the results. Results usually meaning a list of errors that kept the program from running.

Desk checking, studying the listing and trying to fix as many errors as possible before trying again was a bit of an art form. To this day I will often print out a program to look at the big picture in a way that still doesn’t feel effective on a screen. It’s tempting to see that as a way to go – limited opportunities to have the computer check ones code.

There are downsides to this sort of thing though. Specifically, having limited runs or at least long waits between runs encourages writing large amounts of code at a time and discourages writing and testing small pieces of code regularly.

Being able to hit “compile” every other minute though tends to encourage, or at least support, the beginner tendency to “throw some code in and see what happens.” This wastes time in the long run and often leads to ugly, hard to maintain, and inefficient code.

The military has a saying that “slow is smooth and smooth is fast” that some what applies. Slowing down to really analyze code, think smoothly, generally leads to a faster result. Tossing code in on a wing and a prayer is not smooth but chaotic. Slowing down to really look at what is happening is smooth and looks slow to the casual viewer but leads to faster results.

As I was thinking tonight and asking, “what if we limited people to some limited number of compiles a day?” It seemed like a good idea until I thought of the possible problems. That’s when I realized that external controls on speed are not the answer. Rather the answer is for developers to regulate themselves. To slow down and focus in ordered to make faster progress.