Spring15: Difference between revisions
Jump to navigation
Jump to search
imported>Kmk21 No edit summary |
imported>Kmk21 No edit summary |
||
| Line 19: | Line 19: | ||
* OLA's section solve problems A and B from [[rmrc2014]] | * OLA's section solve problems A and B from [[rmrc2014]] | ||
* Kevin's section try to solve problems F and I from [[nwerc2014]] | * Kevin's section try to solve problems F and I from [[nwerc2014]] | ||
=Class 2: 1/28] | |||
==Notes== | |||
* Covered "finding lines | |||
** very low tolerance, can use randomized algorithm | |||
** 10^5 is too slow for n^2....break it into two (or more groups), solve for each group and then combine the solutions (divide and conquer!) | |||
* Indoorienteering | |||
** NP complete, clear must be some brute force solution because n=14 (small) | |||
** since must reach all points, fix one of them as the start point (14! => 13!) | |||
** split it up into two halves, iterating over the midpoint (13 * (12 choose 6) * 6!*6!) | |||
** store the results of one half in a hashmap, and then when doing the second half, simply check whether the proper distance exists in the hashmap (13 * (12 choose 6) * (6! + 6!)) | |||
** Divide and conquer (again) | |||
* Plane ticket pricing | |||
** brute force too slow (and can have invalid solutions...because we only have so many seats) | |||
** greedy doesn't work because we can make a selection now that can hurt us later | |||
** above points SCREAM DP | |||
** time almost always a dimension of the DP | |||
** other things that can lead to invalid solutions (selling too many seats) also almost always a dimension | |||
** value stored is almost always the thing we're trying to solve for (most amount of money) | |||
==Homework== | |||
* Solve Preorder Traversals from [[ncna2014]] (OLA's section) | |||
* Solve Finding Lines (if you haven't already) using either of the two discussed methods (or your own!) (Kevin's section) | |||
* Solve Plane ticket pricing (kevin's section) | |||
Revision as of 15:30, 31 January 2015
test server: http://speedyguy17.info/ucpccc-master/
Class 0: 1/7
Notes
- Reading Input (also tips on eclipse debugging and submission instructions)
- Covered nwerc2014 Problem J
Homework
- Fill out the course information form https://docs.google.com/forms/d/1JFfFQhBfVy4dfTalXX0Xa6cYtvwTBVEvWz_TpdCm0xo/viewform
- Solve one problem from nwerc2014, submit it to http://icpc.egr.duke.edu, and contribute to the wiki page for the problem you solved
- Consider one of the officer positions in DPCC
Class 1: 1/14
Notes
- No class next week (MLK day)
Homework
- Solve any two problems from nwerc2014 or rmrc2014. Contribute to the wiki page for the problem you solved
- OLA's section solve problems A and B from rmrc2014
- Kevin's section try to solve problems F and I from nwerc2014
=Class 2: 1/28]
Notes
- Covered "finding lines
- very low tolerance, can use randomized algorithm
- 10^5 is too slow for n^2....break it into two (or more groups), solve for each group and then combine the solutions (divide and conquer!)
- Indoorienteering
- NP complete, clear must be some brute force solution because n=14 (small)
- since must reach all points, fix one of them as the start point (14! => 13!)
- split it up into two halves, iterating over the midpoint (13 * (12 choose 6) * 6!*6!)
- store the results of one half in a hashmap, and then when doing the second half, simply check whether the proper distance exists in the hashmap (13 * (12 choose 6) * (6! + 6!))
- Divide and conquer (again)
- Plane ticket pricing
- brute force too slow (and can have invalid solutions...because we only have so many seats)
- greedy doesn't work because we can make a selection now that can hurt us later
- above points SCREAM DP
- time almost always a dimension of the DP
- other things that can lead to invalid solutions (selling too many seats) also almost always a dimension
- value stored is almost always the thing we're trying to solve for (most amount of money)
Homework
- Solve Preorder Traversals from ncna2014 (OLA's section)
- Solve Finding Lines (if you haven't already) using either of the two discussed methods (or your own!) (Kevin's section)
- Solve Plane ticket pricing (kevin's section)