Introduction

Intro, Representations, Problem Solving, Program Development

Intro.

1. Who I am
2. Review of course web pages
3. Modes of Learning: We remember:
   
   
   • 10% of what we read
   • 20% of what we hear
   • 30% of what we read and hear
   • 50% of what we hear and see
   • 70% of what we say ourselves
   • 90% of what we do ourselves

How much do you want to remember?

Internal Representations: How does the computer store stuff?

1. Bits, bytes, & words:

   The smallest unit of information a computer can store is a bit, represented as a 0 or a 1. The 0 and 1 values represent different voltages. A byte is a collection of 8 bits, and can be used for instance to represent a single character, such as 'A'. A word is typically a collection of two bytes, for a total of 16 bits.

2. Number Bases
   • Base 10 (decimal) uses digits 0 through 9 and is what we're used to.

456 = (4 * 100) + (5 * 10) + (6 * 1). Note the powers of ten (100, 10, 1) used in each place.

• Base 2 (binary) uses only digits 0 and 1. A binary number is sometimes prefaced with the '%' symbol.

%1011 = (1 * 8) + ( 0 * 4) + (1 * 2) + (1 * 1) = 8 + 0 + 2 + 1 = 11 (decimal). Note the powers of two (8, 4, 2, 1) used in each place.

• Base 16 (hexadecimal, or simply "hex") uses digits 0 through 9 and additionally symbols A,B,C,D,E,F to represent values 10 through 15. A hexadecimal number is sometimes prefaced with the '$' symbol.

$9A = (9 * 16) + (A * 1). Remember that the symbol 'A' stands for the value 10, giving: (9 * 16) + (10 * 1) = 144 + 10 = 154 (decimal).

3. Conversions between bases

1. Binary to Decimal

   Let's say we want to convert %1010 to Decimal. Rewrite the binary number with the place values above each position as follows:

   		8 4 2 1

   		1 0 1 0

   This gives us powers of two (starting with the right-most value of 2 to the 0th power, or simply 2^0) on the top line, with the number itself on the bottom line. Wherever there is a one on the bottom line add the place value on the top line to your sum. This gives 8 + 2 = 10, which is the answer in decimal.
   

2. Decimal to Binary

   The process itself is simple, but trying to write it down makes it appear complicated. Let's say we want to convert 25 to binary. First write down binary place values (powers of 2) for approximately the size of number in question:

   		32 16  8  4  2  1

   		 _  _  _  _  _  _

   Note that we stopped writing down the powers of two once we got to 32, since 25 < 32. Now we need to figure out whether to put a 0 or 1 in each position. Starting from the left, write down a 1 if that place value is smaller than the number in question, in this case 25. Since 32 is not less than 25, we put down a 0 in that position. 16 is less than 25, so we put down a 1 there giving:

   		32 16  8  4  2  1

   		 0  1  _  _  _  _

   We then subtract this place value from 25, giving: 25 - 16 = 9. We now continue using 9 as the number in question. Is there an "8" in 9? Yes, so we put down a 1 in that position, giving:

   		32 16  8  4  2  1

   		 0  1  1  _  _  _

   9 - 8 gives 1. Both 4 and 2 are larger than 1, so we put down a 0 in both those positions, leaving us with a 1 in the last position for the final answer of:

   		32 16  8  4  2  1

   		 0  1  1  0  0  1

   So 25 = %11001.

   Note that the same approach is used when converting between decimal and hexadecimal, except you would use powers of 16 rather than powers of 2.

3. Binary to Hexadecimal

When converting between binary and hex the key is to note that each hex digit corresponds with 4 binary digits. Given the seven digits %1011110 we first add a leading zero so that the number of digits is evenly divisible by four. (You can add leading zeros without changing the value.) Then group by four starting from the right, giving us the groupings: %0101 and %1110. These respectively correspond to the hex digits $5 and $E, so %1011110 = $5E.

4. Hexadecimal to Binary

   Again simply group each four binary digits to correspond to a single hex digit. For instance $7 = %0111, or simply %111, since leading zeros don't give any additional information. We also know that $B = %1011. This idea of grouping by four then shows us that $7B = %01111011.

