% Syllabus
% Combinatorial Optimization, SUAMI, summer 2015
% Brian Kell
\pdfpagewidth=8.5truein \pdfpageheight=11truein
\hsize=5.5truein \vsize=9truein
\pdfhorigin=1.5truein \pdfvorigin=1truein
\font\titlefont=cmbx12
\font\smfont=cmr8
\headline={\hfil}
\footline={\hfil}
\topskip=20pt plus2pt
% get a better-looking underscore (cf. page 356 of the TeXbook)
\def\_{\leavevmode \kern.06em \vbox{\hrule width0.5em height-0.2pt depth0.6pt}\kern.06em\relax}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\centerline{\titlefont Combinatorial Optimization}
\centerline{\smfont SUAMI 2015}
\smallskip
\centerline{\bf Syllabus}
\medskip\hrule\medskip
{%\advance\leftskip by6pt \advance\rightskip by6pt
\noindent{\bf Time and place:} Monday through Friday, 1:30--3:00~p.m., in Wean
Hall 7218.
\smallskip
\noindent{\bf Textbook:} Christos~H. Papadimitriou and Kenneth Steiglitz.
{\it Combinatorial Optimization: Algorithms and Complexity}. Dover, 1998. ISBN
978-0-486-40258-1.
\smallskip
\noindent{\bf Recommended supplementary books} (on reserve at the Sorrells
Engineering and Science Library circulation desk, Wean Hall 4400):
\smallskip
\item{$\bullet$} Bernhard Korte and Jens Vygen. {\it Combinatorial
Optimization: Theory and Algorithms}. Springer, fifth edition, 2012. ISBN
978-3-642-24487-2. (Second edition is on reserve.)
\smallskip
\item{$\bullet$} Dieter Jungnickel. {\it Graphs, Networks and Algorithms}.
Springer, fourth edition, 2013. ISBN 978-3-642-32277-8. (Third edition is on
reserve.)
\smallskip
\item{$\bullet$} Paul~E. Fishback. {\it Linear and Nonlinear Programming with
Maple: An Interactive, Applications-Based Approach}. CRC Press, 2009. ISBN
978-1-420-09064-2.
\smallskip
\noindent{\bf Web page:} {\tt http://www.math.cmu.edu/\char`\~bkell/suami2015/}
} % end \narrower
\medskip\hrule\medskip
{%\advance\leftskip by6pt \advance\rightskip by6pt
\noindent{\bf Instructor:} Brian Kell
\smallskip
\noindent{\bf E-mail:} {\tt bkell@cmu.edu}
\smallskip
\noindent{\bf Office:} Wean Hall 6211
\smallskip
\noindent{\bf Office hours:} Monday through Friday, 12:30--1:30~p.m.\ and
3:00--4:00~p.m., or by appointment. Feel free to stop by at other times; I'll
be happy to meet with you if I'm in.
\smallskip
\noindent{\bf Teaching assistant:} Michael Druggan,
{\tt michaeldruggan@gmail.com}
} % end \narrower
\medskip\hrule
\bigbreak
\noindent{\bf Objectives}
\nobreak\smallskip
\noindent This course is an introduction to the field of combinatorial
optimization, which, in a nutshell, is the study of problems that involve a
search for the ``best'' option among a (usually finite) set of choices. The
meaning of ``best'' and the set of available choices depends on the problem to
be solved. For example, the set of choices might be the possible production
schedules of a factory, satisfying various constraints on resources, and the
``best'' choice might be the production schedule that yields the greatest
profit. Or perhaps a salesperson has a list of cities to visit, so the set of
choices consists of all possible routes among the cities that visit each city
exactly once; the ``best'' choice may then be the route that minimizes total
travel distance, or travel time, or cost.
Combinatorial optimization is therefore a very broad field. In this course we
will focus on the following topics:
\smallskip
\item{$\bullet$} linear programming and the simplex algorithm;
\item{$\bullet$} integer programming;
\item{$\bullet$} graphs and graph algorithms;
\item{$\bullet$} ``hard'' problems, heuristics, and approximations; and
\item{$\bullet$} computational complexity and the P~vs.~NP question.
\smallskip
\noindent We will discuss computational techniques and algorithms as well as
theoretical foundations. Maple will be used as a platform for computation.
\goodbreak
A student who successfully completes this course will be able to:
\smallskip
\item{$\bullet$} recognize many types of combinatorial optimization problems;
\item{$\bullet$} formulate linear and integer programs, and identify when a
problem can be viewed in terms of various ``standard'' combinatorial
optimization problems;
\item{$\bullet$} understand the mathematical concepts underlying these problems
and their solutions;
\item{$\bullet$} solve combinatorial optimization problems using algorithms and
mathematical software; and
\item{$\bullet$} analyze the performance of simple algorithms, understand and
interpret computational complexity, and reduce one problem to another.
\medbreak
\noindent{\bf Evaluation}
\nobreak\smallskip
\noindent This course is officially 21-470 section~H, ``Selected Topics in
Analysis: Combinatorial Optimization,'' in the CMU course register.
Problem sets will be given on Thursdays and Mondays and will be due on the
following Monday or Thursday (i.e., a problem set given on Thursday will be due
the following Monday, and a problem set given on Monday will be due the
following Thursday). There will be approximately 11~problem sets over the six
weeks. Collectively these problem sets will count for 50\% of your course
grade.
Near the midpoint of the course (probably Thursday, June~18), a take-home
midterm exam will be given instead of a problem set. This exam will count for
20\% of your course grade. Even though it is a take-home exam, the midterm is
an individual assessment; no collaboration with other students will be
allowed.
At the end of the course, we will have an in-class written final exam. This
exam will be comprehensive and will count for 30\% of your course grade.
Your final course grade will be determined according to the following scale.
\nobreak\medskip
\centerline{\hss\vbox{\offinterlineskip
\hrule\vskip2pt\halign{\strut\hfil#\enspace&&\enspace\hfil#\hfil\cr
If you get at least this percentage:&
90\%&80\%&70\%&60\%\cr
Then you are guaranteed at least this grade:&
A&B&C&D\cr
}\vskip2pt\hrule}\hss}
\medbreak
\noindent{\bf Expectations}
\nobreak\smallskip
You are welcome and encouraged to collaborate with other students on the
problem sets. It is often more fruitful and enjoyable to work with other people
when trying to figure something out. They can give you a different perspective
or fresh insight on the problem. Conversely, explaining one of your ideas to
another person forces you to clarify your thoughts and can help to highlight
flaws you may have previously overlooked. However, if you work with others to
come up with a solution, afterward you should go away and write it up on your
own, so that you are certain that you understand the solution. You should not
see the solutions that another student will be handing in, and you should not
show your final written solutions to other students. Remember:
\smallskip
\centerline{\bf Working with other students to figure out the problems is acceptable.}
\smallskip
\centerline{\bf Working with other students to write the solutions is NOT acceptable.}
\smallskip
\noindent When you do collaborate with other students, please acknowledge your
partners in your submitted solutions. Also provide references to any sources
other than the textbook (if any) that you used. Always give credit where credit
is due; proper attribution of credit is one of the foundations of academic
research.
Please familiarize yourself with the Carnegie Mellon Statement on Academic
Integrity and the Policy on Academic Integrity:
\smallskip
\item{$\bullet$} {\def\\{\hskip0ptminus0.2pt\relax}%
\tt http\\:\\/\\/www\\.\\cmu\\.\\edu\slash\\student-affairs\slash
theword\slash\\acad\_standards\slash\\integrity\\.\\html}
\item{$\bullet$} {\tt http://www.cmu.edu\slash policies\slash documents\slash
Academic\%20Integrity.htm}
\smallskip
\noindent I will be happy to answer any questions you may have about academic
integrity.
\medbreak
\noindent{\bf Accommodations}
\nobreak\smallskip
\noindent Some students qualify for special accommodations due to various
needs. If you are such a student, please let me know as soon as possible, and I
will do my best to assist you. In addition, please contact the CMU Office of
Disability Resources at {\tt access@andrew.cmu.edu}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bye