Compsci 149s, Fall 2011, Syllabus

Compsci 149s, Fall 2011, Syllabus

• Course Info
• Syllabus
• Getting Started

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:

• Week 0 (August 29th)
• Week 1 (September 5th)
• Week 2 (September 12th)
• Week 3 (September 19th)
• Week 4 (September 26th)
• Week 5 (October 3rd)
• Week 6 (October 10th)
• Week 7 (October 17th)
• Week 8 (October 24th)
• Week 9 (October 31st)
• Week 10 (November 7th)
• Week 11 (November 14th)
• Week 12 (November 21st)
• Week 13 (November 28th)

Week 0 (August 29th): Intro/Greedy

Topics:

• Administrivia
• Basic structure of ACM and TopCoder problems
• Greedy algorithms
• Notes are here
• (optional) TopCoder greedy algorithms tutorial

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

Week 1 (September 5th): Graphs 1

Topics:

• Graph representations
• DFS
• BFS
• Trees
• Notes are here
• Example code showing BFS and DFS
• (optional) TopCoder graph introduction: Part 1, Part 2

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

Week 2 (September 12th): Graphs 2

Topics:

• Priority queues, general search algorithms
• Prim's MST
• Dijkstra
• (Notes to be posted.)
• Code for Prim's and Dijkstra
• (optional) TopCoder graph introduction: Part 3

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

Week 3 (September 19th): In-Class Practice / TopCoder SRM 519

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.

Week 4 (September 26th): Graphs 3

Topics:

• Floyd-Warshall
• directed acyclic graphs/strongly connected components
• Kosaraju/Tarjan (if we have time)
• Example Floyd-Warshall code

Competitions:

• UM Team Practice - September 27th, 2011, from 8PM to 10PM

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.

Week 5 (October 3rd): Dynamic Programming 1

Topics:

• Intro to dynamic programming
• (optional) TopCoder dynamic programming introduction: Part 3
• (Notes to be posted.)

Competitions:

• TopCoder SRM 520 - October 4th, 2011, from 11AM to 1PM
• UM Team Practice - October 4th, 2011, from 8PM to 10PM

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.

Week 6 (October 10th): Fall Break / Max Flow (Optional)

Topics:

• TopCoder tutorial on max flow

Competitions:

• TopCoder SRM 521 - October 13th, 2011, from 7AM to 9AM

Assignment:

Enjoy fall break! If you want to do a few more problems, we suggest either:

1. Working on more of the dynamic programming problems above, if you are not so familiar with dynamic programming.
2. 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)

Week 7 (October 17th): Dynamic Programming 2 / Math 1

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

Week 8 (October 24th): Math 2

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)

Week 9 (October 31st):

Competitions:

• ACM-ICPC Mid-Atlantic Regional Competition - November 5th, 2011, 9AM - 5PM

Week 10 (November 7th): Intro to Ants

Notes:

• Class Notes
• Ants AI Challenge Website

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

Week 11 (November 14th):

Notes:

• A*
• Java Example

Week 12 (November 21st):

Week 13 (November 28th):

Course Evaluation for non-registered students

Notes:

• Ants Fighting

Assignment:

• Sumbit final Ants project by SUNDAY NIGHT (before 8am on Monday)

Read full article from Compsci 149s, Fall 2011, Syllabus