×

Let's log you in.

or

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

×

or

COSC 600 Chapter 1

by: NikkitheNotetaker

72

0

7

COSC 600 Chapter 1 COSC 600

NikkitheNotetaker
Towson
GPA 3.9

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

×
Unlock Preview

Introduction
COURSE
Advanced Data Structures and Algorithm Analysis
PROF.
Dr. Yanggon Kim
TYPE
Study Guide
PAGES
7
WORDS
CONCEPTS
Math, Algo
KARMA
50 ?

Popular in ComputerScienence

This 7 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 72 views. For similar materials see Advanced Data Structures and Algorithm Analysis in ComputerScienence at Towson University.

×

Reviews for COSC 600 Chapter 1

×

×

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 ­ 1 (Chapter 1)  Introduction To analyze a given algorithm, we need to have some mathematical background.  Some of formulas that aid in analysis are as follows 1) Exponents Definition: The base X raised to power N is equal to product of X multiplied N  many times. The power N in this case is exponent X  XXX....X Exponent Rules: A B AB 5 7 57 12 X .X  X  for example, 2 .2 2 2 A B A.B 5 3 15 (X )  X  for example, (2 ) 2 N N N1 5 5 6 X X  X  for example,  2 2 2 2) Logarithms Definition:  X  B  if and only if  gXB A Theorem 1.1 log B log B C whereA,B,C0, A1 A logCA Theorem 1.2 logABlogAlogB whereA,B0 3) Series A,1 ,2,.3.......,N Let  be a sequence then the sum of the sequence is called  series denoted as N  Ai A1A 2A .3.......A N i1 The easiest formula to remember is N  2 (2 2 2 2 .....2 )2 N11 i1 N if 2 (2 2 2 .....2 )2 N1  i0 The companion formula is N i 1 2 3 4 N AN11  A (A  A  A A .....A ) whereA1 i1 A1 N i A N1 1 if 0  A1, lim  A  lim  N i1 N A1 1A Important formulas used for analysis N 2 N(N1) N  i123....N  1) i1 2 2 N 3 2 2 2 2 2 N(N1)(2N1) N  i 1 2 3 ....N   2) i1 6 3 N 4 3 3 3 3 3 N(N1) 2 N  i 1 2 3 ....N ( )  3) i1 2 4 N k1 k k k k k N  i 1 2 3 ....N  wherek1 4) i1 |k1| N1 (N1)(N11) N(N1) for example i   i1 2 2 N N N N N N(N1)N for example (2i1)135....(2N1)  2i  1 2  1 2  N2 i1 i1 i1 i1 i1 2 if N 100 100  (2i1)(135....199)10,000 i1 Rules:  Rule1 N N N N  f (N)  f (N) 1 N  f (N)  f (i)  f(i1 Nf (i) i1 i1 i1 i1 Rule2 N N N01 f (i)  f (i)  f (i)    i0 i1 i1 100 forexample i  (10 1112....100)  (1 2....1011....100) (1 2....9) i10 100 9 100.101 10.11     i   i1 i1 2 2 N 1 (11  1  1 ....1 )  log N  i 2 22 23 2 N e i1 for exaple 27121722....(5N2) N N1   (5i2)   (5i3) i0 i1 N N1 N1   (5i2)2  5 i31 i1 i1 i1 N N 5(N1)(N2)  5 i2 12  2 3(N1) i1 i1 5N(N1) 5N 15N10  2N2  3N3 2 2 5N 5N4N4 5N 15N106N6   2 2 5N 9N4 5N 9N4   2 2 4) Induction Method Principle of Mathematical Induction: Let P be a property of positive integers such that 1) Base Case: P (1) is true, and 2) Inductive Step: if P (n) is true, then P (n+1) is true. Then P (n) is true for all positive integers. The premise P (n) in the inductive step is called Induction Hypothesis.  Steps for proof by Induction Method 1) Base condition: prove the theorem for base condition. For example, N=1 2) Assume that the given theorem is true for N=k case 3) Using assumption, prove the theorem is true for N=k+1 case step by step Example I N N(N1)  i  For example, proof of1 2 for any positive integer N  Proof Base condition: For N=1 1  i1 L.H.S i1 1(11)1 R.H.S 2 N k iN(N1) for Nk ik(k1) i0 2 i1 2 Assume that  For N=k+1 case, k1  i (12....k(k1)) i1  k(k1)(k1) 2 k (k1)( 1) 2 k2 (k1)( ) 2 (k1)(k2)  2  Theorem is true for n=k+1 case  Theorem is true for any positive integer N Example II For example, proof of Fibonacci number  Let   be Fibonacci number  (F 1,F 1,F 2,F 3,F 5,....,F F F ) F i ( 5 ) for i 1 0 1 2 3 4 i i1 i2 Prove  3 Proof F11 5 istrue Base condition: For i=1 case,  3 5 k Assume that  Fk ( 3 ) for anyk For i=k+1 case, 5 k1 5 k F k1 Fk1 (k 3) ( 3 ) k1 ( 5 ) (1 5 ) 3 3 ( 5 ) (18 ) 3 3 9 8 ( 5 ) (1  ) 3 25 3 5 k13 2 8 ( 3) ( 5 ) .(3 ) ( ) (1 28)( ) k1 3 25 3 i  k1 caseistrue 5) Proof by Counterexample This method of proof involves giving an example that fails the stated theorem,  and hence, disproves the theorem. Fi For example, let   is Fibonacci number F kk is false F 01,F 1,F 22F 3,3.... Proof: F11144121 is not true 6) Proof by Contradiction This method of proof begins with the assumption that the stated theorem is false, and during the process shows that the assumption was wrong and, hence proves the stated theorem.  For example,  Theorem: There is an infinite number of prime. e.g. 2,3,5,7,13,17,19, … Proof: Assume that there is finite number of prime P Let,  k be the largest prime NPP P ........P 1 Let,  1 2 3 k P,P,P........,P None of  1 2 3 kdivide N exactly (  there will be a remainder of 1)  N is a prime number P P  N> ( kis not the largest prime which is contradiction to initial assumption  P that  k is the largest prime)  Theorem is true i.e. there is an infinite number of prime 7) Recursion  Any function that is defined in terms of itself is called recursive function. For example, Divide & Conquer Like Merge Sort for traversing an array, whole array is divided in half, and, then  each half is further divided into half, until search item is found. Rules of recursion: 1. Base cases­must always have some base case that can be solved without recursion 2. Making progress­must always to be a case that makes a progress toward  a base case Example I For example, consider following program Public static int f (int n) {   if (n == 0) return 0; else return f (n/3 +1) + n­1; } If we pass value of n as 10, the program will return f (4) + 9, here we do not know what is f (4) so, the program gets called again with value of n= 4. The program  now returns f (2) +3, the program gets called again with value of n=2 to yield f (1) + 2. The program gets called again with n=1 to yield f (1) + 0. The program gets  called again and again with n=1. This is bad example. To make this example  good one we can change if (n==0) to if (n==1). F (10) à F (4) +9 à F (2) +3 à F (1) +2 à F (1) + 0  Example II Consider another example, Hanoi Tower Problem. This problem involves moving  different size disk from source to destination tower with temporary tower in  between following condition that bigger size disk cannot be placed over smaller  as it will crush smaller disk. In this case, the number of movements needed to  move disks from source, to destination along with movements to and from  temporary tower increases with increase in number of disks and is given by  k formula N (number of disk movements) = 2 1 (k is number of disc). A solution to  the problem is as follows T (n, a, b, c) //n= number of disc, a=source tower, b=temporary tower, c=  destination tower { if (n=1) { move disk from source to destination } else { T (n­1, A, C, B) Move n  disc from source A to destination C T (n­1, B, A, C) } } References 1) LERMA, M. (2003, February 8). MATHEMATICAL INDUCTION. Retrieved September 6, 2014, from  http://www.math.northwestern.edu/~mlerma/problem_solving/results/induc tion.pdf

×

50 Karma

×

×

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

Anthony Lee UC Santa Barbara

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

Bentley McCaw University of Florida

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

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