Ausgewählte Probleme aus dem ACM Programming Contest

Mittwochs, 13:30 - 15:00 und 15:15 - 16:45, Raum R2.014Modul-Beschreibung
Dozentin: Doina Logofătu  ^


Die Vorlesung verwendet C, C++ oder Java als Programmiersprache.
Der Kurs folgt dem Buch
Algorithmen und Problemlösungen mit C++ (einige Themen findet man auch in [2]).
Dieses Lehrbuch zur Vorlesung ("Kursbuch") findet man in unserer Bibliothek (auch Online im Campus).

Online Platform: ACM Uva Online Judge
Electronic Board: acm.uva.es/board/
Bitte nicht vergessen!: Kopfkommentar


Bericht NWERC-TeilnahmeACM-Teilnahme Infos

INFO:  Konferenz-Teilnahme DAS 2010 Rumänien, 26-31. Mai 2010: Bilder, Bericht News, Bericht Felix
INFO:  HM Teams belegen Plätze 20, 24 und 33 beim German Collegiate Programming Contest 2010, 12. Juni 2010: Bericht, Bilder, Aufgaben, Solutions Outline, Abschlusstabelle
INFO:  Programming Day 31. Oktomber 2010, Aufgaben, Fotos
INFO:  Programming Day 14. November 2010, Aufgaben, Fotos
INFO:  Teilhnahme NWERC 2010, 21. November 2010, Fotos

North Western European Regional Contest, Bremen, November 19-21, 2010     Registrierungen


StudentIn / Team

Accepted

gelöste Probleme

Marion Gödel

2
[10424][11172]
Stefan Burgmair 18

[10424][11172][10405][836][108]
[574][679][539][436][989][260][10305][10307]
[624][542]
[10432][11984][11936]

Christian Posselt
Christian Mitterreiter
18
[11877][11878][374][489][10424][11172][11734]
[357][674][750][534][11462][291][624][914][10491][11710][10056]

Präsentation

Rolf Schirm
23
[10424][489][11716][357][231][497][10405][674][147]
[348][11462][11321][524][10344][10000][601][775][624][914][10129][542][10245][523]

Präsentation

Christian Beinhofer
13
[10424][11172][11703][11734][10038][11659]
[352][469]
[524][10288][532][601][785]

Hidir Sayli 5
[11172][640][10405][112][10074]

Bastian Hoecker, Philipp Hauck

18
[10038][10193][10424][11172]
[10405][111][11716][531][10465][574][11321][10297][146][624]
[164][526][481][231]

Joseph Weigl, Thomas Müller

13
[10038][10424][11172][11716][10193][102][111][382][10405]
[216][357][10327][601]


Fotos Referate

Kursablauf

SW *
KW *
Thema
Vorlesung
Praktikum

1


OnlineJudge-Einführung
Infoveranstaltung





Warm-Up


Vorlesung01







Beispiele:
The 3n+1 Problem (100), Stacking Boxes (103)
Booklet Printing (637), The House of Santa Claus (291)



Relational Operator (11172), Big Number of Teams will solve This (11734),  Informants (11659), Love Calculator (10424), Perfection (382), B2-Sequence (11063), Above Average (10370), Jolly Jumpers (10038), All You Need Is Love! (10193), LC-Display (706), Ecological Bin Packing (102), Power of Cryptography (113), Digital Fortress (11716), sqrt log sin (11703), Big Mod (374), Product (10106), Super long sums (10013), Minesweeper (10189), No Problem (11608), Hello World! (11636),
Burger Time? (11661), Back to High School Physics (10071), Ecological Premium (10300),  Triangle Wave (488), Hangman Judge (489), Linear Cellular Automata (457), Marvelous Mazes (445),
Power Crisis (151), 487--3279 (755), The Coca-Cola Store (11877), Homework Checker (11878), Reverse and Add (10118)


2



Dynamische Programmierung: Counting Change, Longest Inc-/Decreasing Sequence, LCS, Matrix Chain Multiplication



[2] S. 403
[1] S. 231

2-DP


Tafelbilder 30.03:  1   2

6.04: 1  2  3
13.04: 1  2  3

