CS 111 Aug. 25 What is this class

CS 111  Aug. 25  What is this class

CS 111 Aug. 25 What is this class about? IT = How to make computers useful for people Understanding what goes on inside (and outside) the machine Commitment For next day, please read Chapter 0 CS versus IT Computer science How do we solve problems?

Classify problems; insight from solutions How to represent information, languages What is knowledge/information? How to design better computing system Information Technology An applied science Practical goals: make money, win wars, security, safety, protect environment, etc. How can we use the computer to accomplish .? Human history Agricultural age (up to ~ 1800) Industrial age (1800 1950) Information age (1950 --) We live in an information-based society. In other words, many tasks are defined in terms of doing something with information.

People and businesses depend on IT to get things done. Not all countries follow this timeline. IT functions What does IT need to do? Input or capture information Store information for future use Process: manipulate information and present it in a meaningful form Output, i.e. allow retrieval of info Communicate / transmit info to another location IT components Computer: an electronic device that can process and store information Communication network Know-how: the skills needed to make best use of

the computer system Goals throughout IT: Speed Consistency and reliability Precision Business components What does a business need to do? Create something, i.e. manufacturing or service Sell it Ship it Keep track of employees, customers, inventory Communicate and coordinate all these activities. IT speeds up the process, reduces error/waste. Example: think of an airline. CS 111 Aug. 26 Review:

How might an airline use IT? Chapter 0 Computer origins Algorithms Abstraction Commitment for next day: Please read section 1.1 History Analog machines Abacus Mechanical calculators, adding machines, cash registers

Babbage suggested a programmable machine Hollerith adapted Jacquards punch cards Digital machines ENIAC, ABC, Mark I, Colossus Became commercially successful in 1950s Became increasingly affordable by 1980s Innovations often respond to needs HW & SW Hardware physical computer components CPU, memory, I/O devices, network Software programs that run on machine Allows computer to do useful work (or play) Tell the computer exactly what to do Behind any program is its algorithm

The secret to how it really works Clearly defined list of steps to solve a problem Needs to be precise, and spell out details Analogy: a restaurant building, versus the actual restaurant Algorithm example Euclidean algorithm: Given two numbers, find their greatest common divisor. 1. Let m = larger, and n = smaller number 2. Let r = remainder after dividing m/n 3. If r = 0, then our answer is n, and were done. But if r 0, let m = n, and let n = r, and go to step 2. Try it outDo you understand the steps? Does the procedure work? BTW, an algorithm should also clearly specify its input

and output. Abstraction Our way to manage complex problems Big picture first, then the details Details omitted until they become important top-down design Ex. Road map We can study a machine without knowing how to build one Bits Preview of section 1.1: All information in computer is in binary form (0/1) Smallest unit of information is the bit: a single 0 or 1 When we have lots of bits, usually grouped in set of

8 called a byte Basic building block of CPU is the logic gate, which manipulates bit values. Very fast Logic gates combine to perform math operations CS 111 Aug. 27 Section 1.1 Binary data and operations Logic gates Flip-flop A binary shorthand: hexadecimal

Commitment for next day: Please read sections 1.2 and 1.3 Binary All information inside computer is in binary Smallest unit of data is the bit Only the values 0 and 1 are used 0 means false or off or the number 0 1 means true or on or the number 1 Individual bit values can be manipulated with Boolean operations: and, or, not, etc. In hardware, we implement these operations with logic gates. Boolean examples AND To graduate, you must have 128 credits and 2.0 GPA.

OR Classics scholarship requires 3 years of Latin or 3 years of Greek. XOR (exclusive or) To go to Cincinnati, you can fly or drive. In other words, it doesnt make sense to do both. Do you want a 2-door or a 4-door car? NOT If a statement is true, its negation is false, and vice versa . Gates Basic building blocks of CPUs circuitry. Usually 2 inputs. X and Y could be 0 or 1.

Combining gates into a circuit: The output of one gate becomes input to another. This is how more useful operations are performed. AND and OR AND OR X Y ans

X Y ans 1 1 1 1 1 1

1 0 0 1 0 1 0 1 0

0 1 1 0 0 0 0 0 0

Note: 0 AND (anything) = 0 1 OR (anything) = 1 XOR XOR basically says, either but not both The output is 1 if both inputs are different. XOR X Y Ans

1 1 0 1 0 1 0 1 1

0 0 0 NOR, NAND NOR gate Negation of the OR Same as feeding output of OR into a NOT gate. Symbol for NOR gate is same as OR but with a loop on the end. NAND gate Negation of the AND. analogous to NOR. Interesting property:

NOR and NAND are universal gates. Any other boolean operation can be implemented by using several NANDs or several NORs. Flip-flop circuit Circuit that can store or remember a 1 bit value. Its own output is used as input to one of its gates. To change flip-flops value, set one of the inputs to 1. See diagrams on page 23. Hexadecimal One bit is not enough to convey much information. A single word or numerical value requires several bits. Ex. The word cat can be represented by this bit sequence: 011000110110000101110011 Hex is a shorthand for binary

Allows us to represent every 4 bits with just 1 symbol. Ex. 24 bits of information= 6 hex characters. The word hexadecimal means there are 16 possible symbols, so we use 0-9 and then a-f. See table on page 25. CS 111 Aug. 30 1.2 1.3 Information arranged in memory Types of memory Disk properties Commitment for next day: Read pp. 38-40, 45-47. In other words, only the parts of 1.4 and 1.5 dealing with numbers and text Memory units

Bit = a single 0 or 1 value Nibble = 4 bits = 1 hexadecimal digit Byte = 8 bits Kilobyte (KB) = 210 bytes Megabyte (MB) = 220 bytes Gigabyte (GB) = 230 bytes Terabyte (TB) = 240 bytes 210 = 1024, though 1000 is a close approx.

CPU and memory CPUs job is to obey instructions and do calculations Memory system stores information for current and future use CPU has tiny number of registers for calculations main memory (RAM) stores all files currently open Secondary memory (e.g. hard drive) is for long-term storage of files Backup system: tape, external hard drive Other types of memory: Cache, between CPU and RAM Removable drive, e.g. USB or DVD RAM Runs on electricity: volatile but fast Each byte is numbered and addressable Capable of holding a single character or small # Address

Contents 0 c 1 a 2 t 3 9

4 25 5 100 Memory comparison Type Size

Access time Cost per MB CPU registers 256 bytes 1 ns N/A Cache 64 KB 2 ns

$ 20 RAM 512 MB 50 ns $ 0.20 Disk 200 GB 100,000 ns $ 0.0002

Numbers are approximate. ns means nanosecond = 1 billionth of a second Disk geometry Tracks Sectors Platters Hard drive Ex. A DVD has roughly 50,000 tracks and 40 (2KB) sectors per track. Disk access time Analogous to a record player: Seek time: read-write head moves to find the correct track (up to ~ 8ms) Latency: wait for disk to rotate to beginning of file (up to ~ 4ms) Transfer: grab info from disk (e.g. 1 MB/sec

read or 0.1 MB/sec write) CS 111 Sept. 1 Intro to data representation Binary numbers Convert binary decimal Convert decimal binary Text ASCII and Unicode Commitment: For lab: Be sure you understand number conversions For Friday: Please finish reading sections 1.4 and 1.5 Numbers in binary Place value system just like decimal We understand 278 = (2 * 100) + (7 * 10) + (8 * 1)

In a binary number: Each digit is either a 0 or 1 Digits are multiplied by powers of 2, not powers of 10. For example, 001110 and 100011: 32 * 16 * 8* 4* 2* 1*

Value 0 0 1 1 1 0 14 1

0 0 0 1 1 35 Powers of 2

20 = 1 21 = 2 22 = 4 23 = 8 24 = 16 210 ~ 1 thousand 220 ~ 1 million 230 ~ 1 billion Lets say we have 4 bits. What is the lowest # ? What is the highest # ? What if we had 5 bits? Is there a pattern?

Decimal binary One thing to note is that binary numbers are longer than decimal. A 5-digit decimal number may turn out to be 15 bits long. My technique is the binary store All merchandise is priced $1, $2, $4, $8, $16, You enter store with some money, say $45. Goal is to always buy most expensive gift possible. So, 45 = 32 + 8 + 4 + 1 32 *

16 * 8* 4* 2* 1* 1 0 1 1

0 1 Another example Convert 61 to binary: Go to binary store with $61 61 = 32 + 16 + 8 + 4 + 1 Another way to write this is: 61 = 25 + 24 + 23 + 22 + 20 Our binary answer is 111101. CS 111 Sept. 3 More data representation Review hex notation Text ASCII and Unicode

Sound and images Commitment: For Wednesday: Please read pp. 46-57 Quiz next Friday Numbers in a byte A byte is 8 bits So, how big can an 8-bit binary number be? Hexidecimal shorthand 8/4 = 2 hexidecimal digits per byte What do the letters a f mean? a = 10, b = 11, c = 12, d = 13, e = 14, f = 15 Example: 010111102 = 5e in hex. Try this one: 1110002 = ______ in hex. Try this one: a4c in hex = ________ in binary. Text

