Instructor:
Dr. Shieu-Hong Lin Email: shieu-hong.lin@bubbs.biola.edu
Course
Web site: csci.biola.edu/csci480spring03
Class:
Wednesday 3:30-5:20PM
Office
Hours: Tuesday & Thursday 3:00-5:00 pm, Math&CS department
Things to do:
Week
2
ĄP
Pick two hard problems you feel interested (for example, the Steiner
Tree problem, the SAT problem, the ROBOT localization problem, the optimal
register allocation problem, or others). For each problem, clarify your
understanding of the problem formulation, and search the Internet to find at
least one interesting paper or a web site of related research. Bring to the
class the research results you find people have done in the papers for
discussion next time.
ĄP
Look at the handout of 2-approximation algorithm for the Traveling
Salesman problem and work on paper to make sure you understand how it works and
why it has the factor 2 guarantee of its solution quality. Draw a 5-vertices
graph on paper.
ĄP
Programming assignment #1 (Due: Wednesday, March 5): For the Traveling Salesman
Problem, write a program that randomly generates a fixed number of vertices on
a 500 x 500 pixel screen, then calculates the distance matrix of the vertices,
then derive a solution by applying the factor-2 approximation algorithm, and
show that solution on the screen graphically. (Using the winbgi module of your
old csci105 stuff is good enough for the graphics.) Do your best to bring in
something to demo next time we meet.
ĄP
Examine and play with Excel worksheet solution to the Simon Pie
decision modeling case. WeĄŠll have a variation of the case next time for you to
work on based on the solution you get.
Week
3
ĄP
Witten homework #1: Decision-making case study: Download this
power-point slide set and this Excel worksheet template on a new case. Use that
basic Excel worksheet template and enhance it to do all the things described in
the power-point slide set and repeat all the decision-making analysis and
charts. Send your finished Excel worksheet to me electronically and explain
why you think it is or is not worthwhile to spend $1000.00 dollars per week to
increase the capacity to 30,000 pies per week using one shift. (Due: Wednesday, Feb. 26).
ĄP
Programming assignment #2: Look at the description and some code for the
famous Lin-Kernighan
heuristic algorithm we discussed in the class. Implement and run the
Lin-Kernighan algorithm to compare the solution quality it provides with that
provided by your 2-approximtion algorithm in programming assignment #1.
ĄP
More on the traveling Salesman Problem (TSP): Explore the following web
sites for useful pointers to problem instances, code, papers, and many other
things: (i) Traveling
Salesman Problem - Home Page
(ii) TSPBIB
Home Page
ĄP
Download this lecture
notes
in postscript format on approximation algorithms: Look at the chapter on the
set cover problem we discussed in the class. (You need to download Ghostscript and Gsview to
look at .ps files.)
Week
4
ĄP
Read the handout on Max-flow problem. (Send
me reading comments due: Wednesday, Mar. 5).
ĄP
Do written homework #2: Final the max flow and the minimal cut
of this graph: #1 (due:
Wednesday, Mar. 5)
ĄP
Read sections 1-9 of the Boost graph
library document. Send me reading comments (due:
Wednesday, Mar. 5). Download
and install Boost graph library.
Week
5
ĄP
Read the handout on the 0-1 knapsack problem
and do written homework #2 (due: Wednesday, Mar. 12)
ĄP
Read the handout on the complexity classes P
and NP (Send me reading comments due: Wednesday,
Mar. 12).
ĄP
Read sections 10-12 of the Boost graph
library document. (Send me reading comments due:
Wednesday, Mar. 12).
Week
6
ĄP
Read the handout on depth-first search and bi-connected components (comments due: Wednesday, Mar.
19)
ĄP
Introduction to C++ standard template library: see a tutorial at SGI and download these example programs (comments
due: Wednesday, Mar. 19)
ĄP
Programming assignment #3: Use Boost library to implement a program that
can find out all the biconnected components of any given graph. (due: Wednesday, Mar. 26)
Week
7
ĄP
Further exploration of C++ STL library (look at sample code from
JosuttisĄŠs C++ STL library
book) and Boost
graph library document
ĄP
Reading and discussion assignment: Algorithms & Function objects in
STL (explore the tutorial at SGI and
sample code from JosuttisĄŠs C++
STL library book )
ĄP
Written homework #3: Develop, write down, and analyze your own
algorithm for the bi-connected components
problem Wednesday, April. 2.
Weeks
8-10
ĄP
Reading and discussion assignment: function objects in STL (explore the
tutorial at SGI and sample code from
JosuttisĄŠs C++ STL library
book )
ĄP
Reading and discussion assignment: iterators in STL (explore the tutorial at SGI and sample code from
JosuttisĄŠs C++ STL library
book )
ĄP
Reading and discussion assignment: containers in STL (explore the tutorial at SGI and sample code from
JosuttisĄŠs C++ STL library
book )
ĄP
Reading and discussion assignment: generic algorithms in STL (explore
the tutorial at SGI and sample code
from JosuttisĄŠs C++ STL
library book )
ĄP
Reading and discussion assignment: Intro to
Boost graph library and its related links.
ĄP
Send me reading comments on each of the areas above separately (5 reading
comments due: Wednesday, April 30.).
ĄP
Written homework #4: Develop, write down, and analyze your own
algorithm for the shortest path problem Wednesday, May
7.
In-class written test on STL: Wednesday, May 7.
No.
Class on Wednesday, May 14.
Help
and Review section 1:00pm~5:00pm Monday, May 19 in my office (Just drop by).
Take-home
exam: 5:00pm Monday, May 19 to 5:00pm Monday, May 26.
Final
Exam study guide:
Look at this lecture to review the
matrix-multiplication algorithm for determining all-pairs shortest paths.
Look at this lecture to review the Floyd-Warshall all-pairs shortest path algorithm (the cross method).
Look at this lecture to review the flow augmentation algorithm to find a maximal flow and a minimal cut in a graph.
Look at depth-first search and how to find bi-connected components using the depth-first search
Look at class handouts of approximation algorithms for the Traveling Salesman problem, vertex cover problem, set cover problem.
Basic concepts about the meanings of P, NP, and NP-Complete.