Longest Common Subsequence (10405), Unidirectional TSP (116), Optimal Array Multiplication Sequence (348), Matrix Chain Multiplication (442), Let Me Count The Ways (357), Dollars (147), Coin Change (674), Histroy Grading (111), String Computer (164), Budget Travel (222), Testing the CATCHER (231), Strategic Defense Initiative (497), Jill Rides Again (507), String Distance and Transform Process (526), Compromise (531), Triangles (585), Self Numbers (640),  Walking on the Safe Side (825), Largest Submatrix (836), Vacation (10192), Longest Run on a Snowboard (10285), e-Coins (10306), Homer Simpson (10465), Sumsets (10125), Travelling Salesman (10702), Again Palindrome (10617), Make Palindrome (10453), Complete Tree Labeling (10247), The Unreal Tournament (10207), Facing Problem with Trees (10643), Super Lucky Numbers (10722), Bits (11645), Maximum Sum (108),
Optimal Cut (11782), Unique Story (11775), Up to the Ante (10811), Celebrity Split (11851), Tug of War (10032), What goes up (481)

Nächste Online-Wettbewerbe:    A Local Contest from México, 2.04.2011, 14:00 Uhr
Nächste Wettbewerbe:                A Regional Contest from México, 3.04.2011, 10:00 Uhr

                                                        Huge Easy Contest II, 9.04.2011, 10:00 Uhr


3



Backtracking






Sorting

[2] S. 403
[1] S. 357





 

All Squares (155), The Sultan's Successors (167), Getting in Line (216),  The House of Santa Claus (291), Word-Search Wonder (422),
Prime Ring Problem (524), Addition Chains (529), The Settlers of Catan (539), Jugs (571), CD (624), Su Doku (989), LED Test (416), The Tower of Babylon (437), Sum It Up (574), Bundling Newspapers (598), 8 Queens Chess Problem (750),  Not so Mobile (839), Another n-Queen Problem (11195), Sum-up the Primes (10419), 23 out of 5 (10344), Equidivisions (11110), Take the Land (10074)


Dancing Digits (11198), ShellSort (10152), DNA Sorting (612), Flip Sort (10327), Stacks of Flapjacks (120), Age Sort (11462), Vito's Family (10041), Sort! Sort!! and Sort!!! (11321), Ultra QuickSort (10810), Blind Sorting (11714), Where is Marble? (10474)


Nächste Online-Wettbewerbe:    A Contest dedicated to Renat Mullakhanov (rem), 16.04.2011, 11:00-16:00 Uhr
 

4


Graphen:

  - kürzeste Wege (Floyd-Warshall)

  - Tiefen- und Breitensuche

  - topologische Sortierung

  - minimaler Spannbaum





[2] S.  251

[Floyd-Warshall]


[BFS]  [DFS]


[Topologische Sortierung]


[Flooding-Algorithmus]


[Minimal Spannbaum]
[Kruskal] [Prim]

Dijkstra-Algorithmus



Tree Summing (112), The Postal Worker Rings Once (117), Trees on the level (122), Graph Coloring (193), Tree Recovery (536), Allways on the run (590), Mapping the Route (614), Is it a Tree? (615), The die is cast (657),  Dropping Balls (679), Longest Paths (10000), Bicoloring (10004), All Roads Lead Where? (10009), Wheres's Waldorf? (10010),
Robot Motion (10116), Roads in the North (10308), Ecosystem (626), Numbering Paths (125), Climbing Trees (115), Count the Faces (10178), Virtual Friends (11503), Travel Company (11874)

Frogger (534), Heavy Cargo (544), Risk (567),
Audiophobia (10048), The Tourist Guide (10099), Identifying Concurrent Events (334),  MPI Maelstrom (423), Arbitrage II (436), Page Hopping (821),

Shipping Routes (383), Software Allocation (259), Knight Moves (439), All Walks of length "n" from the first node (677),  We Ship Cheap (762),  Dungeon Master (532), Word Transformation (429), Vertex (280), Traveling Politician (10543), A Node Too Far (336),  Always in the Run (590),  The Net (627), Erdös Numers (10044), Friends (10608), Sorting Slides (663)


Rare Order (200), Ordering Tasks (10305), Following Orders (124), Ordering (872)


Arbitrage II (436), Wetlands of Florida (469),
The Seasonal War (352), The PATH (601), Grid Colouring (785), Il Giocco dell'X (260), Oil Deposits (572), Monkeys in a Regular Forest (776), Contour Painting (782), Maze Exploration (784), Expensive Subway (11710)


Frogger (534), Freckles (10034), Highways (10147), Connect the Campus (10397), Killing Alliens in Borg Maze (10307)

Ubiquitous Religions (10583), Antifloyd (10987), ACM Contest and Blackout (10600), Is There a Second Way Left? (10462), Lift Hopping (10801),
Sending Email (10986), Cockroach Excape Networks (10805), Buy or Build (3505), War (10158), The Toll! Revisited (10537),

The Gossipy Gossipers Gossip Gossips (10850), The Rock (10381), Return of the Jedi (10224), Easter Eggs (10857), A Node Too Far (336),
Graph Connectivity (459), Hamiltonian Cycle (775), Graph Construction (10720), Dijkstra, Dijkstra (10806),
Minimum Transport Cost (523)

Contest Simulation, 18.05.
[10297][146][624]
[914][11710][10129]


5



Wahrscheinlichkeitstheorie



Algorithmische Geometrie

Tafelbilder 01.06:  1   2  3


[Wahrscheinlichkeitstheorie]



[1] S. 219
[Computational Geometry]


Polygon Clipping


Smallest enclosing circle

Programming Day, 29. Mai 2011


Programming Day 19. Juni 2011
Bubble Sort (12004), Complete the Set (12011), Fast Matrix Operations (11992), Fire Station (10278), A Change in Thermal Unit (11984),
Galactic Bonding (11966), The Lazy Lumberjacks (11936), Net Profit (11932), Divisor Game (11960), Hapless Hedonism (11554),
Polygon Inside a Circle (10432), Electoral Districts (11793)




France '98 (542), Burger (557), Coupons (10288), Urn-ball Probabilities! (10169), What is the Probability? (10056), Probability (11346),
Joining With Friend (11722), Cows and Cars (10491),
Supermean (10883),

SCUD Busters (109), Polygons (137), Orchard Trees (143), Intersection (191), Convex Hull Finding (681), Moth Eradication (218),  Intersecting Lines (378), Globetrotter (535), Water Falls (833), Convex Hull (11626), The Closest Pair Problem (10245), Bey Battle (11378), The Skyline Problem (105), Pipe Fitters (121), Bumpy Objects (132), Mouse Clicks (142), All Squares (155), Laser Lines (184), Lining Up (270), Pipe (303), Cops and Robbers (361),  Overlapping Rectangles (460), Points in Figures: Rectangles (476),
Points in Figures: Rectangles and Circles (477), Points in Figures: Rectangles, Circles and Triangles (477), Polygon (634),
Gleaming the Cubes (737), Intersecting Line Segments (866), Overlapping Air Control Zone (904), Sunny Mountains (920), Rectangle by the Ocean (922), Horizon Line (972), Center of Masses (10002), Packing polygons (10005), Chainsaw Massacre (10043), Useless Tile Packers (10065), The Art Gallery (10078), Hotter Colder (10084),
Chinese Ink (11665), The Incredible Hull (596), Points (11072), Nails (11096),
Birthday Cake (10167), The silver bullet (11227)

Packing polygons (10005), Tower for Cellular Telephony (11681), Polygon Intersections (805),
Offset Polygons (877), Stack of Cylinders (915), Sunny Mountains (920), Nice Milch (10117), Polygon Intersection (10321), Cicles in Hexagon ;-) (10353),

* SW = "Semesterwoche", KW = "Kalenderwoche"

Literatur
 
1.  Doina Logofătu, Algorithmen und Problemlösungen mit C++, Vieweg Verlag, ISBN 978-3-8348-0763-2, 2010. (online in Campus)
2.  Doina Logofătu, Grundlegende Algorithmen mit Java, Vieweg Verlag, ISBN 978-3-8348-0369-6, 2008. (online in Campus)
3.  Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen - Eine Einführung, 2. Auflage, Oldenbourg Wissenschaftsverlag, München 2007, ISBN 978-3-486-58262-8.
  - Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. MIT Press, Boston 2001, 2002, 2003, 2005
     ISBN 0-262-53196-8. (engl. Orig.-Fass.)
4.
Online Platform: ACM Uva Online Judge
5. ProblemSolve Toolkit: http://www.uvatoolkit.com/problemssolve.php
6. World of Seven
7. Art of Programming Contest
8. Programming Challenges: http://www.programming-challenges.com
9. ICPC Live Archive: http://acmicpc-live-archive.uva.es/nuevoportal/
10. 
Common Mistakes in Online and Real-time Contests
11. 
Competition Strategies

Weiteres
12.  Timus Online Judge
13.  Hinweise für Neueinsteiger
14.  Topcoder: ein weiterer Programmierwettbewerb, der nicht nur Studenten offen steht
15.  Problemsets: http://bbs.cooldavid.org/acm/

Java
15. 
Java™ Platform, Standard Edition 6 API Specification, Online Referenz: http://java.sun.com/javase/6/docs/api/, Sun Microsystems, Inc, 2006.