Lecture 1: Introduction to Algorithms (cont.)

Conceptual building blocks

In future chapters you will learn about various computational ideas, and the particular Java programming language syntax that you use to express those ideas in a program. Other programming languages will express those ideas with different syntax than Java uses, just like different spoken languages would have different words for the same objects or concepts. However, just as the idea of “tree” is the same whether the word you use to represent the idea is the English word “tree,” or the Spanish word for that concept, or the Japanese word for that concept, likewise, the computational ideas we will learn will be the same, regardless of what language we happen to be using to express those ideas. In this course, we will use Java to express our ideas, and if this is the first time you’ve done any programming, it might be easy to think we are learning Java ideas instead of general programming ideas. That is not the case. We are learning general programming ideas which you will find in almost all modern programming languages, and the particular symbols which represent those ideas in Java, won’t necessarily be the same as the particular symbols that represent those ideas in other languages.

All computer programs basically consist of two components:

1. obtaining data, and
2. running instructions that manipulate that data

With this broad characterization in mind, there are three conceptual ideas we can introduce right now that you will make use of as you design programs throughout your programming career.

1. primitives: Primitives are the lowest-level data values and procedures provided by a programming language. Primitives are not things you need to define, nor are they customizable, since they are built right into the particular programming language. As ‘primitives’ they can’t really be broken down into smaller parts without changing their meaning. (The concept of a primitive is similar to that of an “atom” in chemistry - a basic building block.)
   • Data primitives: In reference to data, the primitives are the built-in data values that your program can use without any further definition. For example, you can type numbers such as 5 or -2 or 38.6 directly into your Java program; the Java language is designed to understand numerical values like these automatically. Similarly, characters such as a lowercase ‘h’ or the dollar sign ‘$’, are understood by the language.

   • Procedural primitives: When talking about procedures, the primitives are small, basic operations such as simple arithmetic. Adding two numbers, or multiplying two numbers, subtracting and division, would all be considered primitive operations – they are built right into the language and you can use them without any further definition.
   
   
2. composition: Taking smaller entities, and putting them together to build a larger entity.
   • Data composition: Building larger pieces of information by collecting together smaller pieces of information. A “user record” in Facebook would include a name, email address, birthdate, a list of friends (which are just other user records), a list of likes (which might be “user records”, or might be “event records” or “product records”). The chunk or collection of data known as a “user record”, is in reality composed of many smaller pieces of data, such as your name, email address, and so on. The user record is a composition of other, smaller data values, which together form a larger, more complex piece of data.

   • Procedural composition: Building larger procedures out of smaller ones. For example, it is possible to add two numbers together, and it is possible to divide a number by six. Let’s apply the first procedure three times adding four numbers together, and then apply the second procedure (division by four) to get an answer.
     

     Given three numbers:

     • (a) add the first two numbers together

     • (b) add the sum from the previous step to the third number
     • (c) add the sum from the preyious step to the fourth number
     • (d) divide the sum from the previous step by four
     
     

     Show what this might look like in a mathematical expression or equation:

      

     We just applied some small, primitive procedures —addition and division— to produce an average of the four numbers we were given. So, what we have really done above is to create a procedure for finding the average of four numbers. By combining primitive mathematical operations, we were able to produce a procedure that is slightly more complex. This more complex procedure is a composition of other, smaller procedures that together form a larger, more complex procedure. Later on, we may even want to give these composite procedures a name. Just as primitive procedures have names like 'addition' and 'division', we might name our composite procedure, 'averageOfFour' to reflect what it does.

3. abstraction: A focus on the “big picture” of an idea; ignoring the details. The advantage of abstraction is that worrying about those details or implementation of a procedure often bogs us down in a lot of little issues that we don’t need to worry about. When you talk to a friend in your cell phone, you might know that the phone is encoding sound waves as electrical signals, but you don’t really worry too much about that when you speak to your friend. Imagine that every time you wanted to use your phone you had to do the encoding on your own! As an abstraction, you can trust that your phone will perform the encoding properly, forget about it, and just pick up the phone and speak. In abstract terms, we are concerned with the overall purpose of the phone, rather than the details of how that purpose is achieved or implemented. Certainly, someone or something has to handle the details, but that someone or something doesn’t have to be you.

   We make use of this idea when writing computer programs, as well:

   • Data abstraction: The idea of viewing a data composition in terms of what the overall collection of data is trying to represent, rather than focusing on the details of what pieces of data make up the composition. For example, we might have procedures that “display a Facebook user record” or “copy a Facebook event record”. In abstracting these ideas, we don’t need to worry about sending a lot of little pieces of data that compose each user record to the display procedure; we simply send one piece of data, a Facebook user record, and don’t need to worry that a user record is “really” lots of smaller pieces of data.

   • Procedural abstraction: A composition of smaller procedures combined to achieve a task. The resulting composition should be considered as a single unit and be referenced in terms of what the overall goal is, rather than viewing it in terms of the smaller procedures that make up the larger one. For example, once we have written a procedure to take the average of four values, we can make use of it whenever we have four values and we need to average them. We can send the four values to our “averageOfFour” procedure, and get the average back. We no longer need to worry about the details of how the average is calculated.

     As an example, we may choose to use the abstract procedure like this:

     • averageOfFour(72, 68, 67, 71)

     where Rory McIlroy’s golf scores for a tournament were 72, 68, 67, and 71. His average for the week will be simply: averageOfFour(72, 68, 67, 71). We do not need to think about what is going on behind-the-scenes, that 72 is added to 68 and 67 and 71 and the sum of the four numbers is divided by four.

   What is a data primitive?

    

   Give some other examples of a data primitives:

    

   Give some other examples of a procedural primitives:

    

   What is mean by composition?

    

   Give some other examples of a data composition:

    

   Give some other examples of a procedural composition:

    

   What is mean by abstraction?

    

   Give some other examples of a data abstraction:

    

   Give some other examples of a procedural abstraction:

    

All these ideas fit together to aid us in program design. Quite often, we will often compose a larger piece of data out of smaller pieces of data, and then focus from then on, on the larger data concept rather than worrying about what smaller pieces of data form the larger one. Sometimes, those smaller pieces of data that form the larger piece of data, will be primitives, and sometimes they will instead be other data compositions we already created earlier. Ultimately, though, if you break any piece of data down into small enough detail, you will find that it is composed of the same limited set of data primitives that the language (and processor) supports. We just choose to focus on the “big picture” when we can, instead of always peeking into a data composition to see the smaller pieces of data from which it is made.

Similarly, we will often compose a larger procedure out of smaller ones and subsequently focus on the composite procedure and the overall task it accomplishes, rather than worrying about all the smaller procedures from which it was constructed. Sometimes, the smaller procedures we use to form the larger procedure will be primitives and sometimes they will instead be other procedural compositions we have created previously. Ultimately though, if you break any procedure down into small enough detail, you will find that it is composed of the same limited set of procedural primitives that the language (and processor) supports. We choose to focus on the “big picture” when we can, abstracting away the smaller procedures from which it is made.

In the first half of our course we will learn about many of the primitives available to us in the Java programming language, and we will also learn about the syntax available in Java for implementing data composition and abstraction. We will also learn the syntax and common patterns used to create procedural compositions and abstractions. In addition, we will see the concept of abstraction used in many other ways, as well.