Spring15

Roster: https://docs.google.com/spreadsheets/d/1CEfNGq704EN6WhBqrFYFrkYb4wDWU4zV9wznkt5TxOU/edit#gid=200319886

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)