Search Algorithms

You know that a topic is interesting to you when you get excited about it even though the lecture you learn about it in isn't the best. Most of the lectures in the Stanford Programming Methodology Java course were pretty good and easy to follow for me but one taught by the teaching assistant was more difficult to follow. No offense is intended to that teaching assistant, I'm sure with more experience he's a better teacher now. Thankfully, as I said, the topic grabbed me anyway.

Seek and You Will Find

We learned about arrays, creating them and valuing them. Then we had to write something to reverse the order of the items in an array. But what about searching them for a value? That was one thing I was always curious about when creating queries in Access or writing things in OmniScript to search for database records. What was going on under the hood to make searching faster? Was writing something one way going to make for a quicker, more efficient search or not? Therefore I was quite interested in learning about search algorithms.

Linear Searches

Linear searches are the most basic kind of searches. To search an array for a value with a linear search is to look at each value in the array, one at a time, in sequential order, until the search value is found or the end of the array is reached. Naturally this takes some time. Computers are very fast, but if the array is very large, this still takes some time. If an array has 100,000 values, each one might have to be looked at.  I realized that there must be some more efficient ways to search, and there are.

Binary Searches

As long as an array's values are sorted in order, you can do a binary search. With a binary search, the value in the middle of the array is looked at first, and if that value in the middle is lower than the value being searched for, then the whole first half of the array can be eliminated as the value being searched for must be in the second half of the array, if it exists. The opposite is true if the value in the middle is higher than the value being searched for. So if the array has 100,000 values, with the first search, 50,000 values are eliminated and no longer need to be looked at.

Next, the middle value of the remaining values is looked at and the process is repeated. If needed, it is repeated again and again, each time cutting the number of values that need to be looked in half. This, of course, makes the search much more efficient and greatly reduces the time needed to perform the search.

A binary search is much like we humans would search a dictionary or phone book. We don't look at every entry, we jump in at a point and decide which way we need to turn to find what we're looking for and we repeat that until we find our entry.

So Which to Use?

Because binary searches can be so much quicker, one might think they are always preferred. But again, in order to do a binary search, the array has to already be sorted. So if an array is already sorted, then a binary search is the obvious choice. But what if the array isn't sorted? Of course you could sort the array so that you can do a binary search. But of course that's going to take time. So for each case you have to decide what's going to be faster. If you are going to need to do a lot of searches on this array then it's probably best to spend the time to sort it as each binary search you do will save a lot of time. If on the other hand, the search only needs to be performed once or a couple of times, then just running the linear search might be the fastest thing.

i++

Random Number Generators

Another interesting topic I came to early in the Stanford Programming Methodology Java course was the generation of random numbers. As someone who early on thought about making simple video games, I knew that you would need a way to come up with random numbers to make aspects of the game unpredictable.

RandomGenerator

As the Stanford course uses the ACM libraries, professor Sahami had us use the RandomGenerator class. I've come to learn that the use of the ACM libraries is somewhat looked down upon and they aren't used very much outside of the academic setting, but this worked fine as an introduction. I believe this was also one of the earlier instances we had of learning about constructors for new objects.

The RandomGenerator methods include nextInt() for integers, nextDouble() for decimal values, nextBoolean() for true or false (1 or 0) values, and, unique to the ACM version, nextColor() for a randomly generated opaque color, with values 0-255.

The first example used was to simulate a six-sided die roll with the code below. As someone who has had an interest in dice, from the six-sided up to the twenty-sided dice used in role playing games, this was a fun application.

 int dieRoll = rgen.nextInt(1,6);  

PseudoRandomness

But are the numbers produced by computers through random number generators really random? No, they are actually determined by a complex algorithm, based on an initial value. Given the same initial value, the seed, they will always produce the same sequence of "random" numbers. For most practical needs, however, pseudorandom numbers are sufficient because the user does not know the what the seed is and so cannot determine the sequence of values that will be produced. The ACM RandomGenerator uses the system time in milliseconds, which no one will know, for the seed.

A process (or data produced by a process) is said to be pseudorandom when the outcome is deterministic, yet also effectively random, as long as the internal action of the process is hidden from observation. (NIST.gov)

Of course from a programming perspective, it's good that, though seemingly random to the user, the sequence is determined and will always be the same, given the same seed. That's for the purpose of debugging. If there was a problem in your program and it only occurred when a certain "random" number was used, you might have a very hard time tracking down the bug. If, on the other, hand, you can set the seed used and so always produce the same sequence of numbers, it will be much easier to reproduce the problem and find the bug that is causing it.

In a future post I want to write about a virtual dice throwing app that I just installed. Rather than just generating random number results, it uses a physics engine to throw the dice and the dice will even interact with each other, affecting the way that they land, just like with real dice.

i++

Been Looping for a While / 2 AM Debugging

