Dynamic Programming is a method of solving problems exhibiting the properties of overlapping subproblems and optimal substructure that takes much less time than naive methods.It is typically applied to optimization problems.
Longest Common subsequence and substring:
Longest Common subsequence and substring are two applications of Dynamic Programming.The longest common subsequence problem is finding the longest subsequence common to all sequences in a set of sequences (often just two) while longest common substring is finding the longest substring.
1)Determine an LCS of {1,0,0,1,0,1,0,1} and {0,1,0,1,1,0,1,1,0}.
2)Give an algorithm to find the Longest common subsequence of sequences with lengths m,n respectively and also analyze their time complexities.
3)Give an algorithm to find the Longest common string of strings with lengths m,n respectively and also analyse their time complexities.
4)Give an O(n^2) time algorithm to find the longest monotonically increasing subsequence of a sequence of n numbers.
5)Give an O(n^2) time algorithm to find the longest monotonically increasing subsequence of a sequence of n numbers.
6)What is the difference between longest common subsequence and longest common substring
7)State few applications of Dynamic Programming.
Search Your Question
Tuesday, July 22, 2008
Dynamic Programming
Labels:
Data Structures
Subscribe to:
Post Comments (Atom)
Archives
-
▼
2008
(992)
-
▼
July
(288)
- Yahoo Interview
- Yahoo Interview Questions
- Yahoo Interview Questions-1
- Yahoo Interview Questions-2
- Visual Basic Interview Questions -7
- Visual Basic Interview Questions -6
- Visual Basic Interview Questions -5
- Visual Basic Interview Questions -4
- Visual Basic Interview Questions -3
- Visual Basic Interview Questions -2
- Visual Basic Interview Questions -1
- SQL Interview Questions -8
- SQL Interview Questions -7
- SQL Interview Questions -6
- SQL Interview Questions -5
- SQL Interview Questions -4
- SQL Interview Questions -3
- SQL Interview Questions -2
- SQl Job Interview Questions
- Solutions to C programming questions
- Modified Array based QuickSort with respect to the...
- Last Non Zero Digit of Factorial
- Quick Sort routine to find the kth smallest elemen...
- Run time Analysis of QuickSort ,Nature of Input,Pi...
- Tree Arithmetic
- Number of ways to express a number as summation of...
- Solutions to Logical Puzzles-2
- Combinations
- Solutions to Basic C Interview Questions
- Solutions to Logical Puzzles-1
- Solutions to Logical Puzzles-3
- C program to find the height of a binary search tree
- C program to determine the number of nodes in a bi...
- C program to delete a tree
- Minimum Value of a Binary Search Tree
- Solutions to Questions on recursion
- C program to create mirror copy of a tree
- Solutions to Amazon Intern Interview Questions
- Traversals of a Binary Tree
- Solutions to Google Top Interview Puzzles
- Solutions to problems in recursion analysis
- solution1
- C-program to make a copy of a tree
- C-program to check whether a binary tree is a Bina...
- C-program to delete a node from a tree
- Search On a Binary Search Tree
- C-program to count the leaves in a tree
- Some Basic Questions on sorting and their solutions
- Resume Tips
- Secrets of a Selling Resume
- The Three R's of Resume Writing
- Top Ten Pitfalls of a Resume
- Ten Tips for Writing Better Resumes
- Frequently Asked Questions - Object oriented Concepts
- Frequently Asked Questions - Operating System Conc...
- Frequently Asked Questions - Database
- Frequently Asked Questions - Networking
- UNIX Concepts
- Resources For Placements Preparation
- Essentials Of Operating Systems
- Networking Concepts
- Microsoft Puzzles
- Important Puzzles
- Important Puzzles
- Important Puzzles
- Important Puzzles
- Important Puzzles
- Important Puzzles
- Important Puzzles
- Important Puzzles
- Important Puzzles
- Practise Puzzles - 1
- Practise Puzzles - 1
- Practise Puzzles - 2
- Practise Puzzles - 2
- Practise Puzzles - 2
- Answers For Practise Puzzles - 1
- Answers for Practise Puzzles - 2
- Practise Puzzles - 3
- Practise Puzzles - 3
- Practise Puzzles - 3
- Answers for Practise Puzzles - 3
- Practise Puzzles - 4
- Practise Puzzles - 4
- Answers For Practice Puzzles - 4
- Puzzles
- Logical Puzzles-1
- Logical Puzzles -2
- Logical Puzzles-3
- Algorithms And Programming #4
- Algorithms And Programming #5
- Algorithms And Programming #6
- Algorithms And Programming #7
- Algorithms And Programming #8
- Algorithms And Programming #9
- Prime Numbers!
- C Programming Puzzles
- C Programming Puzzles 2
- C Programming Puzzles 3
- C Programming Puzzles 4
-
▼
July
(288)
No comments:
Post a Comment