### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# TOPIC CSCE 590B

GPA 3.61

### View Full Document

## 39

## 0

## Popular in Course

## Popular in Computer Science and Engineering

This 58 page Class Notes was uploaded by Trace Mante MD on Monday October 26, 2015. The Class Notes belongs to CSCE 590B at University of South Carolina - Columbia taught by M. Alekseyev in Fall. Since its upload, it has received 39 views. For similar materials see /class/229571/csce-590b-university-of-south-carolina-columbia in Computer Science and Engineering at University of South Carolina - Columbia.

## Reviews for TOPIC

### 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: 10/26/15

Introduction to Bioinformatics Algorithms Lectures 12 Dr Max Alekseyev USC 2009 Organization Lecturer Dr Max Alekseyev TimePlaceMWF 1115am1230pm SWGN 2A22 Office hours after each lecture or by an appointment SWGN 3A48 Course webpage httpcsescedumaxacsce590b Textbook An Introduction to Bioinformatics Algoritth by N Jones and P Pevzner httpwwwbioagorithmsinfo What is Bioinformatics Bioinformatics is a mutually beneficial collaboration between Biology and Computer Science read Chapter 1 in jonesPevzner For CS Biology provides a motivation for studing new challenging problems and developing new algorithms For Biology CS offers effective and cheap as computer experiments are typically cheaper than biological ones solutions to many tough problems Biological Problem lt lnterp ration inttlen Biological Problem I W 397 r 39 Interpr Bta troh Are r sults mean ngful May be noisy Exe ution Is it efficient Why Bioinformatics Algorithms Usually a biological problem can be transformed into a computational problem in a number of ways that feature different levels of accuracy and complexity Highly accurate models often result in intractable computational problems while less accurate models may produce meaningless results Goal to maintain an acceptable level of accuracy keeping the computational problem effectively solvable Plan Brief introduction to Algorithms Chapter 2 Brief introduction to Biology Chapter 3 Study various biological problems and their computational conunterparts Chapter 4 and up Introduction to Algorithms What they are and why you should care Web Resources on Algorithms Algorithms by S Dasgupta CH Papadimitriou and UV Vazirani 7 L 4 y v i iglf l L ll if Algorithms Course Materials byjeffErickson Design and Analysis of Algorithms by Russell lmpagliazzo Design and Analysis of Algorithms How to Think About Algorithms byjeffEdmonds An everyday algorithm A computational problem Defined by inputs and outputs eg 5 Input amount of money to change M Output set of coins summing to M Require precise formulation 6 Solved by algorithms 6 A prerequisite to an algorithm Pseudocode Assignment Assignment Formal a a b Effect Sets the variable a to the value bl Example b 9 2 L39sz Result The value of a is 2 Pseudocode Arithmetic Arithmetic Format Etfecl Example u 1a7 ba babuquot Addition subtraction multiplication division and exponentia h39on of numbers DIST rl yl12 y2 1 LT H 12 e 113 2 Ely H y2 7 1J1 3 return rlr i 11 DIST11 1112 yZ computes the Euclidean distance between points withcoordinates rly1and 12112 DISTANCE U 3 4 returns 5 Pseudocode Conditional Conditional Format Effect Example Result if A is true 2152 If statement A is true executes instructions B otherwise executes instructions C Sometimes we will omit quotelse C in which case this will either execute B or not depending on whether A is true M1Xu I1 1 if a lt b 2 return I 3 else 4 return a M1Xa b computes the maximum of the numbers a and b For example MAX 99 returns 9 Pseudocode for loops Format Eifect Example Result forieatob Sets i to u and executes insh uctions B Sets i to a i 1 and executes instructions B again Repeats fori 7 a gt 2 a gt 3 b 71179 SUMINTEGERsn 1 sum H 0 2 for it ltu n 3 sum lt sum i 4 return sum SUMINTEGERSn computes the sum of integers from 1 to n SUM INTEGERSUO retumsl gt 2 gt gt 10 e 55 whi 1e loops Formal E ect Example while A is true B Checks the condition A If it is true then executes instructions B Checks A again if it s true it executes B again Repeats until 4 is not true ADDUNTILb l ilt 1 2 total 4 i 3 while fatal 5 b 4 ie 1 l 1 5 mm Iotal l i 2 return i ADDUNT1Lb computes the smallest integeri such that 1 l 2 l I iis larger than I For example ADDUNTIL25 returns 7 since 1l2 l l 7728whichislargerthan25butl l 2 l l 6721 which is smaller than 2139 Pseudocode Array access Array access Format al Effect The ith number of array 21 7 a1 a alr For example if F 11235813thean 2 and F4 3 Example FIBONACCIn F1 H 1 Fg e 1 for i A Hon Fi F Fiil I Fiez return F Result FIBONACCIn computes the nth Fibonacci number FIBONACCI8 returns 21 US Change Problem United States Change Problem Convert some amount of money into thefewest number of coins Input An amount of money M in cents Output The smallest number of quarters q dimes d nickels n and pennies 12 whose values add to M ie 2511 10d 5n p AI and q 1 11 p139s assmall aspossible Pseudocode USCHANGEM 1 while M gt O 2 3 c 4 Largest coin that is smaller than or equal to 111 Give coin with denomination c to customer 4 A I 1 1M 7 c More specifically USCHANGEM Give the integer part of 1V 25 quarters to customer Let remainder be the remaining amount due the customer Give the integer part of remainder 10 dimes to customer Let remainder be the remaining amount due the customer Give the integer part of remainder 5 nickels to customer Let remainder be the remaining amount due the customer Give remainder pennies to customer Inelegant but correct USCHANGEM T t M qt r25 r4 r 25q dt rIO 7 1 10d n r5 r4 r 5n P 7 return q 1 1112 1 2 3 4 5 6 7 8 9 But what about say South Africa Generalized Problem Change Problem Convert some amount uf money 1V1 into given denominations using the smallest possible number of coins Input An amount of money M and an array of d denom inations c 6162 cd in decreasing order of value c1 gtc2 gt gtcd Output A list of dintegers 1233 z39d such that and C2 3 edid M and i1 2392 v id is as small as possible Is this a good solution 77 2510514 BETTERCHANGEM c d 1 TQ IW k 1 2 forls39H ltod illt7725 3 3 1k TCk r lt 77325 2 4 TPT Ck ik klt 2 5 retum39i1iz id i2lt 210 0 rlt 2010 2 klt 3 c 25 10 5 1 0k i3lt 25 0 rlt 205 2 c2520 10 5 1 nope kTizl 2 4 rlt 221 0 Done 3 0 02 A correct algorithm BRUTEFORCECHANGEM c d smal l estN umberO f Coins H 00 for each i1 z39d from 0 0 to Mcl Mcd val39ueOfCo39ins 2L1 239ka if ualueOfCoins 1L1 if numberOvains lt smallestNumberOfCuins smallestN umberO f Coins H 39numbe39rO f Coins bestChange 011232 id 1 2 3 4 5 numberOfCoins ZLI ik 6 7 8 9 return bestChange iterations of first index iterations of second index G How fast is it MCl MC2 Each check does 2dk operations k is constant Hence the total number of operations running time complexity is Mc1 Mc2 Mcd 2dk 2c1cd d Md kc1cd Md Od Md Asymptotic Complexity Finding the exact complexity fn number of basic operations of an algorithm is difficult We approximate fn by a function gn in a way that does not substantially change the magnitude of fn ie gn is sufficiently close to fn for large values of the input size n This quotapproximatequot measure of efficiency is called asymptotic complexity Thus the asymptotic complexity measure does not give the exact number of operations of an algorithm but it shows how that number grows with the size of the input This gives us a measure that will work for different operating systems compilers and CPUs Asymptotic Far Out mmm mun leg 1 nun Log I a qundmtic 11 rtcr 5 ha 3 L r 39 i Huh w slarger un 2 ii f39 islargcr Lhan l 39 The unclinm thile chose hm hm though for v u ougll ah Eamirrclevamand mun an Positivevalued uncdcns with leading terms n39 log v g4 and would exhibii the same basic behavior Ihnugh die Em mspmiivul might be dit39remnt BigO Notation The most commonly used notation for specifying asymptotic complexity is the bigO notation The BigO notation Ogn is used to give an upper bound worstcase on a positive runtime function fn where n is the input size Definition of BigO For a function fn that is nonnegative for all n 2 O we say that fn Ogn quotfn i5 Big0 0f9n if there exist n0 2 O and a constant c gt 0 such that fn S cgn for all n 2 no Order notation BRUTEFORCECHANGEM c d smallestNumberOfCoins lt 00 for each i1 id from 0 0 to NIcl Mcd ualueOfCoins 2L1 ik k if valueOfCui ns JVI if numberOfCoins lt smallestNumberOfCums smallestNumberOfC oz ns 4 numbe39rO f Coins bestChange 011112 i1 1 2 3 4 5 numberOfCoins zz ik 6 7 8 9 return hestChange Od Mquotd BigOmega Notation Similarly gn is used to give a lower bound on a positive runtime function fn where n is the input size Definition For a function fn that is nonnegative for all n 2 O we say that fn gn quotfn is bigOmega of gn if there exist n0 2 O and a constant c gt 0 such that fn 2 cgn for all n 2 no BigTheta Notation Similarly Ogn is used to give a tight bound on a positive runtime function fn where n is the input size Definition For a function fn that is nonnegative for all n 2 O we say that fn 9gn quotfn is bigTheta of gn if fn 09n and fn 9n Examples 01 O09n On Onlogn Onx eg On2 On3 etc Oa eg Ol6 02quot etc On On Constant Logarithmic Linear nlogn Polynomial Exponential Factorial Two quotcomplexitiesquot Algorithms have a complexity that determines their execution speed Problems have a complexity that determines how fast the fastest algorithm can go Sorting can be done in polynomial time Listing all subsets takes exponential time NPcompleteness There is a class of problems that might require exponential time Any problem in this class is in some way equivalent to any other problem It is very unlikely that a polynomial time algorithm exists that can solve any of this class of problems The bad news Many useful problems in biology are NPcomplete eg Traveling Salesman Problem Heuristic or statistical approaches aren t correct but are usually the best choice Proving NPcompleteness for a problem is involved Takeaway lesson consider the possibility that your problem is NPcomplete Good vs Bad Problems 6 Good model system well clear precise Bad allows sillymean solutions Algorithms a Good polytime correct Bad Exponential or worse incorrect Implementations 6 Good as fast as the algorithm Bad dumb coding Good vs Bad Problem Bad sorting 6 Input list of numbers Output a sorted list Good 6 Input a list or numbers a Output a list bb1b2 such that b1 S b2 S and for all i there exists such that aibj and b a Summary Computational problems define mapping from inputs to outputs Algorithms solve computational problems Algorithms can be communicated through pseudocode Two fundamental properties of algorithms are correctness and efficiency Problems also have an inherent complexity How can one design an algorithm given a problem Next steps Sorting Problem Quadratic vs log time Towers of Hanoi Problem Recursion and recurrences Trees Sorting problem Sorting Problem Sort 1 list of integers Input A list of n distinct integers a 111412 an Output Sorted list of integers that is a reordering b 71 E22 bu of integers from a such that b1 lt b lt n lt Intuitive approach Find the smallest element Put it first Find the next smallest element Put it next Repeat until done Example A 7 92 87 1 4 3 2 6 A 192 87 7 4 3 2 6 1 287 7 4 3 92 6 1 2 377187 926 A 1 2 3 47 87 92 6 m 1 2 1 1 187 92 7 1 2 79237 1 2 r3 73792 Pseudocode SELECTIONSORTa n for i 1 to n l 2 j INDEXOFMINai n 3 Swap elements 11 and 1 4 return a INDEXOFMINanay first last 1 indez4 first 2 for k 4 first l to last 3 if arrayk lt arrayindBI 4 index f k 5 return index Asymptotic Complexity IndexOfMin On SelectionSort Calls IndexOfMin On times Also performs constant time operations Onn or Onz A faster way There is a faster way of searching MergeSor c Will be covered in Divide and Conquer Think about it for a while see if you can t figure it out Towers of Hanoi Problem Towers of Hanoi Problem Towers of Hanoi Problem Formal Problem Towers of Hanoi Problem Output 1 list ufmwes that solves the Towers of Hanoi Input An integer 71 Output A sequence of moves that will solve the 7 disk Towers of Hanoi puzzle Easy values of n n0 done nl move from left to right peg done n2 small to middle large to right small to right done n3 Move disk from peg 1 k0 peg 3 il l 7 Move disk from peg 1 to peg 2 7 Move disk from peg 3 to peg 2 J 77 gt Mave disk from peg 1 to peg 3 Al 7 Move disk from peg 2 to peg 1 Move disk from peg 2 to peg 3 Move disk from peg 1 to peg 3 Move top three from left to middle Move bottom one to right Move top three from middle to right Recursion To solve n4 we solved the puzzle for n3 multiple times Generalize the problem Given n a and b move n disks from peg a to peg b H But we quotassumed Key observation we know how to solve it for small values of n So we have HanoiTowerslab We can construct HanoiTowers2ab HT3ab HT4ab etc out of it The impossible trick Assume can opener Assume we have HanoiTowerskab that solves correctly the kdisk general HT problem for some k HanoiTowersklab is easy to write if it can call HanoiTowerskab HanoiTowerskac move largest from a to b HanoiTowerskcb Complete algorithm HANOITOWERSn f39rmnPeg toPeg if n 1 output quotMove disk from peg fromPeg to peg toPeg return I unusedPeg lt 6 fromPeg toPeg HANOITOWERSn 1 fro39rnPegunusedPeg output quotMove disk from peg fromPeg to peg toPeg HANOITOWERS n 1 unusedPeg toPeg return 1 2 3 4 5 6 7 8 Algorithm Design Techniques Brute Force 6 Branch and Bound Greedy rules Dynamic programming 6 Divide and conquer Machine learning

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### 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'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.