×

### Let's log you in.

or

Don't have a StudySoup account? Create one here!

×

or

## TOPIC

by: Trace Mante MD

19

0

30

# TOPIC CSCE 590B

Trace Mante MD

GPA 3.61

M. Alekseyev

These notes were just uploaded, and will be ready to view shortly.

Either way, we'll remind you when they're ready :)

Get a free preview of these Notes, just enter your email below.

×
Unlock Preview

COURSE
PROF.
M. Alekseyev
TYPE
Class Notes
PAGES
30
WORDS
KARMA
25 ?

## Popular in Computer Science and Engineering

This 30 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 19 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?

#### 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 Lecture 3 Dr Max Alekseyev USC 2009 Time Complexity TC is a function of the input length L Eg if input is an integer M then L is proportional to ogM ie L elog M if input is an array of size m with elements 5 E then L 6mlog E TCL is the number of operations steps performed by an algorithm in the worstcase We are not interested in exact value of TCL but rather in its asymptotic behavior as L grows Polynomial TC is good exponential TC is bad 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 eg Traveling Salesman Problem 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 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 Summary Computational problems define mapping from inputs to outputs Algorithms solve computational problems Two fundamental properties of algorithms are correctness and complexity efficiency Problems also have an inherent complexity How can one design an algorithm given a problem 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 Key observation Key observation we know how to solve it for small values of n So we have HanoiTowers1ab We can construct HanoiTowers2ab HanoiTowers3ab HanoiTowers4ab etc out of it Thet ck Assume a can opener Assume we have HanoiTowerskab that solves correctly the kdisk general HT problem for some k HanoiTowersk1ab is easy to write if it can call HanoiTowerskab HanoiTowerskac move largest from a to b HanoiTowerskcb HanoiTowers Algorithm HANOITOWERSn f39rmnPeg toPeg if n 1 output quotMove disk from peg fromPeg to peg toPeg return 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 H a 3 n J 5 O U M a a HanoiTowers Complexity Time complexity measures the number of operations in the worst case For Hanoi Towers it is convenient to define operation as a single disk move Let Tn be the number of disk moves performed HanoiTowern Then Tn 2Tnl 1 Tl 1 From this equation we derive Tn 2n 1 Q What is the asymptotic complexity 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 SelectionSort 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 index 4 first 2 for k 4 first l to last 3 if arrayk lt arrayindBI 4 index f k 5 return index Recursive SelectionSort RECURSIVESELECTIONSORTa first last 1 if firs lt last 2 inder 7 INDEXOFIMINQ firstlust Swap Ifm wil39h Mu ax RECURSIVESELECTIONSORHZIfirst q Mus return a 3 4 5 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 Fibonacci Problem Fibonacci Problem Calz ulnte the 71th Filmnm ri number Input An integer 11 Output The nthFibonacd number F1 7 F1 Fg with F1 7 F2 7 l Recursion Tree RECURSIVEFIBON39 cc1n if n 7 1 or n 7 2 return 1 else a e RECURSIVEFIBONACCIOI e b c RECURSIVEFIBONACCIUI retuxn a b Recursive vs Iterative RECURSIVEFIBONACCI u If n 7 1 or n 7 2 return 1 else a RECURSIVEFIBONACCHH 1 b RECURSIVEFIBONACCIUI 2 returna i b 1 2 3 4 5 6 FIBONACCIn 1 F Q What is the difference pgg1 for 1quot 3 to n Fi H Fi l i Fi 2 return F 2 3 4 5

×

×

### BOOM! Enjoy Your Free Notes!

×

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

Steve Martinelli UC Los Angeles

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Kyle Maynard Purdue

#### "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!"

Steve Martinelli UC Los Angeles

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Parker Thompson 500 Startups

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!
×

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