It has been a while since I've written here on the blog. The primary reason was that work was just too busy. For two and a half years I was working on new website for our retirement plan participants and sponsors. Almost 20 internal employees and lots of external resources were working on the development of this site. It has lots of new features compared to the old site and everything had to be built from the ground up.

My role in the project, along with two others, was writing OmniScript to pull the needed participant data from our recordkeeping system and send it to the web in the form of XML. As each retirement plan has it's own set of features and options, this involved a lot of variations. I'll write later about some of these various aspects and what I learned through the project, which was a lot.

After a lot of work and some optimization, the site went through extensive UAT testing and was finally launched to participants at the beginning of December. Overall the launch went very well and it was great to see all of that work finally in use in production. Naturally there were some bugs that were found over the first few weeks and that continued to keep us busy. Finally, though, things are slowing down, at least until the next big project, and I plan to get back to blogging about my experiences in learning programming.

2 AM Debugging

I just wanted to share one programming story, going along with the new website. When you become one of the experts on a new website that allows people control over their money, their retirement savings, then when there's a problem, your phone can ring at any hour of the day or night. I discovered this on New Year's Eve. I hadn't been in bed for long when I noticed at 2:00 AM that I had a couple of missed calls and texts. With the turn of the new year, something was preventing anyone from logging into the website.

So I woke myself up and called my boss back and proceeded to get logged in to find out where the error was coming from. I was probably not at my clearest thinking, and as it was coming from a script that I had not worked on, it took a little while to figure out the problem. By 3:00 AM I had found the problem, a logic bug that, with the turn of the year, was causing the low date in a date range to be higher than the high date. This produced a fatal error.

My boss and I talked it over and decided on a temporary fix that would work until we returned to the office. By 3:30 I had made the fix and people were once again able to log in, though who's trying to log in to their retirement savings site at 3:30 AM on New Year's Day, I do not know. 😃

i++

Characters and ASCII

Fun with Char

One of the things I found to be really interesting early on in the Stanford programming methodology course was chars in Java. I found that I was taking a lot for granted about characters when it comes to computers. I know what an 'A' and a 'B' and a 'C', and so on, are and so I thought that computers understood them in the same way. I think an 'A' and an a are two versions of the same character, upper and lower case. Therefore I sometimes found myself wondering why there was this case sensitivity thing you had to deal with with computers. Doesn't the computer know an 'A' is the same character as an 'a'? So I found it rather eye opening, and oddly fascinating. to learn that an 'A' doesn't mean anything to the computer, it's actually just a number. What's more an 'a' is also just a number, and it's a different number. So of course case sensitivity is an issue for a computer because there's nothing that really ties the two characters together for the computer, they're two entirely different characters, really two different numbers.

The ASCII Table

I had seen and heard about the ASCII table before but was only using it as a reference for the sort order of the numbers and special characters in relation to the letters.  Now I was coming to have a greater appreciation for what had been established and standardized so that we could effectively communicate with one another through different computers.

I learned that an 'A' was decimal number 65 and an 'a' was number 97. I learned that a '0' was actually the number 48.

So then I learned how to write my own method to change an upper case character to it's lower case equivalent. I learned that you could do math on letters! Yes, I am fully aware that the exclamation point at the end of that sentence means that I'm a geek. What's surprising to me isn't that I found this realization fascinating, but that I hadn't discovered this sooner in life so I could geek out on it.

I learned that to change an uppercase 'A' to a lowercase 'a' you actually add 32 (65 + 32 = 97), and the same is true for every other letter. But what's better, I learned that, even though ASCII is unlikely to be changed or abandoned, you wouldn't want to put 32 in your code, instead you want to use the characters themselves and let the computer figure out the number difference between them, just in case they ever did change.

