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 isn’t 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 • don’t distract me or others • don’t 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 can’t 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 8’s (3 bits) 1 011 010 011 000 110 1 3 2 3 0 6 => 132306 base 8 • Hex: group/ungroup by 16’s (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 doesn’t 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; let’s pick hexadecimal since it’s 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 can’t 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 can’t 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 • Don’t 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; don’t 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 can’t 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; that’s 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 don’t have to make the change in more than one place. This makes your program easier to modify and maintain. PI is a constant that doesn’t change during the execution of the program, so it doesn’t 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 wouldn’t 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 (cont’d) 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 don’t 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