×

### Let's log you in.

or

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

×

or

## Lecture Note - 2 (Chapter 2)

by: NikkitheNotetaker

66

1

14

# Lecture Note - 2 (Chapter 2) COSC 600

Marketplace > Towson University > ComputerScienence > COSC 600 > Lecture Note 2 Chapter 2
NikkitheNotetaker
Towson
GPA 3.9

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

×
Unlock Preview

Algorithm Analysis - Asymptotic Notations - General Rule for Psudo Code - Recursive Functions - Master Theorem - Maximum Sub- sequence Sum Problem
COURSE
Advanced Data Structures and Algorithm Analysis
PROF.
Dr. Yanggon Kim
TYPE
Study Guide
PAGES
14
WORDS
CONCEPTS
Math, Algorithm, Asymptotic Notations, General Rule for Psudo Code, Recursive Functions, Master Theorem, Maximum Sub- sequence Sum Problem
KARMA
50 ?

## Popular in ComputerScienence

This 14 page Study Guide was uploaded by NikkitheNotetaker on Tuesday March 8, 2016. The Study Guide belongs to COSC 600 at Towson University taught by Dr. Yanggon Kim in Spring 2016. Since its upload, it has received 66 views. For similar materials see Advanced Data Structures and Algorithm Analysis in ComputerScienence at Towson University.

×

## Reviews for Lecture Note - 2 (Chapter 2)

×

×

