Computing for Engineers
Computing for Engineers CS 1371
Popular in Course
Popular in ComputerScienence
This 0 page Class Notes was uploaded by Alayna Veum on Monday November 2, 2015. The Class Notes belongs to CS 1371 at Georgia Institute of Technology - Main Campus taught by Staff in Fall. Since its upload, it has received 9 views. For similar materials see /class/234108/cs-1371-georgia-institute-of-technology-main-campus in ComputerScienence at Georgia Institute of Technology - Main Campus.
Reviews for Computing for Engineers
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 11/02/15
CS1371 Introduction to Computing for Engineers Stacks and Queues Outline Learning Objectives Understanding the Character of Queues Understanding the Character of Stacks Extending the functionality of a Queue The Linear Data Structures Extending the LinkedList Getting Methods in the Right Place Further Extensions Background Linked Lists seem to provide a lot of general functionality but so what Importance as a foundation for building more restrictive classes Queues and Stacks Queues are powerful tools in modeling realworld situations that involve process flows retail operations print processing etc Stacks are good for modeling todo lists where the last thing to arrive is more urgent than the rest of the work The Queue Basic requirements for a Queue De ned by a set of behaviors Enqueue Dequeue Dequeue IsEmpty Nth Enqueue The Queue ADT An idea a concept an abstraction of the big picture How would you implement it enqueue i isEmpw How about using an Array How about using an Array How about using an Array Two issues Managing the size when you fill the array it has to be expanded requires the old contents to be copied to the new array Shuffling the data each dequeue or enqueue if you work the other way means you have to shuffle every entry in the array Both issues make the computation a linear function of the number of entries in the queue We really need the computation to be independent of queue size Can we do this with a Linked List Extending a Linked List Would this work Dynamic data storage no worries about capacity dequeue would be really easy just take the item off the front Hmmm but the enqueue would need to find the end of the linked list to achieve FIFO behavior How about enqueue accessing the front No then dequeue needs to find the back Sneaky trick By using a second reference to the tail of the list we could in principle avoid the ugliness of iterating down to find the end of the queue Matlab won t actually permit this but most languages do the LinkedList class Linked List count sum head LLNode data ne t I addToHeaditem addToTailitem I addanrderitem Char LLNode 39data Isp ay next I I getHead 39 LLNode setHead 39 data nelxt I v LLNode I removeFromHead data next I Make a Queue by Inheritance LinkedList count sum I addToHeaditem addToTailitem I addanrderitem I Queue removeFromHeay I enqueue J dequeue Char The Methods really tough to code function enqueueq data queue test script enqueue onto a queue addToTailq data assignin39caller39 inputname1 q isEmptyq for ix 110 enqueueq ix q Queue fprintf39is queue empty dn39 d function ans dequeueq en fprintf39is queue empty dn39 isEmptyq dequeue from a Queue ans removeFromHeadq q assignin39caller39 I fprintf39dequeue gt d leaving sn39 inputname1 q dequeueq CharQ fprintf39peek at q gt d leaving sn39 Peekq charq is queue empty 1 is queue empty 0 Queue 12345678910 dequeue gt391 leaving Queue 2345678910 peek at queue gt 2 leaving Queue 2345678910 Questions A Stack Consider the concept of a Stack De ned by a set of behaviors Push Pop PUSh IsEmpty g mu 1 The MStack ADT An idea a concept an abstraction of the big picture i isEmpty Make a Stack by Inheritance LinkedList count sum addToHeaditem I addToTailitem I addanrderitem I removeFromHeay I MStack The Methods function pushstk data push onto a stack addToHeadstk data assignin39caller39 inputname1 stk function ans popstk push onto a stack ans removeFromHeadstk assignin39caller39 inputname1 stk is stack empty 1 is stack empty 0 MStack 10987654321 pop from stack gt 10 leaving MStack 987654321 987654321 stack with whole queue is MStack 1098765432987654321 peek stack gt 9 leaving MStack stack test script stk MStack fprintf39is stack empty dn39 isEmptystk for ix 110 pushstk ix end fprintf39is stack empty dn39 isEmptystk stk fprintf39pop fr st gt d leaving sn39 popstk charstk fprintf39peek stack gt d leaving sn39 peekstk charstk while isEmptyq pushstk dequeueq end fprintf39stack with whole queue is sn39 charstk Making a Priority Queue Why sometimes you actually want to give priority to some jobs in a queue over others For example a print queue might give preference to shorter print jobs A priority Queue is an ordinary queue with a different enqueue method invoking addanrder instead of addToTaHLquot We noted that this confines the classes that can be put into a priority queue to those able to be compared one to another addToHeaditem addToTailitem ddanrderitem display a enqueue 1 The Priority Queue Methods priority queue test script pq PriorityQueue function enqueuepq data for ix 110 enqueue onto a queue value 100rand addInOrderpq data fprintf39 9541151 39 I value quot assignin39caller39 m enqueuePq value inputname1 pq end fprintf39npriority queue is sn39 char Pq 15 747 445 932 466 419 846 525 203 672 priority queue is PriorityQueue 2204245475367758593 Summary We built a Linked List class investing some effort into giving it as much capability as we could foresee Other linear data structures Queues Stacks Priority Queues and goodness knows what else become almost trivial to implement when extending this base class Questions CS1371 Introduction to Computing for Engineers Numbers and Arrays Representing Numbers Learning Outline ObJeCt39VeS Precision and accuracy Understand how Numbers on a computer numbers are Exercises stored in a Summa computer and W what the implications are Not in our textbook pay attention create your own knowledge base Lecture References Online Computer memory httpwww undidaliuseannsa582tutorial httpwwwcrisincaddrcommemoryhtml httpwwwhowstuffworkscomcomputer memoryyhtm Numeric representation httpwwwscrifsuedujaCMAD3401Backgrndieeehtml httpwww3mathbyueduschowworkfloatingpointsystem htm httpwwwcsutaheduzacharyispappletsFPFPhtml httpwwwresearchmicrosoftcomhollaschcgindexcoding ieeefloathtml h t tp www cs unc edudmUNCCOMP205LECTURESERRORl ec23 node4html Standards httpstandardsieeeorg How are Numbers Represented Numeric representation is a key part of defining data used in a computer program We will consider several topics Limitations in representation when using finite sized numbers precision amp accuracy Binary representation Integers versus real numbers aka xed vs floating point numbers IEEE Floating Point How Matlab handles this Numbers Precision and Accuracy Good Accuracy Good Precision Good Precision Poor Accuracy Good Accuracy Poor Precision Poor Accuracy Poor Precision Low precision 7 314 High precision 7 3140101011 Low accuracy 7 310212 High accuracy 7 314159 High accuracy amp precision 7 3141592653 In most cases computers must deal with finite precision some software provides unlimited precision 5 Numbers Numbers we use are DECIMAL or base 10 Digits 0 1 2 3 4 5 6 7 8 9 123 1102 2101 3100 But we can always use other bases Octal base 8 Digits 0 1 2 3 4 5 6 7 123 182 281 380 1238 64163 8310 Binary base 2 Digits 0 1 1011 123 022 121 120 10112 8021 1110 1238 001 010 011 10100112 Hexadecimal base 16 Digits 0 1 2 3 4 5 6 7 8 9 A B C D E 123 1162 2161 3160 1236 256 32 3 291 O O 0 12316 0001 0010 0011 1001000112 Hexadecimal makes for shorter numbers Inside the Bytes A byte is the smallest memory allocation available A byte contains 8 bits so that Smallest 0 0 0 0 0 0 0 0 010 Largest 11111111 127126125124123122121120 25510 or 281 Result a single byte can be used to store an integer number ranging from 0 to 255 256 different numbers If negative numbers are included one bit must be dedicated to the sign leaving only 7 bits for the number Smallest 0 Largest 127 or12810 Sig nedMagnitude OPTIONAL MATERIAL Example of signed magnitude 000001012 gt 5 100001012 gt 5 Notice also that signedmagnitude gives plus and minus zero 000000002 gt 0 100000002 gt 0 Two s Complement OPTIONAL MATERIAL Widely used to avoid 0 problem If first bit is zero the number is positive and there is no further interpretation needed 011111112 gt 127 If first bit is one the number is negative Complement all bits and add one to get to the positive magnitude of the negative number 111111112 F 00000000 1 000000012 Therefore original number 1 Two s Complement OPTIONAL MATERIAL Two s Complement has no negative zero for a one byte integer 01111111 127 00000001 1 00000000 0 11111111 1 10000000 128 Range 128 127 Inside the Bytes Integers 281 255 is not a very big number so computers generall us multiple bytes to represent numbers 39 39 Integers are defined in various sizes Size Precision Matlab V I Java 1 byte 28 256 uint8 int8 byte 2 byte 65536 uint16 int16 short 4 byte 4294967296 uint32 int32 int 8 byte 264 long Matlab uint s are unsigned integers no sign bit positive values only Note A word is the basic size of the CPU registers and for Pentium chips it is 4 bytes or 32 bits it is 8 bytes for the new Itanium and some unix chipsets It was 2 bytes for early Intel chips some new game consoles use 16 byte words Inside the Bytes Real Numbers How are fractional numbers called real or floating point numbers stored in a computer The IEEE 754 double format consists of three fields a 52bit fraction f also called the mantissa an 11bit biased exponent e and a 1bit sign 3 Example 12345x 1024 exp quotequott These fields are stored contiguously in 8 bytes or 2 successively addressed 4byte words mantissa 452 52 3951 32 53 52 52 51 32 I E3L I Inside the Bytes Real Numbers Matlab s real is called double and is an 8 byte IEEE 754 format Because only a finite number of bits are used for each part of the number not all possible real numbers can be represented in a computer using IEEE 754 0 I v Negative numbers Positive numbers greater greater than 21022 than 2252 x 21023 negative underflow positive overflow Matab mamax Positive numbers smaller than 21022 positive underflow Matab realmin Negative numbers less than 2252 x 21023 negative overflow Zero actually is a special combination of bits RESULT about 16 digits of precision in the range 10i308 Inside the Bytes Others sources of error in computation Errors in the input data measurement errors errors introduced by the conversion of decimal data to binary roundoff errors Roundoff errors during computation as discussed Truncation errors using approximate calculation is inevitable when computing quantities involving limits and other infinite processes on a computer Never try to compare two oating point numbers for equalty because all 76 digts would have to match perfecty Use Matab routines whene Ier possible the y are optimized to avoid truncation and roundoffprobems Describing Error in Matlab Accuracy How close your answer is to the actual or real answer Precision The smallest difference that can be represented on the computer help eps Recognize MATLAB and other programs that use IEEE doubles give you 1516 good digits MATLAB will also store exact integer values using only the mantissa for about 1516 digits total Matlab commands realmin realmax eps bitmax try With help Memory Allocation in MATLAB MATLAB Eile Edit 1sl ie39sne Web window elp D 3 g n 2 l l stmm CurrentDiret mrylC MATLABBp work vl Size Bytes Class 1x1 8 double array 1x43 86 char array 1x200 16013 double array lU47 AM 95221 01 1 10 x linspace02pi2001 s 39hello world39 l24lJ PH 9522301 i 10 t linspacetlj2pi2001 s 39hellu world39 n mend gtgt 1 k t linspacet02pi20l31 gtgt s hellu world gt whoa Name Size Bytes Class 1 lxl 8 double array 5 1x43 86 Char array t 1x200 1600 double array Grand total is 244 elements using 1694 bytes gtgtI To get started select quotMATLAB Helpquot from the Help mem WhDS I bl Command History I CurrentDirectory I Ready What it Means In the previous slide we see Name Size Bytes i 1x1 8 3 1x43 86 t 1x200 1600 What is the size of the variable 1 What does class represent Class double array char array double array How many bytes are used to store the value Back to MATLAB what does all this mean We must pay attention to the math on any computer Given a finite limited number of bits almost all computations will result in numbers that can t be represented exactly Remember that the result of a floatingpoint computation must be truncated to fit back into it s finite representation Always check your results design your programs to allow for independent verification of computations SUMMARY Describe memory List different kinds of memory What is IEEE 754 Describe how MATLAB represents numbers Draw a number line and identify ranges where computers will generate errors Describe three potential sources of errors in computation Describe precision Describe accuracy Describe how we can protect ourselves from computation error Summary Lecture Outline Numbers in the Computer Precision and Accuracy Action Items Review the lecture How will you use this information in your current work future work at GT Start Exploring Matlab Increment your record of commands learned Come prepared to ask questions about MATLAB Questions
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'