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)

Class 3: 2/2

Problems: http://cerc.tcs.uj.edu.pl/2014/data/cerc2014problems.pdf

Notes

• Covered Can't Stop Playing
  • just like http://gabrielecirulli.github.io/2048/ but in 1 dimension
  • can't get small numbers stuck between big numbers
  • greedy solution should work, or smart brute force (try everything, but eliminate losing positions based on above point)
  • since only one of each power of 2 on each side, and must go in order, can simply store in a bit field, and use "lowest ones bit"
• Covered Pork Barrel
  • Seems like category:Minimum Spanning Tree but too much time to recompute for all the test cases
  • How do we use data computed from previous test cases in newer test cases?
• Covered Wheels
  • Have to figure out which wheels are connected to which...BFS!

Homework

• Solve Underground Cables Link: https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=403&page=show_problem&problem=2873 (Kevin's Section)
  • Feel free to use my MST code: http://speedyguy17.info/algorithms/kevins%20algos/src/MST.java
• Derive an algorithm for Pork Barrel (Kevin's Section)
  • HINT: read about Kruskal's algorithm: http://en.wikipedia.org/wiki/Kruskal%27s_algorithm and Reverse-delete algorithm: http://en.wikipedia.org/wiki/Reverse-delete_algorithm
• Solve Wheels (owen's section)
• Ask for a wiki login and contribute for the problem you solved!