CS 297: Championship Algorithms

Presentations

The schedule:

  January   14     Introduction
            21     MST-lecture
            28     MST-lecture, TSP-lecture
  February   4     TSP-lecture, MST-1 (Scott M)
            11     No class
            18     [Phillips-736] TREC lecture, TSP-lecture
            24     DUE: Problem & solution algorithms for Graph-Display problem
            25     TSP-1 (Xiaofan), Chess-lecture
  March      4     Chess-lecture, Chess-1 (Greg)
            11     SAT-lecture
            12     DUE: project proposal (1 page)
            18     SPRING BREAK
            25     SAT-1 (Scotty S), SAT-2 (Ateeq)
  April      1     CF-lecture, CF-1 (Leenarat)
             8     [Phillips-736] 2008 Netflix winner W.Roberts, CF-2 (Chinfeng).
            15     CF-3 (Rizwan), PLAN-1 (Sandeep)
            22     PLAN-2 (Amir), Final project presentations
            28     DUE: final project reports (3 pages)

Slides: Chess-1, SAT-1, SAT-2, CF-1, CF-2, CF-3, PLAN-2.

The papers:

(MST1) D.R.Karger, P.N.Klein and R.E.Tarjan. A randomized linear-time algorithm to find minimum spanning trees. J. ACM, 42:2, March 1995, pp.321-328.
(TSP1) S.Arora. Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and other Geometric Problems. J.ACM, 45:5, 1998, pp.753-782.
(Chess1) E.Schroder. How REBEL plays Chess. 2004.
(CF1) The BellKor solution.
- R.M.Bell, Y.Koren and C.Volinsky. The BellKor 2008 Solution to the Netflix Prize.
- Y.Koren. The BellKor Solution to the Netflix Grand Prize.
(CF2) The BigChaos solution.
- A.Toscher and M.Jahrer. The BigChaos Solution to the Netflix Prize 2008.
- A.Toscher and M.Jahrer. The BigChaos Solution to the Netflix Grand Prize.
(CF3) PragmaticTheory solution.
- M.Piotte and M.Chabbert. The Pragmatic Theory solution to the Netflix Grand Prize.
(SAT1) Mini-SAT and SATLite.
- N.Een and N.Sorensson An Extensible SAT-solver. SAT 2003.
- N.Een and N.Sorensson MiniSat: A SAT Solver with Conflict-Clause Minimization. SAT 2005.
- N.Een and A.Biere. Effective Preprocessing in SAT through Variable and Clause Elimination. SAT 2005.
(SAT2) Chaff.
- M.Moskewicz, C.Madigan, Y.Zhao, L.Zhang and S.Malik. Chaff: Engineering an Efficient SAT Solver. 39th Design Automation Conference (DAC 2001), Las Vegas, June 2001.
- L.Zhang and S.Malik. The Quest for Efficient Boolean Satisfiability Solvers. , Proc. 8th Int. Conf. Computer Aided Deduction (CADE), 2002.
(PLAN1) Introduction to the Planning problem, and partial-order planning. Material from: (1) Chapter 11 (pages 375-395) of S.Russell and P.Norvig, Artificial Intelligence; (2) Chapters 4 and 5 of M.Ghallab et al, Automated Planning.
(PLAN2) The Graph-Plan algorithm and improvements. Material from: (1) Chapter 11 (pages 395-402) of S.Russell and P.Norvig, Artificial Intelligence; (2) Chapter 6 of M.Ghallab et al, Automated Planning.