B o b G r o s s , B i o 3 9 / 1 3 9Programming and AlgorithmsB o b G r o s s , B i o 3 9 / 1 3 9Computer Programs•provide instructions to the computer on what to do•can be written at different levels•low level languages are more efficient but more work for programmer•high level languages are easier for programmer and often are intelligible by humans - usually need to be compiled•Compiling turns source code into an executable binary file that can be run by the computerB o b G r o s s , B i o 3 9 / 1 3 9Some Computer Languages•HTML•BASIC•Perl•C++•Java•Javascript•Machine languageB o b G r o s s , B i o 3 9 / 1 3 9Algorithmsis a list of well-defined instructions for completing a taskB o b G r o s s , B i o 3 9 / 1 3 9Opening a Door: Example 1open the doorDONEB o b G r o s s , B i o 3 9 / 1 3 9Opening a Door: Example 2search until door found! walk to door! turn doorknob! open door! DONEB o b G r o s s , B i o 3 9 / 1 3 9Opening a Door: Example 3look straight ahead for a door! if you see a door! ! walk to door! ! tilt your head to look at top of door! ! look for doorknob! ! ! if see a doorknob! ! ! ! extend arm towards doorknob! ! ! ! open hand! ! ! ! grasp doorknob! ! ! ! turn hand! ! ! ! push door! ! ! ! ! if door opens! ! ! ! ! ! DONE! ! ! ! ! if door does not open! ! ! ! ! ! pull door! ! ! ! ! ! DONE! ! ! if don’t see doorknob! ! ! ! look down 10°! if you don’t see a door! ! rotate 10° to right start over at topB o b G r o s s , B i o 3 9 / 1 3 9How Many Rectangles?B o b G r o s s , B i o 3 9 / 1 3 9Are These Rectangles?B o b G r o s s , B i o 3 9 / 1 3 9Are These “Rectangles” The Same Size?Finding a Word: Method 1define variables! p = 1 [current page number being examined]! w = 1 [current word on page being examined]open dictionary to page p! examine word w! if word w matches query! ! DONE! if word w does not match query! ! if not at last work on page! ! ! w = w + 1 (increment w by 1, add one to w, w++)! ! if at last word on page! ! ! p = p + 1! ! ! w = 1Finding a Word: Method 1adefine variables! p = 1 [current page number being examined]! w = 1 [current word on page being examined]open dictionary to page p! examine word w! if word w matches query! ! DONE! if word w does not match query! ! if not at last work on page! ! ! w = w + 1 (increment w by 1, add one to w, w++)! ! if at last word on page! ! ! p = p + 1! ! ! w = 1repeat until end of dictionaryB o b G r o s s , B i o 3 9 / 1 3 9Finding a Word: Method 2define variables! w = 1 [word number on page]! first = 1 [first page number to examine]! last = total number of pages in dictionary [last page to examine]! p = a number between first and lastopen dictionary to page p! examine word w! ! if word w matches query! ! ! DONE! ! if word w does not match query! ! ! if word w is alphabetically AFTER query word last = p! ! ! ! p = p - (p-first)/2 [go half way back to beginning]! ! ! ! w = 1! ! ! if word w is alphabetically BEFORE query word! ! ! ! w = w + 1! ! ! ! if new w is on next page first = p! ! ! ! ! p = (last-p)/2 + p [go halfway to end]! ! ! ! ! w = 1(could check last word on page to speed things up)B o b G r o s s , B i o 3 9 / 1 3 9Finding a Word: Method 3define variables! w = 1! first = page number of first tab! last = page number of tab following the first tab! p = a number between first and lastselect TAB in dictionary that has same first letter as your query worduse method 2 with w, first, last, pB o b G r o s s , B i o 3 9 / 1 3 9Base Composition: Method 1define variables! Atot=0,Ctot=0,Gtot=0,Ttot=0 ‘total occurrences for each base! n = 1 ‘position of current nucleotide being examined! len = length of sequencelook at nucleotide at position n! if nucleotide at n is ’A’! ! Atot = Atot + 1! if nucleotide at n is ’C’! ! Ctot = Ctot + 1! if nucleotide at n is ’G’! ! Gtot = Gtot + 1! if nucleotide at n is ’T’! ! Ttot = Ttot + 1! n = n + 1! if n > len ! ! DONE ‘no more bases left to countvalues in Atot, Ctot, Gtot, and Ttot represent the base compositionB o b G r o s s , B i o 3 9 / 1 3 9Base Composition: Method 2define variablesAlist="",Clist="",Glist="",Tlist="" ‘these are string variables, not numbersAtot=0,Ctot=0,Gtot=0,Ttot=0n = 1 ‘position of current nucleotide being examinedlen = length of sequencenuc = identification of the current nucleotide being examined (A, C, G, T)!nuc = nucleotide at position n! if nuc is an ’A’ Atot = Atot + 1! ! APPEND n to Alist ‘assume commas are placed in list as delimiters! if nuc is a ’C’ Ctot = Ctot + 1! ! APPEND n to Clist! if nuc is a ’G’ Gtot = Gtot + 1! ! APPEND n to Glist! if nuc is a ’T’ Ttot = Ttot + 1! ! APPEND n to Tlist! n = n + 1! if n > len! ! DONEAtot = number of entries Alist, Ctot = number of entries ClistGtot = number of entries Glist, Ttot = number of entries TlistB o b G r o s s , B i o 3 9 / 1 3 9Object Oriented Programming•modern way of writing code•large complex programs can be put together by combining individual units of code called objects•each object performs a specific function and operates independently of other objects•objects can interact with each other through messages•easy maintenance of code - can change one object without affecting rest of program•objects can be reusedB o b G r o s s , B i o 3 9 / 1 3 9Base Composition Examplemain program call input object call counting object call output object(count)input object - interacts …