Algorithmic Problem Solving

Arne Andersson

Course Evalutaion

http://evaluering.ibg.uu.se/it

TextBook

Zbigniew Michalewicz, David B. Fogel: How to Solve It: Modern Heuristics

Handout material

• Lecture notes on Integer Programming http://www.it.uu.se/edu/course/homepage/ehandel/V04/IP.html

Task and Deadlines

For exercises: Hand in your solution either on paper on in an email with "APS" in the header.

• First assignment, Use Citeseer and try to find the most cited paper presenting a solution to the Traveling Salesman Problem (TSP). Find, using Citeseer and/or any search engine, your favorite paper on TSP and make a four-slide executive summary. Deadline, Wednesday Jan 23. You should deliver
  1. (i) Title, author, journal/conference etc of the most cited paper,
  2. (ii) the same for the paper presenting the best solution (in your opinion),
  3. (iii) plus a 4-slide executive summary of your favorite paper.

- If you mail your solution, make sure to write "APS" in the header

• second assignment: Read the book chapters 1-4 and be prepared to discuss them. Dedaline Monday Jan 28.

• third assignment: Read the book chapters 5,6 and be prepared to discuss them. Dedaline Thursday Jan 31.

• fourth assignment: Find your favorite paper on Tabu Search and write an executive summary. Do the same for your favorite paper on simulated annealing. Deadline: Friday Feb 8

• fifth assignment: Find your favorite paper on Genetic Algorithms and write an executive summary. Deadline: Tuesday Feb 12

Main assignment

Find a good pa er on algorithms and/or optimization, preferrably from a ACM or IEEE journal or conference. Write a 2-3 page executive summary, make a 5-slide presentation.
This assignment is done individually, you can not cooperate in pairs. Deadline: Tuesday Mar 4.

Schedule

Day	Date	Time	Type	Room	Lecturer	Subject	Book chapters
Tue	Jan 22	10:15-12:00	Lecture	1145	Arne Andersson	Introduction,
Wed	Jan 23	13:15-15:00	Lecture	1145	Arne Andersson		Discussion of TSP
Mon	Jan 28	10:15-12:00	Lecture	1145	Arne Andersson		Duscussion on book chapters 1-4
Thu	Jan 31	13:15-15:00	Lecture	1145	Arne Andersson		Duscussion on book chapters 5,6
Tue	Feb 5	13:15-15:00	Lecture		CANCELED
Fri	Feb 8	15:15-17:00	Lecture	1145	Arne Andersson		Assignements on Tabu Search and Simulated Annealing
Tue	Feb 12	10:15-12:00	Lecture	1145	Arne Andersson		Assignment on Genetic Algorothms
Wed	Feb 13	10:15-12:00	Lecture	1145	Arne Andersson		Integer programming
Wed	Feb 27	15:15-17:00	Lecture	1145	Arne Andersson		NP-completeness
Fri	Feb 29	10:15-12:00	Lecture	1146	Arne Andersson
Tue	Mar 4	15:15-17:00	Lecture	1145	Arne Andersson	Student presentations
Fri	Mar 7	15:15-17:00	Lecture	1145	Arne Andersson	Student presentations

Useful Links

• CiteSeer, for finding articles, refernces, etc: http://citeseer.ist.psu.edu/
• A nice presentation of the Traveling Salesman Problem: http://www.tsp.gatech.edu/
• See also this page on TSP art: http://www.oberlin.edu/math/faculty/bosch/making-tspart-page.html
• Dictionary of Algorithms and Data Structures http://www.nist.gov/dads/
• Compendium on NP Optimization Problems http://www.nada.kth.se/~viggo/problemlist/compendium.html
• DIMACS Implementation Challenges http://dimacs.rutgers.edu/Challenges/
• The art gallery problem Given a polygon-shaped art gallery with n sides, what is the minimal number of guards that need to be placed in the gallery so that they see every corner of it? There are museums with 3n walls for which n guards are required. On the other hand, floor(n/3) guards are enough for any n walls museum, but an algorithmic problem could be to determine the positions of them. http://mathworld.wolfram.com/ArtGalleryTheorem.html
• Related (difficult) problems are 5, 6, 7 of http://www.ics.uci.edu/~eppstein/280g/open.html
• Solving Rubik's Cube. Maybe too famous, there are solutions at, e.g., http://helmsoft.org/cube/rubikscube
• Given a finite set of building blocks consisting of several 1x1x1 cubes (or, in the 2d version, 1x1 squares) glued together at facets, put them together into a big cube (rectangle) of given dimensions. The Slothouber-Graatsma Puzzle http://mathworld.wolfram.com/Slothouber-GraatsmaPuzzle.html and Conway's Puzzle http://mathworld.wolfram.com/ConwayPuzzle.html are special cases.
• Magic squares: How to generate magic squares (nxn matrices with constant row, column, and big diagonal sums). The magic squares are obviously solutions to a linear equation system so they form a subspace of the space of all nxn matrices. But you can easily invent restrictions that makes it more interesting, such as requiring all numbers to be prime, or powers, or any other numerologically interesting property. You can also try many-dimensional magic squares. see http://mathworld.wolfram.com/topics/MagicSquares.html
• The Domino game: Given a game board consisting of a subset X of {0,...,n}^2, player 0 and 1 alternatingly remove two adjacent squares from X. (Equivalently, paint some squares of a chessboard red, then try to cover only red squares with domino bricks.) The player that gets stuck first (cannot move) loses.
• http://www.ics.uci.edu/~eppstein/junkyard/open.html. Open Problems in Computational Geometry
• http://cs.smith.edu/~orourke/TOPP/Welcome.html. The Open Problems Project
• http://www.ics.uci.edu/~eppstein/280g/open.html. Mesh Generation for Graphics and Scientific Computation, Open Problems
• http://www.ics.uci.edu/~eppstein/cgt/. Combinatorial Game Theory
• http://mathworld.wolfram.com/topics/MagicSquares.html
• http://mathworld.wolfram.com/topics/Chess.html