Syllabus
Problems are roughly sorted by difficulty. Problems are usually related to material covered during the lecture; however, there are usually one or two unrelated problems thrown in as well. Read
this page to figure out how to test your solutions. Submit your solutions via email to hewner at cs dot duke dot edu. Problems turned in late will receive reduced credit.
Contents:
Topics:
Assignment:
Due 5PM Monday, September 5th: Do at least two problems from the current problem set, and one problem from next week's set.
- Google Code Jam, 2011, Round 2, Walkways
- TopCoder, SRM 311, MatrixTransforming
- TopCoder, SRM 512, DoubleRoshambo
- Google Code Jam, 2011, Qualification Round, Candy Splitting
- TopCoder, SRM 414, StringInterspersal
- TopCoder, SRM 502, TheProgrammingContestDivOne
- TopCoder, SRM 466, MatrixGame
Topics:
Assignment:
Due 5PM Monday, September 12th: Do at least two problems from the Week 1, and one problem from the Week 2 Set. For those new to graph theory, we recommend KingdomXCitiesandVillagesAnother.
- CS 100 APT, WordLadder
- TopCoder, Member Beta SRM, ErdosNumber (The Member
Beta SRM took place between SRMs 446 and 447.)
- TopCoder, SRM 316, SpreadingNews
- TopCoder, SRM 440, MazeWanderingEasy
- TopCoder, SRM 505, RectangleArea
- TopCoder, SRM 443, CirclesCountry
- TopCoder, SRM 302, DivisorInc
Topics:
Assignment:
- TopCoder, SRM 503, KingdomXCitiesandVillagesAnother Hint: This problem can be solved using a modification of Prim's algorithm. If you don't know Prim's algorithm, it's definitely worth looking it up and practicing it on this problem.
- TopCoder, SRM 383, HillWalker
- CS 100 APT, AllWordLadders
- TopCoder, SRM 474, TreesCount
- TopCoder, Pilot 2, TransportationNetwork (Pilot 2 took place between SRMs 449 and 450.)
- TopCoder, SRM 451, PizzaDelivery
- TopCoder, SRM 479, TheAirTripDivOne
Topics:
- During this class period we will not focus on a specific topic, but we will break into groups to work on the problem set.
- The class will be followed by SRM 519. Problems from the SRM will count towards problems solved for this problem set.
Assignment:
- Google Code Jam, 2010, Qualification Round, Bot Trust
- Google Code Jam, 2010, Round 1B, File Fix-it
- Google Code Jam, 2011, Qualification Round, GoroSort
- Google Code Jam, 2010, Round 1B, Your Rank is Pure
- Problems from TopCoder SRM 519.
Topics:
Competitions:
Assignment:
Due 5PM Monday, October 3rd: Do at least two problems from this week's set, and one problem from next week's set. We suggest looking at the Fibonacci and combination problems.
- Mid-Atlantic ACM Regional Programming Contest, 2009, Word Ladder (Problem H)
- TopCoder, TCCC 07, Semi 3, Police
- TopCoder, SRM 516, NetworkXMessageRecovery
- TopCoder, SRM 480, NetworkSecurity
- German Collegiate Programming Contest, 2010, Field Plan (Problem D)
- Northwestern European Regional Contest, 2008, Proving Equivalences (Problem B)
- TopCoder, SRM 500, FractalPicture
- Any problems from the UM Team Practice, September 27th, 2011.
Topics:
- Intro to dynamic programming
- (optional) TopCoder dynamic programming introduction: Part 3
- (Notes to be posted.)
Competitions:
Assignment:
- Fibonacci Numbers
- Combinations
- Greater New York Regional Contest, 2008, Recursively Palindromic Partitions (Problem D)
- Nordic Collegiate Programming Contest, 2006, Honeycomb Walk (Problem I)
- Dennis Matveyev Programming Contest, 2010, Coins (Problem A)
- Mid-Central Regional Programming Contest, 2005, Pascal's Travels (Problem A)
- Google Code Jam, 2009, Qualification Round, Welcome to Code Jam
- Greater New York Regional Contest, 2009, Balls (Problem C) --- It is not too difficult to find an O(B*M^2) solution. Can you do better? Can you explain what this solution is doing?
- Mid-Atlantic ACM Regional Programming Contest, 2010, Roller Coaster (Problem F)
- TopCoder, SRM 511, FiveHundredEleven
- TopCoder, SRM 520, SRMIntermissionPhase
- Any problems from the scrimmages/competitions that we did this week.
Topics:
Competitions:
Assignment:
Enjoy fall break! If you want to do a few more problems, we suggest either:
- Working on more of the dynamic programming problems above, if you are not so familiar with dynamic programming.
- For more advanced students, solving some of the max flow problems below would be helpful.
- Mid-Central Regional Programming Contest, 2005, Leapin' Lizards (Problem H)
- Northwestern European Regional Contest, 2007, March of the Penguins (Problem B)
- TopCoder, SRM 477, PythTriplets
- TopCoder, SRM 465, GreenWarfare
- Stanford Local ACM Programming Contest, 2010 October 10, Matryoshka Dolls, Again (Problem D)
- Northwestern European Regional Contest, 2004, Taxi Cab Scheme (Problem C)
Topics:
- More dynamic programming
- Bitmasking
- Probability
- Notes
Competitions:
- ACC Scrimmage - October 23rd, 2011, 1PM to 6PM (Problem set here.)
Assignment:
- TopCoder, SRM 422, PrimeSoccer
- TopCoder, SRM 488, TheBoredomDivOne
- TopCoder, SRM 475, RabbitStepping
- TopCoder, SRM 464, ColorfulMazeTwo
- Southeastern European Regional Contest, 2008, Lucky Numbers (Problem G)
- TopCoder, SRM 459, ParkAmusement
- Nordic Collegiate Programming Contest, 2006, Shoot-out (Problem A)
- TopCoder, SRM 519, RequiredSubstrings (from a previous set)
- Any problems from the scrimmage: Link
Topics:
- BigInteger
- Useful mathematical algorithms from the library
- Dot/cross products
- Polygon area
- Convex hull
- (Notes to be posted.)
Competitions:
- TopCoder SRM 522 - October 26th, 2011, from 9PM to 11:30PM
- ACC Scrimmage 2 - October 30th, 2011, 1PM to 6PM
Assignment:
- Google Code Jam, 2009, Round 1C, All Your Base
- TopCoder, SRM 455, EasySequence
- East Central North American Regional Contest, 2003, This Takes the Cake (Problem H) (from a previous set)
- Greater New York Regional Contest, 2009, Convex Hull of Lattice Points (Problem G)
- TopCoder, SRM 467, SuperSum
- Internet Problem Solving Contest, 2010, Broadway (Problem B)
- East Central North American Regional Contest, 2004, I Conduit! (Problem D)
- German Collegiate Programming Contest, 2010, The Two-ball Game (Problem J)
Competitions:
Notes:
Assignment:
- Final Ants project requirements (due last day of class) on blackboard
- Choose your Ants team
- Get the ants environment set up (you can start here)
- Write ants that can at least search for food (if you're writing in Java or Python, go through the whole tutorial)
- Submit your code/team members via blackboard
Notes:
Course Evaluation for non-registered students
Notes:
Assignment:
-
Sumbit final Ants project by SUNDAY NIGHT (before 8am on Monday)