UNOFFICIAL COURSE OUTLINE

CSC 445: Operations Research: Linear Programming

Term Fall 2012
Course Website http://webhome.cs.uvic.ca/~wendym/445.html
Instructor Wendy Myrvold
Email: wendym at csc.uvic.ca
Office: ECS 552
Phone Number: (250) 472-5783 [Use e-mail for a faster response]
Office Hours: See course web page.
Lecture Schedule 
(A01)     MWR   3:30 - 4:20 p.m.    Ell 162
Laboratory Schedule This course has no labs or tutorials.
Course Overview In the first part of the course, students are provided with a strong foundation consisting of the mathematics required to understand linear programming. This is followed by a sampling of interesting applications.
Topics
  • The Simplex Method for Linear Programming.
  • Pitfalls and how to avoid them.
  • How fast is the Simplex Method?
  • Duality.
  • The Revised Simplex Method.
  • Applications in business (efficient allocation of scarce resources).
  • An overview of theoretically fast algorithms for Linear Programming.
  • Network Flow problems.
  • Transshipment problems.
  • Matchings in graphs.
  • Applications in graph theory and chemistry.
  • Integer Programming.
  • Selected topics as time permits (Matrix games, ...).
Course Objectives And Learning Outcomes The skills students will develop include:
  • Identification of problems for which a linear programming solution is applicable.
  • Setting up a linear program for a problem.
  • Understanding the mathematics of the Simplex method and its potential pitfalls.
  • Writing a program to solve linear programs.
  • Demonstrating that a solution is optimal.
  • Appreciation of numerous areas of application.
Textbooks
Required: Linear Programming
by Vasek Chvatal
H. Freeman and Co.,
ISBN-10: 0716715872, ISBN-13: 978-0716715870
Other Materials Please refer to the connex pages and the web pages for the class for other course materials.
Programming Projects Students will be required to program the Simplex method for linear programming. The code may be written in C, C++, or JAVA. Code which does not work will receive no credit. The programming project will be divided into two phases each worth 10% of your grade. Phase 1 is due at 3:30pm on Thurs. Sept. 27, and Phase 2 is due at 3:30pm on Thurs. Oct. 18.
Assignments There will be 4 assignments of equal weight. The schedule for the assignments will be available from connex.
Optional Programming Project An additional programming project (programming the revised Simplex Method) is optional. The due date is Thurs. Dec. 13 at 1pm. If students complete this project, the mark obtained will replace the contribution from one of
(a) Test #1,
(b) Test #2,
(c) the two lowest assignment marks,
where the option chosen will be selected so that the final numerical score in the course is maximized.
Late Assignments And Projects Assignments and projects can be handed in 4 days after the deadline (for example, on Monday at 3:30pm for an assignment due on Thursday at 3:30pm) with a 10% penalty for being late.
Course Policies On Collaborative Work Assignments:
Students are encouraged to work in study groups. However, final assignment submissions should be generated independently. You are expected to solve the problems yourself. Copying solutions from others, the web, or any other source will be considered a serious academic offense and may result in failure of the course.

Programming:
All code submitted must be your original work. If you use code taken from the internet, an API, other students, previous model solutions or other sources and submit it as your own work you will not get credit for that code. Further if your source is not acknowledged, you are subject to disciplinary action according to the department policies for plagiarism.
Exams There will be two tests each worth 25% in class on Thurs. Oct. 11 and Thurs. Nov. 15. There will be no final exam.
Participation Marks for participation will be recorded starting Mon. Nov. 19 and ending at the last class. Absences will be accommodated by assigning additional work to replace the class attendance if there is a valid medical reason, accident, or disability (for yourself or an immediate family member who requires your care) or other reason covered by the university guidelines. Appropriate documentation is required (e.g. a note from a physician, health services, counselling services, ...). Provisions for absence due to religious holidays should be requested by Sept. 17.
Grading
Coursework Weight (out of 100%)
Assignments (4) 20%
Programming Project 20%
Test 1 (Oct. 11) 25%
Test 2 (Nov. 15) 25%
Participation 10%

