UNOFFICIAL COURSE OUTLINE: CSC 445: Operations Research: Linear Programming

Term Fall 2014
Course Website See below for the connex site and class web pages.
Instructor Wendy Myrvold
Email: wendym at cs.uvic.ca
Office: ECS 552
Phone Number: (250) 472-5783 (use e-mail for a faster response)
Office Hours: ECS 552, See course web pages.
Lecture Schedule
(A01)     TWF   12:30 - 1:20 p.m.    ECS 108
Laboratory Schedule This course has no labs or tutorials.
Course Registration Number (crn) 10806
Course Connex Site: For private course materials and for electronic assignment submission: http://www.csc.uvic.ca/courses/csc445
Course Web Pages: For public course materials: http://webhome.cs.uvic.ca/~wendym/445.html
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. The course concludes with an introduction to some other optimization tactics.
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 12:30 p.m. on Fri. Sept. 26, and Phase 2 is due at 12:30pm p.m. on Fri. Oct. 24.
Assignments There will be 4 assignments of equal weight worth 20% of your grade. The schedule for the assignments will be available from connex. Projected assignment deadlines (subject to change) are: Sept. 19, Oct. 3, Oct. 31 and Nov. 21.

Optional Programming Project An additional programming project is optional. The due date is Fri. Dec. 12 at 1:00 p.m. If students complete this project, the mark obtained will replace the contribution from one of
(a) the midterm, or (b) 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 will be due on Fridays at the beginning of class. They can be handed in late at 12:30pm on the following Tuesday with a 10% late penalty.
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 a midterm worth 20% in class on Fri. Oct. 10 and a final exam worth 35% will be scheduled by the registrar.
For courses which have final exams, students are strongly advised not to make final plans for travel or employment during the exam period since special arrangements will not be made for examinations that may conflict with such plans.
Participation Marks for participation will be recorded starting Tues. Nov. 18 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. 20.
Grading
Coursework Weight (out of 100%)
Assignments (4) 20%
Programming Project 20%
Midterm (Oct. 10) 20%
Participation 5%
Final exam 35%

Grading Scheme Effective Summer 2014, University of Victoria follows a "percentage grading system" in which the instructor will submit grades in percentages. The University will use the following Senate approved standardized grading scale to assign letter grades. Both the percentage mark and the letter grade will be recorded on the academic record and transcripts.

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. Normally achieved by a minority of students. 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. Normally achieved by the largest number of students. 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. 20, 2014 .
Course Experience Survey (ces) Course Evaluation Survey (CES) is an important activity through which the instructor and the department can get valuable feedback about the course from the students directly. Towards the end of term, as in all other courses at UVic, students will have the opportunity to complete an anonymous survey regarding course learning experience. This survey is vital to providing feedback regarding the course, the instructor and the teaching, as well as to help the department improve the overall program for students in the future. The survey is accessed via MyPage and can be completed using a laptop, tablet, or any mobile device. The instructor will remind students and provide with more detailed information near the end of term but please be thinking about this important activity during the course.
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.