×

Let's log you in.

or

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

×

or

Data Structures

by: Dewitt Paucek

32

0

22

Data Structures CSCD 300

Dewitt Paucek
Eastern Washington University
GPA 3.86

Staff

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.
Staff
TYPE
Class Notes
PAGES
22
WORDS
KARMA
25 ?

Popular in ComputerScienence

This 22 page Class Notes was uploaded by Dewitt Paucek on Sunday October 11, 2015. The Class Notes belongs to CSCD 300 at Eastern Washington University taught by Staff in Fall. Since its upload, it has received 32 views. For similar materials see /class/221503/cscd-300-eastern-washington-university in ComputerScienence at Eastern Washington University.

×

Reviews for Data Structures

×

×

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/11/15
Recursion CSCD 326 Slide 1 2106 Proof by Induction Introduction only topic will be covered in detail in CS 327 Prove Z iNN12 i1 Basis Step show true for trivial case here N 1 forN1thesum is 11 1 21 CSCD 326 Slide 2 2106 Proof by Induction Inductive hypothesis statement is true for N k Inductive step if true for N k show true for N k 1 k1 k 2i k1Zi i1 i1 CSCD 326 Slide 3 2106 Proof by Induction Inductive step k1 Zik1kk12k1k22 i1 so by induction the statement is true for all k cscn 326 Slide 4 2106 Recursion 0 Math definition a a solution to a problem that is defined in terms of a simpler version of itself 0 Programming definition 0 a function which calls itself CSCD 326 Slide 5 2106 Recursion e Recursive definition of Sum of Integers public static int Sum int n assumes n is gt1 if n 1 return 1 else return Sum n 1 n CSCD 326 Slide 6 2106 Factorial Mathematical Definition Mathem tical definition recursive 1 if N1 or NO N NN1 if Ngt1 CSCD 326 Slide 7 2106 Factorial Recursive Method Recursive method for factorial public static int factorial int n int temp SystemoutprintlnquotEntering factorial n quot n mm nmm temp 1 else temp n factorialn1 SystemoutprintlnquotLeaving factorial n quot n return temp Call SystemoutprintlnquotFactorial4quot factorial4 CSCD 326 Slide 8 2106 Stack Frames System Stack used to control which function is currently active and to reverse the order of function calls when returning Stack Frame a variable size piece of memory that is pushed onto thedsystem stack each time a function call is ma e CSCD 326 Slide 9 2106 Stack Frames Stack Frame contains 0 space for all local automatic variables 0 the return address the place in the program to which execution will return when this function ends 0 the return value from the function 0 all parameters for a function with actual parameter values copied in The stack frame on top of the stack always represents the function being executed at any point in time only the stack frame on top of the stack is accessible at any time csco 326 Slide 10 2105 Factorial Trace Return Addr 1 N 4 Return Val System Stack output CSCD 326 Slide 11 2106 Rules of Recursion 0 Always include a terminal case which does not require recursion to calculate a Each recursive call should progress toward the terminal case 0 Assume each recursive call works when designing a recursive algorithm csco 326 Slide 12 2106 Recursive Array Printing public class ArrayPrintDriver public static void printem int array int n int last ifn lt last Systemoutprintln arrayn printemarray n 1 last9 public static void main String args int values new int5 forint i 0 i lt 5 i valuesi i1 printemvalues 0 4 0 cscn 326 Slide 13 2106 Array Printing Trace Ret Addr last 4 larray values n 2 0 CSCD 326 Slide 14 2106 Multiple Recursion Fibonacci Sequence 0 1 1 2 3 5 8 13 21 44 oeach number in sequence is the sum of the previous two numbers except the first two eFibonacci number 0 O Fibonacci number 1 1 call other Fibonacci numbers are defined as the sum of the previous two csco 326 Slide 15 2106 Multiple Recursion public static int fib int n if n lt 1 return n else return fib n 1 fib n 2 Problem multiple calls are made to calculate the same Fibonacci number cscn 326 Slide 16 2106 Problems with Recursion 3 Memory stack exhaustion e if many stack frames are pushed can run out of space for stack 0 if each call allocates much memory either automatically or dynamically heap exhaustion is possible 0 Time 8 each recursive call requires time to set up a new stack frame copy in actual parameter values and transfer execution csco 326 Slide 17 2106 Problems with Recursion Any recursive algorithm can be rewritten using iterative technique it will be longer and more likely to have problems but will run faster csco 326 Slide 18 2106 Recursive Binary Search public int binarySearchComparable anArray Comparable target int left int right ifright lt left return 1 ll target not present else int mid left right I 2 if targetcompareToanArraymid 0 return mid if targetcompareToanArraymid lt 0 return binarySearchanArray target left mid 1 else return binarySearchanArray target mid1 right ll end else cscn 326 Slide 19 2106 Binary Search Analysis 0 Worst case target is not found Analysis proceeds in the same way as for the iterative version only the number of passes is replaced by the number of calls to binarySearch csco 326 Slide 22 2106 Towers of Hanoi Problem disks of varying diameter are all on one peg of three with the largest disks on the bottom and the smallest on the top Goal move all disks from peg A to peg C Rules must move one disk at a time can not place a larger disk on a smaller disk quotl lil th l w a w csco 326 Slide 23 2105

×

25 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

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

Allison Fischer University of Alabama

"I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over \$600 per month. I LOVE StudySoup!"

Steve Martinelli UC Los Angeles

Forbes

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

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