Application of dynamic programming

Hey!!

:smile:

I have to write an

O(n^3)

algorithm to determine whether a given string

w=a_1 a_2 \dots a_n

is in

L(G)

, where

G=(N,\Sigma ,P, S)

is a context-free grammar in Chomsky normal form.

Could you explain me how we could use the dynamic programming in this case??

Original post by mathmari

Hey!!

:smile:

I have to write an

O(n^3)

algorithm to determine whether a given string

w=a_1 a_2 \dots a_n

is in

L(G)

, where

G=(N,\Sigma ,P, S)

is a context-free grammar in Chomsky normal form.

Could you explain me how we could use the dynamic programming in this case??

Scroll down to his web development tutorials, he's really good at explaining things.
https://m.youtube.com/channel/UCc1Pn7FxieMohCZFPYEbs7w

This talk has two goals:
a) A review of the fundamentals of dynamic programming, and an introduction to nonserial dynamic programming.

b) An application of the techniques to some of the issues involved in the problem of determining globally optimum storage patterns.

1

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you

How to choose a uni to study a Master’s

How to choose a uni to study a Master’s

What is an LLM and how could it benefit your career?

What is an LLM and how could it benefit your career?

Powerful questions business students forget to ask their career advisers

Powerful questions business students forget to ask their career advisers

Why I chose a law degree and what studying law was like

Why I chose a law degree and what studying law was like