CSC 520: Analysis of Algorithms

Term Spring 2014
Course Website See below for the connex site and class web pages.
Instructor Wendy Myrvold
Email: wendym at csc.uvic.ca
Office: ECS 552
Phone Number: (250) 472-5783 (for a faster response, send e-mail)
Office Hours: TWF 10:30 - 11:15 a.m. and TWF 12:30pm
Lecture Schedule 
(A01)     TWF   9:30 - 10:20 a.m.    MAC D 116
Laboratory Schedule This course has no labs or tutorials.
Course Connex Site: For private course materials and for electronic assignment submission: http://www.csc.uvic.ca/courses/csc425
Course Web Pages: For public course materials: http://webhome.cs.uvic.ca/~wendym/425.html
Course Overview General techniques for designing and analyzing algorithms; an in-depth examination of several problems and algorithms with respect to their time and space requirements; advanced data structures; sorting and searching; graph algorithms; backtracking; NP-complete problems; approximation algorithms.
Topics Algorithm Design Techniques covered will include a selection of the following:
  • Graph algorithms,
  • Greedy algorithms,
  • Divide and conquer,
  • Dynamic programming, and
  • Network flows.
Students will be introduced to intractable problems and tactics for tackling them such as:
  • Approximation algorithms,
  • Backtracking,
  • Randomized algorithms,
  • Restriction to specific classes of sub-problems are easier to solve.
Course Objectives And Learning Outcomes The skills students will develop include:
  • getting to the mathematical core of problems,
  • improving mathematical and algorithmic writing,
  • enhancing programming skills,
  • performing a literature review for a problem,
  • preparing visual aids and presenting a talk,
  • identifying appropriate algorithms and data structures,
  • analysis of algorithms for time and space complexity,
  • understanding of algorithm design methodologies,
  • identification of difficult questions and finding strategies to cope with them.
Textbooks
Required: Algorithm Design (paper back or hard cover)
by Jon Kleinberg and Eva Tardos
Addison Wesley,
ISBN-10: 0321295358 ISBN-13: 978-0321295354
Implementation Challenge The class project involves participation in an implementation challenge whose goal is to develop and evaluate practical algorithms for an NP-hard problem. The weighting of each contribution for this project and deadlines for each milestone are available from the course web page. Students will present a short talk (about 10 minutes) summarizing the results from their project in the last week of classes.
Assignments There will be 5 assignments of equal weight. The schedule for the assignments is available on the course web page.

Late Assignments And Projects Assignments and the project milestones (with the exception of your final project submission that must be submitted by April 20) can be handed in up to one week after the deadline with a 2% penalty for each day that the assignment is 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.

Participation Students can miss up to 3 classes without penalty. After this, 0.5% will be subtracted from the final class mark for each class that is missed. Additional 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 Jan. 20.
Grading
Coursework Weight (out of 100%)
Assignments (5) 45%
Project 55%

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+ Exceptional work. Technically flawless and original work demonstrating insight, understanding and independent application or extension of course expectations; often publishable.
A Outstanding work. Demonstrates a very high level of integration of material demonstrating insight, understanding and independent application or extension of course expectations.
A- Excellent work. Represents a high level of integration, comprehensiveness and complexity, as well as a mastery level of relevant techniques/concepts..
B+ Very good work. Represents a satisfactory level of integration, comprehensiveness and complexity; demonstrates a sound level of analysis with no major weakness.
B Acceptable work that fulfills the expectations of the course. Represents a satisfactory level of integration of key concepts/procedures. However, comprehensiveness or technical skills may be lacking.
B-, C+, C, D Unacceptable work revealing some deficiencies in knowledge, understanding or techniques. Represents an unacceptable level of integration, comprehensiveness and complexity. Mastery of some relevant techniques or concepts lacking.
F Failing grade. Unsatisfactory performance. Wrote final examination and competed course requirements.

Final Grades are obtained by converting the numerical scores using the conversion table below.


F D C C+ B- B B+ A- A A+
0-49 50-54 55-59 60-64 65-69 70-74 75-79 80-84 85-89 90-100
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 Jan. 20, 2014.
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. Their facebook page is at: https://www.facebook.com/pages/UVic-Computer-Science-Course-Union/45233204144

Women in Engineering and Computer Science (https://connex.csc.uvic.ca/portal/site/wecs/) - The purpose of the WECS is to encourage more women and girls to consider Computer Science or Engineering as a career and to support them in their decision once they arrive at UVic.

The Engineering Students' Society (ESS) (http://ess.uvic.ca/) serves all students registered in an Engineering degree program, including Software Engineering (BSEng). For information on ESS activities, events and services navigate to http://ess.uvic.ca/
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.