Lecture Note 02
Introduction to Computing
(CS111)
Junar A. Landicho
junarlandicho@ustp.edu.ph
“
The only limit to our realization of tomorrow will be our doubts of today.
Franklin D. Roosevelt
Topic 2:
Data
Manipulation
IT 416
Information Systems Development and Management
Learning Outcomes
By the end of this topic, students will be able to: Describe the variety of abstractions used to represent data.
Explain how binary sequences are used to represent digital data.
Identify multiple levels of abstractions that are used when writing programs.
Explain how programs implement algorithms.
Use abstraction to manage complexity in programs.
CS 111 – Introduction to Computing
Overview
1. Computer Architecture
2. Machine Language
3. Program Execution
4. Arithmetic/Logic Instructions 5. Communicating with Other Devices 6. Programming Data Manipulation 7. Other Architectures
CS 111 – Introduction to Computing
Computer Architecture Java
PHP
Python
CS 111 – Introduction to Computing
Computer Architecture
Central Processing Unit (CPU) ▪ Arithmetic/Logic Unit
▪ Control Unit
▪ Register Unit
o General purpose registers
oSpecial purpose registers
Bus
Main Memory
CS 111 – Introduction to Computing
CPU Basics
CPU and main memory connected via a bus
CS 111 – Introduction to Computing
Stored Program Concept
A program can be encoded as bit patterns and stored in Main
Memory. From there, the Control Unit can extract, decode, and
execute instructions.
Instead of rewiring the CPU, the program can be altered by
changing the contents of Main
Memory.
CS 111 – Introduction to Computing
Machine Language Java
PHP
Python
CS 111 – Introduction to Computing
Machine Language
Machine instruction: An instruction
encoded as a bit pattern
recognizable by the CPU
Machine language: The set of all
instructions recognized by a
machine
CS 111 – Introduction to Computing
Machine Language Philosophies
Reduced Instruction Set Computing
(RISC)
▪ Few, simple, efficient, and fast
instructions
▪ Examples: PowerPC from
Apple/IBM/Motorola and ARM
Complex Instruction Set Computing
(CISC)
▪ Many, convenient, and powerful
instructions
▪ Example: Intel
CS 111 – Introduction to Computing
Machine Instruction Types
Data Transfer: copy data from one
location to another (e.g. LOAD,
STORE)
Arithmetic/Logic: operations on bit
patterns
(e.g. +, -, *, /, AND, OR, SHIFT,
ROTATE)
Control: direct the execution of the
program
(e.g. JUMP, BRANCH)
CS 111 – Introduction to Computing
Vole: An Illustrative Machine Language
Adding values stored in memory
Dividing values stored in memory
The architecture of the Vole
CS 111 – Introduction to Computing
Parts of a Machine Instruction
Op-code: Specifies which operation to execute Operand: Gives more detailed information about the operation ▪ Interpretation of operand varies depending on op-code
CS 111 – Introduction to Computing
Parts of a Machine Instruction
Decoding the instruction 0x35A7
Decoding the instruction 0x35A7
CS 111 – Introduction to Computing
Program Execution Java
PHP
Python
CS 111 – Introduction to Computing
Program Execution
Controlled by two special purpose registers ▪ Instruction register (holds current instruction) ▪ Program counter (holds address of next instruction)
Machine Cycle: (repeat these 3 steps) ▪ Fetch, Decode, Execute
CS 111 – Introduction to Computing
The Machine Cycle
CS 111 – Introduction to Computing
Decoding the InstructionCS 111 – Introduction to Computing
An Example of Program Execution
Stored in main memory ready for execution
CS 111 – Introduction to Computing
An Example of Program Execution Performing the fetch step of the machine cycle
CS 111 – Introduction to Computing
Arithmetic/Logic Instructions
Python
Java
PHP
CS 111 – Introduction to Computing
Arithmetic/Logic Instructions
Logic Operations:
▪ AND, OR, XOR
▪ often used to mask an operand
Rotation and Shift Operations:
▪ circular shift, logical shift, arithmetic shift
Arithmetic Operations:
▪ add, subtract, multiply, divide
▪ two’s complement versus floating-point
CS 111 – Introduction to Computing
Arithmetic/Logic Instructions
Logic Operations:
▪ AND, OR, XOR
▪ often used to mask an operand
Rotation and Shift Operations:
▪ circular shift, logical shift,
arithmetic shift
Arithmetic Operations:
▪ add, subtract, multiply, divide
▪ two’s complement versus floating
pointRotating the bit pattern 0x65 one bit to the right
CS 111 – Introduction to Computing
Communicating with Other Devices
Python
Java
PHP
CS 111 – Introduction to Computing
Communicating with Other Devices
Controller: handles communication
between the computer and other
devices
▪ Specialized (by type of device)
▪ General purpose (USB, HDMI)
Port: The point at which a device
connects to a computer
Memory-mapped I/O: devices
appear to the CPU as though they
were memory locations
CS 111 – Introduction to Computing
Communicating with Other Devices
Controllers attached to a machine’s bus
CS 111 – Introduction to Computing
Communicating with Other Devices
A conceptual representation of memory-mapped I/O
CS 111 – Introduction to Computing
Communicating with Other Devices
Direct memory access (DMA):
Main memory access by a
controller over the bus
▪ Von Neumann Bottleneck: occurs
when the CPU and controllers
compete for bus access
Handshaking: the process of
coordinating the transfer of data
between the computer and the
peripheral device
CS 111 – Introduction to Computing
Communicating with Other Devices
Popular Communication Media
▪ Parallel Communication: Several
signals transferred at the same time,
each on a separate “line”
(computer’s internal bus)
▪ Serial Communication: Signals are
transferred one after the other over a
single “line” (USB, FireWire)
CS 111 – Introduction to Computing
Data Communication Rates
Measurement units
▪ bps: bits per second
▪ Kbps: Kilo-bps (1,000 bps)
▪ Mbps: Mega-bps (1,000,000 bps)
▪ Gbps: Giga-bps (1,000,000,000 bps)
Bandwidth: Maximum available
rate
CS 111 – Introduction to Computing
Programming Data Manipulation
Python
Java
PHP
CS 111 – Introduction to Computing
Programming Data Manipulation
Programing languages shields
users from details of the machine:
▪ A single Python statement might
map to one, tens, or hundreds of
machine instructions
▪ Programmer does not need to know
if the processor is RISC or CISC
▪ Assigning variables surely involves
LOAD, STORE, and MOVE op-codes
CS 111 – Introduction to Computing
Bitwise Problems as Python Code
print(bin(0b10011010 & 0b11001001))
# Prints '0b10001000'
print(bin(0b10011010 | 0b11001001))
# Prints '0b11011011'
print(bin(0b10011010 ^ 0b11001001))
# Prints '0b1010011'
CS 111 – Introduction to Computing
Control Structures
If statement:
if (water_temp > 140):
print('Bath water too hot!’)
While statement:
while (n < 10):
print(n)
n = n + 1
CS 111 – Introduction to Computing
Functions
Function: A name for a series of operations that
should be performed on the given parameter or
parameters
Function call: Appearance of a function in an
expression or statement
x = 1034
y = 1056
z = 2078
biggest = max(x, y, z)
print(biggest) # Prints '2078'
CS 111 – Introduction to Computing
Functions
Argument Value: A value plugged into a
parameter
Fruitful functions return a value
void functions, or procedures, do not return a
value
sideA = 3.0
sideB = 4.0
# Calculate third side via Pythagorean
Theorem
hypotenuse = math.sqrt(sideA**2 + sideB**2)
print(hypotenuse)
CS 111 – Introduction to Computing
Input / Output
# Calculates the hypotenuse of a right triangle
import math
# Inputting the side lengths, first try
sideA = int(input('Length of side A? '))
sideB = int(input('Length of side B? '))
# Calculate third side via Pythagorean Theorem
hypotenuse = math.sqrt(sideA**2 + sideB**2)
print(hypotenuse)
CS 111 – Introduction to Computing
Sample Python Script
# Marathon training assistant.
import math
# This function converts a number of minutes and # seconds into just seconds.
def total_seconds(min, sec):
return min * 60 + sec
# This function calculates a speed in miles per hour given
# a time (in seconds) to run a single mile. def speed(time):
return 3600 / time
CS 111 – Introduction to Computing
Sample Python Script (cont)
# Prompt user for pace and mileage.
pace_minutes = int(input('Minutes per mile? ')) pace_seconds = int(input('Seconds per mile? ')) miles = int(input('Total miles? '))
# Calculate and print speed.
mph = speed(total_seconds(pace_minutes, pace_seconds)) print('Your speed is ' + str(mph) + ' mph')
# Calculate elapsed time for planned workout. total = miles * total_seconds(pace_minutes, pace_seconds) elapsed_minutes = total // 60
elapsed_seconds = total % 60
print('Your elapsed time is ' + str(elapsed_minutes) + ' mins ' + str(elapsed_seconds) + ' secs')
CS 111 – Introduction to Computing
Sample Python Script (cont) Example Marathon Training Data
CS 111 – Introduction to Computing
Other Architectures Java
PHP
Python
CS 111 – Introduction to Computing
Other Architectures
Technologies to increase throughput:
Pipelining: Overlap steps of the machine cycle
Parallel Processing: Use multiple processors
simultaneously
▪ SISD: Single Instruction, Single Data (No parallel
processing)
▪ MIMD: Multiple Instruction, Multiple Data (Different
programs, different data)
▪ SIMD: Single Instruction, Multiple Data (Same
program, different data)
CS 111 – Introduction to Computing
CS 111 – Introduction to Computing
</End>
Introduction to Computing
(CS111)
Junar A. Landicho
junarlandicho@ustp.edu.ph
“
The only limit to our realization of tomorrow will be our doubts of today.
Franklin D. Roosevelt
Topic 2:
Data
Manipulation
IT 416
Information Systems Development and Management
Learning Outcomes
By the end of this topic, students will be able to: Describe the variety of abstractions used to represent data.
Explain how binary sequences are used to represent digital data.
Identify multiple levels of abstractions that are used when writing programs.
Explain how programs implement algorithms.
Use abstraction to manage complexity in programs.
CS 111 – Introduction to Computing
Overview
1. Computer Architecture
2. Machine Language
3. Program Execution
4. Arithmetic/Logic Instructions 5. Communicating with Other Devices 6. Programming Data Manipulation 7. Other Architectures
CS 111 – Introduction to Computing
Computer Architecture Java
PHP
Python
CS 111 – Introduction to Computing
Computer Architecture
Central Processing Unit (CPU) ▪ Arithmetic/Logic Unit
▪ Control Unit
▪ Register Unit
o General purpose registers
oSpecial purpose registers
Bus
Main Memory
CS 111 – Introduction to Computing
CPU Basics
CPU and main memory connected via a bus
CS 111 – Introduction to Computing
Stored Program Concept
A program can be encoded as bit patterns and stored in Main
Memory. From there, the Control Unit can extract, decode, and
execute instructions.
Instead of rewiring the CPU, the program can be altered by
changing the contents of Main
Memory.
CS 111 – Introduction to Computing
Machine Language Java
PHP
Python
CS 111 – Introduction to Computing
Machine Language
Machine instruction: An instruction
encoded as a bit pattern
recognizable by the CPU
Machine language: The set of all
instructions recognized by a
machine
CS 111 – Introduction to Computing
Machine Language Philosophies
Reduced Instruction Set Computing
(RISC)
▪ Few, simple, efficient, and fast
instructions
▪ Examples: PowerPC from
Apple/IBM/Motorola and ARM
Complex Instruction Set Computing
(CISC)
▪ Many, convenient, and powerful
instructions
▪ Example: Intel
CS 111 – Introduction to Computing
Machine Instruction Types
Data Transfer: copy data from one
location to another (e.g. LOAD,
STORE)
Arithmetic/Logic: operations on bit
patterns
(e.g. +, -, *, /, AND, OR, SHIFT,
ROTATE)
Control: direct the execution of the
program
(e.g. JUMP, BRANCH)
CS 111 – Introduction to Computing
Vole: An Illustrative Machine Language
Adding values stored in memory
Dividing values stored in memory
The architecture of the Vole
CS 111 – Introduction to Computing
Parts of a Machine Instruction
Op-code: Specifies which operation to execute Operand: Gives more detailed information about the operation ▪ Interpretation of operand varies depending on op-code
CS 111 – Introduction to Computing
Parts of a Machine Instruction
Decoding the instruction 0x35A7
Decoding the instruction 0x35A7
CS 111 – Introduction to Computing
Program Execution Java
PHP
Python
CS 111 – Introduction to Computing
Program Execution
Controlled by two special purpose registers ▪ Instruction register (holds current instruction) ▪ Program counter (holds address of next instruction)
Machine Cycle: (repeat these 3 steps) ▪ Fetch, Decode, Execute
CS 111 – Introduction to Computing
The Machine Cycle
CS 111 – Introduction to Computing
Decoding the InstructionCS 111 – Introduction to Computing
An Example of Program Execution
Stored in main memory ready for execution
CS 111 – Introduction to Computing
An Example of Program Execution Performing the fetch step of the machine cycle
CS 111 – Introduction to Computing
Arithmetic/Logic Instructions
Python
Java
PHP
CS 111 – Introduction to Computing
Arithmetic/Logic Instructions
Logic Operations:
▪ AND, OR, XOR
▪ often used to mask an operand
Rotation and Shift Operations:
▪ circular shift, logical shift, arithmetic shift
Arithmetic Operations:
▪ add, subtract, multiply, divide
▪ two’s complement versus floating-point
CS 111 – Introduction to Computing
Arithmetic/Logic Instructions
Logic Operations:
▪ AND, OR, XOR
▪ often used to mask an operand
Rotation and Shift Operations:
▪ circular shift, logical shift,
arithmetic shift
Arithmetic Operations:
▪ add, subtract, multiply, divide
▪ two’s complement versus floating
pointRotating the bit pattern 0x65 one bit to the right
CS 111 – Introduction to Computing
Communicating with Other Devices
Python
Java
PHP
CS 111 – Introduction to Computing
Communicating with Other Devices
Controller: handles communication
between the computer and other
devices
▪ Specialized (by type of device)
▪ General purpose (USB, HDMI)
Port: The point at which a device
connects to a computer
Memory-mapped I/O: devices
appear to the CPU as though they
were memory locations
CS 111 – Introduction to Computing
Communicating with Other Devices
Controllers attached to a machine’s bus
CS 111 – Introduction to Computing
Communicating with Other Devices
A conceptual representation of memory-mapped I/O
CS 111 – Introduction to Computing
Communicating with Other Devices
Direct memory access (DMA):
Main memory access by a
controller over the bus
▪ Von Neumann Bottleneck: occurs
when the CPU and controllers
compete for bus access
Handshaking: the process of
coordinating the transfer of data
between the computer and the
peripheral device
CS 111 – Introduction to Computing
Communicating with Other Devices
Popular Communication Media
▪ Parallel Communication: Several
signals transferred at the same time,
each on a separate “line”
(computer’s internal bus)
▪ Serial Communication: Signals are
transferred one after the other over a
single “line” (USB, FireWire)
CS 111 – Introduction to Computing
Data Communication Rates
Measurement units
▪ bps: bits per second
▪ Kbps: Kilo-bps (1,000 bps)
▪ Mbps: Mega-bps (1,000,000 bps)
▪ Gbps: Giga-bps (1,000,000,000 bps)
Bandwidth: Maximum available
rate
CS 111 – Introduction to Computing
Programming Data Manipulation
Python
Java
PHP
CS 111 – Introduction to Computing
Programming Data Manipulation
Programing languages shields
users from details of the machine:
▪ A single Python statement might
map to one, tens, or hundreds of
machine instructions
▪ Programmer does not need to know
if the processor is RISC or CISC
▪ Assigning variables surely involves
LOAD, STORE, and MOVE op-codes
CS 111 – Introduction to Computing
Bitwise Problems as Python Code
print(bin(0b10011010 & 0b11001001))
# Prints '0b10001000'
print(bin(0b10011010 | 0b11001001))
# Prints '0b11011011'
print(bin(0b10011010 ^ 0b11001001))
# Prints '0b1010011'
CS 111 – Introduction to Computing
Control Structures
If statement:
if (water_temp > 140):
print('Bath water too hot!’)
While statement:
while (n < 10):
print(n)
n = n + 1
CS 111 – Introduction to Computing
Functions
Function: A name for a series of operations that
should be performed on the given parameter or
parameters
Function call: Appearance of a function in an
expression or statement
x = 1034
y = 1056
z = 2078
biggest = max(x, y, z)
print(biggest) # Prints '2078'
CS 111 – Introduction to Computing
Functions
Argument Value: A value plugged into a
parameter
Fruitful functions return a value
void functions, or procedures, do not return a
value
sideA = 3.0
sideB = 4.0
# Calculate third side via Pythagorean
Theorem
hypotenuse = math.sqrt(sideA**2 + sideB**2)
print(hypotenuse)
CS 111 – Introduction to Computing
Input / Output
# Calculates the hypotenuse of a right triangle
import math
# Inputting the side lengths, first try
sideA = int(input('Length of side A? '))
sideB = int(input('Length of side B? '))
# Calculate third side via Pythagorean Theorem
hypotenuse = math.sqrt(sideA**2 + sideB**2)
print(hypotenuse)
CS 111 – Introduction to Computing
Sample Python Script
# Marathon training assistant.
import math
# This function converts a number of minutes and # seconds into just seconds.
def total_seconds(min, sec):
return min * 60 + sec
# This function calculates a speed in miles per hour given
# a time (in seconds) to run a single mile. def speed(time):
return 3600 / time
CS 111 – Introduction to Computing
Sample Python Script (cont)
# Prompt user for pace and mileage.
pace_minutes = int(input('Minutes per mile? ')) pace_seconds = int(input('Seconds per mile? ')) miles = int(input('Total miles? '))
# Calculate and print speed.
mph = speed(total_seconds(pace_minutes, pace_seconds)) print('Your speed is ' + str(mph) + ' mph')
# Calculate elapsed time for planned workout. total = miles * total_seconds(pace_minutes, pace_seconds) elapsed_minutes = total // 60
elapsed_seconds = total % 60
print('Your elapsed time is ' + str(elapsed_minutes) + ' mins ' + str(elapsed_seconds) + ' secs')
CS 111 – Introduction to Computing
Sample Python Script (cont) Example Marathon Training Data
CS 111 – Introduction to Computing
Other Architectures Java
PHP
Python
CS 111 – Introduction to Computing
Other Architectures
Technologies to increase throughput:
Pipelining: Overlap steps of the machine cycle
Parallel Processing: Use multiple processors
simultaneously
▪ SISD: Single Instruction, Single Data (No parallel
processing)
▪ MIMD: Multiple Instruction, Multiple Data (Different
programs, different data)
▪ SIMD: Single Instruction, Multiple Data (Same
program, different data)
CS 111 – Introduction to Computing
CS 111 – Introduction to Computing
</End>