In order to pass this course you must:
1. Achieve an average score on the two tests which is at least 50% (disregarding the optional programming project).
2. Achieve an overall passing grade in the course.

Final numeric scores (in percentages) will be converted to letter grades as follows:

F D C C+ B- B B+ A- A A+
0-49 50-59 60-64 65-69 70-72 73-76 77-79 80-84 85-89 90-100

Grades Description
A+, A, A- Exceptional, outstanding or excellent performance. These grades indicate a student who is self-initiating, exceeds expectation and has an insightful grasp of the subject matter.
B+, B, B- Very good, good or solid performance. These grades indicate a good grasp of the subject matter or excellent grasp in one area balanced with satisfactory grasp in the other areas.
C+, C Satisfactory, or minimally satisfactory. These grades indicate a satisfactory performance and knowledge of the subject matter.
D Marginal Performance. A student receiving this grade demonstrated a superficial grasp of the subject matter.
F Unsatisfactory performance. Wrote final examination and completed course requirements; no supplemental.
Posting Of Grades Term marks, provisional final grades and final grades will be posted by student number. NO NAME WILL APPEAR. These postings are for your information and for your validation of the data entry. If you do not wish your term marks and grades to be publicly posted in this manner, please notify the course instructor by e-mail no later than Sept. 13, 2012.
Csc Student Groups The Computer Science Course Union (http://cscu.csc.uvic.ca/mediawiki/index.php/) serves all students who are either in a computer science program or taking a class in computer science. Please sign yourself up on their mailing list if you would like to be informed about their social events and services.

The Engineering Students' Society (ESS) serves all students registered in an Engineering degree program, including Software Engineering (BSEng). For information on ESS activities, events and services navigate to http://www.engr.uvic.ca/~ess .
Course Policies And Guidelines Coursework Mark Appeals: Mark appeals can be done at any time and you are strongly encouraged to appeal if you feel your course work has been misgraded. Express your concern in writing on your submission and hand it to me for reconsideration.
Attendance: We assume that students attend all lectures. It is entirely the students' responsibility to recover any information or announcements presented in lectures from which they were absent.
Electronic devices in labs and lectures: No unauthorized audio or video recording of lectures is permitted.
Electronic devices in midterms and exams: Calculators are not permitted for examinations and tests, no other electronic devices (e.g. cell phones, pagers, PDA, etc.) may be used during examinations or tests (unless required to accomodate a student with a disability).

Plagiarism: Submitted work may be checked using plagiarism detection software. Cheating, plagiarism and other forms of academic fraud are taken very seriously by both the University and the Department. You should consult http://web.uvic.ca/calendar/FACS/UnIn/UARe/PoAcI.html for the UVic policy on academic integrity. Note that the university policy includes the statement that "A largely or fully plagiarized assignment should result in a grade of F for the course".

The Faculty of Engineering Standards for Professional Behaviour are at http://www.uvic.ca/shared/shared_engineering/docs/professional-behaviour.pdf

The department guidelines concerning fraud are at http://www.csc.uvic.ca/courseinfo/policies/fraud.html

Department Policies: A list of department policies regarding all courses may be found at http://www.csc.uvic.ca/courseinfo/policies/index.html

This course aims to provide equal opportunities and access for all students to enjoy the benefits and privileges of the class and its curriculum and to meet the syllabus requirements. Reasonable and appropriate accommodation will be made available to students with documented disabilities (physical, mental, learning) in order to give them the opportunity to successfully meet the essential requirements of the course. The accommodation will not alter academic standards or learning outcomes, although the student may be allowed to demonstrate knowledge and skills in a different way. It is not necessary for you to reveal your disability and/or confidential medical information to the course instructor. If you believe that you may require accommodation, the course instructor can provide you with information about confidential resources on campus that can assist you in arranging for appropriate accommodation. Alternatively, you may want to contact the Resource Centre for Students with a Disability located in the Campus Services Building.

The University of Victoria is committed to promoting, providing, and protecting a positive, and supportive and safe learning and working environment for all its members.