New User Special Price Expires in

Let's log you in.

Sign in with Facebook


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


Create a StudySoup account

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

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Data Structures and Introduction to Algorithms

by: Americo Huel

Data Structures and Introduction to Algorithms CSE 2100

Marketplace > University of Connecticut > Engineering Computer Science > CSE 2100 > Data Structures and Introduction to Algorithms
Americo Huel
GPA 3.73


Almost Ready


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

Purchase these notes here, or revisit this page.

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

Preview These Notes for FREE

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

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in Engineering Computer Science

This 32 page Class Notes was uploaded by Americo Huel on Thursday September 17, 2015. The Class Notes belongs to CSE 2100 at University of Connecticut taught by Staff in Fall. Since its upload, it has received 23 views. For similar materials see /class/205932/cse-2100-university-of-connecticut in Engineering Computer Science at University of Connecticut.

Similar to CSE 2100 at UCONN

Popular in Engineering Computer Science


Reviews for Data Structures and Introduction to Algorithms


Report this Material


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/17/15
UCONN CSE 2100 w Dynamic Programming CSEZIOO DS amp Algorifhms 1 f verview W UCONN IMm ivm ion Inedimension example IRecurrence Recursion IThe Knapsack Problem ORecurrence OSolufion me rhod OTracing a solufion CSEZIOO DS amp Algorifhms 2 Mofivafion IFacf OSome rimes recursion is very slow Iues rion OWhy CSEZIOO DS amp Algori rhms ORecursion is offen nm uml and ef cient UCONN UC ONN edundancy I IRecursion Speed OSIow because many subproblems can be redundamL CSEZIOO DS amp Algori rhms 4 Sub roblems amp edudancy ISubProblems can even by iden rical 133 Th m WTME cswoo DS amp Algorifhms UC ONN ne Dimension Example iii UCONN IRemember the Fibonacci Numbers OFibO O OFib1 1 OFiblt Fibllt1Fibllt2 public class Fibonacci public Fibonacci public int fibint k if k return 9 else if k1 return 1 else return fibk 1fibk 2 public static void mainString args System outprintln Fib12 new Fibonaccifib12 CSEZIOO DS amp Algorithms 7 ecursion Tree 3 Fib6 Fib5 Fib4 Fib3 F1b3 Fib2 Fib1 Fib2 Fib1 Fib2 Fib1 Fiba Fiba Fiba Fibm Fiba Fibm R Fib1 FibO CSEZIOO DS amp Algori rhms 9 UCONN Bof rom Up Fib2 Fib1 Fib2 N Fib j Fib1 Fib1 FibO Fib1 FibO Fibl FibO CSEZIOO DS amp Algorifhms 11 UCONN a The ecipe W ITwo ingredients OBo rfom up OMemorize in an arrm 0 I 4 5 7 2 3 w Fib0 bo M Fibl bu 0 I I Fibz FibOFibI 0 I I 2 Fiba FibI Fib2 0 I I 2 FibA Fib2 Flb 3 o I I 2 o I I 2 8 0 I I 2 8 I CSEZIOO DS amp Algorifhms 12 The Code UCONN public class Fibonacci public Fibonacci public int fibint k int tab new intk1 tab 9 tabl 1 forint i 2iltki tabi tabi l tabi 2 return tabi public static void mainString args Systemoutprintln Fib12 quot new Fibonacciflb12 csczmo DS amp Algorithms 13 UCONN The Code Even Batten ii public class Fibonacci private int tab public Fibonacci tab new int2tabtab11 public int fibint k if k gt tablength int nt new intk1 forint kklttablengthk ntk tabk forint i tablengthiltki nti ntil ntiZ tab nt return tabi public static void mainString args Systemoutprintln Fib12 new Fibonaccifib12 csezmo DS amp Algorithms 14 The Knapsack IThe Sefup 0A frip in fhe wilderness OWhof do you bring wifh you OSubjecf 0 OYou can carry a limifed weight IIngredienfs 0A limifed capacify backpack Valuable i rems IYour Problem OChoose wha r you bring OChoose valuablewor rhwhile i rems CSEZIOO DS amp Algorifhms UCONN 15 Dilemma 1 f r V 5 R U i j r 4 11 I mm 1quot 1 1 K I v i wquot I 3 FA quot a 1 I if v 139 quot km m i n 11 E 2quot A quot1 E5 1 a i 39539 ll 3 L 0quot quot m CHAN H Michael T jmdrich Rohm m 39l amaq ia w Gawain3mm m3 Ill V f x I villingten Ashhrd 4quot lJ a W quotI V a Ill 0 I E quot x If W39 I quot MW quot f N r raw 35 Am I 1 5 b I I r x Universn yigfr f annectlcuti M a h g e a quot u 0 39 lt E C ov nh v quot 1 f 39H x B S IP Lquot 39 x j 3395 1 x 4 w 1 L J quot Kzt If xxxfr I As K31 gt fa 39 2039km I 0 mi f Iquot w V E 2003 Rand MNraly amp Company e 2093 Navigation 1 qu CSEZIOO DS amp Algorifhms The C a rch l3 UCONN Inly limiled Space INol everylhing is valuable You CANNOT TAKE EVERYTHING OYou MUST CHOOSE IWhal is ralional OMaximize lhe value of wha r you lake OResPecl weigh r limi r CSEZIOO DS amp Algorilhms 17 Formaliza rion IKnapsack Capacify C Decision xi in 01 II rems OSe r of ifems S 1n ltW1V1gt ltw2v2gt ltw3v3gt ltwnvngt n max E 217 39 337 i1 TL such that 2 mi 56139 lt C 71 CSEZIOO DS amp Algorifhms UCONN 18 UCONN t A ecursive Solufion W IIdea OSolve Recursively ODecomposifion OBase case OInducfion CSEZIOO DS amp Algorifhms 19 5 Base Case IthnL isare fhe base cases OSugges rion CSEZIOO DS amp Algorifhms UCONN 21 UCONN a Inducfion 33 IPull if all fogefher OBuild solufion f0 Full problem OFrom solufions of smaller problems OSmaller collecfion OSmaller knapsack CSEZIOO DS amp Algorifhms 22 The ecurrence UCONN ksgtxlt0 O ks0 gtIlt O ksUc 10 maX CSEZIOO DS amp Algorifhms ltigt cZy OVwkSC 23 UCONN ecursive Code ii public class Knapsack private int w private int v private int cap public KnapSackint wint vint cap public int doItint kint c if k 0 return 0 else if c return 0 else int dontTakeProfit doItk 1c int takeProfit wk lt c doItk 1c wkvk 6 return MathmaxdontTakeProfittakeProfit public int doIt return doItwlength1cap public static void mainString args Knapsack ks new Knapsack Systemoutprintln Value of carryon ksdoIt CSEZIOO DS amp Algorithms 24 UCONN Wifh Dynamic rogmmming 3 ISame idea Buf ODo if Boh omup OSave subproblems in an array CO C1 C2 C3 C4 item0 item 1 item2 item3 CSEZIOO DS amp Algorifhms 25 UCONN a Inifializafion egg IInif The Firs r Row OThe Firsf Column 0 C1 C2 C3 C4 itemzo 0 0 0 0 0 0 0 0 0 0 0 item1 item2 item3 c c c e c Q CSEZIOO DS amp Algorifhms 26 Compufa rion 3 UCONN IScan across rows IScan eff fo righf increasing size CO C1 C2 C3 C4 itemZO 0 O O O O 0 O O 0 O 0 0 item1 0 item2 0 4quot I item3 0 O O O CSEZIOO DS amp Algorifhms 27 ne S rep IGrey parf already known 0 C1 C2 C3 C4 item0 0 0 0 0 0 item1 item2 item3 G G G G G G G G G O CSEZIOO DS amp Algorifhms 312 UCONN kslltc max kslt1c ksklcwk vllt ltgt c 2 wk 28 UCONN ne S rep 3 IGrey parf already known kslltc max ksltlc ksklcwk vllt ltgt c 2 wk Q wllt 3 0 C1 C2 C3 C4 item0 0 0 0 0 0 0 0 0 0 0 0 item1 item2 item3 G G G G G G G G G O CSEZIOO DS amp Algorifhms 29 ne S rep g UCONN IGrey parf already known kslltc max ksltlc ksklcwk vllt ltgt c 2 wk CO C1 C2 C3 C4 itemZO 0 O O O O O O O O O 0 0 item1 0 item2 0 item3 0 O O O 0 O CSEZIOO DS amp Algorifhms 30 Oh Final 25qu W UCONN ILocafed in boHom righf corner CSEZIOO DS amp Algorifhms 31 UCONN Any Cafch 2 a 11 works IBuf 015 fhere a po renfial problem CSEZIOO DS amp Algorifhms 32 roblem instance I20 I rems Valuesz 10020015013094125 Weighfsz 50000 48000 52000 49900 IKnapsack capacify 1000000 C0 C1 C2 C3 C4 item0 item 1 item2 item3 CSEZIOO DS amp Algorifhms UCONN 33 O Knapsack amp Complexify W UCONN IKnapsack is OPseudoPolynomial ORunfime depends on Orows Ocolumns Ocolumns depends on knapsack capaci ry OUCH IConclusion OKnapsack is a hard problem CSEZIOO DS amp Algorifhms 34 UCONN 0 Tracing a Solufion quot3 IWifh fhe mafrix we have OThe value of fhe solu rion ONo r fhe acfual selecfion IBuf OWe can recover rhe selecfion From fhe ma rrix Il low OTrace our sfeps backward in fhe ma rrix CSEZIOO DS amp Algorifhms 35 s IAf one point UCONN Tracing rrick W wlo4 ZU101Q1 z maxy x v10 zygt33100 CSEZIOO DS amp Algorifhms 36


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

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

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

Janice Dongeun University of Washington

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

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


"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


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


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:

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

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.