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 7 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 Computability Introduction Learning Objectives Introduction Reasonable vs Unreasonable Learn the issues Algorithms associated with computability Reasonable vs Unreasonable Reasonable algorithms have polynomial factors 0 Log N O N O NK where K is a constant Unreasonable algorithms have exponential factors O 2N O N 0 MN Algorithmic Performance Thus Far Some examples thus far 01 Insert to front of linked list OIog N Binary Search ON SimpleLinear Search ON Log N Merge Sort 0N2 Insertion Sort But it could get worse 0N5 0N2000 etc An ON5 Example For N 256 N5 2565 1100000000000 If we had a computer that could execute a million instructions per second 1100000 seconds 127 days to complete But it could get worse The Power of Exponents A rich king and a wise peasant The Wise Peasant s Pay DaygN Pieces of Grain 1 2 2 4 3 8 4 16 2N 63 9223000000000000000 64 18450000000000000000 How Bad is 2 Imagine being able to grow a billion 1000000000 pieces of grain a second It would take 9 585 years to grow enough grain just for the 64th day Over a thousand years to fulfill the peasant s request So the King cut off the peasant s head The Towers of Hanoi A B C Goal Move stack of rings to another peg Rule 1 May move only 1 ring at a time Rule 2 May never have larger ring on top of smaller ring Towers of Hanoi Solution 39quot WI IJLTXIJLI IJLI J I FLT II I Move 2 I I Move 3 I III I FIELI AL 1 ill J I I Move 4 I I Move 5 I I ILA MAI I Move 6 I I Move 7 I Towers of Hanoi Complexity For 3 rings we have 7 operations In general the cost is 2 1 02N Each time we increment N we double the amount of work This grows incredibly fast Towers of Hanoi 2 Runtime For N 64 2N 264 18450000000000000000 If we had a computer that could execute a million instructions per second It would take 584000 years to complete But it could get worse The Bounded Tile Problem H Match up the patterns in the tiles Can it be done yes or no The Bounded Tile Problem Matching tiles Tiling a 5x5 Area 25 available tiles remaining Tiling a 5x5 Area 24 available tiles remaining Tiling a 5x5 Area 23 available tiles remaining Tiling a 5x5 Area 22 available tiles remaining Tiling a 5x5 Area 2 available tiles remaining Analysis of the Bounded Tiling Problem Tile a 5 by 5 area N 25 tiles 1st location 25 choices 2nd location 24 choices And so on Total number of arrangements 25 24 23 22 21 3 2 1 25 Factorial 15 500 000 000000 000 000 000000 Bounded Tiling Problem is ON Tiling N Runtime I For N 25 25 15500000000000000000000000 If we could place a million tiles per second It would take 470 billion years to complete Why not a faster computer A Faster Computer If we had a computer that could execute a trillion instructions per second a million times faster than our MIPS computer 5x5 tiling problem would take 470000 years 64ring Tower of Hanoi problem would take 213 days Why not an even faster computer Where Does this Leave Us Clearly algorithms have varying runtimes We d like a way to categorize them Reasonable so it may be useful Unreasonable so why bother running Performance Categories of Algorithms Polynomial Sublinear Linear NeaHyHnear Quadratic Exponen al OLog N ON ON Log N ONZ O2N ON ONN Two Categories of Algorithms Runtime 1035 1030 1025 1020 1015 trillion billion million 1000 100 10 Unreasonable I Don t Care 2 4 8 1632 64 128 256 512 1024 Size of Input N Summary Reasonable algorithms feature polynomial factors in their 0 and may be usable depending upon input size Unreasonable algorithms feature exponential factors in their 0 and have no practical utility Questions Problem Complexity Cost and Complexity Algorithm complexity can be expressed in Order notation eg at what rate does work grow with N 01 Constant OIogN Sublinear ON Linear ONIogN Nearly linear ONZ Quadratic OXN Exponential But for a given problem how do we know if a better algorithm is possible The Problem of Sorting For example in discussing the problem of sorting Two algorithms to solve Insertion Sort ON2 Mergeson ON Log N Can we do better than ON Log N Algorithm vs Problem Complexity Algorithmic complexity is defined by analysis of an algorithm Problem complexity is defined by An upper bound defined by an algorithm A lower bound de ned by a proof The Upper Bound Defined by an algorithm Defines that we know we can do at least this good Perhaps we can do better Lowered by a better algorithm For problem X the best algorithm was ON3 but my new algorithm is ON2 The Lower Bound Defined by a proof Defines that we know we can do no better than this It may be worse Raised by a better proof For problem X the strongest proof showed that it required ON but my new stronger proof shows that it requires at least ON2 Upper and Lower Bounds The Upper bound is the best algorithmic solution that has been found for a problem What s the best that we know we can do The Lower bound is the best solution that is theoretically possible What cost can we prove is necessary Changing the Bounds Upper bound 1 Lowered by better algorithm Lower bound Raised by better proof Open Problems The upper and lower bounds differ Lowered by better Upper bound 1 algorithm Unknown Lower bound Raised by better proof Closed Problems The upper and lower bounds are identical Upperbound Lower bound
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'