Introduction to Computing Using MATLAB
Introduction to Computing Using MATLAB CS 1112
Popular in Course
verified elite notetaker
Popular in ComputerScienence
This 190 page Class Notes was uploaded by Lacey Collier on Saturday September 26, 2015. The Class Notes belongs to CS 1112 at Cornell University taught by Staff in Fall. Since its upload, it has received 11 views. For similar materials see /class/214342/cs-1112-cornell-university in ComputerScienence at Cornell University.
Reviews for Introduction to Computing Using MATLAB
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: 09/26/15
CS1112 Lecture 2 I Previous Lecture l Intro to computer programming I CSI l l2vs CSI l l0 I Today39s Lecture I Anatomy of a program I Variables amp assignment I Functions for input amp output I Sequential execution I Branching next lecture Formula I Surface area of a sphere 214 I Have the cosine of some angel 6 0 7 and want cos6i 2 E l gt cos 239 A computer program computation input output Surface Area Increase gtgt 1 6365 gtgt delta 000001 gtgt Aplus 4pirdeltaquot2 gtgt A 4pirquot2 gtgt Increase Aplus A Increase 0155396992588043 Variable amp assignment I Variable a named space for storing a value r l delta E I Valid names start with a letter can contain digits I Use meaningful variable names Variable amp assignment I Variable a named space for storing a value r S I Assignment putting a value into a variable I Assignment operator I An assignment statement r 2 4 5 I Expression on rhs is evaluated before the assignment operation September 2 2008 CS1112Lecnue2 Assignment I Expression on rhs is evaluated before the assignment operation I Examples X 23 l4 y 1X z 4A2 cos y I Question can we reverse the order of the 3 statements above Matlab39s builtin functions 39MZET W cosltygt Script execution A script is a sequence of statements an m le 8 Quadl 8 Solves XA2 5X 6 0 Henrny space H m sqrt bA2 4ac r1 b d2a r2 b d2a Statements in a program are executed in sequence 8 A program fragment X 2314 y 1X X 5 8 What is y now 8 Example 11 Surface area of a sphere 8 A surface area of the sphere 8 r radius of the sphere r input39Enter the radius A 43 14159rr fprintf39Surface area is 8fn39 A Semember22008 Input amp output I variable input prompt r input Enter radius I fpr intf message to print fprintf Increase 39 fprintf is 8f inchesn39 x fprintf Position ddn xy CS1112 Lecture 2 Substitution sequences Comments conversion specifications I For readability if xed POlnt or floating POlnt I A comment starts with and goes to the end 96d decimal whole number of the ne 9 EXPonential I Start each program script with a concise g general Matlab chooses a format description of what it does 60 character I Define each important variableconstant s 58 string I Top a block of code for a specific task with a concise comment Examples 96f 15 2f Example c Example 12 Surface area increase c given an increase in the radius Modify the previous program to calculate the r input39Enter radius r in miles v increase in surface area given an increase in the delta input 39Enter delta r in inches v radius of a sphere Note I mile 5280 feet What39s next I So far all the statements in our scripts are executed in order I We do not have a way to specify that some statements should be executed only under some condition I We need a new language construct September 2 2008 Previous Lecture Iteration using while Introduce nested loops Today s Lecture Developing algorithms Nested loops Announcements Section in the computer lab this week Project 2 due 2l2 Thurs at l lpm Prelim l on 2l9 Thurs 730pm If you have a conflict tell us email Bill Hogan now no later than 2 l2 Quiz I 2 questions I A quiz counts as can miss several without loerng quot ur score Eg if there will be l5 exercises in total you can miss 3 about 20 I Answer the quiz using your registered clicker I Honor system Use only your clicker and don t consult your neighbors or notes in any way February 10 2009 Lecture 7 2 Example Nested Stars February 10 2009 Lecture 7 Example Nested Stars February 10 2009 Draw a black square Bigger39 Than The biggesT sTar39 aT leasT 2 Times radius of sTar39 CenTer39 aT 00 Draw a sequence of sTar39s STar39s alTer39naTe in color39 STar39s geT smaller39 r39adius r391 To sTar39T 1ST sTar39 smaller Than The sqr39 When To sTop when r39 is small Lecture 7 6 nestedStarsm February 10 2009 Lecture 7 Knowing how to draw How difficult is it to draw February 10 2009 Lecture 7 Pattern for doing something n times end February 10 2009 Lecture 7 x0 y0 figure centered at 00 s 21 side length of square DrawRectx s2y s2ss k r 1 k 1 while r gt 01 r still big draw a star if remk2 odd number DrawStarxyr m magenta else DrawStarxyr y yellow end reduce r r r12 k k 1 end February 10 2009 Lecture 7 for c 028 xc yc figure centered at cc s 21 side length of square DrawRectx s2y s2ss k r 1 k 1 while r gt 01 draw a star if remk2 DrawStarxyr m else DrawStarxyr y end reduce r r r12 k k 1 end r still big odd number magenta yellow end February 10 2009 Lecture 7 Pattern for doing something n times end February 10 2009 Lecture 7 Example Are they prime l Given integers a and b write a program that lists all the prime numbers in the range a b I Assume agt bgt and altb Example Are they prime l Given integers a and b write a program that lists all the prime numbers in the range a b I Assume agt bgt and altb February 10 2009 Lecture 7 14 Example Are they prime Subproblem Is it prime I Write a program fragment to determine whether a given integer n is prime ngt l Reminder remxy returns the remainder of x divided by y February 10 2009 Lecture 7 15 All 1de 417331 2 Mm mm novimM D Koraf dtlI75W3o12vfsoy 1 rm VIAWE 0 it7W 9mm5wI 39ch ampv h A KP IPfIMQ gt LEM dV m 70 mm W at Omaha lmva 9 n A Given n display whether it is prime divisor 2 while remndivisor0 divisor divisor 1 end if divisorn fprintf d is primen n else fprintf d is compositen n end February 10 2009 Lecture 7 for n azb Given n display whether it is prime divisor 2 while remndivisor0 divisor divisor 1 end if divisorn fprintf d is primen n else fprintf d is compositen n end end February 10 2009 Lecture 7 Example Times Table Write a script to print a times table for a speci ed range Row headings February 10 2009 3 4 5 6 7 34567 9 l2 l5 l8 2 l2 I6 20 24 28 IS 20 25 3O 35 I8 24 3O 36 42 2 28 35 42 49 Column headings Developing the algorithm for the times table 34567 9 l2 l5 l8 2 l2 I6 20 24 28 IS 20 25 3O 35 I8 24 3O 36 42 IQU IAW 2 28 35 42 49 Developing the algorithm for the timestable 3 4 5 6 7 3 9 l2 l5 l8 2 4 l2 I6 20 24 28 5 IS 20 25 3O 35 6 I8 24 3O 36 42 7 2 28 35 42 49 February 10 2009 Look for patterns Each entry is row gtlt col Row col increase regularly gt Loop What kind of loop forloop since the range of the headings will be speci ed and increment regularly for each row get the products with all the cols Then go to next row and get products with all cols u gt Nested loops Details what will be the print format Don t forget to start new lines Also need initial input to specify the range Lecture 7 24 disp39Show the times table for specified range39 lo input39What is the lower bound 39 hi input39What is the upper bound 39 Find the biggest rectangle Here39s the biggest rectangle you drew I 5 that the user speci es using mouse clicks I Color the biggest one red February 10 2009 Lecture 7 26 Find the biggest rectangle develop an algorithm thebiggestrectangtyoudrewi I What are the main tasks I Draw 5 yellow rects I Find the biggest one I Draw biggest one in red I Repetition is needed Which kind I Finite iteration forIoop I Do I need to keep track of all 5 rectangles I No February 10 2009 Lecture 7 27 DaTa STrucTure Choice Numerical arrays Cell arrays STrucTure arrays CharaoTer arrays ApplicaTion CharacTer RecogniTion A handwriTTzn Is This a 3quot or an 8quot Superimpose The digif on a 7 by 5 grid Color 1 Tile if if houses quotenoughquot of The blue line A quotLibraryquot of PerfecT DigiTs This is The inpuT This is The problem Who is ifs nearesf Perfecf digiT Compare with Perfect 3 A quotLibraryquot of Perfec r Digi rs 4 tiie discrepancies Compare with Perfect 8 Digi i Recogni iion is a very hard problem I mm E ii is 652 If 3 tiie discrepancies i W T IIILilltl stall A surprising i A surprising amount of A H number of data behind ii 7 features eacii digit 7 it behind i 4 mi m e 7 7 e 7 WIVW 7 if Designing a code where The digiTs are 39really differenT39 7 1890814447 3 Desigr code where digiTs 39r eally diffen quotD L a 3 Lquot 5 E 39i E ll i n Tasks How To we r39epr39esenT 7by5 digiTs How do we quotpackagequot The library How do we decide on The closesT perfecT digiT 7by5 DoT MoTr39icesquot You Have Seen Them Before Harvard Cornell A IighT is eiTher39 on or39 off A 7by5 moTr39ix of 2 zeros and ones can Tell The whole Design Decisions How do we package a particular digit numerical array or character array How do we package the collection of digits cellarray or structurearray Could Use a Numerical 2D Array For Each Digit 0 1 o 039 o 0 1 IIIIOOOIIO 111 000 001 010 100 000 111 Now Let Us Store the 10 Bitmaps Two Choices 1 Use a cell array 2 Use a struct array Storing a Single Bitmap Two Choices A 2D numerical array matrix A character array Could Use a Character Array for Each Digit 0111039 1000139 0001039 0010039 01ooo39 1oooo39 11111391 Cell Array with Matrix Entries Sample Compu ra rion Commen r on Clar i ry M Mk if MV431 disprl Mid dle Light is39 Onquot With DlD10 set up M Dk end if M43 The following is zquivalznf buf a le confusing disp Middle Light is 01139 end if Dk43 disp Midd1e Light is 01139 end mm quot um w Cell Ar r ay wi rh Char Ar39r39ay En rr39ies sample Compufa on M 01110 Lquot WI l l D1D10 set up 1000139m 0001039m 0010039m 0100039m 1000039m 11111 M Dk if strcmpM43 39139 disp Midd1e Light is On39 D2 M Can Also Store The 10 Bi rmaps as a S rr uc r Array M m O 1 O O u 0 O 1 IIIIOOOIIO 1 1 1 O O O O O 1 O 1 O 1 O O O O O 1 1 1 D2 struct mat39M Sample Computation With DlD10 set up M Dkmat if M43 disp Midd1e Light is On39 ma ilu i39iihl J quotn 1J39il Sample Computation With DlD10 set up M Dkmat if strcmpM43 1 disp Midd1e Light is On39 end Assume Availability of This function D TheDigits D cell101 D1 001o 0110 010 0100 010 010 111 00000 Struct Array with Char Array Field M 01110 m 10001 m 00010 m 00100 m 01000 m 10000 m 11111 D2 struct mat39M L V V acMgmmww Choices for Storing the Bit Maps Cell array better than struct array No point in having a structure with one field Numerical array better than char array Plan on doing numerical computations with the bit arrays Char arrays not handy A Sample Problem Produce a cell array of quotreversequot digits Reversing Column Order SupposeA has5columns If B1 A5 B2 A4 B3 A3 B4 A2 B5 A1 Then B is A wiTh iTs cols reversed A FuncTion To Do The Job function E ReverseCol A pq sizeA B zerospq for k1q Bk Aqk1 A Cell Array of Reversed DigiTs D TheDigits revD ce11101 for k110 M Dk revM ReverseColM revDk revM end AnoTher Problem 100000 random digiTs are displayed in succession on a 7 by5 How ofTen does each of The 35 quotbulbsquot go on and off Digression 2D Array Ops gtgtA1234 gtgt B 10 20 3O 40 gtgt C A B 11 22 33 44 Adding Up The Changes D TheDigits Count zeros75i n 10000 for k1n 11 ceil10randi 12 ceil10randi 9s Mii 1 if the two bitmaps disagree in 95 position ij M shsDi1 Di2 Count Count i end Resul rs 43979 33570 37754 33570 43979 33933 37935 37935 0 0 49032 50079 33970 43935 43795 0 0 0 39033 33707 37754 33707 33943 Back To The Recogni rion Problem Who is ifs nearesf Neighbor The Discrepancy Be rween Two Bi r Maps Discrepancy red dots function a DiscrepancyAB 9s A and B are phyq arrays 9s a is the discrepancy between A and B Pq sizeA a o for i1p for j1q d d ahsAii Bij end end Ma iching Plan Minimize file discrepancy 95 Assume T is the mystery digit D TheDigits dMin inf for k110 dk DiscrepancyTDk if dk lt dMin i k dMin dk end end TheMatch modi10 ResulTs 10 bar pIoTs follow one for each digiT To generaTe The kTh bar pIoT we repeaT The following 10000 Times Take a perfecT digiT k and flip each lighT wiTh probabiliTy p 30 CompuTe The nearesT perfecT digiT m mm u mnm mwm E 3 454 4 A A g g 3 y4 i 4 44 44J444 E z my szmhmmwusnm m r m 39 we r m m m 2 3 5 n 1 g u nanum NHMMMWNN m pm nImmmmwcmmn m CSlOOM Section Exercise 11 1 Where to put your longburning light bulb In this exercise7 you need to think about the problem and come up with a plan to solve it Think about the approach that you will take and the functions you may need to write in answering the question Refer to the dotmatrix examples from the lecture on lllli Suppose you have one extralong life light bulb that can be used in a 7 X 5 board for displaying a digit 0 to 9 In which position of the 7 X 5 board would you put this special longlife light bulb Assume that function digitToShow is given and the display board displays the digit returned by the function function 11 digitToShowO n is the next digit to be displayed on the 7by5 display board 11 is an integer Oltnlt9 Assume this function is given and use it in your solutionidonlt assume that all digits are equally likely to occur Further assume that a bulb Lj that is in a lit part of the board simply stays oniinstead of rst turning off and then back oniwhen the display changes to another digit that requires bulb Lj to be on Answer the question for these two separate cases ll The longer that a bulb is on7 the more it degradesi 2 Switching a bulb on and off frequently causes it to degrade Take the extreme casePassume that continuous burning doesn7t degrade the bu Assume the availability of function TheDigits7 shown in lecture7 that returns a lObyl cell array D such that Dk is the matrix encoding digit kl Part of the function is shown below function D TheDigitsO 39 D is a 10by1 cell array 39 D39Ck is a 7by5 matrix that encodes the digit k D10 encodes O D cell101 D fl 00100 01100 00100 00100 00100 00100 01110 D2 01110 10001 00001 00010 00100 01000 11111 D f10 0 1 1 1 0 10001 10001 10001 10001 10001 01110 2 Challenge question Refer to the question above What if you have ve extralong life light bulbs Determine in which positions you should place these special light bulbs in the two cases described above CS1112 Lecture 7 2008918 I Previous Lecture Iteration using while I Todays Lecture Developing algorithms Nested loops I Announcements Project 2 due 921Mon at 6pm Prelim l on 925 Thurs 730pm lfyou haveacon ict tell us email Kelly Patwell now no later than omorrow You39ll use your clicker for a quiz soon register it Example Nested Stars Draw a black s uare Bigger Than The biggesT sTar CenTer aT 00 Make side lengTh 21 Draw a sequence of sTars STars geT smaller STars alTernaTe in color 15 sTar smaller Than The sqr radius r1 to start When To sTop when r small Example Is it prime I Write a program fragment to determine whether a given integer n is prime Assume ngtl I Reminder remxy returns the remainder ofx divided by y Example Are they prime I Given integers a and b sketch a program that lists all the prime numbers in the range a b I Assume abgtl and altb Lecture slides Example Times Table Write a script to print a times table for a specified range Row headings headings lmU lAW CS1112 Lecture 7 2008918 disp39Show the times table for a specified range39 Developing the I I algorithm for the lo lnputWhat Is the lower bound times table hi input39What is the upper bound 39 34567 2 ID U IAW Find the biggest rectangle Draw 5 rectangles that the user specifies using mouse clicks I Color the biggest one re Th Find the mode in a sequence e savvy Pregmmmer l A mode is the number in a sequence that appears the where approprla most number of times I Learns useful programming patterns and use them te Seeks inspiration by working through test data by I Develop an algorithm for calculating the mode of a user hand entered sequence that is Asks What am I doingquot at each step N at I Declares avariable for each piece of information maintained onneg We when working the problem by hand Entered onebyone Innondecreaslng rder Decomposes the problem into manageable subtasks 39 Term39m ed by a 933quot Mb Re nes the solution iteratively solving simpler subproblems rst I Eg sequence 87 92 92 98 98 98 00 has a mode I Write the algorithm and then the code on your own for 39 Remembers to CheCk me Pquot l3 lemYS boundary e conditions practlc I Validates the solution program by trying it on test data Lecture slides Previous Lecture 2d array matrix Today s Lecture More examples on matrices Contour plot Read 72 73 Announcements Project 3 due tonight at l lpm Prelim 2 on Thurs Mar l2 Email whhcscornelledu TODAY if you have a prelim con ict Review session next week Initialize vectorsmatrices if dimensions are known instead of building the array one component at a time Initialize y Build y on the fly xlinspaceabn xlinspaceabn yzerosln for k1n for k1n yk myF x yk myF x end end I Much faster for large n March 5 2009 Lecture 14 Matrix example Random Web I N web pages can be represented by an Nby N Link Array A I Aij is I if there is a link on webpage j to webpage i I Generate a random link array and display the connectivity 1 I Aij l with probability I There is more likely to be a link ifi is close to j I There is no link from a page to itself March 5 2009 Lecture 14 function A RandomLinksn A is n by n matrix of ls and 0s representing n webpages A zerosnn for i1n for j1n r rand1 if ij ampamp rlt 11 absij 1 end end end March 5 2009 Lecture 14 March 5 2009 01110000010010000000 10001000111000000100 01010000000000000000 00101000000000000000 00010000001100000000 00000000000001010000 01111100010110000000 00000010000100000011 01000000010010001000 00000001101000000001 00000010000011000000 00000010010000000001 00010000110101100000 00000010000000110000 00000101000010010001 00000010001000001010 01000000100001010110 00000000000000011001 00000010000000000000 00000000000000001010 Lecture 14 Represent the web pages graphically 0000000000000 0 o o o o d 93 o 93 69 0o OOOoOOOOOOOOOOo oo 0o o 0 00000000000 00 do o 0o O O OO 0 0 0000000000000 0 oo IOO Web pages arranged in a circle Next display the links March 5 2009 Lecture 14 Represent the web pages graphically 5V 39A quot dquoty q quot 1393q44939gt 7 V M rs quots A Wi4w AAyga39nm 4 A a IA Line black as it leaves page j red when it arrives at page i March 5 2009 Lecture 14 ShowRandomLinksm March 5 2009 Lecture 14 A CostInventory Problem I A company has 3 factories that make 5 different products I The cost of making a product varies from factory to factory I The inventory varies from factory to factory March 5 2009 Lecture 14 11 Problems A customer submits a purchase order that is to be lled by a single factory I How much would it cost a factory to ll the order 2 Does a factory have enough inventory to ll the order 3 Among the factories that can fill the order who can do it most cheaply March 5 2009 Lecture 14 Cost Array March 5 2009 10 36 22 15 62 12 35 20 12 66 13 37 21 16 59 Lecture 14 Inventory Array Inv 38 5 99 34 42 82 19 83 12 42 51 29 21 56 87 March 5 2009 Lecture 14 Purchase Order PO 391 I0 12295 I March 5 2009 Lecture 14 15 10 36 22 15 62 C 12 35 2o 12 66 13 37 21 16 59 PO 391 I0 12295 I 110 036 1222 29 15 562 March 5 2009 Lecture 14 10 36 22 15 62 C 12 35 2o 12 66 13 37 21 16 59 PO 391 I0 12295 I s 0 Sum of cost for j15 s s C1jPOj end March 5 2009 Lecture 14 10 36 22 15 62 C 12 35 2o 12 66 13 37 21 16 59 PO 391 I0 12295 I s 0 Sum of cost for j15 s s C2jPOj end March 5 2009 Lecture 14 10 36 22 15 62 C 12 35 2o 12 66 13 37 21 16 59 PO 391 I0 12295 I s 0 Sum of cost for j15 s s CijPOj end March 5 2009 Lecture 14 19 Encapsulate function TheBill iCostiCPO The cost when factory i fills the purchase order nProd lengthPO TheBill 0 for j1nProd TheBill TheBill CijPOj end March 5 2009 Lecture 14 20 Finding the Cheapest 1o 36 22 15 62 C 12 35 2o 12 66 13 37 21 16 59 PO 391 I0 12295 I March 5 2009 Lecture 14 Finding the Cheapest iBest 0 minBill ltgt for i1anact iBill iCostiCPO if iBill lt minBill Found an Improvement iBest i minBill iBill end end March 5 2009 Lecture 14 22 inf a special value that can be regarded as positive infinity 100 assigns inf To 2 1x assigns inf To y lx OSSignS 0 To Z lt inf is always True if w is numeric SNKlN March 5 2009 Lecture 14 23 Inventory Considerations What if a factory lacks the inventory to ll the purchase order Such a factory should be excluded from the find thecheapest computation March 5 2009 Lecture 14 24 Who Can Fill the Order 38 5 99 34 42 Yes Inv 82 19 83 42 No 51 29 21 56 87 yes P 1 12 March 5 2009 Lecture 14 25 Wanted A TrueFalse Function Inv DO PO D0 is True if fac ror39y i can fill The order D0 is false if fac ror39y i canno r fill The order March 5 2009 Lecture 14 26 Example Check inventory of factory 2 Inv March 5 2009 Lecture 14 Initialization Inv 38 5 99 34 42 82 19 83 12 42 51 29 21 56 87 P0 l1 lo 12295 March 5 2009 Lecture 14 DO Still True 38 5 99 34 42 Inv 19 83 12 42 Do 1 51 PO 0 12295 I 29 21 56 87 March 5 2009 Lecture 14 29 Still True Inv 38 82 51 5 99 34 42 83 12 42 29 21 56 87 March 5 2009 Lecture 14 DO Still True 38 Inv 82 March 5 2009 Lecture 14 31 No Longer True 38 5 99 34 42 Inv 82 19 83 42 Do 0 51 29 21 56 87 March 5 2009 Lecture 14 32 Encapsulate function D0 iCanDoiInvPO D0 is true if factory i can fill the purchase order Otherwise false nProd lengthPO D0 1 for j 1nProd D0 DO ampamp Invij gt POj end March 5 2009 Lecture 14 Encapsulate function D0 iCanDoiInvPO D0 is true if factory i can fill oo the purchase order Otherwise false nProd lengthPO j1 while jltnProd ampamp InvijgtPOj j j1 end March 5 2009 Lecture 14 35 Back To Finding the Cheapest iBest 0 minBill inf for i1anact iBill iCostiCPO if iBill lt minBill Found an Improvement iBest i minBill iBill end end W 1 gs uness March 5 2009 Lecture 14 37 Back To Finding the Cheapest iBest 0 minBill inf for i1anact if iCanDoiInvPO iBill iCostiCPO if iBill lt minBill Found an Improvement minBill iBest i iBill end end end March 5 2009 Lecture 14 March 5 2009 Cheapestm Lecture 14 Finding the Cheapest 10 36 22 15 62 1019 Yes C 12 35 2o 12 66 930 No 13 37 21 16 59 1040 Yes PO 391 I0 12295 I I March 5 2009 Lecture 14 41 Contour Plot Visualize a function of the form 2 fxy Think of 2 as an elevation that depends on the coordinates X and y of the location Read Sec 72 and 73 but not for exams I I I A N o N 0 J March 5 2009 Lecture 14 43 CS1112 Lecture 17 Mar 24 2009 I Previous Lecture I Working with images I Today39s Lecture I Characters and strings I Brief introduction to recursion more later I Announcements I Section will be in the classrooms this week I Project 4 posted Due Thurs l 030 at 6pm Characters amp strings I We have used strings already I I1 input Next number I sprintf Answer is d ans I A string is made up of individual characters so a string is a ld array of characters CSlll2 rocks 39 is a character array of length l3 it has 7 letters 4 digits l space and l symbol Single quotes enclose strings in Matlab Anything enclosed in single quotes is a string even ifit looks like something else I 100 is a character array string of length 3 I 100 isanumericvalue I pi is a character array of length 2 I pi is the builtin constant 3 l4l6 I X is a character vector of length l I X may be a variable name in your program Strings are important in computation Numerical data is often encoded in strings Eg a le containing lthaca weather data begins with the string W07 629114226 meaning Longitude 76 2939 West Latitude 42 2639 North We may need to grab hold of the substring W07629 convert 076 and 29 to the numeric values 76 and 29 and do some computation Comparison of genomic sequences is another example of string computation I Eg looking for a pattern Given the sequence ATTCTGMGATC Look for the pattern ACCT I Eg quantifying the difference between sequences ATTCTGACCTCGATC ATTC TGACCTCGAT moved 6 his nudedl de 5 r 1 x WW mm mm mm 17 a Lecture slides Strings as vectors Vectors Strings I Assignment I Assignment 7 o 5 3 hello39 Indexing x v3 xi 5 v vix05 w v23 w is o 5 I nomtion 39on 25 v is 2 3 A 5 x 239 g39 x is zbcdelg39 I Appending I Appending v 7 o 5 x duck39 m 2 v is 7 o 5 2 5 x39 x is duckx I Concatenation I Concatenation v v A 5 x x qmck v is 70 5 2 A 6 x is duckx quack mm mm is 17 7 CS1112 Lecture 17 Mar 24 2009 Some useful string functions str Cs 1112 Example capitalize l t letter Write a function to capitalize the rst letter of each word in a string sume that the string has lower case letters 1 th t 1 eng 5 r and blanks only isletterstr an 7 1100000 1sspacestr 1 o o 1 o o o 0 lowerstr 1 as 111239 function str nCaps capsstr upperlstr 9 CS 1112 Post Capitalize rst letter of each word str partially capitalized string lsfharlStrl nCaps no of capital letters 9 Is Str a Char array True 1 Pre str string with lower case letters amp blanks only strcmpstr12 cs 1 Compare strings str12 amp cs False 0 strcilipstr13 CS 1 False 0 look for the spaces Look For The Spaces ASCII characters AmericanSmndard Cudefurlnfurmatiunlnmrchange Character vs ASCll code ascii code Character ascii code Character 39 39 39 39 str Age 19 39 l l l a 1d array of characters 65 A 48 0 code doublestr 66 B 49 I 67 lo 50 2 convert chars to asc11 values I I I I strl charcode 90 Z 57 939 convert ascii values to chars Arithmetic and relational ops on characters What is in variable g if it gets created I c a gives 2 d1 Mar 3 d2 Mar 9 x1 d15 x2 d25 g x2x1 I 6 5 gives l I letterl e letter2 f I letterlletter2 gives l I c gt a gives true I letter letter2 gives false I A 2 gives 67 I char A 2 gives C39 mm mm em 17 2 mm mm law n n Lecture slides CS1112 Lecture 17 Mar 24 2009 What is in variable g if it gets created d1 Mar 13 d2 Mar 29 x1 d156 x2 d256 g x2x1 Example toUpper Write a function toUppercha to convert character cha to upper case if cha is a lower case letter eturn t e converted letter If cha is not a lower case letter simply return the character cha Hint Think about the distance between a letter and the base letter a or A Eg a b c d e f g h GA distance g a A B C D E F G H Of course do not use Matlab s function upper Example removing all occurrences of a character I From a genome bank we get a sequence ATTG CCG TA GCTA CGTACGC AACTGG AAATGGC CGTAT I First step is to clean it upquot by removing all the blanks Write this function function 5 removeChar c s 8 Return string 5 with all occurrences of character c removed Example removing all occurrences of a character I Can solve this problem using iteration check one character one component of the vector at a time I New strategy recursion Possible when result can be accumulated iteratively Eg remove all the blanks in string s Same as remove blank in s nd remove blanks in s1lengths Eg capitalize rst letter of all words in a sentence Same as capitalize l5I letter of rst word and capitalize l5I letter of the rest of the words function s removeCharc 9 Return string s with character c removed if 1engths a Base case nothing to do return 9 return string is just a the remaining s with char c removed Lecture slides There is recursion in grammar I Anoun paper I A noun phrase blue paper I A noun phrase is a series of adjectives possibly empty followed by a noun So thin blue paper is also a noun phrase Recursive de nition A noun phrase is a noun an adjective followed by a noun phmse mm mm ram 17 031112 Section Exercise 7 1 Determinant of a 3 X 3 matrix Write a function myDeterminant x where x is a 3 X 3 matrix Use the following formula a b c det d e f adetltlt fgtgt7bdetltltd fgtgtcdetltltd g h 239 Z 9 Z 9 You may use the builtin function det to nd the determinants of 2 X 2 matrices For example det m returns the determinant of 2 X 2 matrix m Recall that you can construct a matrix by puting two row vectors one below the other or two column vectors side by side 2 Find a value in a matrix Write the following function function r c findInMatrixnM quot0 Find all occurrences of the number n in matrix M quot0 r and c are column vectors of row and column numbers such that quot0 Mrkck is equal to n quot0 If n is not found in M r and c are empty vectors Do not use the builtin function find Note The next two questions require that you design solutions Instead of giving you the speci cations of a function we are asking you to design a complete solution you decide what functions andor scripts are necessary and implement those functionsscripts Take some time to do the planningidonlt jump immediately to coding 3 Random walk A random walk that starts from the center of a 21 X 21 grid ends when a boundary is reached Which square or grid point is visited most often 4 Bounded random walk In a bounded random walk a set number of steps are taken within a bounded area For example when the right boundary excluding the corners is reached the next step can go left up or down only Similarly when a corner is reached the next steps can be in two directions only For a 100step bounded random walk in a 21 X 21 grid which square is visited most often CS1OOM Lecture 21 20081111 I Previous Lecture Working with large data les Builtin 5 art function I Todays Lecture Review matrix cell array structure array I Announcement I P5 due I I3 at pm an exam con ict Prelim 3 next Tues We must know by now ifyou have I Review session this Sunday 30pm Kimball BI Application digital dis plays 7by5 dot matricesquot A bit mapquot for each digit A light is either on or off A 7by5 matrix of zeros and ones can tell the whole storyquot Computing with these bitmaps I What is a good scheme for storing the l0 bitmaps I How to draw one digit I How to display a number I Other interesting questions I How to dmw a mirror image of a digit I Which light bulb switches on most often Lecture slides Design decisions How do we package a particular digit numerical array or character array How do we package the collection of digits cell array or structure array CS1OOM Lecture 21 20081111 Can use a numerical array for each digit Can use a character array for each digit 0 1 1 1 0 01110 1 0 0 0 1 10001 0 0 0 1 0 00010 0 1 0 orquot 0010039 0 1 0 0 0 01000 1 0 0 0 0 10000 1 1 1 1 1 11111 Can use a cell array to keep the l0 bitmaps with DD0 set up as a cell array of numerical matrices can do computation as follows M 0 l l l 0 l 0 0 0 l 1ven lltklt10 0 0 0 1 0 I 9 00100 I Mlel 0 1 0 0 0 I if W43 1 0 0 0 0 EEIE disp Middle light is on 1 1 1 1 1 7 end I mer ml D12 M E hceoec 39array953 at quot matrix Still using a cell array to keep the IQ bitmaps with DD0 set up as a cell array of M 01110 I m character matrIces can do computatlon as follows 10001 00010quot E E given lltklt10 0010039 M Dik 0100039 I if strcmpM43 39139 disp H e light is on I 39 III 1 39 end t xol Dl2l MlE hc e oi elj lt fr3 l39D Sva m 39 39 39 39 39C aracters Lecture slides CS1OOM Lecture 21 20081111 Which do you prefer a Numerical matrix for each digit Character matrix for each digit Can use a structure array to keep the l0 bitmaps 11 00 00 01 10 00 11 Using a structure array to keep the IO bitmaps The kth component of array D encodes digit k 1 amp m the digit 2 1 0 1 1 0 1 0 0 0 1111 D2 struct matrix R Which fragment on the right is correct given 1ltklt10 M 30 if no 31 disp Middle light our and M Dk matiix if M43l disp Midd1e light oh39 d if 4 l disp Middle light oh39 M Dkmatzix if M431 disp Midd1e light our end With DlDl 0 set up as a structure array of numerical matrices can do computation as follows given lltklt10 M if M43 disp Middle light is on end M 01110 10001 00010 00100 01000 10000 11111 Can use a structure array to keep the l0 bitmaps D2 struct matrix M a structur39ee arid th omatrixgof characters Lecture slides With DlDl 0 set up as a structure array of character matrices can do computation as follows given lltklt10 D k 39 trCInPM43 1 disp Middle light is on if end CS1OOM Lecture 21 20081111 Choice for storing the bit maps Cell array better than struct array No point in having a structure with one field Numerical array better than char array Plan on doing numerical computations with the bit maps char arrays not handy functinn n TheDigitsO vs 1 is s 10hy1 ee11 array where ink is s 7by5 matrix vs that encndes digit k mm encndes o n ee111o1 m1 00100 01100 00100 00100 00100 00100 V 0 1 1 1 0 Gwen this function v r ritzothz 02 01110 C mwv 5m Fawn 10001 function Hz 00001 singlzdlgll39mu P 00010 H a 00100 d 9 ts o1ooo 11111 Produce a cell array of reverse digits For even digit matrix need to reverse the order of the columns function B reverseCol A 8 B is a matrix obtained by reversing 8 the order of the columns in matrix A nr nc sizeA B zeros nrnc for k 1nc B k A nc k1 end function revD reverseDigits 8 revD is a 10 by 1 cell array 8 revDk is the reversed 7 by 5 bitmap 8 of digit k revD10 encodes 0 D TheDigits revD cell 10 1 for k 1 length D M D k F revM reverseCol M revD k revM end Lecture slides Digital display of a whole number I Example showNumber 2008 I Need to convert the number to a vector of digits I200892 0 0 8 I Then display the digits in the vector sidebyside CS1OOM Lecture 21 20081111 functinn s g h mlumhel n is Digital display at integer n ngt0 How to calculate the difference between 2 bitmaps had an axis sgddi nff it Cnnvert n tg d mistgr nf digits is 1 while ngt0 v remn10 V n f1m7rn10 it Display the digits in v n Thsnigitso it Dk is matrix snsgding digit k A B C fur k11sngthv i k 2F v i ndsxo an Cij abslt Aij Bij drawnigitk11nindex end 1 A and B have same size Section exercise nrnc sizeA a zerosnrnc for r 1 mt If you have an extralonglife light bulb for your 7 E C 1 byS display board at which position would you Crrc abArr 39Brr r39 install this light bulb and and s A and a have same size c abs A B c is a OI matrix where ates that Aij and Bij are fferent Lecture slides CS1112 Lecture 6 2008916 I Previous Lecture Iteration using for I Todays Lecture Iteration usingwhile Review loops condidonals using graphics I Announcements Section in classrooms not lab this week Projectz due Monday 922 Prelim i on Sept 25 at 730pm Email Qatwell cscornelLedu if you have a con ict I We do not use break in this course Register your clicker Example ngon 9 circle Inscribed hexagon circumscribed hexagon ii2 sin27ln n tan7VL As I approaches in nity the inscribed and circumscribed areas approach the area ofa circle How big should I be Find n such that outerA and innerA converge First itemize the tasks define how close is close enough seecf an inifia n cacuafe innerA ouferA for currenf n diff ouferA innerA close enough i f no 7 increase n repeaf above fass Find n such that outerA and innerA converge Now organize the tasks 9 algorithm n gefs inifia vaue Repeaf unfi foerance is reached cacuafe innerA ouferA for currenf n diff ouferA innerA increase n Convergence oi inner and outer area oi regular ngonx on unit circle lprintlmn ntAnt Bnn39 Initialize n innerA and outerA n innerA 3xqrt34 outerA 3qrt3 tol 00l emergence tolerance Compute and print area until convergence while outerA inner t fprintf394d 96I96fn39 n innerA outerA n n l innerA nZxin2pin outerA mxinpincospin end fprintf394d 95i95in39 n innerA outerA Lecture slides Can we replace the initialization of innerA and outerA with the following innerA n2sin2pin outerA nsinpincospin innerA2 outerA4 Both A and B would work NeitherA nor B would work CS1112 Lecture 6 2008916 Common loop patterns Do someih ng I mes Do something an ndef nite number of i mes for k 1n while nutstuppingsignul Initialize loop variables Pattern to do something n times lnitialize loop variables k 1 while k lt n for k 11n do for and whileloops can do the same things In Matlab which claim is true without break forloop can do anything whileloop can i whileloop can do anything forloop can do forloop or whileloop that is the question I forloop loop body repeats a fmed predetermined number of times The quotincrementquot is fmed l whileloop oop body repeats an inde nite number of times under the control of the loop conditionquot all equal off Lecture slides Example Nested sm CS100M Lecture 23 20081118 Previ Semen in n on Lecture Orkng wnn sound mes Today39s Lecture Frequenoomp Toudnmne pnon I Announcement e omputer iab this week arm on e Prehm 3 tonight 7 3079pm A47 in H 7744 7H77777 am i M77 203 MmZmUpsanBW What about the frequency domain yt sin27rgt A puretonequot sound is a sinusoidal function Digitize for Graphics Digitize for Sound 7 s7m77e 77777777 7777 7 s7m77e 77777 777777 7 7 7 Sample Rate 5 32753 7 Sample times t 0 1n tE inal t 0 1E s tE inal a the frequency 7 Digitized 71777 7 Dlgitlzed s 777777 7 777777 e 7 y sin2 piquotnmegaquott F sin2quotpiquotnmegaquott ngher frequency means that yt changes WNW sawMr more rapidly with time EqualTempered Tumquot Adding Sinusoids 77 7777 77777 77777 77777 77777 777777 77 7777 77777 77777 77777 77777 777777 C 77 7777 777 77777 77777 77 777777 7c 7777 77777 77777 77777 777777 777777 4c 7777 77777 77777 77777 777777 777777 77 7777 77777 77777 77777 777777 777777 77 7777 77777 77777 77777 777777 777777 77 7777 77777 77777 77777 777777 777777 7 77 7777 77777 77777 77777 777777 777777 7 77 7777 77777 77777 77777 777777 777777 777 7 77 77777 77777 77777 777777 777777 777777777 77777 77777 77777 777777 777777 M 777 77777 77777 77777 77777 777777 777777 77 r n w 4 71177777 e Lecture slides CS100M Lecture 23 20081118 Adding Sinusoids A frequency is associated with each row amp column F5 32758 urinal 1 So two frequencies are associated With each button t 0 1E s tE inal 697b C3 25152 yC3 sin2pic3t 770 A4 r aszb A4 39 2 39A4t 39 y Slnl P1 9419 3 YC3 yA42 soundyE s I I I 1209 1336 1477 Signal for button 5 What does the signal look like for a multidigit call7 E s 32758 tE inal 25 t 0 1E s tE inal yR sin2pi770t yC sin2pi1336t y YR yC2 sound yE s The Segmentation Problem Fourier Analysis When does a band begin7 Once a band is isolated we know it is the sum of two sinusoids When does a band end7 What are the two frequencies Somewhat like the problem of nding an edge in a digitized picture Use Fourier analysis to lind out Lecture slides CS1112 Lecture 17 Oct 28 2008 I Previous Lecture I Working with images I Today39s Lecture I Characters and strings I Very brief introduction to recursion more later I Announcements I Section will be in the classrooms this week I Project 4 posted Due Thurs I 030 at 6pm Characters amp strings I We have already used strings n input Next number fprintf Answer is ed39 ans I A string is made up of individual characters so a string is a Id array of characters I The character array CSlllZ rocks 39 is oflength I3 has 7Ietters 4 digits I space and I symbol I Use single quotes to enclose characters I 10039 is a character array of length 3 I 100 is a numeric value Strings as vectors Vectors Strings I Assignment I Assignment v 7 3 hello39 Indexing n 42 may vixl 05 I J39 xix ello39 wix o 5 t 424 ti ell39 I nota ion I notation v 25 v is 2 3 A 5 3 art x is abtdeig Appending Appending v 7 o 5 x u 39 v4 2 v is 7 o 5 2 5 x39 x is duckx I Concate 39 I Concatenation v v A 5 x x qmtk vix70524 6 xix dukxqu2k39 Some useful string functions str Cs 1112 1engthstr 1 7 isletterstr 1 1 1 o o o o 0 isspacestr 1 o o 1 o o o 0 lowerstr 1 cs 111239 upperstr 1 cs 111239 ischarstr s str a char array True 1 strcmpstr12 cs 1 Compare strings str12 5 cs False 0 strcmpstr13 Cs 1 False 0 Example capitalize I letter Write a function to capitalize the rst letter of each word in a string Assume that the string has lower case letters and blanks only function str nCaps capsstr Post Capitalize rst letter of each word str partially capitalized string nCaps no of capital letters Pre str string with lower case letters amp blanks only look for the spaces Look For The Spaces Lecture slides Character vs ASCII code str Age 19 a 1d array of characters code doublestr convert chars to ascii values strl charcode convert ascii values to chars mama na lawn CS1112 Lecture 17 Oct 28 2008 Arithmetic and relational ops on characters c 3 gives 2 I 6 5 gives l I letterl e letter2 f I letterlletter2 gives l I c gt 3 gives true I letter letter2 gives false I A 2 gives 67 I char A 2 gives C39 What is in variable g if it gets created d1 Oct 3 d2 Oct 9 x1 d15 x2 d25 g x2x1 What is in variable g if it gets created d1 Oct 13 d2 Oct 29 x1 d156 x2 d2 56 g x2x1 Example toUpper Write a function toUppercha to convert character cha to upper case if cha is a lower case letter Return t e converted letter If cha is not a lower case letter simply return the character cha Hint Think about the distance between a letter and the base letter aY or A Eg a b c d e f g h distance g a 5 BEA A B C D E F G H Of course do not use Matlab s function upper Example removing all occurrences of a character I From a genome bank we get a sequence ATTG CCG TA GCTA CGTACGC AACTGG AAATGGC CGTAT I First step is to clean it upquot by removing all the blanks Write this function function 5 removeChar c s 8 Return string 5 with all occurrences of character c removed Lecture slides Example removing all occurrences of a character I Can solve this problem using iteration check one character one component of the vector at a time New strategy recursion Possible when result can be accumulated iteratively Eg remove all the blanks in string s Same as remove blank in s and remove blanks in s2lengths Eg capitalize rst letter of all words in a sentence Same as capitalize l5I letter of rst word and capitalize l5I letter of the rest of the words am 2 mm mm 17 17 CS1OOM Lecture 26 2009423 Lecture I Previous Lecture Divide and conquerquot strategies Binary seartn Merge sort I Todays Lecture Some ef ciency considerations Divide and conquerquot strategies cont39d recursion Merge sort renovecnsr revisited sierpinskiTr39nnye I Announcements I Project 6 due 430 at l l m I CSI l l1final will be 58 Fri 9002m Tell us now if you nal exam conflict mail Bill Hogan with your complete exam schedule course s and times Merge sort is a divideandconquerquot strategy BIEBIBIBIBIBIBIB BIBIBIEB BIBIEBIB BIEBBIEB BIEBBIEB BIIBIIBIIBIIBIIBIIBIIBII E E E function y mergeSortx 8 X is a vector y is a vector 8 consisting of the values in X 8 sorted from smallest to largest n lengthx if n x else m floorn2 y1 mergeSort x 1 m y2 mergeSortxm1n F Y merge YlIYQ function z merge xy n lengthx m lengthY z zeros 1 nmF i 1 1y for iz1 nm 21z yiy iy iy1 elseif iygtm ziz xix ix ix 1 elseif xix lt yiy ziz xix ix ix 1 else 2iZ yiy iy iy 1 How do merge sort insertion sort and bubble sort compare I Insertion sort and bubble sort are similar I Both involve a series of comparisons and swaps I Both involve nested loops I Merge sort uses recursion slides function x insertSortx 8 Sort vector x in ascending order with insertion sort n 1engthx for i 1n 8 Sort x1i1 given that x1i is sorted Fquot 39 w 50quotquot 31mm 5quot m is It u s r6 rs 1A1 CS1OOM Lecture 26 2009423 How do merge sort and insertion sort compare I First nd out by timing benchmarking the two functions I In Matlab l tic resets timer I too returns the time elapsed since tic Which method is more efficient How do merge sort and insertion sort compare I Merge sort I Insertion sort worst case takes j operations to insert an element in a sorted array of elements In total for big N length I Insertion sort is done inplace merge sort recursion requires much more memory How to choose I Depends on application I Merge sort is especially good for sorting large data set but watch out for memory usage I Insertion sort is order N2quot at worst case but what about an average case If the application requires that you mainmin a sorted array insertion sort may be a good choice Why not just use Matlab39s sort function I Flexibility I Eg to maintain a sorted list just write the code for insertion sort I Eg sort strings or other complicated structures I Sort according to some criterion set out in a function le Observe that we have the comparison x j1ltx j The comparison can be afunction that returns a boolean value I Can combine different sortsearch algorithms for speci c problem Expensive function evaluations I Consider the execution of a program that is dominated by multiple calls to an expensivetoevaluate function eg climate simulation models T f h t k TlmE spent an evaluatlng a functlun WE E El WSWquot as S Tutal time I Can try to improve ef ciency by dealing with the expensive function evaluations slides Dealing with expensive function evaluations I Can the function code be improved I Can we do fewer function evaluations Consider function fgtlt lfd1ere are many function calls and few distinct values of x can get subsmntial speedup Only speeds up main program execution it still takes time to do the precompumtion CS1OOM Lecture 26 2009423 What are some issues and potential problems with the table lookup strategy Accuracy need a dense grid to get high accuracy x f x 9 signi cant memory 1 1 01 usage 2 2 67 I If an exact Xvalue is not 3 5 71 found need some kind of 4 9 12 approximation 5 7 98 I lncur searching cost ifthe Xvalues are not simple A ind39ces I Feasible in high dimensions Precalculate and multi le dependent store these values vanab e 7 eg in a vector H Example removing all occurrences of a character I Can solve using iteration check one character one component of the vector at a time I Can solve using recursion I Possible when result can be accumulated iteratively I Eg remove all the blanks in string s Same as remove blank in s l and remove blanks in s2lengths mllnn s remecnnuc sl 1 mummm xel else u my 2 e SUD xnimvechaxlc s2lengthslll s remvecnnuc s2lengthslll end end Lecture slides Back to Recursion I Merge sort I Remove all occurrences of a character from a string gc aatc gga c gcaatcggac function 5 removecharc s 1 Return string 5 w ith character 2 removed a Base case if 1engths nothing to do retu n is rem 39ning s with char 2 removed 51 removecharc s2lengths return string is t the re aining s with char 2 removed 5 removecharc s2lengths d CS1112 Lecture 3 200894 I Previous Lecture l Variables amp assignment I Builtin functions I Input amp output names use comments I Today39s Lecture I Branching conditional statements I Good programming style meaningful variable I So far all the statements in our scripts are executed in order I We do not have a way to specify that some statements should be executed only under some condition I We need a new language construct W Consider the quadratic function qxx2bxc on the interval L R IWhich is smaller qL or qR I Ils the function strictly increasing in L R IWhat is the minimum value of qx in L R W I What are the critical points I End points xL xR Iixlq x0 x qx xZ bx c q x 2xb q39x0xe Problem I Write a code fragment that prints yes if qx increases across the interval and no if it does not Quadratic qx XA2 bx c b c input Enter L R 8 b input Enter c input Enter L R input Enter Lecture slides 8 Determine whether q increases 8 across LR Xc b2 CS1112 Lecture 3 200894 The Situation qxx2bxc 6647 qxx2bxc Ixc b2 gt X L R X 80 what is the requirement qx x2 bx 1 o xc 472 Determine Whether q increases across LR xc b2 if fprintf Yesn else fprintf Non L R X end Relational operators lt Less than gt Greater than lt Less than or equal to gt Greater than or equal to diSP Yes 39 Equal to Not equal to fprintf Yesn Lecture slides CS1112 Lecture 3 200894 Consider the quadratic function qx x2 bx c on the interval L R llS the function strictly increasing in L R fWhich is smallele qL39 o39rq4R IWhat is the minimum value of qx in L R Problem 2 Write a code fragment that prints qL is smallerquot if qL is smaller than qR lf qR is smaller print qR is smallerquot Algorithm v0 calculate qL calculate qR lfqL lt 4a print 39q at L is smaller otherwise print 39q at R is svnaLLer39 Algorithm v01 caLcuLate XD If distance ET is svnaLLer than distance 74 print 39q at L is svnaLLev othemise print 3914 at R is smallerquot Do these two fragments do the same thing given X y given X y if Xgty if ygtx disp alpha disp beta else else disp beta disp alpha end end Lecture slides Algorithm v1 caLcuLate XD If distance El is svnaLLer than distance T print 39qL Less than qE othemise print 39qR Less than or equai ta qL CS1112 Lecture 3 200894 Algorithm v2 oanLate X If distanceij is same as distam Priwt 39qL is equal to qR otherwise ifxT Ls shorter thaw Prim 39qL Less than qR ckhcnvke Print 39q1z Less than qL 95 Which is smaller qL or qR xc bl2 x at center if absxcL absxcH disp qL and qR are the same39 elseif absxcL lt absxcR disp qL less than qR39 else disp qR less than qL39 9 Which is smallerI qL or qR qL LL bL c qL qR H R bH c qR if qL CIR disp qL and qR are the same39 elseif qL lt qR disp qL less than qR39 else disp qR less than qL39 end 95 Which is smaller qL or qR qL LL bL c qL qR RR bR c qR if qL qR disp qL and qH are the same fprintf q value is 9sfn l qL elseif qL lt qR disp qL less than qR39 else disp qR less than qL39 end Consider the quadratic function qx x2 bx c on the interval L R What if you only want to know if qL is close to qR 95 Is qL close to qR tol 194 tolerance QL LtL bL c qR R R bR c if absCILqR lt 101 dispvql is close to QH end mpor tant parameter and define T33 lcommen tl Lecture slides CS1112 Lecture 3 200894 Do these two fragments do the same thing given x y given x y if xgty if xgty disp alpha disp alpha else end disp beta if ygtx end disp beta end Simple if construct statements to execute if is true else statements to execute if v end is false Even simpler if construct statements to execute if is true The if construct if statements to execute if is tIue elseif statements to execute if is false but is tIue else statements to execute if all previous conditions are alse s f r of 2 92 mm quotmine 52 branch v2 MY 2 can hem a most one Things to know about the if construct I branch of statements is executed I There can be elseif clauses I There can be else clause I The else clause in the construct I The else clause boolean expression Lecture slides The value of a boolean expression is either true or false Lltxc ampamp xcltR This compound boolean expression is made up of two simple boolean expressions Each has a value that is either true or false Connect boolean expressions by boolean operators and or not 85g 1 CS1112 Lecture 4 20090129 I Previous Lecture Variables a b and c have whole number values True or false This fragment prints Yes if there is a right triangle with side lengths a b and c and prints No otherwise I Branching I Logical operators I Today39s Lecture if aAz bA2 CA2 I More branching nesting d W I Think about repetition lsP es else I Announcements dlsp N0 I Project PI due today at Ipm and I Register your clicker with CIT by Feb 6 Use the link on course website W Consider the quadratic function qx x2 bx C xc 7172 qx x2 bx c on the interval L R min at R Ils the function strictly increasing in L R IWhich is smaller qL or qR I LIWhi at isjth minimum value of Vi39n l Start with pseudocode Set up structure first ifelse condition If xc is between L and R if Lltxc ampamp xcltR Min is at xc else Otherwise Min is at one of the endpoints Mln Is at one of the endpolnts end Lecture slides CS1112 Lecture 4 20090129 Refinement filled in detail for task min at xcquot Re nement detail for task min at an endpoint if LltXc ampamp xcltR if Lltxc u xcltR min is at XC 1 min is at xc inn ch2 bxc 2 inn XCAZ bxc c else 1 min is at one of the endpoints else if 1 xc left of brac et 1 m39 i at L else 1 xc right of bracket Min is at one of the endpoints 1 min is at end Final solution given bcLRXc Notice that there are 3 alternatives9can use elseif if Lltxc u xcltR if Lltxc u xcltR 1 min is at xc 1 min is at xc inn ch2 bxc c inn ch2 bxc c else else 1 min is at one of the endpoints 1 min is at one of the endpoints if xc lt L if xc lt L inn 192 bL c inn Lquot2 bu c else else inn Rquot2 bR c inn Rquot2 bR c TopDown Design Sfafe problem if Lltxc ES xcltR I I XC inn ch2 bxc c elseif xc lt L M39 LAZ bL 39 q 1quot c Sfep 2 else reflnemenf inn Rquot2 bR c 39 end True or false We donquott need The l 39f ke word of all in The A if I y An algorithm is an idea To use an algorithm you must a a anguage 39 choose a programming language and implement the algorithm Lecture slides CS1112 Lecture 4 20090129 Question A stick of unit length is split into two pieces The breakpoint is randomly selected On average how long is the shorter piece Physical experimentO Thought experiment 9 analysis Computational experiment 9 simulation dd 2 ed many l oNeed To w 8 one trial of the experiment reath rand1 if breathlt05 shortPiece breath else shortPiece l breath 8 one trial of the experiment reath rand1 shortPiece minbreath l breath WanT To do many Trials add up The lengThs of The shorT pieces and Then divide by The number of Trials To geT The average lengTh RepeaT n Times 8 one trial of the experiment reath rand1 shortPiece minbreath l breath total total shortPiece Take average PrinT resulT n 10000 8 number of trials total 0 8 accumulated length so far for k 1n one trial of the experiment breath rand1 shortPiece minbreath 1 breath total total shortPiece end aveLength total fprintf Average length is 8fn aveLength Pattern for doing something n times for k 1n Lecture slides CS1112 Lecture 4 20090129 Syntax of the for loop for ltvargt ltstart valuegtltincrgtltend boundgt WW Syntax of the for loop for ltvargt ltstart valuegtltincrgtltend boundgt end Loop body Mom mus my for 00p examp es for k 2053 k takes on thevaluesl153 dispk Noninteger incrementis OK en for k 14 k takes on thevalues 234 di spk Defaultincrement is I en for k o 2 5 k takes onthevaluesOZ46 di spk Increment may be negative end for k 0 2 7 k takes onthevaluesOZ46 di spk Colon expression speci es a humid end for k 52 1 dispk en Loop header speci es all the values that the index variable will take on one for each pass of the loo Eg k 31 7 means k will take on the values 3 4 5 6 7 one at a time mm me my 5 Lecture slides The Google Page Rank Problem Background Index all The pages on The Web from 1 To N N is around ren billion The PageRank algor39i rhm orders These pages from mos r impor ran r ro leas r impor ran rquot I r does This by analyzing links no r conTenT Key Ideas Random Web Surfer Transition Probability Ma rr39ix TPM Fr39om Link Connec rivi ry Ma rr39ix To TPM Fr39om TPM To Page Rank Island Hopping Transition Probability A Random Process Suppose There are a 1000 people on each island AT The sound of a whis rle They hop ro ano rher39 island in accordance wi rh rhe ou rbound pr39obabili ries Migra rion 0T 1er Time STepquot New Dis rribu rion T 0 T 1 Island 1 1000 1000 Island 2 1000 1300 Islan 3 1000 700 RepeaT The Process Tl T2 Island 1 1000 1120 Island 2 1300 1300 Island 3 700 580 Af rer 100 I rem rions T 99 T 100 Island 1 114285 114285 Island 2 135714 135714 Island 3 50000 50000 A S ra re Vec ror39 Describes The Sys remquot a r Each T 1000 1000 1000 0 1000 1300 700 T1 1120 1300 580 T2 1143 1357 500 T 100 In The LimiT They Converge 1000 1000 1000 0 1000 1300 700 T1 1120 1300 580 1143 1357 500 mLoumgt 395 mi US coluzboga mf mEEcxm MB Transi rion Probabili ry Army Pij is the probability of hopping form island j to island i Formula for39 The New S ra re Vec ror39 w from Old S ra re Vec ror39 v Wl W2 W3 2vl 6v2 2V3 7vl 3v2 3v3 lvl lv2 5V3 Formula for39 The New S m re Vec ror39 w from Old S ra re Vec ror39 v Wl Pllvl P12v2 P13v3 W2 P21vl P22v2 P23v3 W3 P31vl P32v2 P33v3 The General Case function w UpdatePv lengthv zerosnl I w for iln for jln Wi Wi Pijvj end end S ra rionary Vec ror Compu ra rion function werr StatPvtolkMax w UpdatePv Err maxabswv k 1 while kltkMax ampamp errgttol V W vaQWS EEWVW w UpdatePv ll err maxabswv k kl end Now Regard The Islands As Webpages Rank Pages in Impor rance 2 gt 1 gt 3 From Island Hopping To Web Surfing Now Imagine an A roll wi rh 10 Billion Islands The Web The Migra ring Islanders become random Web surfers How do we genera re The Transi rion probabilities The ConnecTiviTy Army CA 01001010 10000011 01001000 10110100 Gij is 1 if There is a link on pagej To page i 00010010 01100100 G 10000010 00100100 From CA To TransiTion Pr39ob Aregy 01001010 10000011 01001000 10110100 00010010 01100100 10000010 00100100 12 c 14 13 b a P Connec rivi ry9 Transi rion nn sizeG P zerosnn for jln Pj GjSumGj end From S ra rionary Vec ror v To PageRank v widx sor39Tv PageRank for kl8 j idxk index of kth largest PageRankj k end v widx sor39Tv PageRank The Island Hopper is a Random Surfer RepeoT You are on a webpoge There are m ou rlinks Choose one of random Click on The link Go There InLink Rank 3 01001010 IT m ltIT o M MD m I 324 100 100 001 010 001 001 010 101 00010010 01100100 10000010 00100100 PageRank Inans In Link Rank is Flawed You can improve your39 inlink ranking by Setting up millions of dummy webpages each of which poin rs To your39 webpage Wi rh PageRank your39 webpage is impor ran r if o rher39 impor ran r webpages link To i r PageRankValue Shakespeare SubWeb n4383 0012 O c 4 o o o o O O O O O O O O I A G I O Shakespeare Web Inlink Profile I I 500 1000 1500 Shakespeare Web PageRank Profile I I 2000 2500 Page Index 3000 3500 4000 4500 500 1000 1500 2000 2500 Page Index 3000 3500 4000 4500 PRank ooqmmpwaH InRank 24 417 110 14 68 8 37 54 2 261 67 118 50 Na r39l Par39ks SubWeb n4757 PRank National Parks Web Inlink Profile I I I 1000 1500 2000 2500 3000 3500 4000 4500 5000 Page Index 0 500 National Parks Web PageRank Profile I I I PageRankValue 1000 1500 2000 2500 3000 3500 4000 4500 5000 Page Index 0 500 ooqmmpwaH InRank 100 77 386 62 110 37 109 127 32 28 830 169 168 64 Q g 300 PageRankValue SubVVebn6049 Basketball Web lnlink Profile I BaskeTbaH 700 600 500 E 400 E 200 1 00 00 lllll1llolcl u L ll umll ll Illllh lull llllllllll l 0 2000 3000 4000 5000 6000 Pagelndex 7000 Basketball Web PageRank Profile I 0 1000 2000 3000 4000 6000 7000 Page Index 5000 PRank ooqmmpwaH InRank 20 19 61 23 43 91 28 85 358 313 71 68 Back To The Random Surfer RepeoT You are on a webpoge There are m ou rlinks Choose one of random Click on The link Go There h W n UK iquot 39 3957 Modified Rules for The Random R T Web Surfer epea You are on a webpage If There are no ouTlinks Pick a random page and go There else Flip an unfair coin if heads Click on a random ouTlink and go There else Pick any page aT random and go There end end The Unfair Coin I r comes up heads wi rh probability p 85 This value works bes rquot The Google Page Rank Problem Background Index all The pages on The Web from 1 To N N is around Ten billion The PageRank algoriThm orders These pages from mosT imporTanTquot To leasT imporTanTquot IT does This by analyzing links noT conTenT Key Ideas Random Web Surfer TransiTion ProbabiliTy MaTrix TPM From Link ConnecTiviTy MaTrix To TPM From TPM To Page Rank Island Hopping 3 Transition Probability A Random Process Suppose There are a 1000 people on each island AT The sound of a whisTle They hop To anoTher island in accordance wiTh The ouTbound probabiliTies MigraTion aT 13 r Time STepquot RepeaT The Process T 1 T 2 Island 1 1000 1120 Island 2 1300 1300 Island 3 700 580 A S ra re Vec ror Describes The Sys remquot of Each T 1000 1000 1120 1143 1000 1300 1300 00 1357 1000 700 580 500 T 0 T 1 T 2 T 100 New DisTr39ibuTion T 0 T 1 Island 1 1000 1000 Island 2 1000 1300 Islan 3 1000 700 AfTer39 100 ITer39aTions T 99 T 100 Island 1 114285 114285 Island 2 135714 135714 Island 3 50000 50000 In The LimiT They Converge 1000 1000 1120 1143 1000 1300 1300 1357 LeT39s Examine The Pr oducTion of The STaTe VecTor39s TransiTion ProbabiliTy Array Pij is the probability of hopping form island j to island i Formula for The New STaTe VecTor w from Old STaTe VecTor v wl 2vl 6V2 2V3 W2 7vl 3V2 3V3 W3 lvl 1V2 5V3 Formula for The New STaTe VecTor w from Old STaTe VecTor v w1 P11v1 P12v2 P13v3 w2 P21v1 P22quotV2 P23quotV3 w3 P31v1 P32quotV2 P33quotV3 The General Case function w UpdatePv n 1engthv w zerosnl for iln for jln wi wi Pijvj end end STaTionar y VecTor CompuTaTion function w err Stat Pv tol kMax w UpdatePv Err maxabsw v i k 1 while kltkMax ampamp errgttol w w UpdatePv err maxabsw v k k1 Now Regard the Islands As Webpages Rank Pages in Importance 2 gt 1 gt 3 From Island Hopping to Web Surfing Now Imagine an quotAtollquot with 10 Billion Islands The Web The Migrating Islanders become random Web surfers How do we generate the transition probabilities From CA to Transition Prob Argay a13 b12c14 6ij is 1 if there is a link on page j to page i Connectivity Transition 1111 sizeG P zerosnn for j1n Pj GjsumGj end From Stationary Vector v to PageRank V widgtlt sortv PageRank for k1z8 j idxk 95 index of kth largest PageRankj k end V widgtlt sortv PageRank The Island Hopper is a Random Surfer Repeat You are on a webpage There are m outlinks Choose one at random Click on the link Go There In Link Rank Most I m portant In links PageRank InLink Rank is Flawed You can improve your inlink ranking by setting up millions of quotdummyquot webpages each of which points to your webpage With PageRankyour web a e is important if other important webpages link to it Shakespeare SubWeb n4383 PRank InRank WWW mm 1 24 ma 2 417 Em 3 110 2m 4 14 5 l ll l ll 5 5 Ill lllil ill l llilili ii ll ill 5 9 sun man m In ux nan um nm a 7 37 Magnum mmka 9 54 9 2 a 10 261 g 11 1 Hanna g 12 57 m l 13 118 m lllllillilll lni l lllinlimllll ll Mn 14 50 San man mm mm 25m annn um nm H mm 15 3 NaT39I Parks SubWeb n4757 PRank InRank mmmm WM 1 1 in 2 100 gm 3 77 gm 4 385 H 5 52 m iin thi ii i ii iii A m 111 5 110 San mm m mpmum 35m nan sun 5 7 37 manawmsvmb Piwhnk mie 8 9 127 1o 32 11 28 nms m 12 830 W l l 13 159 iii ninmi mm ii J H Hi 14 158 San mm m man 2mm 3m 3m nan sun an mm 15 54 BaskeTball SubWeb n6049 PRank InRank sadismma m pm mmwm am 1 2 5m m 2 1 3m 3 20 m I 4 19 m iii u i ii Mild iiii miii iiimmi I 5 3 mm mm magma snnn ma 7 n 5 51 mm WWW 7 23 8 43 W 9 91 W 10 28 am 11 85 nuns 12 358 ii mm m Hm Ii 1 ii ii i 13 313 mm mm am am snnn ma 7 8 mm 14 71 15 58 Back To The Random Surfer RepeaT You are on a webpage There are m ouTIinks Choose one aT random Click on The link Go There The Unfair Coin IT comes up heads wiTh probabiIiTy p 85 This value works besTquot Modified Rules for The Random R Web Surfer epea You are on a webpage If There are no ouTIinks Pick a random page and go There e Flip an unfair coin if heads Click on a random ouTIink and go There else Pick any page aT random and go There d Previous Lecture Developing algorithms Nested loops Today s Lecture Finiteinexact arithmetic Plotting continuous functions using discrete values Introduction to arrays Announcements Project 2 due today at lpm Prelim on 2l9 Thurs 730pm February 12 2009 Lecture 8 Find the biggest rectangle Here39s the biggest rectangle you drew I 5 that the user speci es using mouse clicks I Color the biggest one red February 12 2009 Lecture 8 3 Find the biggest rectangle develop an algorithm thebiggestrectangtyoudrewi I What are the main tasks I Draw 5 yellow rects I Find the biggest one I Draw biggest one in red I Repetition is needed Which kind I Finite iteration forIoop I Do I need to keep track of all 5 rectangles I No February 12 2009 Lecture 8 4 The sawy programmer Learns useful programming patterns and use them where appropriate Seeks inspiration by working through test data by hand Asks What am I doing at each step Sets up a variable for each piece of information maintained when working the problem by hand Decomposes the problem into manageable subtasks Re nes the solution iteratively solving simpler subproblems rst Remembers to check the problem s boundary conditions Validates the solution program by trying it on test data February 12 2009 Lecture 8 5 Screen Granularity 08 06 After how many halvings will the disks disappear 04 02 02 04 06 08 February 12 2009 Lecture 8 Xeno s Paradox I A wall is two feet away I Take steps that repeatedly halve the remaining distance I You never reach the wall because the distance traveled after n steps 39239A l2n 2 l2n February 12 2009 Lecture 8 10 Example Xeno disks Draw a sequence of 20 disks where the k1th disk has a diameter that is half that of the kth disk 08 06 04 02 The disks are tangent to each other and have centers on the xaxis 02 o4 06 08 First disk has diameter 1 and center 12 0 February 12 2009 Lecture 8 11 Example Xeno disks What do you need to keep track of 06 0 Diameter cl 0 Position Left tangent point x 02 O2 o4 O6 X d 1 1 0 1 2 01 12 3 0112 14 February 12 2009 Lecture 8 12 Xeno Disks DrawRect012239k39 Draw 20 Xeno disks Xeno Disks DrawRect012239k39 Draw 20 Xeno disks for k 120 end Xeno Disks DrawRect012239k39 Draw 20 Xeno disks d 1 X 0 Left tangent point for k 120 end Xeno Disks DrawRect012239k39 Draw 20 Xeno disks d 1 X 0 Left tangent point for k 120 Draw kth disk Update x d for next disk end Xeno Disks DrawRect012239k39 Draw 20 Xeno disks d 1 X 0 Left tangent point for k 120 Draw kth disk DrawDiskxd2 0 d2 y Update x d for next disk x xd d d2 end Here s the output Shouldn t there be 20 disks February 12 2009 The screen is an array of dots called pixels Disks smaller than the dots don t show up The 20th disk has radiuslt000001 Computer arithmetic is inexact I There is error in computer arithmetic floating point arithmetic due to limitation in hardware Computer memory is finite I What is Oquot6 l OOOOOOOOOOOOOOO in real arithmetic I in floating point arithmetic IEEE I Read Sec 43 February 12 2009 Lecture 8 19 Patriot missile failure In l99l a Patriot Missile failed resulting in 28 deaths and about IOO injured The cause wwwnamsanamjntgallerysysmms February 12 2009 Lecture 8 20 Inexact representation of timenumber l System clock represented time in tenths of a second a clock tick every O of a second I Time number of clock ticks X O exact value 00011001100110011001100110011 0001100110011001100110011 vaue in Patriot System Error or 0000200095 February 12 2009 Lecture 8 21 Resulting error after IOO hours 000000095 x I 00x60x60 034 second At a velocity of I700 ms missed target by more than 500 meters February 12 2009 Lecture 8 22 Plot a continuous function from a table of values sinx Plot based on 5 points February 12 2009 Lecture 8 23 Plot based on 200 discrete points but it February 12 2009 looks smooth sinx Lecture 8 Generating tables and plots A vector 5 a ctors x Y are Ve of values 1 dimensional list x linspace02pi9 y sinx plotxy sinx 1 00 00 04 02 0 02 04 0e 08 1 I I I I I I I 1 0 1 2 3 4 5 6 7 Note x y are shown in columns due to space limitation they should be rows Builtin function linspace x linspace135 x 10 15 20 25 30 x lins ace0 p 1 1 i x 000 01 002 T 099 100 Left endpoint umber Right endpoint 0f DOintS February 12 2009 Lecture 8 26 How did we get all the sine values February 12 2009 Lecture 8 27 Examples of functions that can work with arrays February 12 2009 Lecture 8 Does this assign to y the values sin0 sin sin2 sin90 x linspace0pi290 Y sinx February 12 2009 Lecture 8 29 Can we plot this sin5x eXp x 2 for February 12 2009 Lecture 8 30 Can we plot this sin5x eXp x 2 for fx 1x2 2ltXlt3 Yes x linspace23200 y sin5xexp x21 x 2 plot 2 y I I I EIement byelement arithmetic operations on arrays February 12 2009 Lecture 8 Elementbyelement arithmetic operations on arrays Also called vectorized code x linspace23200 y sin5xexpx21 xA2 Contrast with scalar operations that we ve used previously a 21 b sin5a February 12 2009 Lecture 8 33 Vectorized addition x 1E 39lt z Matlab code z x y February 12 2009 Lecture 8 Vectorized subtraction Matlab code z x y February 12 2009 Lecture 8 Vectorized code a Matlabspeci c feature See Sec 41 for list of vectorized arithmetic operations I Code that performs elementbyelement arithmeticrelationalIogical operations on array operands in one step I Scalar operation x y where x y are scalar variables I Vectorized code x y where x andor y are vectors If x and y are both vectors they must be of the same shape and length February 12 2009 Lecture 8 36 Vectorized multiplication Matlab code C a b February 12 2009 Lecture 8 Vectorized elementbyelement arithmetic operations on arrays gt III II III II I III II A dot is necessary in front of these math operators February 12 2009 Lecture 8 Shift Y El ll w Matlab code z February 12 2009 zanmm Y Reciprocate quot4 H H H II N H I a a U1 Matlab code z x y February 12 2009 Lecture 8 40 Vectorized elementbyelement arithmetic operations between an array and a scalar I I I I I I I I I I A dot is necessary in front of these math operators iTii39ie mm 39 February 12 2009 Lecture 8 41 Color is a 3vector sometimes called the RGB values I Any color is a mix of red green and blue 04 06 0 I Each component is a real value in 0 l I 0 0 0 is black February 12 2009 Lecture 8 I Example colr 42 Fading Xeno disks I First disk is yellow I Last disk is black invisible I nterpolate the color in between February 12 2009 Lecture 8 43 Draw n Xeno disks d 1 X 0 Left tangent point for k lzn Draw kth disk DrawDiskxd2 0 d2 y X xd d d2 February 12 2009 Lecture 8 44 Draw n Xeno disks d 1 X 0 Left tangent point for k 1n O 6 Draw kth disk DrawDiskxd2 0 d2 1 1 0 X xd d d2 February 12 2009 Lecture 8 45 Draw n fading Xeno disks d 1 X 0 Left tangent point yellow 1 1 0 black 0 0 0 for k 1n Compute color of kth disk Draw kth disk DrawDiskxd2 0 d2 x xd d d2 February 12 2009 Lecture 8 46 Linear interpolation February 12 2009 Lecture 8 47 Linear interpolation 9105 900 900 2 February 12 2009 Lecture 8 48 Linear interpolation 9105 900 910 125 5 1025 1 4 11 3 4 3910 mmgi 9 9 9 91050 2439g11 2439g10 g1075 3439g11 1439g10 VOLjquot February 12 2009 Lecture 8 49 Linear interpolation 110 M83 025 195 A C v 9 1 o February 12 2009 9105 900 910 910 0439g3911 4439g10 g1025 1439g11 3439g3910 g1050 2439g11 2439g3910 g1075 3439g11 1439g3910 g11 4439g11 O439g10 If 911 1f g10 Draw n fading Xeno disks d 1 X 0 Left tangent point yellow 1 1 0 black 0 0 0 for k 1n Compute color of kth disk Draw kth disk DrawDiskxd2 0 d2 x xd d d2 February 12 2009 Lecture 8 Draw n fading Xeno disks d 1 id kn gt knl x o Left tangent pOlnt k 1n yellow 1 0 black 0 0 0 k1n1 for k lzn Compute color of kth disk f colr fblack 1 fyellow Draw kth disk DrawDiskxd2 0 d2 EQEE x xd d d2 February 12 2009 Lecture 8 52
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'