Algonquin College
Computer Studies
CST 8110
Introduction to Computing
Ian D. Allen
Rideau B215A
idallen@freenet.carleton.ca
Welcome to
Algonquin College
Focused on Your Career
Customized Training
Workplace Skills
Quality Instruction
Instructor
Ian D. Allen
B.A.
Honours Psychology
University of Waterloo
1980
MMath
Computer Science
University of Waterloo
1985
Contact
Information
Ian D. Allen
idallen@freenet.carleton.ca
Rideau B215A
Telephone (727-4723) x5949
Voice Mail
Office hours
see my office door
Notes and Course Outlines
online:
http://idallen.com/teaching/
in library
Things You
Should Know
Your Student Number
marks are grouped by number
Your Course Number
CST8110 section 030 - Ian Allen
Course Times
Lectures: two hours / week
030 Mon 11:00-12:00 RE201
Wed 11:00-12:00 RE201
Labs: two hours / week
031 Thu 14:00-16:00 RC209
032 Fri 13:00-15:00 RC205
033 Tue 14:00-16:00 RC209
CST 8110
Course Outline
course outlines are available online
please review academic policies
withdrawing
repeating courses
probation
academic discipline
Course Learning
Requirements
Lectures
2 hours Class
2 hours Lab (mandatory)
Evaluation / Earning Credit
35% in-class tests & quizzes
40% final examination
25% assignments
Assignment Late Penalty
up to one week ... 20%
after one week ... 100%
Marking
Scheme
A: 85-100
An outstanding level of achievement has been consistently
demonstrated.
B: 75-84
Achievement has exceeded the required level.
C: 65-74
Course requirements are met.
D: 50-64
Achievement is at a marginal level. Consistent, ongoing
effort is required for continuing success in the program.
CST 8110 Major
Academic Events
Midterm #1
in class
Wednesday, February 5, 1997
Spring Break
March 3 - 7, 1997
Midterm #2
in class
Wednesday, March 19, 1997
Final Exam Period
in auditorium
April 26 - May 3 (inclusive)
How to Succeed
in this Course
Do the assignments
understand the theory
apply the theory
practice
Attend Lectures and Labs
remember your diskettes
be on time
ask questions
Learn the tools
memorization isnt enough
Lab and Lecture
Dialogue Protocol
There are no dumb questions
ask
ask
ask
Stop me if I go too fast
assist me in knowing your learning styles
Do your homework
use class time to ask questions
Lab and Lecture
Dialogue Protocol
Be here
Lab attendance is mandatory
Be on time
use class time well
Listen
to me
to questions (and answers!)
Focus
dont distract me or others
dont distract yourself
Required
for Laboratories
Diskettes
3 ½ inch
high density (HD)
disks for assignments
spare disks for back-up
You
sign in
please be on time
attendance is mandatory
missed labs result in no course credit: see the course
outline
CST 8110
Assignment 0
Generate your accounts
you must do this for e-mail
daily in C114, E121
Labs: C204, C205, C209, +?
Choose a good password
you can remember it
other people cant guess it
Use your account
ask for assistance
find the course outline
send your neighbour some e-mail
How a Computer
Works
Addressable Memory
composed of binary digits: bits
bits grouped by 8 into bytes
each byte has an address
bytes grouped into words
Central Processing Unit (CPU)
reads bytes and words from memory
operates on the bits (adds, shifts, etc.) based on the
numeric instruction code also read from memory
writes bytes and words into memory
Input and Output (I/O)
printers, terminals, modems, etc.
Computer
Programs
are simply numbers stored in the main memory of the
computer
the numbers have special meaning when read by the
Central Processing Unit (CPU)
the CPU reads the numbers as instruction codes that
tell it to perform some actions
the action taken by the CPU upon reading a numeric
instruction code from memory depends on the type of the CPU,
e.g. PC, Macintosh, Atari
Number
Systems
Natural Numbers
1, 2, 3, ...
Whole Numbers
0, 1, 2, 3, ...
Integers
, -2, -1, 0, 1, 2,
Rational Numbers
22/7, 1/3, etc.
Irrational Numbers
PI=3.14159265358979323
Positional Notation
Base 10
4,295 base 10
4 x 10 to the power 3 = 4,000
2 x 10 to the power 2 = + 200
9 x 10 to the power 1 = + 90
5 x 10 to the power 0 = + 5
------
as a base 10 number = 4,295
3.1415 base 10
3 x 10 to the power 0 = 3.0
1 x 10 to the power -1 = +.1
4 x 10 to the power -2 = +.04
1 x 10 to the power -3 = +.001
5 x 10 to the power -4 = +.0005
-------
as a base 10 number = 3.1415
Base 8
Octal
7162 base 8
7 x 8 to the power 3 = 3,584
1 x 8 to the power 2 = + 64
6 x 8 to the power 1 = + 48
2 x 8 to the power 0 = + 2
------
as a base 10 number = 3,698
2.1730 base 8
2 x 8 to the power 0 = 2.0
1 x 8 to the power -1 = +.125
7 x 8 to the power -2 = +.109375
3 x 8 to the power -3 = +.0058593
0 x 8 to the power -4 = +.0000000
----------
as a base 10 number = 2.2402343
More Digits for
Base 16 - Hexadecimal
Base 2 digits: 0,1
Base 8 digits: 0,1,2,
,6,7
Base 10 digits: 0,1,2,
,8,9
Base 16 digits:
0,1,2,
,8,9,A,B,
,E,F
A is a digit with value 10
B is a digit with value 11
C is a digit with value 12
D is a digit with value 13
E is a digit with value 14
F is a digit with value 15
F + 1 = 10 base 16
D + E = 1B base 16
C - 7 = 5 base 16
F - E = 1 base 16
Base 16
Hexadecimal
719F base 16
7 x 16 to the power 3 = 28,672
1 x 16 to the power 2 = + 256
9 x 16 to the power 1 = + 144
F x 16 to the power 0 = + 15
-------
as a base 10 number = 29,087
F.1C3 base 16
F x 16 to the power 0 = 15.0
1 x 16 to the power -1 = + .0625
C x 16 to the power -2 = + .046875
3 x 16 to the power -3 = + .000732
----------
as a base 10 number = 15.110107
Any Base
to Base 10
Conversion of a whole number in any base to decimal
(base 10):
Multiply each digit in the number by the base raised to
the power corresponding to the position of the digit in the
number
The rightmost digit is multiplied by the base raised to the
power zero, next digit is multiplied by the base raised to
the power 1, etc.
Sum the resulting products
Base 10
to Any Base
Left-to-Right:
Start dividing by the largest power of the base that is
less than or equal to the value; continue with all the
lesser powers of the base in order. Write down the
quotient digits from top-to-bottom and left-to-right.
Right-to-Left:
Keep dividing by the base until the quotient is zero.
Write down the remainder digits in order from top-to-
bottom and right-to-left.
Base 10 to Binary:
Left-to-Right
Start dividing by the largest power of the base that is
less than or equal to the value; continue with all the
lesser powers of the base in order:
1933 base 10 to binary (base 2):
1933 div 2**10 = 1 rem 909
909 div 2**9 = 1 rem 397
397 div 2**8 = 1 rem 141
141 div 2**7 = 1 rem 13
13 div 2**6 = 0 rem 13
13 div 2**5 = 0 rem 13
13 div 2**4 = 0 rem 13
13 div 2**3 = 1 rem 5
5 div 2**2 = 1 rem 1
1 div 2**1 = 0 rem 1
1 div 1**0 = 1 rem 0
= 11110001101 binary
( top-to-bottom and left-to-right )
Base 10 to Hex:
Left-to-Right
Start dividing by the largest power of the base that is
less than or equal to the value; continue with all the
lesser powers of the base in order:
1933 base 10 to hex:
1933 div 16**2 = 7 rem 141
141 div 16**1 = 8 rem 13
13 div 16**0 = 13 rem 0
= 78D hex (base 16)
( top-to-bottom and left-to-right )
Note that 13 is written as the digit D in hexadecimal
notation.
Base 10 to Binary:
Right-to-Left
Keep dividing by the base until zero; write all the
remainder digits down from right-to-left:
1933 base 10 to binary (base 2):
1933 div 2 = 966 rem 1
966 div 2 = 483 rem 0
483 div 2 = 241 rem 1
241 div 2 = 120 rem 1
120 div 2 = 60 rem 0
60 div 2 = 30 rem 0
30 div 2 = 15 rem 0
15 div 2 = 7 rem 1
7 div 2 = 3 rem 1
3 div 2 = 1 rem 1
1 div 2 = 0 rem 1
= 11110001101 binary
( top-to-bottom and right-to-left )
Base 10 to Hex:
Right-to-Left
Keep dividing by the base until zero; write all the
remainder digits down in order from top-to-bottom and right-
to-left:
1933 base 10 to hex:
1933 div 16 = 120 rem 13
120 div 16 = 7 rem 8
7 div 16 = 0 rem 7
= 78D hex (base 16)
( top-to-bottom and right-to-left )
Note that 13 is written as the digit D in hexadecimal
notation.
Between Binary, Octal,
and Hexadecimal
Bases 2, 8, and 16 are easily related
Binary: Consider a two-byte value:
10110100 11000110
Octal: group/ungroup by 8s (3 bits)
1 011 010 011 000 110
1 3 2 3 0 6
=> 132306 base 8
Hex: group/ungroup by 16s (4 bits)
1011 0100 1100 0110
B 4 C 6
=> B4C6 base 16
1323068 = B4C616 = 46,27810
Conversion
Summary Sheet
Decimal to other bases
For positive or unsigned numbers:
Use the right-to-left or left-to-right dividing-by-the
base method
Other bases to decimal
For positive or unsigned numbers:
Multiply each digit by its corresponding power of the
base
Add up the products
Among binary, octal, and hex
For all bit patterns, whether signed or unsigned, just
group and ungroup bits:
Octal: group/ungroup by 3 bits
Hex: group/ungroup by 4 bits
Short Cuts
in Number Systems
Note that 0111111 base 2 is one less than 1000000 base
2
Note that 0777 base 8 is
one less than 1000 base 8
Note that 0999 base 10 is
one less than 1000 base 10
Note that 0FFF base 16 is
one less than 1000 base 16
Numbers to Characters
7-Bit ASCII
American Standard Code for Information Interchange
An interpretation of 7-bit numbers
7 bits means 128 values (characters)
the value of ' ' (space) = 32
Upper-case: 'A' = 65 'Z' = 90
Lower-case: 'a' = 97 'z' = 122
ASCII characters are 7-bit numbers:
'A' + ' ' = 'a' (= 97)
'B' + ' ' = 'b' (= 98)
'a' + 2 = 'c' (= 99)
Unsigned
8-bit Integers
Consider one-byte (8-bit) integers:
2**8 = 256 possible numbers:
0000 0000 0016 0
0000 0001 0116 1
0000 0010 0216 2
0000 0011 0316 3
. . .
0111 1110 7E16 126
0111 1111 7F16 127
1000 0000 8016 128
1000 0001 8116 129
1000 0010 8216 130
1000 0011 8316 131
. . .
1111 1101 FD16 253
1111 1110 FE16 254
1111 1111 FF16 255
Signed (+/-)
8-bit Integers
Consider one-byte (8-bit) integers:
2**8 = 256 possible numbers:
0000 0000 0016 0
0000 0001 0116 1
0000 0010 0216 2
0000 0011 0316 3
. . .
0111 1110 7E16 126
0111 1111 7F16 127
1000 0000 8016-128
1000 0001 8116-127
1000 0010 8216-126
1000 0011 8316-125
. . .
1111 1101 FD16 -3
1111 1110 FE16 -2
1111 1111 FF16 -1
Signed (+/-)
16-bit Integers
Consider two-byte (16-bit) integers:
2**16 = 65,536 possible numbers:
000016 0
000116 1
000216 2
000316 3
. . .
7FFE16 32,766
7FFF16 32,767
800016 -32,768
800116 -32,767
800216 -32,766
. . .
FFFC16 -4
FFFD16 -3
FFFE16 -2
FFFF16 -1
Observations on
Signed Integers
Since half the bit values are used for negative
numbers, signed integers have half the positive range of
unsigned integers
16 bit unsigned: 0
65,535
16 bit signed: -32,768
0
+32,767
The most positive value and most negative value are
adjacent bit patterns
adding one to the most positive value generates the bit
pattern for the most negative value (integer overflow)
-1 is always all bits turned on
8 bits: FF
16 bits: FFFF
32 bits: FFFFFFFF
adding 1 to -1 turns all bits off: zero
Observations on
Signed Integers II
The same bit pattern may be interpreted as either signed or
unsigned. We say N is a signed integer if, when we
interpret N, we interpret all bit patterns with the sign bit
set as negative numbers.
If N is a signed integer, then its bit pattern is to be read
as signed, and the leftmost (top) bit is known as the sign
bit. If N is signed and the sign bit is set, the bit
pattern will be interpreted as a negative number.
Note: If the sign bit is zero, the bit pattern has the
same numeric value whether interpreted as signed or
unsigned.
If the number is a signed number, zero is positive (the
sign bit is not set).
Operations on
Signed Integers
Negating signed binary, octal, hex
invert all the bits: 1 => 0, 0 => 1
(same as subtracting from -1)
then add 1
i.e. -N = ((-1) - N) + 1
e.g. to negate C0F6 (negative):
= ((-1) - C0F6) + 1
= (FFFF - C0F6) + 1
= 3F09 + 1
= 3F0A (positive)
Converting negative decimal numbers
convert the positive equivalent
then negate it (using the above method)
e.g. to convert decimal -16,138
= -(16,138) - make positive
= -(3F0A) - convert
= C0F6 - negate
Operations on
Signed Integers II
Numbers with the sign bit set
Only signed numbers can be negative, and negative only
if the sign bit is set
e.g. C0F6, 80A7, FFFF
To convert signed, negative numbers from binary, octal,
and hex to decimal
negate the number (make positive)
then convert to decimal
then change the sign
e.g. to convert signed C0F6 (negative)
= -(3F0A) - negate
= -(16,138) - convert
= -16,138 - change sign
e.g. to convert signed 10101010
= -(01010110) - negate
= -(86) - convert
= -86 - change sign
Conversion of
Signed Integers
From signed, negative bit patterns to negative decimal
numbers
negate the negative bit pattern to make it a positive
bit pattern
convert the positive bit pattern to a positive decimal
number
change the sign on the positive decimal number to make
it negative again
From negative decimal numbers to signed, negative bit
patterns
change the sign on the negative decimal number to make
it positive
convert the positive decimal number to a positive bit
pattern
negate the positive bit pattern to make it a negative
bit pattern again
CST8110 Intro to Computing - Assignment #1
Due: 8:45am Monday, January 20, 1997
Purpose and Instructions:
A review of Number Systems.
Always show the steps of your calculations for all
conversions!
1. Write out the hexadecimal A times table in
hexadecimal,
i.e. A x 1 = A, A x 2 = 14, A x 3 =,
, A x E =, A x F
=
2. Convert 32,047 decimal to 16-bit
a. octal
b. hexadecimal
c. binary
3. Convert the signed 16-bit binary number
10010010 01010101 to
a. octal
b. hexadecimal
c. decimal
4. Convert the signed 16-bit binary number
01010101 10010010 to
a. octal
b. hexadecimal
c. decimal
5. What ASCII characters have numeric values greater
than Z but less than a? List the characters and
their decimal and hexadecimal numeric values.
6. If we group 11 bits together,
a. How many different numeric values can be stored in
11 bits?
b. What range of unsigned numbers can be represented,
starting at zero?
c. What range of signed numbers would be representable?
7. What is a CPU and what does it do in a computer?
8. How is computer memory organized?
Your assignment is due in the Ian Allen assignment box
before 8:45am Monday, January 20.
Please fasten all pages of your assignment firmly, or
place all parts into a full-size brown envelope.
Identify your assignments:
Make obvious on your assignment these things (type or
print clearly):
your name,
your student ID number,
your weekly Lab section number, and
the the course number: CST8110
CST8110 Intro to Computing - Assignment #1
Answer Key I
Always show the steps of your calculations for all
conversions!
1. A x 0 = 00 A x 1 = 0A A x 2 = 14 A
x 3 = 1E
A x 4 = 28 A x 5 = 32 A x 6 = 3C A
x 7 = 46
A x 8 = 50 A x 9 = 5A A x A = 64 A
x B = 6E
A x C = 78 A x D = 82 A x E = 8C A
x F = 96
All digits and numbers above are Base 16.
2. 32,047(10)=> 7 x 8**4 rem 3375
6 x 8**3 rem 303
4 x 8**2 rem 47
5 x 8**1 rem 7
7 x 8**0 rem 0 => 76457(8)
octal
32,047(10) => 7 x 16**3 rem 3375
13 x 16**2 rem 47
2 x 16**1 rem 15
15 x 16**0 rem 0 => 7D2F(16)
hexadecimal
32,047(10) => 7D2F(16) => 0111 1101 0010 1111(2)
binary
3. Re-group the 16 binary bits by threes and by fours:
1 001 001 001 010 101(2) 1001 0010 0101 0101(2)
1 1 1 1 2 5(8) octal 9 2 5
5(16) hexadecimal
The number is negative, since the sign bit is set; but,
that doesnt affect conversions between bases 2, 8, and 16
where we simply group the bits differently. Only the
conversion of a signed negative bit pattern to decimal
needs the signed conversion method. We can convert the
negative bit pattern to a negative decimal starting with
any of binary, octal, or hexadecimal; lets pick
hexadecimal since its the shortest:
a) Invert the bits by subtracting 9255(16) from a 16-bit
-1: (FFFF - 9255) => 6DAA(16)
b) Add 1 to complete the negation of the bit pattern:
6DAA + 1 = 6DAB(16)
c) Convert 6DAB(16) to decimal: B x 16**0 + A x 16**1 +
D x 16**2 + 6 x 16**3 giving 28,075(10)
d) Changing the sign gives the correct negative decimal
answer -28,075(10)
CST8110 Intro to Computing - Assignment #1
Answer Key II
4. Re-group the 16 binary bits by threes and by fours:
0 101 010 110 010 010(2) 0101 0101 1001 0010(2)
0 5 2 6 2 2(8) octal 5 5 9 2(16)
hexadecimal
The number is positive, since the sign bit is zero.
Positive numbers can be converted to decimal using the
direct multiply-by-powers-of-the-base conversion method:
2 x 16**0 + 9 x 16**1 + 5 x 16**2 + 5 x 16**3 = 21,906(10)
5. [ 91 5B \ 92 5C ] 93 5D
^ 94 5E _ 95 5F ` 96 60
6. a) 11 bits can store 2**11 (2,048) different values
b) All the values are positive if the number is unsigned,
so the range is from 0 to +2,047
c) 11-bit signed integers can range from -1,024 to +1,023
7. CPU stands for Central Processing Unit. The CPU
reads bytes and words from the computer memory,
interpreting the numbers as instruction codes. The
instruction codes tell the CPU what to do. The CPU
coordinates all computer operations, performs arithmetic
and logical operations, and copies bytes and words to and
from memory. (Text: section 1.2)
8. Computer memory is made up of binary digits (bits).
The bits are grouped into bytes (usually 8 bits) and the
bytes are grouped into words (usually 2 or 4 bytes). Each
location in memory (each byte or each word) has a unique
address so that the CPU can find it and read or write it.
(Text: section 1.2)
Marking Scheme
Q1. 5
Q2. 3+3+3
Q3. 3+3+3
Q4. 3+3+3
Q5. 5
Q6. 3+3+3
Q7. 2
Q8. 2
Followed assignment submission instructions: 10
Total: 60
Floating-Point
Numbers I
see Scientific Notation p.5 in the Algonquin CST8110
Blue Book
Floating-point numbers are stored as separate mantissa
(fraction) and exponent
.31415926 E+1
Limits on the size of the mantissa and exponent limit
the precision (accuracy) and range of floating-point numbers
precision: # bits used in mantissa
1.234567 E1
1.234567890123456789 E1
range: # bits used in exponent
1.0 E38
1.0 E300
Floating-Point Numbers II
Just as some numbers are too big to fit in a given
number of bits of storage, some floating-point numbers are
too small
e.g. 1.0 E-500
Numbers nearer to zero are closer together than numbers
with larger exponents
the mantissa multiplies the exponent; successive
numbers in the mantissa multiply the larger exponents
Adding a relatively small number to a large one may not
change the large one
e.g. 1.0E30 + 1.0E1 = 1.0E30
the mantissa may not have enough precision to reflect
the addition of such a relatively small number
Floating Point
Limitations
Binary values between 0 and 1 are sums of products of
negative powers of two; they do not always accurately
express sums of products of negative powers of ten.
Similar problem: 1/3 cannot be exactly expressed as a
finite decimal number:
0.333333333333333333
1/10 (0.1 decimal) cannot ever be accurately
represented in base 2, 8, or 16:
0.000110011001100
base 2
0.0631631631631
base 8
0.19999999999
base 16
a sum of ten binary tenths will not be exactly 1 due
to this representation error
Using
Floating Point
Be aware of round-off error occurring due to the
limited number of bits available for each of the mantissa
and exponent.
Make sure you pick a storage type with enough bits for
precision and range to accurately represent the numbers you
use.
Note that a four-byte integer has more bits of precision
than a four-byte floating-point number. A four-byte integer
has less range than a four-byte floating point #.
Never compare floating-point numbers for exact
equality; test for close enough against a reasonably
small value:
absolute_value(f1 - f2) < epsilon
Floating Point
Implementations
For general use, the C language on most computers defines a
float floating-point storage type, 4 bytes long, that
handles approximately 6-7 decimal digits of mantissa and an
exponent between -38 and +38
The C language double floating-point storage type, 8 bytes
long, handles approximately 17-18 decimal digits of mantissa
and an exponent between -308 and +308
Remember: Bits are bits. The same bit pattern may be a
signed or unsigned integer, a character, or a floating-point
number, depending on how it is used.
CST8110 Intro to Computing - Assignment #2
Due: 8:45am Monday, February 3, 1997
Instructions:
Always show the steps of your calculations for all
conversions!
1. What does the 8-bit binary bit pattern 01111010
look like when expressed
a. in octal b. in hexadecimal c. as an
unsigned decimal number
d. as a signed decimal number e. as an ASCII
character
2. Convert the value -125 decimal to 8-bit
a. octal b. hexadecimal c. binary
3. Convert the value -32,047 decimal to 16-bit
a. octal b. hexadecimal c. binary
4. What value do you add to an upper-case ASCII
letter to make it a lower-case ASCII letter?
5. What range of signed numbers can be stored in 23
bits?
6. Define the precision and the range of a floating-
point number.
7. Explain the difference between how integers and
floating-point numbers are stored in computer memory.
8. What are the precision and range of the C Language
float floating-point storage type?
9. For each of the following measurements, indicate
whether the numeric value is best stored in a signed
two-byte integer or a C Language float floating-point
storage type. Explain why:
a. Price (dollars and pennies) of a computer b.
Count of children in one family
c. Count of children in all of Canada d. Your
height in centimetres
e. Your height in metres f. Exchange rate between
Canadian and U.S. dollars
10. 1/10 (0.1) is a binary fraction that repeats
forever. What happens when such a fraction is entered
into a computer memory location that only has a fixed
number of bits to store it?
Due dates and times:
Your assignment is due in the Ian Allen assignment box
before 8:45am Monday, February 3.
Please fasten together firmly all parts of your assignment
so that no parts will be lost.
(An excellent strategy is to put all your pages into a
labelled full-size brown envelope.)
Identify your assignments:
Make obvious on the outside of your assignment these four
things (type or print clearly):
1. your name,
2. your student ID number,
3. your weekly Lab time and section number (031, 032, or
033), and
4. the course number: CST8110.
Evaluation
Assignments are marked for clarity and simplicity as well
as correctness.
Late assignments are handled according to the policy given
in the course outline.
CST8110 Intro to Computing - Assignment #2
Answer Key
Always show the steps of your calculations for all
conversions!
1. 01111010(2) => 01 111 010 => 0111
1010(2)
1 7 2(8) 7 A(16)
7A(16) = 7 x 16**1 + A x 16**0 = 122(10)
7A(16) = z ASCII
2. -125(10) is negative, so it cant be converted
directly. We must convert the positive value first, then
negate the bit pattern to make it a negative bit pattern.
125(10) = 7 x 16**1 rem 13
13 x 16**0 rem 0 => 7D(16)
hexadecimal
Alternately convert +125(10) to hex by observing it is 3
larger than 122(10) from question 1:
125(10) = 122(10) + 3 = 7A(16) + 3 = 7D(16)
1) Invert the bits by subtracting 7D(16) from an 8-bit -
1: (FF - 7D) => 82(16)
2) Add 1 to complete the negation of the bit pattern:
82(16) + 1 = 83(16)
Octal: regoup 83(16) by three bits -> 1000 0011(2) -> 10
000 011(2) -> 203(8)
3. -32,047(10) is negative, so it cant be converted
directly. We must convert the positive value first, then
negate the bit pattern to make it a negative bit pattern.
32,047(10) = 7 x 16**3 rem 3375
13 x 16**2 rem 47
2 x 16**1 rem 15
15 x 16**0 rem 0 => 7D2F(16)
hexadecimal
1) Invert the bits by subtracting 7D2F(16) from a 16-bit
-1: (FFFF - 7D2F) => 82D0(16)
2) Add 1 to complete the negation of the bit pattern:
82D0(16) + 1 = 82D1(16)
Octal: regoup 82D1(16) by three bits -> 1 000 001 011 010
001(2) -> 101321(8)
4. a - A = 32
5. From -2**22 to +2**22-1, i.e. from -4,194,304 to +
4,194,303
6,7,8. See text and class notes.
9. a) float; needs decimal b) integer; small integral
count c) float; large number
d) integer; small integral count e) float; needs decimal
f) float; needs decimal.
10. The repeating binary fraction is either truncated
after a certain number of bits, resulting in a stored
value slightly smaller than the exact value, or it is
rounded up, resulting in a stored value slightly larger
than the exact value. In either case, the value stored is
not the exact value.
Algonquin College
CST 8110 - Introduction to Computing
Midterm #1 - February 5, 1997
11:00 - 11:50 - 50 minutes
Lecture Section 030 - Ian D. Allen
Identification
Your name: Please Print Clearly
Your student ID: Your Lab Section:
Instructions
Read the whole test before you start.
Do the things you know best first. You have 50 minutes.
Answer questions in the space provided.
Hand in this entire test when you are finished.
No calculators or other aids are permitted.
This test is closed book.
Raise your hand if you have questions.
Do not leave your seat.
You may not be able to complete the entire test.
Remain calm.
Marking Scheme
This midterm test is marked out of 60.
Marks for each question are listed beside each question.
Midterms and class quizzes count together for 35% of your
final grade.
Your mark on this first midterm is part of that 35%.
Problem Solving and
Stepwise Refinement
Text: Section 1.5 - 1.6
Blue Book: Stepwise Refinement (p. 12-24)
Problem Solving:
Define the problem
Determine the Outputs
Determine the Inputs
Derive the Algorithm
Stepwise Refinement of an Algorithm:
Steps are followed in order
Each stepwise refinement is indented
Each indentation explains how to do the higher-level
step above it
No more than half a dozen steps at any level of
indentation
Dont focus on detail and refinement until all the
higher-level steps are understood
Problem: Feed Me
Get Food
Obtain Money
go outside and unlock bicycle
pedal over to bank machine and get cash
Go Shopping
pedal to local market with cash
purchase macaroni and cheese dinner
Come home
put cheese dinner ingredients in bicycle bag
cycle home (lock bike; go inside with food
)
Prepare Food
Prepare Water
add salt to water
heat water on stove until boiling
Prepare Macaroni
place macaroni in boiling water
wait until cooked just right
drain macaroni
Add Magic Cheese Sauce
mix magic cheese powder into macaroni
mix butter and milk into macaroni
Serve Food
Set table for one
Turn on nice dinner music
Light candles
Place pot of food on dining room table
Put some food from pot onto plate
Eat Food
Place fork into delicious food
Lift fork with food into face
Repeat until food is gone or face is full
Algonquin Pseudocode
Basics
Blue Book: p.10-11,
Appendix A
Use pseudocode to express the details of your
Algorithms
Pseudocode is English text combined with key
programming words
Less strict than programming languages
More strict than English
Algonquin Pseudocode
Rules
Pseudocode should be well structured and pleasing to
the eye.
Each statement must be concise.
Omit words such as the and and.
Start each line with a capital letter.
Use lower case English with upper case programming
keywords.
Keywords are used for:
input and output: GET, PUT
decisions: IF, ELSE
looping: FOR, WHILE
comparison: EQUAL, LESS
Algonquin Pseudocode
Keywords
Input:
GET
Output:
PUT
Decisions:
IF
ELSE
ENDIF
Looping:
FOR
ENDFOR
WHILE
ENDWHILE
DO
WHILE
Proper indentation must be used for each type of
statement.
Indent three spaces for all compound statements and all
statements within loops.
The simple IF statement makes a yes/no decision
Any time execution encounters the simple IF statement, a
choice is made whether or not to execute the enclosed set
of statements:
IF control_expression
Statement 1
Statement 2
ENDIF
If control_expression tests true, execute the set of
statements between the IF and the ENDIF.
If control_expression tests false, skip all the
statements and continue execution with whatever comes after
the ENDIF.
IF is not a loop. When the simple IF statement is
encountered, the set of enclosed statements is only executed
once, or not at all.
The compound IF statement gives two choices (once)
Any time execution encounters a compound IF statement, one
of two sets of statements are chosen:
IF control_expression
A first set of one
or more statements
ELSE
A second set of one
or more statements
ENDIF
If control_expression tests true,
execute the first set of statements, once.
If control_expression tests false,
execute the second set of statements, once.
When this style IF statement is encountered, one or the
other of the sets of statements is done.
Never both sets of statements; never no set
Always one set or the other
How to Construct
a Loop
Initialization
What variables need starting values, once, before we
begin the loop?
Variables used in the control_expression?
Variables used in the loop body?
Condition (control_expression)
Determine the terminating condition that makes the
logical control_expression false and thus tells when to stop
looping.
Increment / decrement
What variable or variables must change value during the
looping, so that the terminating condition eventually
happens?
Usually done at the end of the loop body.
Body
The statements that are repeated in the loop.
The WHILE statement loops zero, one, or many times
The WHILE looping statement iterates zero or more times:
WHILE control_expression
Statement 1
Statement 2
ENDWHILE
While the control_expression tests true at the start of an
iteration of the loop, execute the set of statements between
the WHILE and the ENDWHILE.
When the control_expression tests false at the beginning of
an iteration of the loop, skip all the statements and
continue execution after the ENDWHILE.
Some statement within the loop must cause some value in the
control_expression to change from true to false, otherwise
the control_expression will never test false and the looping
will never stop.
If the control_expression is not true when the WHILE
statement is first encountered, the set of statements is not
executed even once.
The DO/WHILE statement loops one or many times
The DO/WHILE looping statement iterates one or more times:
DO
Statement 1
Statement 2
WHILE control_expression
Execute the set of statements between the DO and the WHILE,
and then repeat while the control_expression tests true at
the end of an iteration of the loop.
When the control_expression tests false at the end of an
iteration of the loop, continue execution after the line
containing the WHILE; dont do any more iterations.
Some statement within the loop must cause some value in the
control_expression to change from true to false, otherwise
the control_expression will never test false and the looping
will never stop.
Because the control_expression is tested at the end of the
loop, the set of statements is always executed at least
once, even if the control_expression is false.
The FOR statement loops (zero, one, or many times)
The FOR looping statement iterates zero or more times:
FOR variable from N1 to N2
Statement 1
Statement 2
ENDFOR
Execute the statements between FOR and ENDFOR with the
variable first set to the value N1. Redo the same
statements with variable taking on the next value (up or
down) toward N2. Continue until variable is equal to N2.
If N1 is already past N2 when the FOR statement is first
encountered, the set of statements is not executed even
once. Execution continues after the ENDFOR.
Definitions
Variable: a named location in memory
Iterate: to loop; to do something more than once
Increment: to increase the value in a variable, usually
by 1
Decrement: to decrease the value in a variable, usually
by 1
Termination condition: the condition that terminates a
loop
Problem 1 in English
Problem: Numbers will be input from keyboard one at a time.
Find the sum of the positive numbers and the sum of the
negative numbers. Display both results.
Use a loop controlled by a character from the keyboard.
The user will be asked if he/she wishes to enter a number.
If the response is 'Y', get the next number and sum it.
Terminate input for any other response character.
Semi-English solution:
Initialize positive sum, negative sum, and prompt message
variables
Prompt user for a Y response
WHILE response is Y
GET number
IF number >= 0
Add to positive sum
ELSE
Add to negative sum
ENDIF
Prompt user for a Y response
ENDWHILE
PUT both sums
Problem 1 in Pseudocode
PosSum <-- 0
NegSum <-- 0
Prompt <-- Enter Y to continue:
Echo <-- Your response was:
PUT Prompt
GET Response
PUT Echo Response
WHILE Response = Y
PUT Enter a number:
GET Number
PUT You entered: Number
IF Number >= 0
PosSum <-- PosSum + Number
ELSE
NegSum <-- NegSum + Number
ENDIF
PUT Prompt
GET Response
PUT Echo Response
ENDWHILE
PUT The positive sum is: PosSum
PUT The negative sum is: NegSum
Problem 2 in English
Problem: The marks for 70 students are to be entered. Find
and display the average mark.
Use a loop controlled by a counter.
Semi-English solution:
Initialize counter, sum
WHILE counter <= 70
GET mark
Add mark to sum
Increment counter
ENDWHILE
Calculate average using counter, sum
PUT average
Problem 2
in Pseudocode
Sum <-- 0
Counter <-- 1
WHILE Counter <= 70
PUT Enter Mark number Mark :
GET Mark
PUT You entered: Mark
Sum <-- Sum + Mark
Counter <-- Counter + 1
ENDWHILE
Average <-- Sum / Counter
PUT The average of Counter
PUT marks is Average
Pseudocode
Exercises
Write the pseudocode for the following problems:
1. Accept numbers from keyboard. Use 9999 to terminate.
Find and display largest number (excluding 9999).
2. To count the number of times it takes player #2 to
guess a number between 1 and 100 that is input by player
#1.
When the guess is too high or too low, display appropriate
messages. When a correct guess is made, display an
appropriate message and the number of guesses taken.
3. Accept positive numbers from keyboard.
Terminate with a negative number.
Determine the smallest and largest positive number that
was entered. Display both.
4. Accept student test marks from the keyboard.
Terminate with a -1. Display each mark.
Count the number of marks that correspond to each letter
grade: A, B, C, D, and F. Display the five counts.
C Language
Basics
Text: Chapter 2
Floating Point
Imprecision
main()
{
int i;
float x;
double y;
printf("\nFloats:\n");
for( i=0; i <= 9; i++ ){
x = 1.0 + (i / 10.0);
printf("Expect 1.%d - actual is %.42f\n",
i, x);
}
printf("\nDoubles:\n");
for( i=0; i <= 9; i++ ){
y = 1.0 + (i / 10.0);
printf("Expect 1.%d - actual is %.42f\n",
i, y);
}
}
Output of
Imprecise Floats
Floats:
Expect 1.0 - actual is
1.000000000000000000000000000000000000000000
Expect 1.1 - actual is
1.100000023841857910156250000000000000000000
Expect 1.2 - actual is
1.200000047683715820312500000000000000000000
Expect 1.3 - actual is
1.299999952316284179687500000000000000000000
Expect 1.4 - actual is
1.399999976158142089843750000000000000000000
Expect 1.5 - actual is
1.500000000000000000000000000000000000000000
Expect 1.6 - actual is
1.600000023841857910156250000000000000000000
Expect 1.7 - actual is
1.700000047683715820312500000000000000000000
Expect 1.8 - actual is
1.799999952316284179687500000000000000000000
Expect 1.9 - actual is
1.899999976158142089843750000000000000000000
Doubles:
Expect 1.0 - actual is
1.000000000000000000000000000000000000000000
Expect 1.1 - actual is
1.100000000000000088817841970012523233890533
Expect 1.2 - actual is
1.199999999999999955591079014993738383054733
Expect 1.3 - actual is
1.300000000000000044408920985006261616945267
Expect 1.4 - actual is
1.399999999999999911182158029987476766109467
Expect 1.5 - actual is
1.500000000000000000000000000000000000000000
Expect 1.6 - actual is
1.600000000000000088817841970012523233890533
Expect 1.7 - actual is
1.699999999999999955591079014993738383054733
Expect 1.8 - actual is
1.800000000000000044408920985006261616945267
Expect 1.9 - actual is
1.899999999999999911182158029987476766109467
Chapter 2
2.1, 2.2, 2.3 Answers
Answers to the odd-numbered questions are in the back of the
text book.
2.1-2 The standard identifiers have particular meanings in
C programs. Redefining standard identifiers for use as
variables may mean that C cant use them for their
original purpose. Your program may not work as intended.
The C compiler will not let you use reserved words as
identifiers; thats why the words are called reserved.
2.1-4 Using the word PI is clearer and less subject to
typing error than using the string of digits. Defining it
once, you can change the definition in that one place to
add or remove precision and the change will be used
everywhere that PI appears; you dont have to make the
change in more than one place. This makes your program
easier to modify and maintain. PI is a constant that
doesnt change during the execution of the program, so it
doesnt need to be a variable.
2.2-2 int: 15, -999; double: 25.123, 15.0, 32e-4, .123;
char: x, *
The others are not valid C language int, double, or char
constants.
2.2-P1 #define PI 3.14159
int num_circ;
double radius, area, circumf;
char circ_name;
2.3-2 Before: undefined. After execution: m=10, n=21.
2.3-4 Change the \n at the end of the sentence to be \n\n.
2.3-P1 printf(Enter three integers: );
scanf(%d%d%d, &first, &second, &third);
2.3-P2-a printf(The value of x is %f\n, x);
2.3-P2-b printf(The area of a circle with radius %f is
%f.\n, radius, area);
2.3-P3 #include
#define PI 3.14159 /* sufficient accuracy for float
arithmetic */
int main(void)
{
float radius; /* 6-7 decimal digits; 10E-38 to
10E38 */
printf(Enter the radius of the circle: );
scanf(%f, &radius);
printf(The area of the circle with radius %f is
%f.\n,
radius, PI * radius * radius );
return(0); /* the operating system return
code */
}
Chapter 2
2.4 Answers
2.4-2
/*
* Calculate and display the sum of two input variables.
* Extra comments have been added to explain each line.
* (One wouldnt normally have so many comments.)
*/
#include /* define standard I/O */
int main(void) /* start of main program */
{
int first, second; /* two input variables
*/
printf(Enter two integers: ); /* prompt for
input */
scanf(%d%d, &first, &second); /* get the input
*/
/* echo the input and display the sum, all in one line:
*/
printf(%d + %d = %d\n, first, second, first +
second);
return(0); /* return to the O/S */
}
2.4-P1
#include
int main(void)
{
char mychar; /* input character */
float myfloat; /* input floating-point number */
printf(Enter a character and a floating-point number:
);
scanf(%c%f, &mychar, &myfloat);
printf(You entered %c and %f\n, mychar, myfloat);
return(0);
}
Chapter 2
2.5 Answers
2.5-2 1.8 * celsius + 32.0
1.8 * 3 + 32.0
5.4 + 32.0
37.4
( salary - 5000.00) * 0.20 + 1425.00
(12400.00 - 5000.00) * 0.20 + 1425.00
7400.0 * 0.20 + 1425.00
1480.0 + 1425.00
2905.0
2.5-4 #define PI 3.14159
#define MAX_I 1000
int i, a=5, b=2;
double x, y=2.0;
a) i = a % b -> 1
b) i = (989 - MAX_I) / a -> negative division; varies
c) i = b % a -> 2
d) x = PI * y -> 6.28318
e) i = a / -b -> negative division; varies
f) x = a / b -> 2.0
g) x = a % (a / b) -> 1.0
h) i = b / 0 -> divide-by-zero fault
i) i = a % (990 - MAX_I) -> negative modulus; varies
j) i = (MAX_I - 990) / a -> 2
k) x = a / y -> 2.5
l) i = PI * a -> 15
m) x = PI / y -> 1.570795
n) x = b / a -> 0.0
o) i = (MAX_I - 990) % a -> 0
p) i = a % 0 -> divide-by-zero fault
q) i = a % (MAX_I - 990) -> 5
Chapter 2
2.5, 2.6, 2.7 Answers
2.5-6 a) x = 4.0 * a * c
b) a = a * c
c) i = 5 * j * 3
d) k = 3 * (i + j)
e) x = (5 * a) + (b * c)
2.5-P1 q = (k * a * (t1 - t2)) / l
2.5-P2The statements that handle the declaration and input
of your data in your program would look like this:
char char1, char2;
float number1;
int number2;
/* . . . */
printf(Enter two characters followed by a number: );
scanf(%c%c%f, &char1, &char2, &number1);
number2 = 35;
2.6-2 %8.4f -> -15.5640
%8.3f -> X-15.564 (using X to represent a blank)
%8.2f -> XX-15.56
%8.1f -> XXX-15.6 (note the decimal rounding)
%8.0f -> XXXXX-16 (note the rounding)
%.2f -> -15.56 (two decimals; no blanks in
output)
2.6-P1 printf(%5d%11.2f%9.1f, a, b, c);
2.7-2 Interactive input comes from a human being via an
input device such as a keyboard. The program issues
prompts to the user, so the user knows what data is
expected.
Batch data comes from a file, either opened by the
operating system and substituted for the keyboard
(redirection), or opened by the program itself (program-
controlled). The file contains the data in the same order
as it would have been typed in by the user.
Just as the same number typed in at the keyboard might be
stored in an integer, a float, or a double, the numbers in
a batch data file might be read by the program and stored
in different ways. There is nothing about the content of
the batch input file itself that says how the program will
interpret the numbers. Different programs may read the
same batch input file and read and store the numbers
differently.
Chapter 2
2.7 Answers (contd)
2.7-P1In our programs done in class and in the Labs, we
have been prompting for input, getting the input, and
echoing it. To convert such a program to a batch
program that works best with input redirection, all we
need to do is remove the prompting statements from the
program, since we dont need to prompt when input comes
from a file.
To convert the programs in the text, we also remove the
prompting statements. Then, if the program does not echo
its input already, we add statements that echo the input
after it has been read, just as we already do in our in-
class programs.
2.7-P1To turn most any program into one using a program-
controlled input and output file, including the program in
Figure 2.12, make these changes:
1) First turn the interactive program into a batch
program by removing the existing prompts and making
sure there are statements that echo the input. Test
the program using input redirection to make sure that
it works and that all the input echoes properly when
reading from a batch file supplied on the command line:
C: myprog