Homework 1

pdf

School

Georgia Institute Of Technology *

*We aren’t endorsed by this school

Course

6515

Subject

Computer Science

Date

Feb 20, 2024

Type

pdf

Pages

Uploaded by KidDovePerson386

8/28/23, 2:43 PM Homework 1 https://gatech.instructure.com/courses/344296/assignments/1503380 1/2 Homework 1 Due Sep 4 by 8am Points 20 Submitting a file upload File Types pdf Available Aug 28 at 8am - Sep 4 at 8am Start Assignment Suggested reading Chapter 6 [DPV]. Practice Problems ( do not turn in) [DPV] Problem 6.4 – Dictionary lookup You are given a string of n characters s[1...n],which you believe to be a corrupted text document in which all punctuation has vanished... [DPV] Problem 6.8 – Longest common substring Given two strings x = [1...n] and y = [1...m] we wish to find the length of their longest common substrings... [DPV] Problem 6.18 – Making change II Consider the following variation on the change-making problem (Exercise 6.17): you are given denominations , ... [DPV] Problem 6.19 – Making change k Given an unlimited supply of coins of denominations , we wish to make change for a value v using at most k coins... [DPV] Problem 6.20 – Optimal Binary Search Tree Suppose we know the frequency with which keywords occur in programs of a certain language, for instance ... [DPV] Problem 6.26 – Alignment Sequence alignment. When a new gene is discovered, a standard approach to understanding its function is to look through a database of known genes and find close matches Graded Problem

8/28/23, 2:43 PM Homework 1 https://gatech.instructure.com/courses/344296/assignments/1503380 2/2 A thief is planning on burglarizing some subset of n consecutive houses in a neighborhood. The houses are labeled 1, 2, . . . , n and the thief will address them sequentially. The thief has an estimate of the profit to be earned from burglarizing each house , i = 1 . . . n, where . To avoid detection, he decides that he will never burglarize two adjacent houses, meaning that if he burglarizes house 2, he cannot burglarize house 1 or house 3. Design a dynamic programming algorithm to determine the maximum total profit he can achieve. Example: In each of the following two neighborhoods, the maximum achievable profit is $100: Case 1: p = [$20, $100, $30]. Case 2: p = [$40, $30, $10, $60]. Your input is the table . Your output should be the maximum profit the thief can get. You do not have to return the subset of houses the thief has to burglarize to achieve the maximum. Please answer the following parts: 1. Define the entries of your table in words. E.g. T(i) or T(i, j) is ... 2. State a recurrence for the entries of your table in terms of smaller subproblems. Don't forget your base case(s). 3. Write pseudocode for your algorithm to solve this problem. 4. State and analyze the running time of your algorithm. Faster (in asymptotic Big O notation) and correct solutions are worth more credit. You will upload a pdf of your typed solution. Handwritten solutions will be penalized.

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

Related Documents

standard three.docx

Tch 505 Culminating Project 5-30-22.docx

sp21final.pdf

Quiz 1.docx

IST 7040 Week 1 Discussion.docx

NeuralNet_report.pdf

Tutorial01_Case4_Rubric.docx

CS 2203 Programming 1 (5).docx

sample_midterm cs mcq.pdf

fire prevention essay.docx

Course Hero Logo.docx

module 2 short responses.docx

Recommended textbooks for you

C++ for Engineers and Scientists

Computer Science

ISBN:9781133187844

Author:Bronson, Gary J.

Publisher:Course Technology Ptr

Programming Logic & Design Comprehensive

Computer Science

ISBN:9781337669405

Author:FARRELL

Publisher:Cengage

C++ Programming: From Problem Analysis to Program...

Computer Science

ISBN:9781337102087

Author:D. S. Malik

Publisher:Cengage Learning

Np Ms Office 365/Excel 2016 I Ntermed

Computer Science

ISBN:9781337508841

Author:Carey

Publisher:Cengage

Systems Architecture

Computer Science

ISBN:9781305080195

Author:Stephen D. Burd

Publisher:Cengage Learning

Microsoft Visual C#

Computer Science

ISBN:9781337102100

Author:Joyce, Farrell.

Publisher:Cengage Learning,

SEE MORE TEXTBOOKS

Recommended textbooks for you

C++ for Engineers and Scientists
Computer Science
ISBN:9781133187844
Author:Bronson, Gary J.
Publisher:Course Technology Ptr
Programming Logic & Design Comprehensive
Computer Science
ISBN:9781337669405
Author:FARRELL
Publisher:Cengage
C++ Programming: From Problem Analysis to Program...
Computer Science
ISBN:9781337102087
Author:D. S. Malik
Publisher:Cengage Learning
Np Ms Office 365/Excel 2016 I Ntermed
Computer Science
ISBN:9781337508841
Author:Carey
Publisher:Cengage
Systems Architecture
Computer Science
ISBN:9781305080195
Author:Stephen D. Burd
Publisher:Cengage Learning
Microsoft Visual C#
Computer Science
ISBN:9781337102100
Author:Joyce, Farrell.
Publisher:Cengage Learning,