Difference: LeetCode8 (1 vs. 4)

Revision 42019-03-31 - JimSkon

Line: 1 to 1
 
META TOPICPARENT name="Math391F2016"

LeetCode Exercise 8

Dynamic Programming


Teams

Changed:
<
<
Group 1 Thomas, Isaac
Group 2 Preston, Kyle
Group 3 Charlie, Boning
Group 4 Flynn, John
>
>
Group 1 Thomas, Isaac
Group 2 Preston, Kyle
Group 3 Flynn, John, Boning
 
Due: April 12, 11:55 pm

Moodle Link

Revision 32019-03-24 - JimSkon

Line: 1 to 1
 
META TOPICPARENT name="Math391F2016"

LeetCode Exercise 8

Dynamic Programming
Changed:
<
<
Due: Nov 9, 11:55 pm
>
>


Teams

Group 1 Thomas, Isaac
Group 2 Preston, Kyle
Group 3 Charlie, Boning
Group 4 Flynn, John
Due: April 12, 11:55 pm
 
Changed:
<
<
Moodle Link
>
>
Moodle Link
 

368. Largest Divisible Subset

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0.

Revision 22016-11-15 - JimSkon

Line: 1 to 1
 
META TOPICPARENT name="Math391F2016"

LeetCode Exercise 8

Dynamic Programming
Line: 22 to 22
 You are to find a dynamic programming solution to this problem, and implement it on Leetcode.
Hints:
  1. Can you think of a bottom-up approach? How is the larger problem a made up of sub-problems?
Changed:
<
<
  1. Refiew the solution in class of Weighted Interval Scheduling. Consider the methods and data structures of that.
>
>
  1. Review the solution in class of Weighted Interval Scheduling. Consider the methods and data structures of that.
 
  1. DP usually depends on the ordering of objects. How might ordering here be useful?
  2. How is an optimal solution for a given size problem useful in constructing a solution for a larger problem.
  3. For a given problem size of n, can you first solve all of the problems for 0<i<=n-1 and keep track of those solutions with some sort of a data structure?

Revision 12016-11-04 - JimSkon

Line: 1 to 1
Added:
>
>
META TOPICPARENT name="Math391F2016"

LeetCode Exercise 8

Dynamic Programming
Due: Nov 9, 11:55 pm

Moodle Link

368. Largest Divisible Subset

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0.

If there are multiple solutions, return any subset is fine.

Example 1:
nums: [1,2,3]
Result: [1,2] (of course, [1,3] will also be ok)
Example 2:
nums: [1,2,4,8]
Result: [1,2,4,8]

You are to find a dynamic programming solution to this problem, and implement it on Leetcode.

Hints:
  1. Can you think of a bottom-up approach? How is the larger problem a made up of sub-problems?
  2. Refiew the solution in class of Weighted Interval Scheduling. Consider the methods and data structures of that.
  3. DP usually depends on the ordering of objects. How might ordering here be useful?
  4. How is an optimal solution for a given size problem useful in constructing a solution for a larger problem.
  5. For a given problem size of n, can you first solve all of the problems for 0<i<=n-1 and keep track of those solutions with some sort of a data structure?
  6. If you have solved (and have available) the solutions for all smaller problems, how can you select and use the smaller solutions to create a solution for n?
Turn in:
  1. Source code for your solution
  2. Samples runs showing the operation with input and outputs.
  3. An explaination of how this problem includes the concept of an optimal substructure.
  4. A complete runtime asymptotic analysis.
Be prepared to discuss you solutions in class.
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback