Hemuppgifter

Uppgifterna kommer att dyka upp här successivt under kursens gång.

Problem lösta innan deadline ger 1 betygspoäng, problem lösta efter deadline ger 0,5 betygspoäng på momentet OVN1. Lösningar kommer att gås igenom på entimmespass strax efter respektive deadline. Se schemat för plats.

Problem märkta med (*) bedöms vara lite svårare och för att få ett A behöver man (förutom övriga krav för A) lösa minst ett av dessa per hemtalsomgång.

Vecka 1: Uppvärmning / Giriga algoritmer / Dynamisk programmering

Deadline: 2013-01-31 12:00

• Ants (*)
• Buying Coke
• Cheering Game
• Introspective Caching (*)
• Moving Pianos
• The Mailbox Manufacturers Problem

Vecka 2: Datastrukturer

Deadline: 2013-02-07 12:00

• Almost Union-Find
• CD
• Chopping Wood (*)
• Mega-Inversions (*)
• The SetStack Computer
• Turbo

Vecka 3: Strängar och strängmatchning

Deadline: 2013-02-14 12:00

• Dominant Strings
• Dvaput
• Intellectual Property (*) (Obs: i detta problem är Kattis petig med whitespace i utdata, som måste vara exakt rätt. Tänk också på att utdataspecifikationen säger att det ska vara en tom rad mellan testfall, det ska alltså inte vara någon tom rad efter det sista testfallet!)
• Messages From Outer Space
• Phone List
• SMS Typing (*)

Vecka 4: Dynamisk programmering igen

Deadline: 2013-02-21 12:00

• Cheating Luck
• Copying DNA (*)
• Shoot-Out (*)
• Square Fields (Att titeln säger 'hard' betyder inte att problemet räknas som *-märkt!)
• The Uxuhul Voting System
• Whac-a-Mole (Det finns ett lömskt specialfall. Tips: se bilden!)

Vecka 5: Grafalgoritmer I

Deadline: 2013-02-28 12:00

• Coast Length
• Frogger
• Killing Aliens in a Borg Maze (*)
• Money Matters
• Slikar
• Subway Tree System (*)

Vecka 6: Grafalgoritmer II

Deadline: 2013-03-07 12:00

• Bicikli (*)
• Budget (*)
• Full Tank?
• Get Shorty
• Jogging Trails
• Proving Equivalences

Vecka 7: Kombinatorisk sökning

Deadline: 2013-04-11 12:00

• A Different List Game (*)
• All Friends
• Gokigen Naname
• Knights in Fen
• Maximum Loot (*)
• Who owns the Amiga?

Vecka 8: Aritmetik

Deadline: 2013-04-18 12:00

• Dick and Jane (*)
• Ignore the Garbage
• Ladder
• Perfect Pth Powers (Tänk efter!)
• Three Digits (*)
• Three Powers

Vecka 9: Talteori

Deadline: 2013-04-25 12:00

• A List Game
• Factovisors
• Gears in Action (*)
• Granica
• Jackpot
• Sequence (*)

Vecka 10: Kombinatorik / Sannolikhetsteori

Deadline: 2013-05-02 12:00

• Boastin' Red Socks
• Blocks on Blocks (*)
• Cat Coat Colors (*)
• Honey Comb Walking
• So You Want To Be A 2^n:aire?
• Zapis

Vecka 11: Beräkningsgeometri

Deadline: 2013-05-09 12:00

• Airline Hub
• Barking Up The Wrong Tree (*)
• Billiard
• Biometrics
• White Water Rafting
• Square Pie (*)

Vecka 12: Gott och blandat

Deadline: 2013-05-16 12:00

• Bachet's Game
• Cycles (*)
• Factstone Benchmark
• Fire Station
• Hay Points
• Ice Floe Jumping (*)
• Ones
• Peer Streaming
• Tour de France
• Watering Grass