====== CS 39000-CP0: Competitive Programming ====== Development of strategies, techniques, and skills used in competitive programming contests. Topics include problem solving and programming techniques and algorithms. Course format consists of a twice-weekly meetings that includes brief discussion, problem solving and programming practice, a practice programming contest, and a wrap-up discussion. Grading is based on class attendance and participation, problem solving skills, and programming contest progress and results. Credit: 1 hour. Prerequisite: CS 25100 (Data Structures and Algorithms). Text: //Competitive Programming 2//, by Halim and Halim, Lulu. You may get either the original (2011) [[http://www.lulu.com/shop/steven-halim/competitive-programming-2/paperback/product-16377304.html|A5 edition]] or the new (2012), larger [[http://www.lulu.com/shop/steven-halim/competitive-programming-2-a4/paperback/product-20143247.html|A4 edition]]. \\ **//Class is over for the semester!\\ Congratulations to all ACM ICPC ECNA RPC participants. Results are at the [[http://acm.ashland.edu|Ashland]] site. Good luck next year!//** ====== Course/Lab Meetings (Required) ====== * 3:00-5:50 Thursdays (Aug 23-Nov 1, 2012) * LWSN B146 This term we will be using Piazza for class discussion. The system is highly catered to getting you help fast and efficiently from classmates, the TA, and myself. Rather than emailing questions to the teaching staff, I encourage you to post your questions on Piazza. If you have any problems or feedback for the developers, email team@piazza.com. ====== Other Events (Mark Your Calendar!) ====== * Sep. 29, 3:00-8:00 pm: //Practice Contest// (pizza included!). All Purdue students welcome (not just CS 39000-CP0 students). Sign up [[http://cs.ecs.baylor.edu/~hamerly/icpc/qualifier_2012/|here]] for "East Central NA Qualifier". Send [[mailto:jtk@purdue.edu|me]] with your ICPC login (preferably your Purdue email address). * November 2-3, 2012: //ACM Regional Contest.// Leave Friday (11/2) at 1:00 pm for Cincinnati, compete Saturday (11/3) 10:00-3:00, return Saturday evening. Only the 12 students who are chosen to compete in the contest are required to attend. ====== Class/Lab Schedule for Fall 2012 ====== - [08/23]: [[https://docs.google.com/present/view?id=dtfz3pn_0cbgtnqhn|Introductions, contest guidelines, course logistics, practice contest.]] ([[contest_2012-08-23|Contest: Ad Hoc Problems]]) - [08/30]: [[https://docs.google.com/present/view?id=dtfz3pn_3d8crchdf|Announcements, concepts, and problems.]] ([[contest_2012-08-30|Contest: Linear Data Structures]]) - [09/06]: [[https://docs.google.com/present/view?id=dtfz3pn_4f78msxff|Announcements, ACM qualifier, DS notes.]] {{::week02_ds_libraries.pdf|Halim DS Slides.}} This weekend: {{::purdue-hackathon.pdf|Hackathon}} and [[http://hackerrank.com/hackergames|Hacker Games.]] ([[contest_2012-09-06|Contest: Non-Linear Data Structures]]) - [09/13]: [[https://docs.google.com/present/view?id=dpvv85p_58dq4tzbd6|Announcements and Notes.]] [[contest_2012-09-13|Contest: Complete Search]] - [09/20]: [[https://docs.google.com/present/edit?id=0AcVsm1lcySCMZHB2djg1cF82MGtnajY2emN0|Announcements and Notes.]] [[contest_2012-09-20|Contest: Divide and Conquer (with Binary Search) and Greedy]] - [09/27]: [[https://docs.google.com/presentation/d/1Ju5K2E0AK-4Q_ido5fqcf9d22BoFOJXEmCW1WUBD_98/edit|Announcements and Notes.]] [[contest_2012-09-27|Contest: Dynamic Programming I]] - [10/04]: [[https://docs.google.com/presentation/d/1jFAmWRVlJKe1Ndffj2Q9_-F5GZQ02wohWfXYAUD9HWQ/edit|Announcements and Notes.]] [[contest_2012-10-04|Contest: Dynamic Programming II]] - [10/11]: [[https://docs.google.com/presentation/d/1HsLjaX7WHsVL4NFUzdIhaUm4ZlqSNdMc1XN0YLwGtXE/edit|Announcements and Notes.]] [[contest_2012-10-11|Contest: Graph Traversal]] (also, for help testing, try using the [[dominator_data|Dominator Data]]) - [10/18]: [[https://docs.google.com/presentation/d/14dO7CGuSSBJO-BEwoLR175SSm7wr3hprDXU9ch0fReM/edit|Announcements and Notes.]] [[contest_2012-10-18|Contest: More BFS (Single-Source Shortest Path)]] - [10/25]: [[https://docs.google.com/present/edit?id=0AcVsm1lcySCMZHB2djg1cF82MWhydGh4NWZ3|Teaming Notes.]] [[contest_2012-10-25|Contest: PC^2 Team Set]]; [[http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=331|ECNA 2008 at OnlineJudge]] (link is flaky; when it works, it links to livearchive.onlinejudge.org) - [11/01]: [[https://docs.google.com/present/edit?id=0AcFgahwA2c79ZHRmejNwbl82aGZycTZzZDU|Contest Notes.]] [[contest_2012-11-01|Contest: PC^2 Team Set]] Other topics to be sprinkled in: - [00/00]: [[contest_2012-00-00|Contest: Minimum Spanning Tree]] - [00/00]: [[contest_2012-00-00|Contest: All-Pairs Shortest Path]] - [00/00]: [[contest_2012-00-00|Contest: Max Flow]] - [00/00]: [[contest_2012-00-00|Contest: DAGs, Trees, and Other Graphs]] ====== Other Notes ====== * Things to do: * Sign up at Piazza: https://piazza.com/purdue/fall2012/cs39000cp0 * Sign up at UVa: http://uva.onlinejudge.org (if you get a "redirect loop", delete your onlinejudge cookies) * Register your UVa user name ("handle") at: http://pc.cs.purdue.edu/progress (use Profile button at top) * Halim [[https://sites.google.com/site/stevenhalim/home/material|downloadable]] code from the book * Tutorial on [[http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor|Segment Tree and Lowest Common Ancestor]] * UVa problem [[http://uvatoolkit.com/problemssolve.php|output generator]], producing correct output from your choice of input * Blackboard Learn [[http://mycourses.purdue.edu|link]] * [[mid-semester_evaluations|Mid-Semester Evalutions (Fall 2012 TBD)]] * [[http://acm.ashland.edu|Review of ACM-ICPC ECNA RPC Problems]] * [[http://www.youtube.com/watch?v=_YwN3c8kPxA|Tips from 2012 ICPC International teams]] * Instructions for [[competing_remotely|competing remotely]] with the PC^2 software. * [[http://picasaweb.google.com/jtkorb/ACMICPCECNARPC2010?authkey=Gv1sRgCM3kwoDmpNTCPQ&feat=directlink|RPC Pictures]] from 2010. Enjoy! * There are at least 19 problems that are not correctly judged by the Programming Challenges (PC) website (http://www.programming-challenges.com). Here are the problems with the corresponding UVA (http://uva.onlinejudge.org/) problem number in parenthesis (from [[http://www.programming-challenges.com/bb/viewtopic.php?f=1&t=7|here]]): 110104 (706) 110204 (843) 110208 (10149) 110307 (10150) 110402 (120) 110403 (10037) 110404 (10191) [ not listed at website ] 110407 (10152) 110508 (10202) 110705 (10168) 110802 (10181) 110808 (10270) 110906 (10051) 111002 (10054) 111007 (10249) 111008 (10092) 111101 (10131) 111106 (10261) 111305 (10167) 111307 (10209) * Another useful source of competitive programming tips comes from [[http://anh.cs.luc.edu/314-315/basics.html|Andrew Harrington]]. ====== Statement Concerning Campus Emergencies ====== [[http://www.itap.purdue.edu/tlt/faculty/|Campus Emergency Information]] In the event of a major campus emergency, course requirements, deadlines, and grading percentages are subject to changes that may be necessitated by a revised semester calendar or other circumstances. Here are ways to get information about changes in this course: this web page, my email address (jtk@purdue.edu), and my office phone (494-6184). ====== Schedule for Fall 2011 (FYI Only) ====== Topics by week (based on Skiena textbook and course topics; subject to change): - [08/23]: [[https://docs.google.com/present/edit?id=0AcVsm1lcySCMZHB2djg1cF80NWM2NmM0NDZ2&hl=en&authkey=CPWxqcQK|Getting Started]] | [[contest_2011-08-23|Contest]] - [08/30]: [[https://docs.google.com/present/edit?id=0AcVsm1lcySCMZHB2djg1cF81NGRwbnB2cHJj&hl=en_US|Data Structures]] | [[contest_2011-08-30|Contest]] - [09/06]: Strings, Sorting, Arithmetic and Algebra | [[contest_2011-09-06|Contest]] - [09/13]: More Strings, Sorting, Arithmetic and Algebra, with Combinatorics | [[contest_2011-09-13|Contest]] - [09/20]: [[https://docs.google.com/present/edit?id=0AcVsm1lcySCMZHB2djg1cF81NWNxa242YmY1&hl=en_US|Still More Strings, Sorting, Arithmetic and Algebra, and Combinatorics]] | [[contest_2011-09-20|Contest]] - [09/27]: Number Theory | [[contest_2011-09-27| Contest]] - [10/04]: [[https://docs.google.com/present/edit?id=0AcVsm1lcySCMZHB2djg1cF81NmNiZnZjY2Yz&hl=en_US|Announcements]] and [[http://prezi.com/h7i9ejy1ta6h/backtracking/?auth_key=a21fc6e47fa176f93a3ad63d3c622e0c565ff326|Backtracking]] | [[contest_2011-10-04| Contest]] - [10/11]: //fall break (no class)// | [[http://spoj.pl/PCS11|Team Practice Contest]] - [10/18]: Graph Traversal, Graph Algorithms, Dynamic Programming | [[icpc_logistics]] | [[https://docs.google.com/present/edit?id=0AcVsm1lcySCMZHB2djg1cF80OWQ0M2drdmhj&hl=en&authkey=COLR5PkN|Competition Notes]] | [[http://spoj.pl/PCS11B|Team Practice Contest]] - [10/25]: //competition make-up 1 (no class)// - [11/01]: ICPC Competition I | {{:icypc-2011.pdf|Lecture Notes}} | [[http://www.bikmort.com/dokuwiki/icypc_instructions|Local Instructions]] | [[http://queue.acm.org/icpc/|Queue ICPC Site]] - [11/08]: ICPC Competition II - [11/15]: ICPC Competition III - [11/22]: //Thanksgiving// - [11/29]: //competition make-up 2 (no class)// - [12/06]: ICPC Tournament (bonus points awarded) Old textbook: [[http://www.amazon.com/exec/obidos/ASIN/0387001638/thealgorithmrepo|Programming Challenges]]//, Steven S. Skiena and Miguel Revilla, Springer, 2003 (ISBN 978-0387001630).