4. Names of binary number formats
1. Unsigned binary: This format means that all the bits are used to represent the magnitude of a number.
2. Signed magnitude: In this format the left-most bit represents the sign of the number only. A 0 means the number is positive, and a 1 means the number is negative.
3. Two's complement: This is a format used to facilitate the use of negative numbers. Don't worry about all the reasons why for now. To take the two's complement of a binary number simply reverse the bits and add one. For example, we know that 6 = %110. To represent -6 as a two's complement number, reverse the bits (giving %001) and add one, giving %001 + %1 = %010. (Note that %1 + %1 = %10)

 

5. Representing Characters

   Certain bit values can be interpreted to stand for characters. For instance, %01000001 = 65, which when treated as a character is 'A'. Appendix A in our text shows the correspondance between characters and code values. You can also use the man ascii unix command to show a character table.

6. One set of bits, different interpretations

   A single bit string could mean different things, depending on how it is interpreted, i.e. the context in which it is used.

   E.g. %1000001 could be:

   • 65 as a 7-bit unsigned integer
   • -1 as a 7-bit signed-magnitude number
   • -63 as a two's complement number
   • 'A' as an ASCII character

 

7. Compiling is a process used to translate high-level language into a machine's low-level language.

   The first electronic computers were programmed by hand by people plugging in or unplugging wires to represent 0's or 1's, which gave instructions in machine language, e.g. 01100111. This was tedious, so assembler commands were developed (e.g. ADD R3,R5), which could then be translated into machine language. Subsequently high-level languages (e.g. x = x + y) were developed, which allowed expressing mathematical ideas more directly.

   The translation process of going from a higher-level language into machine language is called compiling.

Problem Solving Steps: How do I organize my thoughts about solving a problem?

If you can't solve the problem by hand, chances are you won't get the computer to do it for you either.

Consider the following example of writing a program that gives the average of students' midterm 1 grades:

• The program takes as input the grades for the 90 students. Each grade is a whole number (an integer) from 0 to 100. The results of running the program, the output, is the average (the mean) of the numbers
• What the program will need to do is to step through all the scores, accumulating the sum and keeping track of how many scores have been seen. The average will be calculated as the sum divided by the total number of scores.
• After figuring out the process described above, it is a good idea to test out this process by hand on a small problem.
• If the process seems to work correctly for a small problem, then the next step is to translate the process into a computer language such as C and type it in.
• After the program compiles and runs correctly, test it, paying careful attention to the "boundary conditions", such as when there are 0 students, or only 1 student, or more than 90 students. Also consider whether or not you need to do error checking for your input, such as verifying that each score is in fact within the 0..100 range.

More formally, the above steps of problem solving and implementation on a computer can be summarized as:

1. Problem Specification: what's the input and output look like?
   • Input: 90 integers ranging from 0 to 100, e.g. 95 68 100 99 ...
   • Output: average of the input numbers, e.g. 90
2. Algorithm Design: what are the processing steps used to transform the input into the output? E.g.
   1. sum = 0, counter = 1
   2. Read a grade
   3. counter = counter + 1
   4. sum = sum + grade
   5. if counter < 90 then go back to step 2
   6. mean = sum / 90
   7. display the mean
3. Hand Test
4. Coding
5. Testing

Program Development: How do I go about writing a program?

1. Use a program "template" as a starting point. It should contain a sample header documentation section.
2. Next figure out exactly what your input and output is supposed to look like. Write your program to handle this input and output, even if the "answers" are all wrong. This will help you in subsequent stages of writing. Get your program to compile and run at this point with just the program "skeleton".
3. Now add functionality to your program one piece at a time, getting each piece to compile and run, and verifying that it is correct up until that point. The following approaches/attitudes have been shown to end up taking much longer:
   • I'll just type the whole thing in, then try to get it to run.
   • I don't understand what's wrong, so I'll just randomly change things and hope I get lucky.
   • I don't understand how to do it by hand, but I'm sure the computer is smart enough to get it to work
4. As you get each stage of your program to work, make a copy of it (in other words copy the file) before starting on the next stage. That way if you totally goof up, you don't have to start over.