### 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: 03/08/16
COSC 600: Advanced Data Structure and Algorithm Lecture Note ­ 2 (Chapter 2)  Algorithm Analysis Every program depends on ALGORITHM and DATA STRUCTURE. PROGRAM = ALGORITHM + DATA STRUCTURE ALGORITHM: An algorithm describes how to solve a problem. Important features of an algorithm are   Correctness   Robustness  Efficiency Measuring method for correctness is a (step by step) mathematical proof. Efficiency is related to run time, it is the key part of an algorithm. Measuring method for  efficiency is a simple abstraction method (asymptotic analysis which uses time complexity).  Algorithm’s time complexity is how fast or how slow a particular algorithm performs, which  gives the rate/order of growth in terms of variable ‘N’, where ‘N’ is the problem size. It can be defined as a numerical (int) function T(N) versus the input size ‘N’. Here we assume that each statement takes the same unit time to execute, the running time function f(N) is  given as the duration it takes to execute N number of statements. There are 3 cases of running time:  Best case  Average case  Worst case ASYMPTOTIC NOTATION: Asymptotic notations are convenient for describing the worst case running time function,  where the constant coefficients of higher order terms and constant factors can be ignored. The four types of Asymptotic Notations are  Big­Oh notation O(f(N))  Big­Omega notation Ω(f(N))  Big­Theta notation θ(f(N))  Little­Oh notation o(f(N)) Big­O O(f(N)): ASYMPTOTIC UPPER BOUND Definition: T(N)=O(f(N)) if there are positive constants c and N 0such that T(N)≤ c*f(N) where N ≥ N 0 Big­Omega O(g(N)): ASYMPTOTIC LOWER BOUND Definition: T(N)=Ω (g(N)) if there are positive constants c and N 0such that T(N) ≥ c*g(N) where N ≥N 0 Big­Theta θ(h(N)): ASYMPTOTIC TIGHT BOUND Definition: T(N) =θ(h(N)) iff T(N)=O(h(N)) and T(N)=Ω(h(N)) Little­Oh o(p(N)) Definition:  T(N)=o(p(N)) iff T(N)=O(P(N)) and T(N) ≠ θ(P(N)) Example: for(i=0; i<n; i++) { St­1; St­2; St­3; } for(j=0; j<n; j++) { 2 2 St­4; T(n)=3n+2n +1+4= 2n +3n+5 4 n 2 3 St­5;        =O(n )=O(2 )=O(n )=O(n ) 2 2 n 4 }        =Ω(n)=Ω(log  n2=Ω(n )=θ(n )=o(2 )=o(n ) St­6; St­7; St­8; St­9; RULES: Rule­1 If T1(N) = O(f (N)) and T (N)2= O(g(N)), then (a)  T1(N) + T 2N) = max(o(f (N)), o(g(N))). (b)  T1(N) ∗ T (2) = O(f (N) ∗ g(N)). Rule­2 k If T(N) is a polynomial of degree k, then T(N) = θ(N ). Note: k i  Polynomial function p(n)= ∑ i=o  i (ai∞ coefficient, a  k 0). Example:  p(n)=3n +4n +2n +…..10000n 0 5 6 5 4        =θ(n )=O(n )=O(n )=O(n )3        =Ω(n)=Ω(n )=Ω(n )=Ω(n )=Ω(n )=Ω(n ) 5 6 (c)T1(n) / T nn) ≠ min(O(f(n)), O(g(n))) Example: T (n1=1/n > T 1n) / T 2n) = n ≠ O(1/n ) 2 3     2 =1/n Rule­3 Log  N = (log N)  = O(N), where k is constant (logarithms grow very slowly). L’ Hospitals Rule: Lim  N→∞  f (N) / g(N)   = 0, it means f (N) = o(g(N)) (growth rate of g(N) > f(N))  = c ≠ 0, it means f (N) = θ(g(N)) (growth rate of f(N)=g(N))  = ∞, it means g(N) = o(f (N)).  Oscillator, it means no relation Example: 2 2 n +O (n)=O(n )   n ¿ ¿ 1 ¿ 2   ¿ 2 √ n ¿ 1 n −100n=Θ(n ) 2 2   Typical Growth Rate 1/n slow C log N log  N k log  N N Nlog N 1 (N) 4   1 3   (N) 2 (N)   2 N N 3 . . n (1.1) n  2 fast Example: n +200n log   n=θ(n ) 2 1. n +O(n) =O(n )=θ(n ) 2 2. √n = n 1/2 Ω(log n) 3. x=0 for(i=0; i<n; i++) { 2 St­1; T(n)=1+2n =O(n)=O(n )=θ(n) St­2;      } 4. for(i=0; i=n; i++){ for(j=0; j<n; j++) {  St­1;         n               n St­2; } n =O (n2)=θ (n2) T(n)= 2 5. for(i=0; i=n; i++){ for(j=0; j<i; j++) {  St­1;         i               n St­2; }         T(n)=(1+2+3+……n) 2 2 2        =n(n+1)/2=n =O(n )=θ(n ) 6. for(i=0; i=n; i++){ for(j=0; j<i*i; j++) {  St­1;                        St­2; }         T(n)=(1 +2 +3 +……n )=n(n+1)(2n+1)/6=O(n )=θ(n ) 3 3 General Rule for Psudo Code: Rule­1: loop (while, for, ……) At most the running time of the statement inside the loop body times the number of iterations.  Coefficient based on problem size N Rule­2: nested loop The running time of statement multiplied by the product of the size of all the loops. Rule­3: consecutive loop Summation of the running times of the statement inside the loop body times the number of  iterations. RECURSIVE FUNCTIONS: Using Divide and Conquer: A divide and conquer algorithm works by recursively breaking down a problem into two or  more sub­problems of the same (or related) type, until these become simple enough to be  solved directly. The solutions to the sub­problems are then combined to give a solution to the  original problem. 1. Binary Search:  For binary search, the array should be sorted (either ascending or descending order). In  each step, the algorithm compares the search key value with the middle element of the  array. If the keys matches, then a matching element has been found and its index is  returned. Otherwise, if the search key is less than the middle element, then the algorithm  repeats its action on the sub­array to the left of the middle element or, if the search key is  greater, on the sub­array to the right. T(n)=T(n/2)+c n       =(T(n/ 2 ¿+C¿+C       =((T(n/ 2 ¿+C ¿+C¿+C . log n times   .       =T(1)+c+c+c+……………c log (n)       =T(1)+c*log n= O(log n)= θ¿ 2. Merge Sort T(n)=2T(n/2)+O(n)        =(2(T(n/2 )+O(n))+O(n)         . log n        =2 +O(1)+O(2)+…..O(n)        =n+n log n Master Theorem: k T(n)=A*T(n/B)+O(N ), where A≥1, B≥1 logbBA   O( n ) if A> B k k k T(n)= O( N .logn¿  if A= B n ¿ Bk O(   if A< Hanoi Tower: T(N) = 2T(N­1)+1          =2(2T(N­1)+1)+1          =.          =.          =2 +2 +2 +……..2 0          =O(2 ) Example 1: Exponential (Compute X ) N public static long pow(long X, int N) {   //X N  if(N==0) return 1; if(N==1) terminating condition   return X; if(is even(N)) return pow(X*X,N/2); else recursive function return pow(X*X,N/2)*X; } For this program let’s take an example: For 5 (5*5) (5 *5 ) (5 *5 ) (5 *5 ) (5 *5 ) 16 16 1 Another example: For 7   (7*7) *7 (49*49) *49(49 *49 )  (49 *49 ) *49 4 4 1 4  Comparatively more multiplications=>more time Note: O(log N) even the worst case (N is odd) =O(2 log N) ≈ O(log N) MAXIMUM SUB­SEQUENCE SUM PROBLEM A1 A N Given (possibly negative) integers  , A2,A3,…..  find the maximum value of  j ∑ k=i(wk re 1≤i≤j≤N ) Example:               ­2, 11, ­4, 13, ­5, ­2 Possible sub sequences =6+5+4+3+2+1 =21 for N =N(N+1)/2 Approach 1: simplest, trivial way (here i=starting element, j= ending element)  A 1  A 2  …3……………………………………………………...….A N N−1 N−1 j T N = ∑ ∑∑ 1 i=0 j=i k=1 ≈O(N ) ≈ θ(N ) 3 Approach 2: 2 2 T(N)= O(N )≈θ(N ) Approach 3: Divide and Conquer method T(N)=2T(N/2)+O(N)         =O(N log N) ≈ θ(N log N) Approach 4: Linear Time Maximum Contiguous Sub Sequent Sum Algorithm: Here, if any sequence is negative it has to be thrown away as it cannot be the larger sequence. T(N)= O(N)=θ (N ) Majority: Divide and Conquer  T(N)= 2T(N/2)+O(N)= O(N log N)         verification n2 A. Each row and a column the order to be n * n => T(n)= O( ). But for a more  efficient one, we would start by scanning either at last element of the first row, or last  element of the first column. With comparisons, either a match is found we go left, or  we go down. Therefore, the number of comparisons is linear. Worst case T(n) = (2n­1) = O(n).

×

×

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

Jim McGreen Ohio University

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

Anthony Lee UC Santa Barbara

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

Jim McGreen Ohio University

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

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