Chapter 1 Lecture Notes



Chapter 1 Lecture Notes (9/9/99)

Introductory information (not directly related to Pascal)

Some definitions…

hardware – the physical machines that make up a computer installation (ex. printer, monitor, motherboard)

software – the collection of programs used by a computer (ex. Word, Excel, Turbo Pascal)

There are 4 primary parts to a computer system:

1. Input devices

Input devices allow a person to communicate information to the computer. Examples of input devices would be a keyboard and mouse.

2. Output devices

Output devices communicate information to the user. Examples of output devices would be a monitor or printer.

3. CPU

The CPU, or Central Processing Unit, is the device that reads the instructions in a program and performs the calculations specified by the program. Typical CPU instructions say things like “interpret the zeros and ones as numbers and then add the number in memory location 37 to the number in memory location 59 and put the answer in location 83.”

There are three major parts to the CPU: the CU, the ALU, and the registers.

CU (Control Unit)

The CU controls the flow of instruction execution in the CPU.

ALU (Arithmetic Logic Unit)

The ALU performs the mathematic and logic calculations in the CPU.

Registers

Registers are high-speed memory present on the CPU that is used for temporary storage in calculations.

4. Memory

There are two types of memory: primary memory and secondary memory.

Primary Memory

Primary memory is the RAM (Random Access Memory) of a computer. It is temporary storage space for data when the computer is in a power-on state. It is much slower than the registers in the CPU, but there is a lot more of it (more data storage capacity). Primary memory holds both data and programs (once they are loaded for execution). (ROM, or Read Only Memory, could also be considered primary memory, but there is usually a lot less ROM than there is RAM. The difference between ROM and RAM is that data cannot be written to ROM.)

Primary memory is like a table of addresses and contents. Also, 4 or 8 bytes (depending on the CPU-type) is grouped together to form words.

Secondary Memory

Secondary memory is what the disk drives are – places data can be stored and kept there even after the computer is turned off.

Data Representation

Computer data is made up of long sequences of ones and zeros, called bits, grouped by eight to form bytes.

Actual information is represented by the bit values stored in these bytes, such as signed and unsigned integers, real numbers (fractional numbers), characters, etc.

We’ll talk about integer values here. We won’t talk about fractional (floating point numbers) representation.

Integers

The number system that we are used to is a decimal number system because it is base 10. For example:

54318 = 5x104 + 4x103 + 3x102 + 1x101 + 8x100

= 5x10000 + 4x1000 + 3x100 + 1x10 + 8x1

= 50000 + 4000 + 300 + 10 + 8

= 54318

(Remember, anything to the zeroth power is 1.)

The binary number system works like the decimal number system, but it is a base 2 system. To convert binary to decimal, use the same method used above but use base 2!

11010101 = 1x27 + 1x26 + 0x25 + 1x24 + 0x23 + 1x22 + 0x21 + 1x20

= 1x128 + 1x64 + 0x32 + 1x16 + 0x8 + 1x4 + 0x2 + 1x1

= 128 + 64 + 0 + 16 + 0 + 4 + 0 +1

= 213

To perform this calculation, you may find the following power of 2 table helpful:

|Power |Result |Power |Result |

|0 |1 |9 |512 |

|1 |2 |10 |1024 |

|2 |4 |11 |2048 |

|3 |8 |12 |4096 |

|4 |16 |13 |8192 |

|5 |32 |14 |16384 |

|6 |64 |15 |32768 |

|7 |128 |16 |65536 |

|8 |256 | | |

To convert from decimal to binary, start with the binary number and keep dividing by 2, writing the remainder (of any) after each division. Keep doing this until you reach one. Your result, then, is the remainders, starting from the bottom. Here’s an example:

132

----- 0

66

----- 0

33

----- 1

16

----- 0

8

----- 0

4

----- 0

2

----- 0

1

Starting from the 1 at the bottom, the binary equivalent of 132 is 10000100.

Two’s Complement for Signed Values

Computers can represent both signed and unsigned integer values. To do this, most computers use the two’s complement. The two’s complement of a number is the negative version of the number. To take the two’s complement of a binary number, take the inverse of the number (change all 0’s to 1’s and all 1’s and 0’s – produces the one’s complement), then add 1 (produces the two’s complement). So, if I want to represent –7, first I convert 7 to binary (0111), then I take the inverse (1000), then I add one (1001). If I use the two’s complement in standard binary arithmetic, everything works out.

