### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Introduction To The Analysis Of Algorithms CS 38100

Purdue

GPA 3.68

### View Full Document

## 122

## 0

## Popular in Course

## Popular in ComputerScienence

This 3 page Class Notes was uploaded by Nick Rowe on Saturday September 19, 2015. The Class Notes belongs to CS 38100 at Purdue University taught by Mikhail Atallah in Fall. Since its upload, it has received 122 views. For similar materials see /class/208072/cs-38100-purdue-university in ComputerScienence at Purdue University.

## Popular in ComputerScienence

## Reviews for Introduction To The Analysis Of Algorithms

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

CS381 Examples of Exam Questions The below samples illustrate the types of questions that I could ask in exams both midterms and nals An actual exam would have roughly twice as many questions as the below it would have 100 points whereas the examples below are worth 52 points only The italicized notes between square brackets explain my rationale for asking each sample question 7 no such notes would be included in an actual exam Question X 16 points This is meant to test pro ciency in quickly estimating an algorithm s time complexity 7 a student who understands the recursion tree method of analysis can do these quickly without too much complicated math In all of the four recurrences shown below it is assumed that T1 d for some constant at State using the big oh77 notation the solution to each of the recurrences shown below Just state the answers 7 you do not need to justify them 1 Tn 4Tn2 cnz Answer 0n210gn 2 Tn 3Tn3 cnz Answer 0n2 3 Tn Tn2 Tn3 Cn Answer On 4 Tn Tn4 T3n4 Cn Answer On log n Question Y 9 points This is an example of a question based on a homework to test who actiuely worked on that homework and understands its solution Given n distinct numbers y1 yn not in sorted order let if be a number y that mini mizes y 21 ly 7 where ly 7 denotes the absolute value of y 7 y Mark by T True or F False each of the following statements about this problem 1 True We must have y for somei E 1 2 n ie one ofthe n numbers yl yn is guaranteed to minimize the function f to False We must have if E y1 yg yn ie any value of y that minimizes y has to come from the set y1 yn 03 False There are always in nitely many choices for if ie in nitely many values of y that minimize F True If the ms were given to us sorted in an array then we could nd a if in constant time Question Z 9 points A question to test understanding of lower bounds and of inorder tree traversal Let S be a set of n distinct elements S is not given sorted A binary search tree T for set S is de ned as follows The root of T contains the median call it i of S7 ii the left subtree of the root is a binary search tree for the elements of S that are smaller than i and iii the right subtree of the root is a binary search tree for the elements of S that are larger than i Mark by T True or F False each of the following statements 1 False Given S7 T can be built in On time 2 True Given T7 a sorted version of S can be obtained in On time 3 True The problem of consructing T from the set S has an Qnlogn time lower bound Question V 12 points Tests algorithmic thinking without asking for the design of a full fledged algorithm in a short amount of time Let S p1 pn be a set of n two dimensional points7 no two of which have same x coordinate or same y coordinate Let M and yi denote the z and respectively y coordinate of a point pi E S Point pi is said to be maximal if no other point p of S has both zj gt mi and yj gt yi The maximal elements problem is Given such a set S of two dimensional points7 compute the set MazS of maximal elements in S The following are two different algorithms for computing the maximal elements for such a set S Each description contains pairs of choices7 each of which is surrounded by boldface curly brackets as in Choice1Choice2 For each such pair of the form ChoiceLChoice2 you must choose by circling it one of the alternatives either Choicel or Choice2 in such a way that in the end t he description sketches an Onlog n time algorithm for solving the maximal elements problem Algorithm A 0 First sort the points according to their z coordinates7 then go through the sorted points by increasing7decreasing m coordinates and maintain as you go along the smallestlargest y coordinate call it y encountered so far The point at which you are is maximal if and only if its own y coordinate is smallerlarger than 3 Algorithm B c Find the median of the m coordinates of the points call it z Let S be the subset of points in S that have m coordinates z Let S be the points of S not in S Recur sively compute MazS 7 then recursively compute MamS Let y be the largest y coordinate in MazS 7 MamS MazS consists of all of MamS 7 MamS 7 followed by those points of MazS 7 MazS whose y coordinate is larger than 2 Answer decreasing7 largest7 larger MamS 7 MamS 7 MazS Question W 6 points A question based on a particular lecture In the On log n time algorithm for nding a closest pair among a set S of n 2 7 points in two dimensions7 we rst partitioned the set of points in two equal sets S1 and S2 according to their z coordinates Then we recursively solved the problem for S17 and also for S2 Call 61 the closest distance for S17 62 the one for S27 and let 6 min6162 Mark by T True or F False each of the following where c denotes a constant 1 True There could be on pairs of points in S that are for each pair closer to each other than 6 2 True Let p be any point in S Then there are at most 01 points of S whose distance to p is lt 6 3 False Let p be any point in S1 Then there are at most 01 points of S1 whose distance to p is lt 67 but there could be on points of S2 whose distance to p is lt 6

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

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

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

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