Computer Programmings & Algorithms
Coming Up …. • • • •
Recent Roles History Bad forecasting How it works – Hardware – Software
• The language • Algorithms
Computer – recent development • Deep blue defeated Garry Kasparov • Analysing & recognizing faces of terorist suspects • Weather forecasts – Butterfly in China Storms in the U.S. and so on …
Bad forecasting about computers • "Computers in the future may weigh no more than 1.5 tons." --Popular Mechanics, forecasting the relentless march of science, 1949
• "But what ... is it good for?" --Engineer at the Advanced Computing Systems Division of IBM, 1968, commenting on the microchip
Bad forecasting about computers • "There is no reason anyone would want a computer in their home." --President, Chairman and founder of Digital Equipment Corp., 1977
"640K ought to be enough for anybody." -- Bill Gates, 1981
The History of ‘computer’
How it works – hardware
Digital Computer Hardware
Auxiliary Storage Output Devices
System Unit
0 3 instr1 4 7 instr2 .. .. . . 100 107 101.101 108 109
75
110 -121
label
Memory Addresses
Input Devices
Main Memory(RAM)
Control Unit (CU) Arithmetic -Logic Unit (ALU) CPU
Digital Computer Hardware (2) Mai n (Internal ) Memor y: • All data and instructions are stored in main memory as a sequence of 0’s and 1’s called Bits (Binary Digits) • Byte (smallest addressable element of memory) Storage size for one character of information (ASCII-8 8 bits). Every (single) address refers to a byte in memory. • 210 bytes is defined as 1 kilo-byte (1KB) 220 bytes is defined as 1 mega-byte (1MB) 230 bytes is defined as 1 giga-byte (1GB)
Digital Computer Hardware (3) Central Processing
Uni t (CP U) :
• Transfers information into, out of, and between memory locations. • Executes instructions stored in memory. • Set of instructions for a CPU is known as a machine language. • Each CPU (Pentium III, Power PC, ...) has its own specific machine language.
Machine Cycle Instruction Cycle
Main Memory 1
Control Unit Fetch
2
Decode Execution Cycle
CPU
RAM 4
Store
3
Execute
Arithmetic/Logic Unit Includes Cache (very fast memory)
Open architecture on computer design
How it works – software
Programming Languages Classified as Low L evel • Machine Language (binary-based code; machine dependent) • Assembly Language (mnemonic form of machine language)
High Level
High Level • Closer to natural languages. • Generally, machine independent • Usually, several machine instructions are combined into one high-level instruction. • Examples: FORTRAN COBOL BASIC Pascal Ada PL/I C GPSS C++
Java Lisp Matlab
Processing a High-Level Language Program Programs written in high-level languages must be converted to machine language. Two approaches: (1) Compilation (see p. 28 FER Figure 2.4) Used with C, C++, Fortran,... (2) Interpretation Used with Matlab, Visual Basic,...
Compilation Step 1) Use Xemacs to create a “source” file. We will name source files with a suffix “.c”
Step 2) Run the gcc compiler on the source file to create an executable or object file with the default name a.out . For CS101 we will only create executable files.
Step 3) Check to see if gcc caught any syntax errors , if so go back to step 1)
Step 4) Run the program by typing > a.out at the Unix prompt
Problem Solving and C Computer programming is the art/science of transforming a “real world” problem into a finite sequence of instructions(statements) in a computer language. The method stated in the following slide will be used throughout the rest of the semester. Follow this method in your Labs and for any Machine Problem.
Software Development Method 1. Requir emen ts S pecification (Problem Def inition) 2. Analysis---Refine, Ge pr oblem d efinition
neraliz e, Decom pos e t he
(i.e., identify sub-problems, I/O, etc.) 3. Design---Develop Algor
ithm
(processing steps to solve problem) Use one of the following: Natural-Language Algorithm Flowchart Algorithm Pseudo-code Algorithm 4. Implementat
ion --- W rite t he " Progr am" (C ode )
5. Ver ification and T Code
est ing --- Tes t and Debug the
C Program Example 1. Requir em ents S pecification (Problem Def ini tion)
Given a light-bulb with a pre-measured power consumption(in watts), compute the resistance (in ohms) of the bulb.
2. Analysis---Refine, Gene pro ble m def ini tion
raliz e, D ecom pose t he
(i.e., identify sub-problems, I/O, etc.) Input = real number representing power Output=real number representing resistance
C Program Example (2) 3. Design---Develop Algor
ithm
Natural-Language Algorithm Prompt user for the power dissipation Read power Store value in storage location called power. Compute the resistance solving the formula “power = (voltage*voltage)/resistance” in terms of resistance. resistance = (voltage * voltage)/ power Print out the value stored in location resistance.
C Program Example (3) 3. Design---Develop Algor
ithm
Pseudo-code Algorithm print “enter power in watts” read power resistance = (117.0 * 117.0)/power print resistance
. Design---Develop Algorit
lowchart Algorithm Flow is assumed down unless otherwise specified with an arrow. Trapezoid used to designate I/O. Rectangle used to designate one or more statements in a block. Circle used as continuation symbol for transfer to another page.
hm
start
Output : “enter power in watts”
Input : power
Compute: resistance=(117*117)/power
Output::resistance
stop
C Program Example 4. Implementat ion -- - W rite t he "P rogr am " (Code) (see the next s lid e)
C Code Implementation of the Algorithm /* C Program to compute the resistance */ /* of a light-bulb.*/ #include <stdio.h> #define VAC 117.0 void main(void) { /* Declare variables. */ float power, resistance; /* request user input power of */ /* light-bulb in watts. */ printf(”Please enter power(watts) :”); /* read value power */ scanf("%f", &power); /* Compute resistance assuming VAC = 117. */ resistance = (VAC * VAC) /power; /* Output the calculated resistance. */ printf(”Resistance is %f (ohms)\n", resistance); } (Note indentation scheme in above code.)
Open Xemacs and enter your code..
C pr ogram compi lati on C program compilation
C pr ogram compi lati on Click the “Save” button in Xemacs to save your code but don’t close the Xemacs window. Click the xterm button to open another window.
C pr ogram compi lati on Use the “gcc” program to compile your C source code in the file “resistance.c”. > ls resistance.c
resistance.c~
Note: backup files begin and/or end with a ~ or a # symbol. Do not edit or compile these files! > gcc resistance.c The “gcc” program will not alter the file “resistance.c”. The output of “gcc” is by default contained in the file “a.out”. The file “a.out” is called an executable file. (continued on next slide)
C pr ogram compi lati on
Note that the “gcc” program noted an error on line 16 in the program and “gcc” generated a warning for line 7. Also, note that there is no a.out file listed. Errors cause gcc to abort and you will not get an a.out file. Go back to Xemacs line 16 and fix the syntax error. (continued on next slide)
The error on line 16 was actually caused by a missing semicolon on line 14. In C a semicolon means “end of statement”. This differs from Matlab where a semicolon means suppress output and is optional. Since there was no semicolon after line 14, C assumed that lines 14 - 16 represented one C statement. That is incorrect syntactically, so gcc (the compiler program or compiler for short) generated an error message and terminated before producing an a.out file.
C pr ogram compi lati on After adding a semicolon to the end of line 14, Click “Save” in Xemacs and go back to the xterm and type again...
Note: The dot-slash in “ ./a.out ” means “ in this working directory”. If you type “ a.out ” at the Unix prompt Unix will first search your home directory for a file “ a.out ”. Of course this would not be the same “ a.out ” file you created in another directory.