Difference: LeetCode8 (1 vs. 4)

Revision 42019-03-31 - JimSkon

Line: 1 to 1

 META TOPICPARENT name="Math391F2016"

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

Revision 32019-03-24 - JimSkon

Line: 1 to 1

 META TOPICPARENT name="Math391F2016"

Changed:
<
<
>
>

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
>
>
 META TOPICPARENT name="Math391F2016"

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.

Copyright © 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