Fundamental unit is the character. Each character of a text document is given a numerical code. ASCII code Contiguous (make it easy to alphabetize) Case sensitive One byte per character ASCII table (p. 597) A = 65 a = 97 0 = 48 Try encoding the word: Dog Unicode To support foreign alphabet and misc. symbols. Extension of ASCII 16 bits per character, rather than 8 unicode.org has code charts

Codes are given in hex. Sampling Real sound and visual data are continuous, constantly changing Sampling means to take rapid snapshots Video: 30 images a second is good enough for our eyes Real sound is in the form of a wave (p. 43) Sampling sound means finding points along the curve. Music CD: take a reading 44,100 times a second, and store as a 16-bit number How much data is captured in 1 hour? MIDI (= Musical Instrument Digital Interface) uses far less space, though does not sound like an actual recording. Images Fundamental unit is the pixel Usually 8 bits (1 byte) per pixel This means each pixel is assigned a value from 0 to 255

What do these numbers mean? Depends on color system Grayscale = system for B/W images Image dimensions are (horiz x vert) Ex. 400 x 300 120,000 pixels Aspect ratio When changing size, this should not change. Resolution Resolution total number of pixels in image hi res takes up more space lo res means pixels become more obvious, pixelated Dynamic range Dynamic range how many colors / how many shades of gray

High dynamic range: more bits per pixel Low dynamic range: may obscure features B/W vs. color B/W: usually 1 byte per pixel Each pixel = grayscale number 0-255 Ex. 180 is a brighter shade of gray Color: usually 3 bytes (24 bits) per pixel Each pixel has 3 values, each 0-255 Ex. (200, 50, 128) = ? Most common scheme is RGB, where each pixel has a red #, green #, and blue #. RGB system Based on primary colors for light (red, green, blue) Examples

Black = (0, 0, 0) Purple = (75, 0, 100) White = (255, 255, 255) How about (x, x, x) or (0, 0, x) ? CS 111 Sept. 8 Finish image repn Adding binary numbers Integer repn in general Unsigned Signed Biased the most important of the 3 Commitment: Meet here tomorrow

Please read pp. 58-64 Quiz Friday RGB examples Color R G B Black 0 0

0 White 255 255 255 Red 255 0 0

Green 0 255 0 Blue 0 0 255 Cyan

0 255 255 Magenta 255 0 255 Yellow 255

255 0 Q: How do we get other shades of blue? Indexed color Do we really need 24 bits to represent color of one pixel? This means we allocate 16,777,216 colors! About 200 would be more practical Indexed color is a compressed RGB 6 values of each primary color, not 256 Use hex values 00, 33, 66, 99, cc, ff This is the color system used on the Web. 1 byte per pixel instead of 3

Use dithering to simulate in-between colors. Binary addition Analogous to decimal addition you know Only a few cases to consider just watch out for carry. 0 + 0 = 0 (no carry) 0 + 1 = 1 (no carry) 1 + 1 = 10 (sum = 0, carry = 1) 1 + 1 + 1 = 11 (sum = 1, carry = 1) Example, 6-bit addition: 001110 + 001100 Can check our answer in base 10 Overflow: correct answer is beyond possible range Integer repn How do we represent integers inside the computer? Scheme I: unsigned Scheme II: signed (a.k.a. Twos complement) Scheme III: biased (a.k.a. Excess notation)

Scheme I: Unsigned This is the scheme you already know. Cannot handle negative numbers. For n bits, possible range is 0 to 2n 1. Scheme II: Signed Basic idea: half of the representations should be negative. Ex. For 5 bits, 16 of the 32 values are negative, so the range goes from 16 to +15. For n bits, possible range is 2n1 to 2n1 1. Signed repn continued How do we represent a number in signed? If positive, same as unsigned. Ex. 6-bit signed repn of 13 is 001101. Ex. 6-bit signed repn of 31 is 011111.

(the largest #) If negative: 3 steps to represent x: 1. Find repn of +x. 2. Invert the bits. 3. Add 1. Try some examples of negative numbers, and check answers. CS 111 Sept. 9 Integer representation: be able to convert both ways (binary decimal) Unsigned Signed Biased Real numbers

Commitment: Please read sections 1.8 and 1.9 Quiz tomorrow Closer look In 5-bit unsigned Smallest number is 00000 (= 0) Largest number is 11111 (= 31) In 5-bit signed Smallest number is 10000 (= 16) Largest number is 01111 (= 15) Given a bit pattern, its signed and unsigned values differ by how much? Try some examples. In signed:

Leftmost bit is the sign bit. Positive #s have same repn as unsigned. Technique for x doesnt work for lowest number. Special case. Signed + and Signed + is like unsigned. Watch out for overflow. The correct mathematical result cant be represented. (Pos) + (Pos) = (Neg) (Neg) + (Neg) = (Pos) Example: 01111 + 00001. To subtract, add the opposite.

Example: 10111 00111 First, (00111) = 11001 Turn into addition problem: 10111 + 11001 = __________ Is there overflow? Scheme III: biased Another way to represent integers that allows for negatives. (It will soon help us see how real numbers are stored.) The bias is the number we subtract from unsigned range. If B is the bias, the lowest number is B. When working with a biased repn, you have to be given the bias. Ex. For 6-bits, bias is typically 31 or 32. Ex. For 8-bits, bias is typically 127 or 128. So, a 6 bit biased-31 repn is based on 6-bit unsigned, except that 000000 is now 31 instead of 0.

How to convert How do we represent a number n in biased (B)? 1. Add the bias: n + B. 2. Determine the unsigned repn of this number. Example: What is the 6-bit biased-31 repn of 9? Its the same as the unsigned repn of 9 + 31 = 22. 22 in 6 bit unsigned is 010110. How do we convert a biased number back into base 10? 1. Interpret the number as unsigned 2. Subtract the bias. Example: 101010 is the 6-bit biased-31 repn of what number? If unsigned, 101010 = 32+8+2 = 42. 42 31 = 11. Integer vs. Real Integer arithmetic on computer is quick & exact, but has

limited range. Real arithmetic needs wide range, and a reasonable degree of precision. Scientific / numerical computation 14 significant digits is usually enough! Skills: Converting a base-10 real number into binary Actual representation relies on scientific notation Examples Consider this sequence: 111 = 7 1110 = 14 11100 = 28 111000 = 56 1110000 = 112 Going the other way

111. = 7 11.1 = 3.5 or 7/2 1.11 = 1.75 or 7/4 .111 = 7/8 .0111 = 7/16 See the pattern? Each digit corresponds to (+ /) power of 2. Convert to binary Separate real number (e.g. 5.7) into integer and fractional parts Integer part use binary store. Fractional part: Keep multiplying fractional part by 2 until it becomes zero, or until you have a repeating pattern. Example: 9.625 Integer part 9 becomes 1001

Fractional part is 0.625: .625 * 2 = 1.25 .25 * 2 = 0.5 .5 * 2 = 1.0 Fractional part reaches 0. So our answer is 1001.101 Repeating pattern Let try converting 0.7 to binary: .7 * 2 = 1.4 .4 * 2 = 0.8 .8 * 2 = 1.6 .6 * 2 = 1.2 .2 * 2 = 0.4 .4 * 2 = 0.8 Aha! The pattern tells you which digits repeat. ____

Answer is 0.1 0110 0110 0110 or .10110 Real number repn Also called floating point Size is 32 or 64 bits: single vs. double precision Based on binary scientific notation Lets look at single precision: 1 bit for sign (0 = positive, 1 = negative) 8 bits for exponent (expressed in biased-127) 23 bits for mantissa Big mantissa precision is most important feature

Example We saw earlier that 9.625 = 1001.101 in binary. Lets continue with the true representation. Sign: 1 bit. Since its a positive number, we have 0 Exponent: 8 bits If we write 1001.101 in binary scientific notation, we get 1.001101 * 23. The exponent 3 is expressed in 8-bit biased-127. In other words 3+127=130 in unsigned: 10000010 Mantissa (23-bits): We only store the fractional part of the mantissa: 001101. Remaining bits are zero. Final answer: 0 10000010 (1) 001101 017 Decoding Lets see if we can decode a real number: 1 10000001 (1) 011 020 Sign: 1 means a negative number

Exponent: 10000001 looks like 129 in unsigned. But in biased-127 it is 129 127 = 2. So our number is something multiplied by 22. Mantissa: 1.011 in binary = 1 + 1/4 + 1/8 = 1.375 Combine all 3 parts: 1.375 * 22 = 5.5 Some thoughts In single precision 8 bit exponent 256 possible exponents Highest number ~ 1038 Lowest number ~ 1038 23 bit mantissa ~ 8 million exact real number per power of 2 We have about 7 significant digits Comparing with double precision What can we conclude? Precision

Sign Exponent Mantissa Single 1 8 23 Double 1

11 52 CS 111 Sept. 10 Quiz Data compression text images sounds Commitment: Please read rest of chapter 1. Department picnic next Wednesday Text compression Goal is for a document to take up less space Techniques

Keyword encoding: replace common words by special symbols like Run-length encoding: replace repetitions with a number: pppppppppppppp [14p] Huffman code: common letters should take up fewer bits Huffman code example Suppose you want to send a message, and you know the only letters you need are A, D, E, L, N, P, S. A Huffman code might look like this table: A D E L

N P S 001 100 01 101 0001 0000

11 How would you decode this message? 01110000101001000100110001 How to create code Were given the set of letters used for the message, and their frequencies. Ex. A = 5, B = 10, C = 20, D = 25, E = 30 Ex. P = 5, N = 10, D = 10, L = 15, A = 20, S = 20, E = 30 Its convenient to arrange the frequencies in order. Group the letters in pairs, always looking for the smallest sum of frequencies. The resulting structure is a tree. Each left arm = 0 in the code; each right arm is a 1. Dictionary & LZW

Dictionary encoding: Convert each word to a number Represent this number in binary If 50,000 words in dictionary, we can represent each with 16 bits (2 bytes) since 216 > 50,000 A lot shorter than the average word LZW Begin by encoding letters as 1-26, space as 27. Each time you form a new word, add it to the dictionary as 28, 29, 30, etc. So, we dont need to encode every word in English language. Ex. AB ABC AB ABC would be 1,2,27,1,2,3,28,29 Image compression RGB 24-bit color represented as (huge) bitmap file *.bmp Most of the time, compressing an image is lossy, meaning that uncompressing wont restore original .bmp

information GIF compression uses indexed color JPG entails several steps Make tiny modifications to the image, so that neighboring pixels will have more uniform values. For example, (10, 11, 12, 90) (11, 11, 11, 90) Use text/numerical compression techniques like run-length encoding. MPEG Motion Picture Experts Group Industry standard for compressing multimedia Note that much information in consecutive frames is the same Delete sound information that humans cant detect Goal: to make streaming video possible: 30 frames per second at a minimal DSL connection Ex. 5-minute 300x200 video ~ 12 MB

CS 111 Sept. 13 Error detection Error correction Review/practice chapter 1 questions Commitment: Please read sections 2.1 and 2.2 Transmission errors When you send data over a network, there could be rare random flipping of bits. Error Detection Error Correction One method of detection is using a parity bit

Add 9th bit to each byte during transmission Goal is that each byte has even # of 1s Receiver checks each byte. Catches many but not all errors. 2-d parity 1 0 1 1 0

1 1 1 0 0 0 0 1 1

1 0 1 0 1 1 0 1 0

1 0 1 1 0 0 0 1 1

1 0 0 1 1 0 1 0 1

0 0 1 0 1 1 0 0 1

0 1 1 1 0 1 0 1 0

0 1 1 0 1 0 0 1 0

1 1 0 0 1 1 0 0 0

1 0 0 0 The 9th byte is called a check byte. Error correction Useful if you think there may be a lot of potential errors, such as a noisy transmission medium. Devise a code so that each symbols bit pattern is quite distinct from all the others. In practice, this means longer codes. In other words, the 8-bit ASCII code would not be enough.

One technique: Hamming code Example code p. 71 Idea for assigning code is Hamming distance: comparing codes, count how many bits differ. When you receive an erroneous code, see which letter its closest to. Then you can make a correction. CS 111 Sept. 15 Chapter 2 Manipulating data by performing instructions What is going on in the CPU? Commitment: Please read through section 2.3 Meet here tomorrow. Basic anatomy Inside a computer are 2 parts

CPU Memory These are connected by a data bus: an HOV lane where traffic can go either way. CPU contains: ALU: arithmetic and logic unit Control unit: figures out what to do next Registers to hold values needed for calculation Memory (RAM) contains: Software: list of instructions the CPU needs to perform Data: Input and output values need to be stored while program runs Stored program idea Program = software = list of instructions for CPU to do Programs reside in memory CPU will do 1 instruction at a time

For each instruction, we do the following: Fetch it from memory Decode figure out what it means Execute do it And then we continue with the next instruction until the program is finished. Simple example A program to add two numbers. This program may reside at bytes 100-116 in RAM. The two numbers we wish to add are located at bytes 200 and 204 in RAM. We want the result to go into memory at byte 208.

Program may go something like this: Load the value at Memory[200] into register 1. Load the value at Memory[204] into register 2. Add registers 1 and 2, and put result in register 3. Store the value from register 3 into Memory[208]. Note that the bus is communicating instructions (RAM to CPU) as well as data (both ways). Machine language Unfortunately, instructions for CPU cant be in English, French, etc. Machine language = binary (or hex) representation of our

instructions. Each type of computer has its own machine language. This is the oldest form of computer programming. Later well look at much more intuitive ways to convey instructions. Verbs: Instruction set. e.g. Add, subtract, load, store Nouns: Operands such as: registers, memory locations, constants, other instructions Verbs 3 kinds of instructions (instruction set) Data transfer, using the bus Load a value from memory into a CPU register Very similar to fetching an instruction! Store a value from a CPU register into memory ALU Bit manipulation: AND, OR, XOR, NOT, shift left, shift right,

Arithmetic: add, sub, mul, div, remainder, =, <, >, , , , Control Go to another instruction in program. In other words, interrupt normal sequence of instructions. Can be conditional or unconditional Example language Our book illustrates with an example HW. 256 bytes of RAM: addressable by 8 bits CPU contains Instruction register Program counter 16 general purpose registers: addressable by 4 bits Each register is 1 byte Each instruction is 2 bytes = 16 bits = 4 hex digits long Instruction format:

First 4 bits are the opcode = specify which instruction type Other 12 bits are operand(s) What do instructions mean? See pp. 602-603. Example instructions Note: 16 possible opcodes: 4 bit opcode Note: 16 possible registers: register number also 4 bits Opcode 5 is used for adding Expects 3 register operands 5RST means R = S + T, where R, S and T are register numbers Ex. 5123 means Add registers 2 and 3 and put result in register 1. Opcode 2 is for putting a constant in a register Expects a register operand, and an 8-bit constant operand 2RXX means R = XX, where XX is some 8-bit pattern Ex. 27c9 means

Put the hexidecimal c9 into register 7. Try an example using both types of instructions. CS 111 Sept. 16 Machine language examples Dont memorize Instruction execution Closer look at operations in instruction set Commitment: Please read sections 2.5 and 2.6. Quiz next Wednesday. More instructions Opcode 1 is for loading a memory value into a register Expects a register operand (4 bits), and a memory address from which to

load (8 bits). Ex. 1820 means to go out to memory at address [20], grab the contents and load it into register 8. (It does not mean put the number 20 in register 8.) Opcode 3 is a store = opposite of load Ex. 3921 means to take the value in register 9, and put it into memory at location [21]. (It does not mean put the number 9 into memory location 21.) Opcode C (hex code for 12) is for telling CPU its done. Expects operand to be 12 zero-bits. Some practice Refer to appendix C How would we put the number 64 into memory at address 12? How would we add the numbers 6 and 8 and put the result in register 1?

How would we add register 7 to register 5 and put the answer in memory at address 32? More examples: p. 91 Execution In our example, each instruction is 2 bytes long. Program counter (PC) begins at address of first instruction. For each instruction: Fetch (and increment PC by 2) Decode Execute Examples pp. 98-99 Note that RAM contains both instructions and data, separated from each other. For example, addresses 099 could be reserved for code. Logic operations

Work just like gates, but we do several bits in parallel. Examples 10101110 01101011 AND 11110000 AND 00011111 Try the same examples with OR and XOR Observations: What happens when you AND with a 1? With a 0? What about ORing with a 1 versus a 0? What about XOR? Shift operations Given a bit pattern like 00011100, we can shift the bits left to obtain: 00111000. If we shift to the right instead, 00011100 becomes this:

00001110. We can even shift by more than one position. Shifting 01010000 by 3 bits right 00001010. Sometimes when we shift, 1s fall off the edge. Shifting 01010000 by 2 bits left 01000000. When we shift, the vacated bits are usually 0. Why shift? One application of a shift operation is to: Multiply by 2: left shift Divide by 2: right shift Try some examples should look familiar with our earlier work on binary numbers. One funny exception: dividing a (signed) negative number by 2.

In this case, we want the vacated bit to be 1 Example: 12 in signed is 11110100. If we shift right by 1, we get 01111010, but it should be this: 11111010. Rotate Rotate operations work the same as shift except that the vacated bits come from the other end of the number. So, instead of 1s falling off the edge, they rotate. For example, 01010000 rotated left by 2 becomes 01000001. Also: 00001111 rotated right by 3 becomes: 11100001. Examples pp. 103-104. CS 111 Sept. 17 2.5 Beyond the CPU and memory Peripheral devices

Communication speed 2.6 Making the CPU faster Commitment: Please read sections 3.1 and 3.2. Quiz next Wednesday. Devices & controllers device = some peripheral plugged into computer, usually for I/O controller = a circuit that allows a device to send data to/from CPU and memory. device driver = program that knows how to use the controller. 2-way communication memory mapped I/O = Program can access controller by referring to it with a memory address, as if its memory. Direct Memory Access (DMA) = allow controller to load/store to memory while CPU is doing other work.

USB: technology allowing one controller to handle a variety of devices. Your machine has several USB ports. Communication rate Used for both internal & network communication. Units baud = bit per second Kbps, Mbps, Gbps If theres overhead/noise, figure on an average of 10 bits per byte, so 1 Mbps = 100 KB per second. I can read a 20 MB file from USB drive in 2 seconds. What is the bit rate? Voice telephone line limited to 57.6 Kbps DSL, cable modem: broadband 50-100+ times faster Uses more of the sound spectrum; and data compression Improving the CPU

Pipelining Run the instruction like an assembly line. Partition the CPU: fetcher, decoder, executor Fetch instruction #2 at the same time it decodes #1; etc. Parallel or multi-processing MIMD = multiple instructions, multiple data Take a large task and give parts to different processors A central node collects final answer. SIMD = single instruction, multiple data Good for: Small program, but a huge amount of data. Each processor runs same program with small part of data. Pipelining or not Without pipelining F D

X 1 With pipelining F D X 1 1 1 2 2

2 3 3 3 2 1 3 2 1 4 3

2 5 4 3 6 5 4 7 6

5 7 6 7 CS 111 Sept. 20 Operating Systems definition origin responsibilities

relationship with other software Commitment: Please read pp. 131-137 Quiz on Wednesday. Original purpose Streamline process of doing jobs on the computer. Reduce overhead spent between jobs. Batch processing: Plan days jobs in advance Give jobs to a computer operator Job Control Language: enter commands to the OS Computer operator not practical Confidentiality Some applications like a game are inherently interactive; require fast turnaround

Utilization Historically CPU time used to be very expensive 2 ways to run jobs Interactively In batch mode. This is useful if jobs must complete by some deadline in a real-time system. Time sharing Many users, but just 1 expensive machine. Do not let any one job monopolize machine. Have several jobs running at same time; give each a turn at the CPU: multi-programming Today: 1 user has many jobs per day use same technique Kinds of software Application fun & useful stuff for people

Hearts, Excel, Firefox, e-mail, PPT, System utilities programs that make the computer more useful, added features Formatting a disk, compress data, play DVD OS shell accept commands from user; display error message OS kernel major responsibilities; manage resources Note: distinctions can be blurred the distinctions among the categories are not exact Responsibilities (1) Security Require many password combinations Penalties for mistake Super user & diagnostic tools to detect abnormal activity

CPU Be aware of all currently running programs Synchronization: make sure 2 executing programs dont interfere with each other Scheduling: deciding which program to execute now Memory Decide which files (or portions of files) should be in RAM Virtual memory: shuffle pages in and out of RAM to give illusion that RAM is bigger than it really is Responsibilities (2) Files Maintain folders Keep information about each file: name, size, owner, type, permissions User quotas

I/O and network Device drivers User interface (shell or GUI) CS 111 Sept. 22 Operating Systems Booting Processes Scheduling File permissions Commitment:

Please read section 3.5 Boot cycle When you turn machine on, OS is on disk. CPU must begin running pre-arranged code in nonvolatile ROM. The ROM program tells the CPU to load OS from disk to RAM. As well as BIOS: basic I/O system Finally, begin running the OS. ROM designed to be fast/efficient, therefore small. The entire OS cannot fit in ROM. Process A program that has started, but hasnt yet completed. Pending work. OS must keep track of all current work, in case of interruption or hibernation.

Possible states for a process Ready (could execute, but doesnt have CPU) Running (in CPU) Waiting (doing I/O operation) During its lifetime, a process may experience many state transitions. CS 111 Sept. 24 Operating Systems Scheduling File permissions Commitment: Please read section 4.1 Scheduling OS may need to decide the order in which to do jobs

Many ways to create a schedule. Well look at 2. First-come, first-served Do the jobs in the order in which they are requested Shortest Job Next Give priority to short/easy tasks. Evaluating schedules People are interested in how long for their requested jobs to complete. Compute the average turnaround time. Turnaround time of a job = (time @ finish time @ request) Example 1 Process number Time of request

Execution time needed 1 0 20 2 5 30 3 10

40 4 20 10 First-come, first-served Process 1 can execute from t=0 to t=20 Process 2 can execute from t=20 to t=50 Process 3 can execute from t=50 to t=90 Process 4 can execute from t=90 to t=100

We can enter this info as extra columns in the table. What is the average turnaround time? What if we tried Shortest Job Next? Example 2 Process number Time of request Execution time needed 1 0 10

2 30 30 3 40 20 4 50 5

Note that its possible to have idle time. System load A measure of how busy the CPU is At an instant: how many tasks are currently running or ready. If load > 1, the system is overloaded, and work is backing up. Typically reported as an average of the last 1, 5, or 15 minutes. Based on the schedule, can calculate average load as well as maximum load. File permissions 3 levels: owner, group, rest of world For each level: r = Can I read the file? w = Can I write to (or delete) the file?

x = Can I execute the file? Examples rw-rw-r- rwxr-xr- rw-r----- (664) (754) (640) Common permissions On many systems, there are no groups, so the group permission is the same as everybody else. Examples 644 600 755 700 Only a file/folders owner or the administrator may change

permissions. CS 111 Sept. 27 Ch. 4 Networking Topology of network Protocols How networks get used Internet applications WWW and HTML security

Commitment: Please read sections 4.2 and 4.3 Communication Claude Shannons model Source and destination of message Sender and receiver programs Transmission medium + noise Sender Must encode info in binary Encrypt if desired Package as required (parity bit, split into packets, etc.) Receiver Undo Senders tasks in reverse order Topology

Shape of network, usually in reference to a LAN Point-to-point Star Token ring Bus: Ethernet Protocols Protocol = established rules on how to communicate; etiquette on what to expect Ethernet protocol

Wait until bus empty before sending a message Each message is broadcast so all can hear Machines listen to see if message is for them Detect collision TCP/IP Detect hidden terminal in wireless network Require all machines to periodically check in with hub Long distance communication Repeater: amplify message in the bus Bridge: connect 2 networks Filter message only allow message across if destination is on the other network Switch: like a bridge, but a hub that connects several networks

(LANs) Router: Special purpose computer that forwards messages according to destination address Internet & internet Connected networks can be quite heterogeneous CS 111 Sept. 29 Ch. 4 Networking, continued Internet architecture Internet applications WWW Commitment: Review notes Internet 1960s: the need for a computer utility Military, academic, commercial uses in its history

Network of networks, connected by routers Maintained by ISPs worldwide Major ISPs are usually national telecoms Local ISPs may offer special service, as in a resort You access Internet by connecting to a host machine owned by your ISP Addresses 2 ways to express URL (Internet address): IP numbers Of the form a.b.c.d where each number ranges 0-255 Ask your ISP for a batch of consecutive IP numbers for your company. Ex. All Furman IP addresses begin 156.143

Difficult to remember Domain names Dotted notation, but words/letters instead of numbers Top level domains regulated by national non-profit company, whose monopoly is enforced by law. ICANN is the arbiter for IP #s and domains for the USA Name server can convert between address types Applications Examples: E-mail, gopher, Web, FTP Usually connect with specific server that specializes in that application

Server needs to have software that obeys relevant protocol. Ex. Mail server needs to adhere to mail protocols, etc. Ex. Web server needs to respond to requests for Web pages Ex. FTP server should allow users to perform upload/download and directory access Alternatively, you can log in to a remote machine Made possible with client programs Telnet or Putty Putty implements a secure shell: encrypts communication WWW 24 years younger than the Internet as a whole World Wide Web = set of linked documents hosted on specific machines called Web servers connected to the Internet Each document has a URL (based on domain names) Web terminology:

Web server Web page Web site Web browser Anatomy of a URL CS 111 Oct. 4 Web design HTML Javascript Commitment:

This week, read sections 4.3 4.5. HTML Stands for: HyperText Markup Language Hypertext means a text document that contains links to other documents Also may contain multimedia. HTML is interpreted by a browser .html file contains content as well as formatting and layout commands Dreamweaver can hide these details from you HTML (2) File format

Head section is optional Body contains material to appear in browser window. What does simplest Web page look like? Common tags h1, h2, etc. = headings br = line break p = paragraph b, i = font should be bold or italic hr = horizontal rule

ol,ul, li = used for lists sub, sup = subscript or superscript text to underline Javascript Can write simple programs with little or no prior experience Purpose of JS is to give some interactive life to Web pages. Works with a Web browser. First, create HTML file using editor or Dreamweaver. Refresh the browser when you make a change. Online guide for general reference http://www.w3schools.com/js/js_examples.asp Were only going to scratch the surface

Simple JS features Printing a message Using variables Looking up the time Making choices Doing something several times (a loop) A form inside HTML Can create form object in Dreamweaver. In Javascript, write instructions on how to handle the input.

CS 111 Oct. 6 Javascript practice See handouts. To get ready for lab. Commitment: This week, read sections 4.3 4.5. Quiz next Wednesday. Examples js1.html: I/O, variables,

making choices Lets fix mistake with printing time. js3.html: I/O, arithmetic, counting/repetition form1.html: form object text boxes text area

function to inspect forms input & perform action form2.html: Function counts number of correct answers Forms input Youll see an expression like this: document.survey.second.value We identify a forms value with these 4 parts: document = What Javascript calls the entire page itself survey = name of the form (where is this in the HTML?)

second = name of text field in the form value = contents of what user typed CS 111 Oct. 8 Internet topics HTML & XML Client / server Internet layers Commitment: Read section 4.5. Quiz next Wednesday. Markup languages HTML specifies format of Web page through <> and commands. Commands convey a list of things, or are nested inside other commands.

Can be generalized to all other documents conveying information. XML: a general markup language that can be used for defining the format of any document One way of representing a database Example: KML is used to define geographic regions for Google Earth. XML example Mercury 88 Mars 687

Phobos 1 Deimos 2 Neptune 60190 // Specify 8 moons here // Specify more planets here Client & server

You want to perform a business transaction with a company via the Web. Internet software usually has 2 parts: Client program: Interactive Web site contains just enough code to get data from the user, and transmit it to the companys server. Server program: Process each clients information. Why the separation? User (client) should not have to download entire program just to buy something. User should not log into companys computer. Server has access to huge amount of proprietary and confidential information. Many clients may want to do business at the same time. Layers of communication Human layer Application layer: client/server relationship, e.g. between your browser & host site.

Transport layer: Your system breaks up messages into packets. Choose desired Internet protocol (TCP or UDP). Recipient assembles message. Network layer: Routers decide best direction to forward packets. Link layer: Managing the traffic, the legwork of moving packets. * Each layer communicates with neighboring ones. CS 111 Oct. 11 Internet topics Network applications and technology for business Security Commitment: Quiz Wednesday. Homework #1 due Oct. 18: Discuss your favorite infamous example of a computer crime. Why is it significant, and

could it happen again? Network applications Both client and server software necessary Many are same as personal applications E-mail Voice mail But others are services that people expect from some establishment Videoconferencing Bulletin board (i.e. forum) Electronic funds transfer, and credit card transactions ! Network architecture Within a company, may be centralized or distributed Need backups of software as well as data E.g. NASDAQ during 9/11

Use a WAN to connect major operators (e.g. stores in a chain) Network operating system Distinct from each machines OS Handle system logins and traffic in WAN Download speed Overhead time prepare and assemble message Flight time first bit to arrive at destination Bandwidth max rate to propagate data (Cruising speed). Divide size by rate. Total time = overhead + flight time + (msg size / bandwidth) Unless message is tiny, bandwidth is crucial issue. Rules of thumb for home users: Dial up: 10 MB per hour DSL: 10 MB per minute

Internet backbone Telecoms maintain traditional phone lines as well as fiber optic cables. T-carriers range from T-1 (1.5 Mbps) to T-4 (274 Mbps) Your business can subscribe to dedicated continuous Internet connection. Ex. Furman subscribes to 200+ Mbps level of service. Fiber optic: OC-1 (51 Mbps) to OC-192 (10 Gbps) Fiber optic generally limited to urban areas Security Areas include security of the

Physical site (traditional notion of security) IT resources such as printer, files Network ability to communicate Service whatever the firm deals with Results of breaches: Destruction of resources, information, service Corruption of data Denial of service Theft Fraud, e.g. cheating the company or defrauding the public

Security issues Viruses, Trojan horses, etc. Firewall for firms network Distinguish between intranet and Internet Firewall is any system that specifies what traffic to allow in either direction Maintain backups of everything Note: Accidents happen. Power goes out, people delete files Audit Internet traffic to/from site looking for anomaly Encryption: Make transmissions secure https and .shtml CS 111 Oct. 13 With a network, you can make $: E-commerce

Commitment: Homework #1 due Oct. 18: Discuss your favorite infamous example of a computer crime. Why is it significant, and could it happen again? E-commerce Means the browsing, buying, and selling of goods and services using public or private computer networks. Two types of commerce: Business to consumer Web site used as the showroom. Some businesses exist only online. (amazon) Some sites are portals that tell you where to buy. Examples: Kayak and salescircular. The travel-agent model. Business to business (the client is another business) Benefits and challenges of e-commerce? What are some goods/services that are easy vs. hard to sell

online? Desired functions Advertise elsewhere, draw people in On Web site: provide product information Shopping cart Back-office processing Update inventory Process payment (credit card) Send goods to consumer, provide return mechanism This is on top of other ordinary business functions, such as payroll, taxes, insurance, etc. Behind the scenes Commerce usually involves the following players:

Supplier of raw materials Manufacturer Distributer Retail outlet Consumer Between each, there can be an e-commerce relationship. Besides business-to-customer, we have business-tobusiness or B2B for short. Gives rise to a supply chain Supply chain Need to manage flow of materials and $ between your suppliers (upstream) and your customers (downstream). You dont want to be sold out of an item.

The business has its own bills to pay. Example goals where IT can help: Keep inventory low, but not zero. (Detect when getting low.) Cut cost of keeping inventory. Reduce replenishment times. Reduce transportation costs! Perhaps outsource activities that do not add value to the company ($ or reputation). Anticipate change, look at trends. (school supplies, Christmas) CS 111 Oct. 18

Discuss computer crimes Ex. Cliff Stolls Cuckoos Egg or the video The KGB, The Computer and Me. Commitment: Please read sections 5.1 and 5.2 CS 111 Oct. 20 Most essential skill in IT: problem solving using the computer Telling the machine exactly what we want it to do. Also: making sure result of software is packaged in a way that ordinary people will understand. Problem solving procedure What does a solution look like? Learn by example, and generalize. Commitment: Please read carefully sections 5.1 and 5.2

Why software? Want computational power To have direct control of machine Sometimes, existing software is not sufficient, doesnt give what you want Programs can be useful or fun for people to use (e.g. game, converting data to image, ) Need to use a computer language E.g. Javascript, PHP, Python, C++, etc. Machine independent Many common calculations are pre-defined, such as sorting, opening files, surfing the Web, creating a form button, etc. Program One specimen of software is called a computer program Small or large, purpose is to solve 1 problem.

Works like a recipe List of necessary ingredients List of instructions for CPU to obey. A simple program normally has 3 phases. Input Calculations Output Recipes Cooking may be a good analogy, because it solves the problem Im hungry What do we see in recipes? Heres one:

Brown the beef 15 min. Drain grease. Dice carrot, celery, onion (aka mirepoix) Cut up and boil 6 potatoes until soft. Mash potatoes Add flour, spices, sauce, mirepoix to beef. Put meat mixture into casserole; top with potatoes. Bake in oven at 400 for 30 minutes. Recipes (2) A computer program has some of the same elements as a recipe. In recipes, we see: Ingredients (the nouns of the problem) Steps to perform (the verbs) In some steps, we continue/wait for something

Sometimes we check things Are potatoes fully mashed? Should I add more _____ to the mixture? Recipes inside recipes But we dont eat the same stuff every day. Once we know a few recipes, we can put together a menu for choices. if if if if (have all ingredients), make Shepherds pie. (no potatoes), just make soup instead. (no veggies), make hamburger. (no beef), make pasta. When you view a whole menu as a program, then making

soup becomes a sub-program. A large program is composed of several parts. In industry, sometimes each part is implemented by different people, like a kitchen having many chefs. Problem-solving 1. Understand problem; inputs and outputs 2. Write solution in English pseudo-code 3. Write code in a programming language 4. Compile 5. Run and test When program works, can refine or generalize. CS 111 Oct. 25

What is a program? Problem solving procedure Step #2 is most important: write solution (algorithm) in English Structure of solution: Sequence of steps (1, 2, 3, ) Sometimes make a choice Sometimes need to repeat Examples Commitment: Please read section 5.3 Problems The earliest problems given to a computer were

mathematical. Sometimes there is no clean formula Many equations cant be solved analytically. For example: try cos(x) = x. Need to solve numerically. Ex. Heat equation is a partial differential equation (PDE). Most PDEs have to be solved numerically. Ex. Calculating a square root. Even if there is a clean formula, a computer can help automate the calculations. Problems (2) What kinds of problems do we solve? Finding directions Predicting trends (weather, finance) Games Record keeping in a business Networking and communication

Multimedia (e.g. image processing, animation and graphics) Compressing and encrypting data Searching for something (spell check) Algorithm A clear sequence of steps to arrive at a solution to a problem. Must specify: Ingredients Input, output, variables and operations used The order in which steps are taken Means that anybody should be able to follow your directions. There is

no ambiguity. Ideally, each step should perform 1 calculation: Input or output of 1 value 1 calculation, or 1 decision to make Calculations usually limited to basic math In your algorithm, tedious details can be put off until later. Explain big picture first. Examples Discuss in general how you would solve these problems:

Print the numbers from 1 to 100. In this list (3, 2, 7, 5, 4) where is the number 5? Which room contains my umbrella? Have 2 people play Tic-Tac-Toe. Lets practice fully with these problems: Ask the user to enter 2 numbers, and output their sum. Determine a persons weekly wage, given the number of hours worked and hourly rate. Dont forget to figure in overtime. Add the numbers from 1 to 5. Solutions Algorithm to add 2 numbers

Ask the user to enter 2 values. Obtain the input, and call the values a and b. Set a new variable sum and set it to: sum = a + b. Output sum. Weekly wage Get hours and rate from the user. Set the wage as follows: If (hours > 40), use overtime formula Otherwise, use regular formula Output wage Solutions (2) Add up the numbers from 1 to 5 No input!

Need 2 variables: sum and count The count variable will go from 1 to 5, one at a time. The sum will start at 0, and we continually add to the sum. Sum = 0 Count = 1 For each value of count from 1 to 5: Sum = sum + count Output sum If we can add 1-5, we can just as easily add 1-1000! Mystery What does this algorithm do? No input. Create two variables: sum and count. Sum = 0 Count = 1 For each value of count from 1 to 20:

Introduce new variable called temp Temp = count * count Sum = sum + temp Output sum CS 111 Oct. 27 Practice problems See handout Work in pairs to devise solution to 1 problem Well discuss results Commitment: Prepare more solutions to practice problems CS 111 Oct. 29 Continue working practice problems Commitment: Consider these problems

How would you find the largest/smallest number in a list? How would you count the number of values that are positive? Counting vowels in a word. CS 111 Nov. 1 Consider these problems Review searching Finding largest/smallest Counting things in a list More practice problems Commitment Read pp. 228-231 (insertion sort) Read #6 and #7 on pp. 232-233 (other ways to sort) Review sections 5.1 5.4 Search error

What is wrong with this technique for searching for the value 3 in a list? list = { 8, 5, 2, 8, 3, 6, 1, 9, 4 } for count = 0 to 8 if list[count] is 3 found = true else found = false How should we fix the mistake? Largest / smallest How would you find the largest number in a list? Assume first number is the largest. For each of the other values, ask if it is larger than what we think the largest value is. If so, update the largest value. Also keep track of the location of the largest value, in

case that is also desired. Finding the smallest number is analogous What should we change? Pseudocode list = { 5, 7, 4, 2, 3, 8, 1 } largest = list[0] location = 0 for count = 1 to 6 if list[count] > largest largest = list[count] location = count Output the largest and location in a sentence, e.g. I found the value 8 at position 5. Counting To determine how many values in a list are positive

First, need a separate variable, numPositive, initialized to zero. Ask each number if its positive. If so, add 1 to numPositive. No else clause is needed. list = { -6, 0, 8, 4, 1, -2 } numPositive = 0 for count = 0 to 5 if list[count] > 0 ++numPositive Output the value numPositive in a sentence. Vowels A word can be thought of as a list/array of characters. Need a numVowels variables, initialized to zero. For each character in the word, see if its a vowel (a, e, i, o or u). If so, add 1 to numVowels. word = "serendipity length = strlen(word)

numVowels = 0 for count = 0 to length-1 c = word[count] if c is a,e,i,o or u ++numVowels Output numVowels in a sentence. Programming note In PHP and other languages, if you need to ask several questions inside in if-condition, you need to separate each one with and/or as appropriate. Each individual condition must be a complete question. Illegal: if (c == a or e or i or o or u) if (x > 10 and < 20) Legal: if (c == a or c == e or c == i or c == o or c == u) if (x > 10 and x < 20)

Practice problems Given a list of numbers, how many are multiples of 5? Given a year, is it a leap year or not? Given a number, is it a prime number? Remaining practice problems from handout. CS 111 Nov. 3 Finish practice problems: designing solutions in English Various ways of sorting Commitment Please read section 6.1 Examples Given a year, is it a leap year or not?

Julian definition Gregorian definition Given a number, is it a prime number? Remaining practice problems from handout. Double letter (repeated value in a list) Triangles Sorting Much studied problem in computing many ways to do it. Given a list, need to arrange it in order. Either ascending or descending. Some methods do better based on type of data or how the values are distributed. Enjoy this Web site demo of sorting methods: http://cg.scs.carleton.ca/~morin/misc/sortalg

Some Methods Selection sort: Find the largest value and swap it into first, find 2nd largest value and put it 2nd, etc. Bubble sort: Scan the list and see which consecutive values are out of order and swap them. Insertion sort: Place the next element in the correct place by shifting other ones over to make room. Merge sort: Split list in half until just 1-2 elements. Merge adjacent lists by collating them. CS 111 Nov. 5 Sorting Selection and Bubble insertion: place next element in correct place by shifting over other ones to make space Merge: Repeatedly split list in half until 1-2 elements each. Then merge adjacent lists by collating them.

Computer languages 3 kinds of software errors Commitment For next week, please read sections 6.2 (review); 9.1, 9.2 Language evolution Machine language Assembly language Like machine language, also unique to each manufacturer High-level language FORTRAN, COBOL

Pascal, Algol, Ada C, C++, C# Java, Javascript, Python many more Example How would we calculate: 12 + 22 + 32 + + 202 ? Lets create our own solution, and see what the code looks like in different types of languages: Machine language Assembly language High-level language Machine language 00003000: 00004000: 00004004:

00004008: 0000400c: 00004010: 00004014: 00004018: 0000401c: 00004020: 00004024: 00000014 200c0001 20080000 3c0a0000 354a3000 8d4a0000 018a4822 1d200005 018c0018

00005812 010b4020 00004028: 0000402c: 00004030: 00004034: 218c0001 08001005 2008000a 0000000c help me! Assembly language

numValue: .word 20 __start: addi $12, $0, 1 addi $8, $0, 0 lui $10, 0 ori $10, $10, 0x3000 lw $10, 0($10) while: sub $9, $12, $10 bgtz $3, end mult $12, $12 mflo $11 add $8, $8, $11 addi $12, $12, 1 j while end: addi $8, $0, 10

syscall HLL (Pascal) var sum : integer; count : integer; begin sum := 0; for count := 1 to 20 do sum := sum + count * count; writeln(sum); end. Bugs Any mistake made in a computer program Term bug coined by Grace Hopper, ca. 1950 3 kinds of bugs Syntax errors

Run-time errors Logical errors Beyond bugs, program can be just slow! Ex. Ineffective ways of finding the divisors of some number. CS 111 Nov. 8 Databases Database Management Systems (DBMS) Structured Query Language (SQL) Commitment Please review sections 9.1 9.2. Database A file containing 1+ tables Table = 2-d arrangement of data into rows and columns Rows correspond to records info about 1 customer, 1 student, 1 animal, 1 house, whatever

Columns correspond to fields individual attributes about each record. For example, name, address, phone number, ID number, $ amount DBMS Data Base Management System Software that allows us to manipulate a database file. Most often, we want to query the database. Examples:

Microsoft Access Open Office Base phpMyAdmin Oracle Datatel SQL = Structured Query Language All DBMS support SQL We use SQL to communicate with the database. SQL Structured Query Language DBMS accepts commands written in this language, so we can manipulate the database file. DBMS may actually have point-&-click shortcut features to save time on tedious tasks, such as entering all the data, or

creating tables from scratch. Most common SQL command is the select statement, which asks the DBMS to return some of the data in the database. Examples: Show me everybodys address How many employees make over $100,000 ? How to begin Create the database file Create first table: specify its format For each field (column), it needs a name, data type and maximum length. Common data types are: Int/number Date Varchar (variable-length character string). Here you must specify a maximum length, such as 20 characters. Sometimes, you may want to indicate whether a field is required, must

have unique values, etc. Enter data into the table. Make queries about the table. Example An Employee table: First Last Location Title Salary Peter

Jacobs Brussels Broker 55000 Denise Lambert Brussels Accountant 42500

Robert Nijs Brussels Broker 66700 Ruth Molloy Chicago Manager

68650 Declan Murphy Chicago Accountant 84125 Susan Patterson Chicago

Economist 51000 Rachel Brady Cincinnati Broker 43300 David Cunningham

Cincinnati Accountant 48000 John Whelan Cincinnati Broker 60500 Yvonne

Butler San Diego Broker 48500 Veronica Keating San Diego Broker 72000

Mary Walsh Dublin Accountant 46850 The select statement Very commonly used in SQL. Some possible formats: select columns from table;

select * from table; select columns from table where condition; Examples: select First, Last from Employee; select Last, Location, Salary from Employee; select Last, Salary from Employee where Salary >= 70000; select * from Employee where Location = Dublin; select * from Employee where Last like M%; Aggregate functions In SQL, we can ask questions that involve arithmetic, such as finding the max, min, avg of numerical values. select max(Salary) from Employee; select min(Salary), max(Salary) from Employee; select avg(Salary) from Employee where Location = Chicago; select avg(Salary) from Employee

where Title = Broker; CS 111 Nov. 10 Structured Query Language (SQL) Weve already seen simple select statements, with optional where clause and aggregate functions. More example commands today Relational database Commitment Review for test after lab Log in As you will see in lab, you first need to log in to the database management system in order to see your database. From a Web browser, go to cs.furman.edu/phpMyAdmin/

Enter your database username & password (Demo) If your SQL commands are incorrect, youll get error message. Example An abridged Employee table: First Last Location Title Salary Peter

Jacobs Brussels Broker 55000 Denise Lambert Brussels Accountant 42500

Robert Nijs Brussels Broker 66700 Ruth Molloy Chicago Manager

68650 Declan Murphy Chicago Accountant 84125 Susan Patterson Chicago

Economist 51000 Rachel Brady Cincinnati Broker 43300 David Cunningham

Cincinnati Accountant 48000 John Whelan Cincinnati Broker 60500 Yvonne

Butler San Diego Broker 48500 Veronica Keating San Diego Broker 72000

Mary Walsh Dublin Accountant 46850 Distinct Sometimes in SQL you have a lot of repeated data. And you only want the values themselves, not the repetitions. Ex. 70, 70, 70, 80, 80, 80, 80, 80, 100 70, 80, 100 Examples select Test2 from Student;

gives all test grades select distinct Test2 from Student; only shows each value once select distinct Test1, Test2 from Student; finds distinct pairs. 70/60, 70/80, and 90/80 are distinct. considered Group by The group by clause is good at finding subtotals. Example: how many employees by job title: Select count(first) from Employee group by Title; Actually, doesnt matter which field we count. To make output easier to understand, we should also print out the job titles: Select Title, count(Salary), avg(Salary) from Employee

group by title; We can even subtotal by 2 fields: What would this command mean? Select Location, Title, count(Salary) from Employee group by Location, Title; Order by This clause is used for sorting. Default order is ascending. select * from Employee order by Last; select * from Employee order by Location, Last; select * from Employee where Salary > 50000 order by Location, Title; More on where Boolean conditions: when you use the where clause can include the word and or or to make complex

conditions. Ex. What if we wanted salaries of employees with names starting with M or P. Use in when you want to select among several possible values. Has the same effect as or Select * from Employee where Location in (Dublin, Chicago); Use between for an (inclusive) range of values to check Select * from Employee where Salary between 60000 and 70000; Relational Database Databases with just 1 table are not very powerful. More interesting if 2 tables are related. Books and publishers Customers and orders Pets and owners

Typically we have a one-to-many relationship The two tables need to have a field in common. You can see this if you try to list the necessary fields in the above examples. In SQL, to refer to a field within some table, we use the dot notation: Customer.First, Pet.Name, Order.ID CS 111 Nov. 15 Relational database Detecting the 1-many relationship Primary key Commitment Please read section 9.2 Overview An entity is something that you want to maintain

information about. A university needs to keep track of students, employees, courses, classrooms, housing accounts, athletic teams, special events, etc. We create a table to store entities of the same type. Each entity becomes a record (row) in a specific table. Each entity has attributes details about itself. Vary widely depending on the type Columns of table. A database usually comprises related tables. Goals Integrating information from > 1 table Reduce redundancy In other words, having unnecessary fields in a table. Redundancy leads to errors and waste

Ex. Consider what info is necessary in a table listing all course enrollments by all students. Maintain integrity Secure and reliable information Allow for change Inserting, deleting information even creating new tables when needed Relational Database Real databases have 2+ related tables. Books and publishers Customers and orders Pets and owners One-to-many relationship The two tables need to have a field in common. You can see this if you try to list the necessary fields in the above

examples. Primary key A field that is unique for each record. This is usually the field used in defining a relationship. Query In SQL, to refer to a field within some table, we use the dot notation: Customer.First, Pet.Name, Order.ID Dot notation also avoids ambiguity Two different tables may coincidentally have same field name. In general, select queries are long enough that we should write them out on 3-4 lines, not 1 long line: Example select Customer.First, Customer.Last, Pet.name from Customer, Pet where Customer.CID = Pet.CID;

We enforce relationship by matching ID #s. CS 111 Nov. 17 Enterprise databases Goals Examples Many-to-many relationship Restricting ones view of entire database Design considerations Concurrency Commitment Homework #2 due Nov. 29 Goals

Retain and please customers Attention to detail Share data across company Allow employees to view the portion of the database relevant to them Quick response to employee or customer query Customers can interact with database via Web site Also: allow concurrent access Distributed database Client capability at point of sale Server capability at HQ Dont keep all data in one place: allow for physical partition or replication Examples

Luxury hotel Goal: Personalized attention to detail Store customer preferences for repeat visits When cleaning room, take note of pillows used, newspapers, drink bottles and snack wrappers discarded Log requests, compliments, complaints On next visit, provide complimentary item as token of recognition Garage Take note of odometer reading Do they only come in for oil change? Give birthday discount on other service Not 1 database A large company probably needs more than 1 database, each with its own purpose

Inventory control (materials, parts, finished goods) Sales (customers and orders) Manufacturing (production schedule, which factory) Accounting (corporate taxes, dividends, payroll) Within a database, could have several tables: Example: Customer, Orders, Order Details, Product Many-to-many relationship CS 111 Nov. 19 Enterprise databases, continued Review tables, joins, queries Restricting ones view of entire database Design considerations Concurrency

Beyond the database Other systems you might see in business. Commitment Please read sections 7.1 7.3 Homework #2 due Nov. 29 Views view = subset of a database Details not relevant to you are hidden When you access a database, it is for a particular function (data entry, lookup). Each function has its own view. Some information is confidential Ex. Customer order history Contact info not needed Ex. Item order history Customer info, quantity of item on hand not needed

This is why many queries are not select * Database design factors Storage cost, Also the need for backups (reliability) Processing cost: Do we have a powerful enough server? Are database operations implemented efficiently? Communication cost: Bandwidth and ISP server cost Retrieval and processing: confirmation response time Making all information available to everyone in company may be impractical. Find out what info people need most often Frequency of updates and queries How often the store should send records to HQ

Concurrency Allowing several people to access database at same time Example: Suppose theres 1 seat left on tomorrows flight 17. Customers A and B simultaneously query availability for that flight. A buys a ticket. Bs screen still shows 1 seat available. B also buys a ticket. Problem is that the purchase is not instantaneous (especially major purchase) 2 transactions can overlap. Possible solution: record locking

Each seat on flight is a record in some table. B cannot purchase seat, because A has already begun process of selecting and buying ticket. Beyond database We need data in IT (e.g. kept in a database), but that is not enough! Transaction processing systems Add record to order table Support queries and summary reports Automatic reporting of suspicious transactions (mistake, fraud?) Management info systems Provide information to make decisions: How much merchandise to order? How many people to hire? Cheapest way to do ___ These problems require general problem solving skill

Other similar support systems also exist for specialized purposes. Big IT tasks To make IT work, people are more important than HW or SW. Here are some examples. Database administrators Deal with database design, performance, security Systems analysts Analyze large problems (e.g. some IT service for company) Estimate time & personnel needed to get jobs done design large applications; may write mock-up prototype

draw up precise I/O and performance specifications Project managers Deal with day-to-day responsibilities Maintain implementation schedule, with deliverables Software engineers Sample IT questions Feel free to paraphrase Plus: Answers to one question may prompt you to ask a follow-up question.

What does IT encompass at your company? What % of your employees are mostly involved in IT? What sort of tasks need to get done? Do you have systems analysts at your company? What do they do? What other IT occupations do you have? What skills (technical & nontechnical) or traits are needed for people who work in IT? Specific knowledge and conceptual understanding What is a typical career path for someone in IT? What is most rewarding aspect of working in IT? Most challenging? CS 111 Nov. 22 Chapter 7 Software engineering Systems analysis Commitment

Please read Section 7.4 (only pp. 336-341), Sections 7.6-7.9 Homework #2 due Nov. 29 Software engineering Large software systems cannot be written by 1 person Several people work together Each is responsible for portion of program These portions interact so must make sure your piece will fit correctly in jigsaw puzzle Example: developing user interface for registration system: Your output (list of desired course sections) must be in format expected by next phase of program Deadlines Tips for success General guidelines

Dont reinvent the wheel Make your solution efficient, elegant, easy to understand Build solution incrementally, test & document often Its easier to fix a bug the sooner its found! Work in pairs, check each others work Integrated development environment (IDE) Software that simplifies job of writing code As you type, code becomes color coded

Automates compiling and testing Built-in debugger: can trace through instructions one by one, inspecting values of variables: rather than modifying code by inserting print statements! Software life cycle Very similar to problem solving procedure 1. Problem specification written 2. Design of solution 3. Implementation 4. Testing 5. Maintenance Systems analysis Distinction Software engineering is mainly concerned with implementation of the project Systems analysis is mainly concerned with specification and

design Definition of systems analysis (Whitten & Bentley): A systems analyst facilitates the study of the problems and needs of a business to determine how the business system and IT can best solve the problems and accomplish improvements for the business. The finished product is eventually a new or improved computer application, implemented by software engineers. Principles Get the owners and users involved The program youre designing doesnt belong to you. Its to help other people. Find out what they desire. Follow problem solving procedure Define what a suitable solution must accomplish / do. Evaluate possible algorithms, and choose the best

After testing, evaluate new systems impact, get feedback from stakeholders. Establish a schedule for the software life cycle How much time do you have How many people can you have on your team & for how long? What are their strengths and weaknesses? Principles (2) Establish coding and documentation standards Your software engineers are writing code for you. Almost like they are students in your class. Essential to have code written in a consistent style Encourage good documentation communication, including list of known problems. Let your people know they wont be penalized for admitting their work is incomplete. You dont want these to be a secret, or else risk future debugging. Give people a list of deadlines of deliverables.

Have your team members meet with you to discuss their accomplishments. Is the project work cost-effective? May need to scale down, trim some functionality or put off to later version. Principles (3) Beware the mythical man-month Doubling your staff will not make project take half the time. IBM found this out the hard way in its System/360 project. Diminishing returns Dont be afraid to scale down or cancel project Project should have milestones / checkpoints to evaluate path toward success Decide how to get back on track, or reduce scope of project. Can final deadline be extended?

If doomed, abort project and cut losses. But, will your superiors understand? Principles (4) Divide and conquer A large project can be overwhelming at first. Break into small, manageable parts. Reminds me of studying for a final exam, or writing large essay. Top-down design and bottom-up implementation. Design for future growth and change Your project may be in service for 10+ years People who adopt and like your work may want to continue using it forever. You will have to live with decisions you make today. (For example, choice of programming language) CS 111 Nov. 29

Today: findings from your interviews Starting Wednesday: how to think like a systems analyst Finish basic principles Examples of possible problems and opportunities Problem solving approach from systems analysis point of view Commitment Please read Sections 7.6-7.9 CS 111 Dec. 1 How to think like a systems analyst Finish basic principles Examples of possible problems and opportunities Refer to handout. Problem solving approach from systems analysis point of view Commitment Please read Sections 7.6-7.9 if you have not done so already.

Principles The guiding principles of systems analysis Ones weve seen already: Get the owners and users involved Follow problem solving procedure (well elaborate later) Establish a schedule for the software life cycle Establish coding and documentation standards Is the project cost effective? Beware the mythical man-month

Remaining ones: Dont be afraid to scale down or cancel project Divide and conquer Design for future growth and change Principles (3) Beware the mythical man-month Doubling your staff will not make project take half the time. IBM found this out the hard way in its System/360 project. Diminishing returns Dont be afraid to scale down or cancel project Project should have milestones / checkpoints to evaluate path toward success Decide how to get back on track, or reduce scope of project. Can final deadline be extended? If doomed, abort project and cut losses. But, will your superiors understand?

Principles (4) Divide and conquer A large project can be overwhelming at first. Break into small, manageable parts. Reminds me of studying for a final exam, or writing large essay. Top-down design and bottom-up implementation. Design for future growth and change Your project may be in service for 10+ years People who adopt and like your work may want to continue using it forever. You will have to live with decisions you make today. (For example, choice of programming language) How to begin How does a big project (e.g. information system) begin? Planned by the system analyst:

The system analyst could be asked to poke around and look for problems or opportunities for improvement. Or its unplanned: Request from management People using the current system complain If there are lots of requests/complaints, someone needs to decide how to approved Purpose of the project is to respond to a problem, opportunity or directive Example Heres a hypothetical example of a directive that could affect a business system. Congress could enact a law requiring anyone buying an international airline ticket to have a valid passport. The FAA specifies how this law will be enforced by writing a

regulation for the airlines: Airline must ask customer to provide country and number of passport when they buy an international ticket. Airline must look up the passport number on a system provided by State Department. If number invalid, reject transaction and refund customers money. This functionality must be implemented for any mode of buying a ticket (online, in person, over phone, etc.) Brainstorming Where does one look for problems to solve, or opportunities to exploit? One approach is the PIECES framework: P = improve Performance I = improve Information E = improve Economics (i.e. profit and costs) C = improve Control (including security) E = improve Efficiency S = improve Service

See handout for details Which categories seem most important to you? CS 111 Dec. 3 Lab recap Problem solving approach for systems analysts 8 phases Just understand the flow/process/sequence of the steps, not specifically how many there are or what they are called. Important to understand the order of the steps is not arbitrary. Similar to problem solving approach for small programs we would do in this class Much more emphasis on pre-design aspects The overall technique can be applied in other areas like planning a vacation. Commitment Review PIECES framework to prepare for in-class activity.

Approach Survey phase Define the scope, budget, staff, schedule Scope: Is this a quick fix or major overhaul? Is the project worth our time & money? Look over PIECES framework for ideas. Should be done in 2-3 days. Study phase Okay, lets do the project. What are the relevant business issues? (Technical issues come later) How beneficial will it be to do it? How much time/money should we invest? List all the objectives you hope to accomplish. Understand the problem are the objectives specific enough? External deadline? Approach (2)

Definition phase Critically important. At end of this phase, the definition document is like a contract that should not change. What are the business requirements for a solution? Need to know specific requirements for: data, geography, interface, process Build a prototype, and get it approved before continuing. Configuration phase Evaluate possible solution strategies. Look at various options. Should we outsource; how much should we do ourselves? For each candidate solution, find out, for example: Can we afford it? Will it actually work? Can we get it done on time? Approach (3) Procurement phase

What should we buy? Do we need new or different kind of equipment, software? Get proposals from vendors; negotiate. Note there are fixed + variable costs. Design phase Tell how to solve the problem in technical terms. This is like step 2 from our original procedure. Decide in what order the components need to be implemented. Come up with an evaluation (testing) plan so that youll know the implementation matches the design. Approach (4)

Construction phase Implement and test the solution, or an interim benchmark if its a longterm project Test the individual components in isolation; test entire system when ready. Most work is done by programmers, overseen by project managers, etc. Caution: many testers are entry-level workers and may need extra help/supervision. Delivery phase Install the HW and SW Train people on the new system Put it into daily use. Put together a plan for regular support and maintenance.

Activity Next time: Lets divide into 3 groups. Each group will address an aspect of a problem Lets examine Furmans class registration system 3 tasks (1 per group) Critically examine and evaluate the current system of preregistration and drop/add. Do you like it? Does it work? How could it be improved? Cover all aspects such as technology, I/O, ease of performing tasks, performance, red tape. What are the requirements of a good class registration system? How should the Web interface be designed? What feedback and information should be available to users online?

Recently Viewed Presentations

  • Efficient and Effective Sparse LSTM on FPGA ... - GitHub Pages

    Efficient and Effective Sparse LSTM on FPGA ... - GitHub Pages

    Efficient and Effective Sparse LSTM on FPGA with Bank-Balanced Sparsity. Shijie Cao1, Chen Zhang2, Zhuliang Yao3, Wencong Xiao4, Lanshun Nie1, Dechen Zhan1, Yunxin Liu2, Ming Wu2, Lintao Zhang2


    BUDGET PROPOSAL 2011 Somerset County Public Schools March 30, 2010 Dr. Karen-Lee N. Brofee, Superintendent of Schools PURPOSE OF PRESENTATION To provide a clear understanding of the proposed 2011 Budget of Anticipated Revenue To compare the 2011 proposed budget with...
  • Land Redistribution - Moodle at Sutton Grammar School

    Land Redistribution - Moodle at Sutton Grammar School

    Who gained land? A lot of land was given to the church - William appointed Lanfranc Archbishop of Canterbury. New cathedrals and abbeys were started in St Albans, Winchester, Salisbury, Rochester and Chichester
  • New Drugs in Palliative Care - Beaumont Hospital, Dublin

    New Drugs in Palliative Care - Beaumont Hospital, Dublin

    Oral use Twice daily dose Targin Recommended starting dose in opioid naïve patients - 10 mg/5 mg oxycodone/naloxone BD Max daily dose of Targin - 80 mg/40mg. If higher doses required - consider administration of supplemental oxycodone hydrochloride prolonged-release at...
  • Central Operations And Resources Health and Environmental Impacts

    Central Operations And Resources Health and Environmental Impacts

    Immediate Office Steve Page Regina Chappell Vacancy Deputy Vacancy AD/CIO John Bachmann Teri Porterfield Policy Analysis and Communications Staff Jeff Clark Barbara Hale Jan Cortelyou-Lee Alison Davis Mary Henigin Denise Johnson Jenny Noonan Alan Rush Sherry Russell Central Operations And...
  • Poetry - Mr. Jason Spitzer, English Language Arts

    Poetry - Mr. Jason Spitzer, English Language Arts

    Sound Devices. Rhythm is the pattern, or beat, of stressed and unstressed syllables in a line (foot/meter) of poetry.. Rhyme . is the repetition of final sounds in two or more words ("Once upon a midnight dr. eary,/ while I...
  • 8: Political Parties American Democracy Now, 5th edition

    8: Political Parties American Democracy Now, 5th edition

    Figure 8.1 The People's Opinion of Democrats and Republicans. The figure shows the percentage of survey respondents who have a favorable view of the Republican and Democratic parties at selected dates between September 1993 and August 2016.
  • EYC Environmental Youth Connections Connie Abert, Waupaca County

    EYC Environmental Youth Connections Connie Abert, Waupaca County

    Connie Abert, Waupaca County UWEX & Gretchen Marshall, UWSP JCEP Conference April, 2011 University of Wisconsin, U.S. Department of Agriculture and Wisconsin counties cooperating. UW-Extension provides equal opportunities in employment and programming including Title IX and ADA.