For each of the following recurrences, provide English description in terms of the parameters i and j. (a) (b) LIS LEC(i, j)= LIS LAB(i, j) = LIS LEC (i-1, j) max max LIS LEC(i-1, j) 1+LIS LEC(i-1, i) 0 LISLAB (i + 1, j) { LIS LAB (i+1, j) 1+LIS LAB(i+1, i) } i=0 A[i]> A[j] A[i]n if i ≤n and A[j] ≥ A[i] otherwise Your solution should be a simple, short, English description of each recurrence. No long proofs for correctness are necessary. This is to make sure you understand how to describe a function (and no, saying "LIS returns the longest increasing subsequence length." is not a sufficient description)
For each of the following recurrences, provide English description in terms of the parameters i and j. (a) (b) LIS LEC(i, j)= LIS LAB(i, j) = LIS LEC (i-1, j) max max LIS LEC(i-1, j) 1+LIS LEC(i-1, i) 0 LISLAB (i + 1, j) { LIS LAB (i+1, j) 1+LIS LAB(i+1, i) } i=0 A[i]> A[j] A[i]n if i ≤n and A[j] ≥ A[i] otherwise Your solution should be a simple, short, English description of each recurrence. No long proofs for correctness are necessary. This is to make sure you understand how to describe a function (and no, saying "LIS returns the longest increasing subsequence length." is not a sufficient description)
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Question
-
Solutions to a dynamic
programming problem have (at minimum) three things: – A recurrence relation– A brief description of what your recurrence function represents and what each case represents.
– A brief description of the memory element/storage and how it’s filled in.
– Always give complete solutions, not just examples.
– Always declare all your variables, in English. In particular, always describe the specific- problem your
algorithm is supposed to solve. – Never use weak induction.
![For each of the following recurrences, provide English description in terms of the parameters
i and j.
(a)
(b)
LIS LEC(i, j)=
LIS LAB(i, j) =
LIS LEC (i-1, j)
max
max
LIS LEC(i-1, j)
1+LIS LEC(i-1, i)
0
LISLAB (i + 1, j)
{
LIS LAB (i+1, j)
1+LIS LAB(i+1, i)
}
i=0
A[i]> A[j]
A[i]<A[j]
if i>n
if i ≤n and A[j] ≥ A[i]
otherwise
Your solution should be a simple, short, English description of each recurrence. No long
proofs for correctness are necessary. This is to make sure you understand how to describe
a function (and no, saying "LIS returns the longest increasing subsequence length." is not a
sufficient description)](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F840ac9d4-eb27-4280-b70d-21eed9a81895%2Fa8bab80b-4e7d-456d-bec2-dab74ca391ee%2Fkesi9c4_processed.png&w=3840&q=75)
Transcribed Image Text:For each of the following recurrences, provide English description in terms of the parameters
i and j.
(a)
(b)
LIS LEC(i, j)=
LIS LAB(i, j) =
LIS LEC (i-1, j)
max
max
LIS LEC(i-1, j)
1+LIS LEC(i-1, i)
0
LISLAB (i + 1, j)
{
LIS LAB (i+1, j)
1+LIS LAB(i+1, i)
}
i=0
A[i]> A[j]
A[i]<A[j]
if i>n
if i ≤n and A[j] ≥ A[i]
otherwise
Your solution should be a simple, short, English description of each recurrence. No long
proofs for correctness are necessary. This is to make sure you understand how to describe
a function (and no, saying "LIS returns the longest increasing subsequence length." is not a
sufficient description)
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 1 steps
Recommended textbooks for you
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education