### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Algorithms and Abstract Data Types CMPS 101

UCSC

GPA 4.0

### View Full Document

## 62

## 0

## Popular in Course

## Popular in ComputerScienence

This 7 page Class Notes was uploaded by Dr. Elyssa Ratke on Monday September 7, 2015. The Class Notes belongs to CMPS 101 at University of California - Santa Cruz taught by Staff in Fall. Since its upload, it has received 62 views. For similar materials see /class/182263/cmps-101-university-of-california-santa-cruz in ComputerScienence at University of California - Santa Cruz.

## Reviews for Algorithms and Abstract Data Types

### 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/07/15

CS 101 Spring 2003 Midterm Review Problems 1 N L J V39 211 Use Stirling s formula to prove that J 8 n Let f n and gn be asymptotically nonnegative functions which are de ned on the positive integers a State the de nition of fn Ogn b State the de nition of f n agn State whether the following assertions are true or false If any statements are false give a related statement which is true a True or False fn Ogn implies fn ogn b True or False fn Ogn if and only if gn Qfn c True or False fn 8gn if and only if 1imfngn L where 0 lt L lt 00 n Use Stirling s formula n 2727 r a 1 81n to prove that lgn 8nlg n e 4H J Consider the following sketch of an algorithm called ProcessArray which performs some unspeci ed operation on an a1ray A1 n ProcessArrayA p q Preconditions p 21 and q S lengthA 1 Do something which takes constant time 2 If p lt q 3 r 9 7p q 1 2 4 ProcessArrayA p r 5 ProcessArrayA r1 q Write a recurrence which gives the running time Tn of this algorithm when called on the full array ProcessArrayA 1 11 Give a tight asymptotic solution to this recurrence 0 1 9 0 Consider the following algorithm mm 1 for 1 e l to 13913 waste a constant amount of time 3 for 1 e l to 7 4 WasteTime l n 2quot 5 ddle around for constant time Write a recurrence which gives the running time Tn of this algorithm Give a tight asymptotic solution to this recurrence Use the Master Theorem to nd asymptotic approximations to the solutions of the following recurrences a Tn 2Tn4 J b Tn 7Tn3 112 Complete the following algorithm called HeapIncreaseKey A i k which sets A1 e maXA1k then updates the heap structure accordingly HeapIncreaseKey A i k 1 if k 2 A139 2 3 Pre 13 1 S HeapSizeA Prove that an n element heap has exactly Ln 2h J Ln 2M nodes at height h Let Tn be the solution to the recurrence 5 n1 Tn 10 112 3TLn3Jn n gt 2 Show that there eXists a c gt 0 such that Tn S cnlgn for all n 2 3 Prove this using induction on 71 not the Master Theorem CMPS 101 Midterm 1 Review Problems N L 4 ON 1 2n 4 Use Stirling s formula to prove that J 8 n Let f n and gn be asymptotically nonnegative functions which are de ned on the positive integers a State the de nition of f n Ogn b State the de nition of fn agn State whether the following assertions are true or false statement which is true 21 f0 0gn implies f0 0gquot b fn Ogn if and only if gn Qfn c fn 8gn ifand only if liinfngn L where 0 lt L lt 00 If any statements are false give a related Prove that 8fn r 8gn 8fn r gn In other words if hln 8fn and h2 n 8gn then M70 11201 8fquot gn Use limits to prove the following these are some of the exercises at the end of the asymptotic growth rates handout a If Pn is a polynomial of degree k 2 0 then Pn 8nk b For any positive real numbers a and 3 n on iff alt n 8n iff a and n an iffagt c For any positive real numbers a and b aquot 0bquot iff a lt b aquot 8bquot iff a b and aquot ab iff a gt b d fquot0fquot 9fquot n Use Stirling s formula n V2717 1 8071 to prove that lgn 8nlg n e J Consider the following sketch of an algorithm called ProcessArray which performs some unspeci ed operation on a subarray Ap r ProcessArravA p r P Jquot p 21 and r SlengthA 1 do something which takes constant time 2 if p lt r p r 3 e 7 q i 2 i 4 ProcessArrayA p q 5 ProcessArrayA q1 r Write a recurrence which gives the running time Tn of this algorithm when called on the full array A1 n Give a tight asymptotic solution to this recurrence CMPS 101 Midterm 1 Review Problems N L 4 ON 1 2n 4 Use Stirling s formula to prove that J 8 n Let f n and gn be asymptotically nonnegative functions which are de ned on the positive integers a State the de nition of f n Ogn b State the de nition of fn agn State whether the following assertions are true or false statement which is true 21 f0 0gn implies f0 0gquot b fn Ogn if and only if gn Qfn c fn 8gn ifand only if liinfngn L where 0 lt L lt 00 If any statements are false give a related Prove that 8fn r 8gn 8fn r gn In other words if hln 8fn and h2 n 8gn then M70 11201 8fquot gn Use limits to prove the following these are some of the exercises at the end of the asymptotic growth rates handout a If Pn is a polynomial of degree k 2 0 then Pn 8nk b For any positive real numbers a and 3 n on iff alt n 8n iff a and n an iffagt c For any positive real numbers a and b aquot 0bquot iff a lt b aquot 8bquot iff a b and aquot ab iff a gt b d fquot0fquot 9fquot n Use Stirling s formula n V2717 1 8071 to prove that logn 8nlogn e J Consider the following sketch of an algorithm called ProcessArray which performs some unspeci ed operation on a subarray Ap r ProcessArravA p r P Jquot p 21 and r SlengthA 1 do something which takes constant time 2 if p lt r p r 3 e 7 q i 2 i 4 ProcessArrayA p q 5 ProcessArrayA q1 r Write a recurrence which gives the running time Tn of this algorithm when called on the full array A1 n Give a tight asymptotic solution to this recurrence CMPS 101 Midterm 2 Review Problems Figure 1 1 Z 3 4 5 6 7 Figure 2 1 Z 3 4 5 L6 7 8 V A 9 10 Figure 3 l Z 3 V V 4 5 6 Problems 1 Trace BFS on the following graphs For each vertex record its color parent and distance fields and draw the resulting BFS tree Process adjacency lists in ascending numerical order a b N The graph in figure 1 with l as the source The directed graph in figure 2 with l as source Trace DFS on the following graphs For each vertex record its color parent discover and finish fields and draw the resulting DFS forest Classify each edge as tree back forward or cross Process adjacency lists in ascending numerical order a b c D 5 The graph in figure 3 The graph in figure 1 Process vertices in the main loop of DFS in ascending numerical order The graph in figure 2 Process vertices in the main loop of DFS in ascending numerical order The transpose of the graph in figure 2 Process vertices in the main loop of DFS in order of descending finish times from part b Determine the strongly connected components of the graph in figure 2 and draw its component graph Process vertices in the main loop of DFS in ascending numerical order Show that this graph is acyclic and determine a topological sort of the vertices The graph in figure 3 Process vertices in the main loop of DFS in descending order topological sort of the vertices which is different from that in part d Determine a CMPS 101 Midterm 1 Review Problems N L 4 UI ON 1 Zn 4quot Use St1r11ng s formula to prove that K j D n Let f n and gn be asymptotically nonnegative functions which are de ned on the positive integers a State the de nition of fn Ogn b State the de nition of f n agn State whether the following assertions are true or false statement which is true a fquot 0gquot implies f0 0gquot b fn Ogn if and only if gn Qfn c fn gn ifand only if leOfngn L where 0 lt L lt 00 If any statements are false give a related Prove that fn gn fn gn In other words if hln fn and h2 n gn then Mquot 11201 fn gn Use limits to prove the following these are some of the exercises at the end of the asymptotic growth rates handout a If Pn is a polynomial of degree k 2 0 then Pn nk b For any positive real numbers a and n 1 on 8 iff alt n 1 n 5 iff a and n an 6 iffagt c For any positive real numbers a and b aquot 0bquot iff a lt b aquot bquot iff a b and aquot abquot iff a gt b d fquot0fn fn n Use Stirling s formula n V2717 1 9071 to prove that logn nlogn e J Consider the following sketch of an algorithm called ProcessArray which performs some unspeci ed operation on a subarray Ap r ProcessArravA p r P Jquot p 21 and rSlengthA 1 do something which takes constant time 2 if p lt r 3 q L 4 ProcessArrayA p q 5 ProcessArrayA q1 r Write a recurrence which gives the running time Tn of this algorithm when called on the full array A1 n Give a tight asymptotic solution to this recurrence CMPS 101 Midterm 2 Review Problems Figure 1 1 2 3 4 5 6 7 8 9 10 11 12 Figure 2 l 2 3 4 A v 5 396 7 8 V A 9 10 Figure 3 2 3 Problems 1 N Trace BFS on the following graphs For each vertex record its color parent and distance elds and draw the resulting BFS tree Process adjacency lists in ascending numerical order a The graph in gure 1 with 1 as the source b The directed graph in gure 2 with 1 as source Trace DFS on the following graphs For each vertex record its color parent discover and nish elds and draw the resulting DFS forest Classify each edge as tree back forward or cross Process adjacency lists in ascending numerical order a The graph in gure 1 Process vertices in the main loop of DFS in ascending numerical order b The graph in gure 2 Process vertices in the main loop of DFS in ascending numerical order c The transpose of the graph in gure 2 Process vertices in the main loop of DFS in order of descending nish times from part b Determine the strongly connected components of the graph in gure 2 and draw its component graph The graph in gure 3 Process vertices in the main loop of DFS in ascending numerical order Show that this graph is acyclic and determine a topological sort of the vertices The graph in gure 3 Process vertices in the main loop of DFS in descending order topological sort of the vertices which is different from that in part d 3 1 Determine a D

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

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

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

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

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