Storage Capability

For any binary number of length n, 2n is the total number of values that can be represented. For example, a 4 bit number has 24 or 16 possible values. (0000, 0001, 0010, 0011, … , 1110, 1111).

For any unsigned binary number of length n, 2n-1 is the highest number that can be represented. For example, a 4 bit number can represent integers from 0-15.

For any signed binary number of length n, we get a range of -(2n/2) to (2n/2)-1. For example, an 8 bit number can represent values from –(28/2) to (2n/2)-1 or –(256/2) to (256/2)-1 or –128 to 127.

High-Level Languages

Pascal, C/C++, COBOL, and FORTRAN are compiled languages. This means that code that is easily written, read, and debugged is saved to a text file. This is called source code. A program called a compiler is then used to convert the source code to object code, which is a file containing machine language. Machine language is a series of binary numbers that are a coded version on simple instructions that CPU carries out when the program is executed.

Lisp, Prolog, Perl, and BASIC are interpreted languages. This means that the source code is read by a program called an interpreter is executed one line at a time. Using languages like this is much slower but they do no need to be compiled.

In this class we will be using Pascal. Pascal is a general-purpose language because it is suitable for a wide range of applications.

Why learn Pascal?

Even though Pascal isn’t widely used to create new programs today, Pascal is an excellent language to start with. It has a very similar structure to many other languages, including C, but its syntax (and the fact that it is very forgiving) makes it easier to learn. Once you know Pascal, you already understand the main concepts behind programming and can very easily learn most other languages.

Algorithms

Algorithms are the most important concept of programming. An algorithm is a series of simple steps that, once completed in order (although many have steps that loop back to a previous step), solve a problem. Algorithms are written in English, but once written, can be implemented in any programming language.

Here’s a sample algorithm for finding the number of times a name occurs in a list of names:

begin

1. Request the list of names and call it NameList;

2. Request the name being sough and call it KeyName;

3. On a blackboard called Count write the number zero;

4. Repeat the following for each name of NameList;

if the name is the same as KeyName

then add one to the number written on Count;

{the old number is erased, leaving only one number of Count}

5. Announce the number written on Count as the answer.

end.

Programming is a process divided into two phases: the problem solving phase and the implementation phase.

The Problem Solving phase

1. Problem definition

Make sure you know as much about the requirements of the program as necessary. Know all required input, output, and supplementary information.

2. Algorithm design

Design an algorithm to complete the task.

3. Desktop testing

Look at the algorithm and run some sample data through it. You may have to go back to the algorithm design stage if you find problems or if you think that you can write a better algorithm.

Implementation phase

1. Coding algorithm as a program

Code.

2. Testing

Run tests on your program. If there are problems you may have to return to the coding stage or even the algorithm design/problem definition stage.

Glass-box testing

With glass-box testing, you give your program test input based on how the program works. Enter input data that tests boundaries. If you know that positive and negative numbers must be handled differently, try a positive number and then a negative number. Check your output to see if the program handled the input correctly.

Black-box testing

With black box testing, you give your program data from the point of view from a person who doesn’t know how it works. Enter random data and check the resulting output. Try as many different combinations of data that is reasonable.

These steps are very important when programming.

Example Problem Solving Phase (programming exercise 9 from the book)

Many banks and savings and loan institutions compute interest on a daily basis. On a balance of $1000 with an interest rate of 6%, the interest earned in one day is 0.06 multiplied by $1000 and then divided by 365, because it only for one day of a 365-day year. This yields $0.16 in interest, and so the resulting balance in $1000.16. The interest for the second day will be 0.06 multiplied by $1000.16 and then divided by 365. Design an algorithm that takes three inputs: the amount of a deposit, the interest rate, and duration in weeks. The algorithm then calculates the account balance at the end of the duration specified.

Problem definition:

Inputs: the amount of the deposit

the interest rate

duration in weeks

Output: account balance (compounded weekly)

Requirements: as listed

Algorithm design:

begin

1. read amount of deposit (call it deposit)

2. read interest rate as a decimal (call it rate)

3. read duration in weeks (call it duration)

4. balance=deposit

5. do this number of weeks times:

balance=balance+(balance*rate)/52

6. output balance

end.

Desktop testing:

Enter sample values for inputs and determine output.

deposit=2000

rate=0.02

duration=2

balance=2000+(2000*0.02)/52=2000.77

balance=2000.77+(2000.77*0.02)/52=2001.54

(check answers)

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download