### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Algorithm Design ECS 122A

UCD

GPA 3.75

### View Full Document

## 56

## 0

## Popular in Course

## Popular in Engineering Computer Science

This 2 page Class Notes was uploaded by Ashleigh Dare on Tuesday September 8, 2015. The Class Notes belongs to ECS 122A at University of California - Davis taught by Zhaojun Bai in Fall. Since its upload, it has received 56 views. For similar materials see /class/187716/ecs-122a-university-of-california-davis in Engineering Computer Science at University of California - Davis.

## Reviews for Algorithm Design

### 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: 09/08/15

Review of Linear Recurrence Relations 1 A recurrence relation for the sequence an is an equation that expresses an in terms of one or more of the previous terms of the sequence namely a0 a1 an1 for all integers n with n 2 no where no is a nonnegative integer The initial conditions for a sequence specify the terms that precede the rst term where the recurrence relation takes effect A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relation to Exercise Let an 2an1 7 ang for n 23 4 Determine whether the following sequences are solutions a an 3n for every nonnegative integer n b an 2 for every nonnegative integer n c an 5 for every nonnegative integer n OJ A linear homogeneous recurrence relation of degree k with constant coe cients is a recurrence relation of the form an C171 6272 Ckan7k where c1 cg ck are real numbers and ck 7 O A consequence of the second principle of mathematical induction is that a sequence satisfying the above recurrence relation is uniquely determined by this recurrence relation and the k initial conditions a0 00 a1 Cl ak1 Ckil q THEOREM Let c1 and cg be real numbers Suppose that the characteristic equation r27c1r7cg 0 has two distinct roots r1 and rg Then the sequence an 010471 egang is a solution of the recurrence relation if and only if an 0417 agrg for n O 1 2 where 041 and ag are constants Proof two steps 0 Show that the sequence an with an 0417 04ng is a soliution 0 Show that if an is a solution then an 0417 agrg for some constants 041 and ag U Exercise What is the solution of the recurrence relation an an1 2ang with a0 2 and a1 a Exercise Find an explicit formula for the Fibonacci numbers fn fikl fikg with the initial conditions f0 0 and f1 1 7 THEOREM Let c1 and cg be real numbers with cg 7 0 Suppose that r2 7 cm 7 cg 0 has only one root r0 multiplicity is two Then the sequence an is a solution of the recurrence relation an 010471 egang if and only if an alrg 04gan for n O 1 2 where 041 and 042 are constants 00 Exercise What is the solution of the recurrence relation an 6044 7 gang with initial conditions a01anda167 H H 9 O to Linear nonhomogeneous recurrence relation with constant coef cients 1 where 0102 ck are real numbers and is a function not identically zero depending only on n The recurrence relation an Giana 6272 Ckanik an C1an71 62an72 Ckanik is called the associated homogeneous recurrence relation THEOREM lf alf l is a particular solution of Then every solution is of the form as m where agh is a solution of the associated homogeneous recurrence relation From the theorem7 we see that the key to solving the nonhomogenous recurrence relations is nding a particular solution Although there is no general method for nding such a solution for every function Fn7 we can make an educated guess for a certain types of functions Exercise Find all solutions of an 3an4 2n What is the solution with the initial condition a1 3 Hint try out a particular solution of the form on d7 where c and d are constants Exercise Find all solutions of an 5an4 7 Sang 7 Hint try out a particular solution of the form 07 for some constant c

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

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

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