### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Algorithms Brochure CS6212

GWU

### View Full Document

## About this Document

## 11

## 1

## Popular in Design and Analysis of Algorithms

## Popular in Computer science

This 6 page Study Guide was uploaded by GW University on Saturday August 27, 2016. The Study Guide belongs to CS6212 at George Washington University taught by Dr. Arora in Fall 2016. Since its upload, it has received 11 views. For similar materials see Design and Analysis of Algorithms in Computer science at George Washington University.

## Popular in Computer science

## Reviews for Algorithms Brochure

### 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: 08/27/16

Algorithms – Design and Analysis George Washington University Amrinder Arora A LGORITHMIC T ECHNIQUES Works well if the problem exhibits “greedy Basic Template choice property”, that is, globally optimal 1. Do a Breadth First Search Divide and Conquer solution can be arrived at by making a locally 2. Evaluate nodes for bounds optimal choice. For example: An optimal 3. Branch into the “best” node Generalization Step Solve(P)Solve(P,Start,End) minimum spanning tree can be built by selecting 4. Terminate if performance goals met the smallest weighted “eligible” edge. Algorithm How to develop bounds Dynamic Programming Branch and Bound depends upon being able to divide_conquer(input I) if (input is small enough) - solve directly Compute solution bottom up by combining “bound” nodes in the search tree. // THE DIVIDE STEP subsolutions. Store the results of subsolutions to divide I into parts I1, I2,... For a minimization problem: Find a lower bound call divide_conquer(I1) avoid recomputation of sub problems. by making some observation that cost can be no call divide_conquer(I2) Think of DP when you see (i) optimal lower than value “x”, perhaps by “relaxing” the ... substructure and (ii) overlapping subproblems problem so that a simpler approach (say greedy) // THE MERGE STEP might work, even though the solution may not be Merge subsolutions Template (Mnemonic: NORA) a feasible solution to the original problem. Recurrence Relations 1. Develop a N otation that can express a Find an upper bound by using any known subsolution for the given problem: “Say s(P,i) Based on how you divide (number of represents the solution to problem instance solution. subproblems, and size of each subproblem) and how long it takes to merge the subsolutions, the P, assuming we start at i.” For maximization problem: Lower bound is any 2. Check if thO ptimal Substructure (Principle feasible solution. Upper bound is theoretical. recurrence relation is established, which then determines the overall running time of your of Optimality) holds. Termination criteria: B&B is used for hard 3. Develop a R ecurrence relation that allows problems, so keep an eye on target performance solution. Examples: building a solution from the subsolutions. of the solution. E.g., if it is OK to find a solution T(n) = 2 T(n/2) + cn O(n log n) that costs at most 5% more than provably [Two subproblems of half the original 4. Develop the bottom upA lgorithm. minimum bound, then use that in B&B to find size, linear time in dividing and merging] For example: Given n real (positive/negative) terminating conditions. T(n) = T(9n/10) + cn O(n) numbers A(1) ... A(n), determine a contiguous T(n) = 8 T(n/2) + cn O(n ) subsequence A(i) ... A(j) for which the sum of Backtracking T(n) = 2 T(n/2) + cn O(n ) elements in the subsequence is maximized. A problem like Sudoku, or knapsack can be solved by building partial solutions, discarding Greedy Method Branch and Bound the ones that don’t work and backtracking in the Build a complete solution by making a sequence More general technique; can be used to solve solution search tree to try a different solution. of “best selection steps”. many optimization problems, even those that are Depending on the discarding mechanism, this NP-complete. can be very efficient technique! Download again? http://is.gd/3YMNBi Algorithms – Design and Analysis George Washington University Amrinder Arora P ROBLEM COMPLEXITY AND C LASSES How to prove that problem X is NP- 2. Premature optimization (something that only complete? works on some inputs) is a distraction. NP-Completeness To prove that problem X is NP-complete, we 3. Generalization can help you in using divide We consider two classes of problems: P and NP. have to start with a known NP-complete and conquer and recursive solutions. Class P consists of problems that can be solved in problem, and reduce that to our problem X. 6212 Solution Process polynomial time. Class NP consists of problems, for which you can verify a given solution in Mnemonic: SoX – ReStoX (SAT Outside the box – Phase 1 – Define Your Problem polynomial time. An NP-Complete problem is a X Inside – Reduce SAT to X). 1. Draw a box, with inputs and outputs problem which can be considered a “central” (or Tackling NP-Completeness 2. (Important) Name the box (Hint: Generic complete) problem for all problems in class NP. word like “solver” is not a name.) Strategy 1 – “Context”: Look for simplifications Class “NPC” is the class of all NP-complete in data and context that render the problem Phase 2 – Solve Your Problem problems. Essentially, class NPC consists of hard problems for which polynomial time algorithms solvable in polynomial time. 1. What is the brute force time complexity? 2. Would a greedy solution work? Would are not known to exist. The reason we try to Strategy 2 – “Find low Exponent”: Look for find if a problem is NP-complete is to determine improvements in running time which make the divide and conquer work? Can we use exponential “bearable.” dynamic programming? if it is hard. If we prove that a given problem is 3. If the problem appears very hard, is it NP- NP-complete, we can convince others, if Strategy 3 – “Approximate and Refine”: required, that the problem is hard, and our complete? Can we prove that, and tackle its Understand performance bounds that are NP-completeness? efforts are more justified in other ways of acceptable practically, and use approximation tackling NP-Completeness. algorithms. Learning to Learn A Fascinating Open Problem Don’t forget the Ebbinghaus forgetting curve. If Beyond class NP you review something 4 times, say once shortly If you (or someone else) finds a polynomial time Some problems are provably undecidable, algorithm for an NP-complete problem, that is after learning, once after a day, once after a irrespective of the time we spend on it. week and another time after a month, there is a equivalent of finding a polynomial time algorithm for ALL problems in NP, and will also imply that A PPLYING A LL T HIS very good chance you will remember it forever. classes P and NP are in fact the same. THAT Tips and Tricks Your chance of learning and remembering WILL BE HUGE! You will be rich! $$$$. something increases if you explain that to Similarly, if you find that a particular NP- 1. Remember the time when you brought that someone. Volunteering to give a presentation on hamster home. When you named it Pete, complete problem cannot be solved in a topic is an excellent way to learn it even polynomial time using our current computation your family knew it was your pet, and it was further. models, that would prove that these classes are going to stay. Naming is your friend. If you can name it, you can own it. Start with a in fact distinct. That would also be huge! good notation: “Let S(n,m) represent ….”) Download again? http://is.gd/3YMNBi Name: Score: / 60 CS 6212 – Final (60 points) (120 minutes) (No calculators allowed) [5 BONUS POINTS.] Q 1 – 6 (5 points each): [Only write answers, NO explanations] What is the time complexity of these algorithms, in terms of n? [ Sum += y is a short form notation for Sum = Sum + y.] j = 1 for (int i = 1 to n) { while (j < n) { int j = 2 for (int j = i to n) { k = j while (j < n) { for (int k = j to n) { while (k < n) { int k = j Sum += a[i]*b[j]*c[k] Sum += a[k]*b[k] while (k < n) { } k += k Sum += a[k]*b[k] If (gcd(i,j) == 1) { } k += n1/3log n j = n j += 0.25 * n } } } j = j*sqrt(5) } } } Solve recurrence relation: T(n) = T(n/2) + O(n log n). Solve recurrence relation: T(n) = 3T(n/2) + O(log n). Give an example of a graph that has all 3 of the following properties. (Note that you need to give a single graph as the answer.) (i) It is connected (ii) It has one articulation point. (iii) The graph needs at least 4 colors for a valid vertex coloring (iv) The graph does not have a 4-clique (that is, a clique of 4 vertices) as a subgraph. Q7 (10 points): Given two DNA sequences (sequences of A, C, T, G characters), the longest common subsequence (LCS) problem is to find the longest subsequence (not necessarily contiguous) that exists in both of the input strings. For example, given strings “ACTGACT” and “CAAGCATA”, the subsequence “CGCT” is common in both. Given two DNA sequences of sizes n and n r1spective2y, find a dynamic programming algorithm to find the longest common subsequence in O(n n ) time. 1 2 Q8 (10 points): “Rectangles” A rectangle can be specified in a 2-dimensional plane using the top left (north west) point and the bottom right (south east) point. Given n rectangles (using 2 points each), give an O(n log n) algorithm that tells if any two rectangles from the list overlap. Two rectangles are said to overlap, if there is a common point in both of them. [If a rectangle is entirely contained in another, they are still said to “overlap”, even though their lines don’t cross.] Q9 (10 points): Long chain of friends: You are given a list of people, and statements of the form “x knows y”. You are asked to find, is there a chain of k people, such as x kno1s x , x kno2s x2, 3 and x k-1knows x . k Prove that this problem is NP-complete by using one of the known NP-complete problems (CLIQUE, 3-SAT, Hamiltonian Path, Hamiltonian Cycle, Independent Set, etc.)

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

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

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

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