What you know is that 'A' through 'Z' will always be sequential numbers in whatever code is used and 'a' through 'z' will always be sequential. In ASCII there are six extra characters ( [  \   ]   ^   _   ` ) between 'Z' and 'a' (26 letters + 6 characters = 32). But should some other table ever be used, the difference may no longer be 32. So what you write to convert an upper case character to it's the lower case version is something like this...

public static char toLowerCase(char ch){
   if (ch >= 'A' && ch <= 'Z') { /* to see if input character is upper case */
      return ch + 'a' - 'A'; 
        /* dynamically determines and adds the difference between the two */
   } else {
      return ch; /* if not upper case, return as is */
   }
} 

Since they are really just numbers, you can also use char in control statements to loop through the equivalent letters, such as...

for (char ch = 'A'; ch <= 'Z'; ch++)

This is actually a simple concept but it was an eye opening and fun realization.

i++

Eclipse and Karel the Robot

The Eclipse IDE

One of the first things I did for the Stanford programming methodology course was to install the Java JDK and then the Eclipse IDE. This was my first experience with an IDE, a step up from Notepad++. While a later book I read encouraged avoiding IDEs and typing out code with no assistance, I found the automatic code completion and instant feedback for syntax errors helpful for beginning to learn Java. For the course, Stanford developed a customized version of Eclipse. This version made it possible for beginners to get started with some basic object-oriented programming ideas without having to start with something like the main() class.

I have since had experience with the Android Studio IDE, which seems quite similar to Eclipse, and have learned of a few others. In time I would like to try out Emacs, NetBeans and others.

Karel the Robot

The first few course assignments were to be written in Karel, a simple object-oriented language similar to Java. Karel is the name of a little robot that will follow programming commands as he moves through a grid. Karel has only four main functions:

• move()
• putBeeper()
• pickBeeper()
• turnLeft()

You are told what to have Karel do and then you must accomplish it using only those four functions. 

move() tells him to move forward one step. putBeeper() has him put down a marker in the grid and pickBeeper() has him pick a marker up. turnLeft() does what the name suggests. You may need to have him turn right but there is no turnRight() function. So you can have him turnLeft() three times, then you learn to write your own turnRight() function to use.

Karel the Robot was a fun introduction to programming. It teaches you to problem solve, using logic, and to begin to think in a object-oriented way. You can find the Karel the Robot Learns Java book here.

i++

Stanford Programming Methodology (CS106A)

The Programming Methodology course is a part of Stanford University's Stanford Engineering Everywhere. Through this program, students and educators can access many of Stanford's courses online, free of charge. I was essentially able to audit this introductory, semester-long, computer science course for free. I watched the lectures, did the reading assignments and the programming assignments. I found it very interesting and learned a lot. You can find the course at https://see.stanford.edu/Course/CS106A. Here's some basic information about it.

Professor

The course was taught by Mehran Sahami. You can read his profile here. You can tell that Mehran enjoys teaching the course. I found his enthusiasm for the subject to be very engaging. He uses a lot of helpful illustrations for what could be complicated topics and even throws in some fun pop culture references that I could appreciate. Through his video lectures, I got a sense of what it would have been like had I pursued computer science in college.

Textbook

The course textbook is The Art and Science of Java by Eric Roberts. It is available for purchase and a free PDF version of an early draft is also available online. Just search for it and you should find it. I found the book to be informative and easy enough to follow. I even put up a quote from the book in my cube at work, his definition of software engineering - “the discipline of writing programs so that they can be understood and maintained by others”.

What's Covered

As one would expect from the course name, it provides an introduction to good programming methodology and uses Java as the language of choice to do this. It covers, among other things, Variables and Types; Expressions, Statements and Control Structures, Methods, Randomness and Events, Objects, Strings, Classes, Arrays and ArrayLists, HashMaps, Interactors, Collections, Debugging Strategies and Searching and Sorting.

Assignments included three games, Breakout, Hangman and Yahtzee; a data graphing program and a simple social networking program. I enjoyed working on these programs.Naturally it would be better to actually take the course and get feedback on your code but because so many people have taken the course, it's easy to find other people writing about the assignments online. I also created a Stack Overflow account and was able to get some help and feedback that way.

I do recommend the course to anyone looking for an introduction to programming in general and to Java in particular. I will get into some of the specific things I learned through this course in future posts.

i++

What Other Languages to Learn?

I consider myself to be very blessed to have been able to start in a full-time programming job in my forties. This is especially true as I did not start with any formal computer science education. Because of what I was able to do for about 15 years, mainly with Microsoft Access and Excel, I was given a chance in my company to write OmniScript. This has shown me just how much I enjoy programming. Therefore I came to want to learn a lot more about it, especially learning some other programming languages.

Where to Start?

What other,  more common,  programming language would I start with?  A simple Google search yields a lot of blog posts and articles on this subject. There are many different opinions but one of the languages that was on the short list of most, if not all, was Java.  C and C++ were also near the top of most lists but I found that Java appealed to me the most.

Why Java? 

I decided to start with Java for a few reasons.

• Though Java has been around for over 20 years now, it is still one of the most popular programming languages. 
• Java is cross platform.  "Write once, run anywhere." 
• Java is used in making Android apps, something I had an interest in doing.
• Though I'm still interested in learning C and/or C++, Java seemed like an easier starting point. 
• I liked what I was seeing for online resources to learn Java.

Regarding the last point, I found a Udemy course in Java that I was planning to start but then I came across the Stanford Programming Methodology course (CS106A) and decided that would be a great place to start. Not only would I be learning Java, I'd also be learning good programming principles. I'll write more about my experience with the Stanford course in my next post.

While to some extent this could be said of my introduction to OmniScript, in the words of Obi-Wan Kenobi, I felt like I was about to take my first step into a larger world, and I was quite excited.

i++