How to Solve It
How to Solve It
Cong Li
Course in Childen's Computer Center, Children's Palace of Chinese Welfare Institute
Spring and Fall 2021; Fall 2018 and Spring 2019; Fall 2016 and Spring 2017; Fall 2013 and Spring 2014; Fall 2011 and Spring 2012; Fall 2009 and Spring 2010; Fall 2007 and Spring 2008; Fall 2005 and Spring 2006; Fall 2004 and Spring 2005
Course Description
Given the recent advances in computing power, it becomes an emerging challenge to solve large scale problems on computers. The course covers classic methods of optimization as well as recent innovations in problem solving. Several interesting puzzles are intersected in the course.
The course is based on the book: Zbigniew Michalewicz and David B. Fogel (2000). How to Solve it: Modern Heuristics, Springer-Verlag.
Lecture Notes
2. Why Are Some Problems Difficult
Assignment 1: solve those SAT problems
Assignment 2: solve the four equations
Assignment 3: find the optimum of the two functions
Assignment 4: solve the problem with simplex method
5. Classical Methods - Part II
Assignment 5: solve those SAT problems with greedy solution construction
Assignment 6: mutiply the four matrices
6. Escaping Local Optima
Assignment 7: solve those SAT problems with Tabu search
Assignment 8: solve those SAT problems with simulated annealing
7. Evolutionary Approach
8. Designing Evolutionary Algorithms
9. Epilogue
Sample Programs
lcSAT - a sample c++ program for solving SAT problems
(a simpler version in c, an even simpler version in c for solving Assignment 8)
lcZero - a sample c++ program for solving Assignment 2
lcGradient - a sample c++ program for solving Assignment 3
lcSimplex - a sample c++ program for solving Assignment 4
lcMultiplier - a sample c++ program for solving Assignment 6