CSC422: Graph Algorithms
Course Dates
CRN(s): Section A01 CRN: 30204
Term: Summer 2017
Classes Start: 2017-05-01
Classes End: 2017-07-28
Cross-listed With
Cross-Listed Course(s): CSC522
Scheduled Meeting Times (M=Mon, T=Tue, W=Wed, R=Thu, F=Fri)
Section: Location: Days of week: Hours of day: Instructor:
A01CUN 146TF14:30-15:50Wendy Myrvold

Name: Wendy Myrvold
Office: ECS 552
Phone: (250) 472-5783
Email: wendym at cs dot uvic dot ca

Office Hours:Comments

Getting help

Office hours will end when there are no more students who have questions.

If you cannot make office hours and need an appointment, send an e-mail with your
list of available times.

Asking for help by e-mail is encouraged. Please put CSC 422 or 522
(use the course number of the class you are taking) in your subject header
plus an informative subject (use different subjects for different questions) so
that your messages are not confused with those from the other class I am teaching.

E-mail is a more effective way to contact me than using a phone.

Course Connex Site:

The connex site is used if there is electronic assignent submission or for private course materials.
Login to connex from here:

Course Web Pages:

For public course materials:


Graph Theory and Its Applications, Second Edition,
by Jonathan L. Gross and Jay Yellen,
Chapman and Hall/CRC Press


This course provides an introduction to graph theory and graph algorithms.
We will start with basic definitions in order to make the class accessible to all. The algorithms studied range from classical polynomial time algorithms for problems such as network flows to those geared towards dealing with intractible problems such as finding a maximum independent set in a graph. The material also includes cutting edge research tactics for solving real world problems.
The class is especially valuable for students requiring graph theory and combinatorics as a tool for research in areas such as networks, database, computer graphics, and software engineering.
Some specific topics to be covered (as time permits, and according to the interests of the students) include:

  • Graph theory notation,
  • Graph isomorphism,
  • Independent sets and cliques,
  • Spanning trees,
  • Vertex and edge connectivity,
  • Hamilton cycles,
  • Dominating sets,
  • Embedding graphs on the plane and other surfaces (the torus and the projective plane) and drawing pictures of graphs,
  • Graph colourings,
  • Network flows,
  • Matchings,
  • Generating specific classes of graphs and other combinatorial objects,
  • Hard problems and approaches to dealing with intractibility, and
  • Applications of graph theory to chemistry.
Course Objectives

  • To provide a solid foundation in graph theory and graph algorithms.

  • To teach some useful algorithms and algorithm design tactics.

  • To develop research skills which include:

    • background literature search,
    • formal writing for graph theory topics (as required for theses, conference or journal papers),
    • implementation of graph theory algorithms.
    • To intrigue and excite students about graph theory research topics.
    • To take students to the leading edge of graph theory research.
  • Assignments

    This class will have 5 equally weighted assignments.
    The schedule for the assignments will be available from connex and the class web page.
    No late assignments except for exceptional circumstances (e.g. RCSD accommodations).
    The assignment are worth 50% for CSC 422 and 40% for CSC 522.

    Literature Review Project

    Students will select a pre-approved subdomain of graph algorithms. They will write a paper that defines the problem considered and summarizes some papers in the area. The breadth of the survey is expected to be more substantial for students taking CSC 522. Students who exceed expectations can get bonus marks. The literature review is due on Friday May 26 at the beginning of class. It can be handed in late at the beginning of class on Friday June 2 with a 10% late penalty. This project is worth 5% of the final grade for CSC 422 and 10% of the final grade for CSC 522.


    The course will have 6-8 equally weighted small pop quizzes that are during a class slot.
    These will count for 10% of your course mark. Your lowest quiz mark will be dropped (and this is how minor illnesses will be accommodated).
    Quizzes will start the week of May 16.
    Students who arrive to class late and miss the start of a quiz will not be provided with any extra time to finish the quiz. Hence, it is advisable to come to class on time.

    There will be an in class Automorphism Group Lab tentatively scheduled for Friday June 16
    that will count for 5% of your mark.

    This class has no midterm or final exam.


    For classes where there is no quiz, attendance will be taken.
    You can miss up to two classes with no penalty.
    The attendance counts for 10% of your mark.

    Do not ask anyone else to sign the list for you.
    If you are caught doing this, then your attendance score for the class will be 0.

    Programming Project

    Students will design and implement an algorithm (or for CSC 522 students, 2 algorithms) for a hard problem in graph algorithms.
    Students who exceed expectations can get bonus marks.
    The final submission will include a paper that describes the algorithm, and the program(s).
    This programming project counts for 20% of the class mark
    for CSC 422 and 25% of the mark for CSC 522. It is due on Sunday August 13 by 11pm.

    Component Weight CSC 422 Weight CSC 522
    Assignments 50% 40%
    Quizzes 10% 10%
    Attendance 10% 10%
    Automorphism Group Lab 5% 5%
    Literature review project 5% 10%
    Programming project 20% 25%
    Grading System

    The 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

    Typically marks for assignments, examinations, and provisional final grades, are made available through conneX, or CourseSpaces where each student will be able to view only their own grades. Sometimes numerical marks/grades may be posted publicly to the entire class. In that case, full student numbers or names will not be included with the posted information.

    Course Experience Survey (CES)

    I value your feedback on this course. Towards the end of term you will have the opportunity to complete a confidential course experience survey (CES) regarding your learning experience. The survey is vital to providing feedback to me regarding the course and my teaching, as well as to help the department improve the overall program for students in the future. When it is time for you to complete the survey, you will receive an email inviting you to do so. If you do not receive an email invitation, you can go directly to the CES site

    You will need to use your UVic NetLink ID to access the survey, which can be done on your laptop, tablet or mobile device. I will remind you closer to the time, but please be thinking about this important activity, especially the following three questions, during the course.

    • What strengths did your instructor demonstrate that helped you learn in this course?
    • Please provide specific suggestions as to how the instructor could have helped you learn more effectively.
    • Please provide specific suggestions as to how this course could be improved.
    Csc Student Groups

    The Computer Science Course Union ( 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 .

    Course Policies And Guidelines

    Late Assignments: No late assignments will be accepted unless prior arrangements have been made with the instructor at least 48 hours before the assignment due date.
    Coursework Mark Appeals: All marks must be appealed within 7 days of the mark being posted.
    Attendance: We expect students attend all lectures and labs. 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 only permitted for examinations and tests if explicitly authorized and the type of calculator permitted may be restricted. No other electronic devices (e.g. cell phones, pagers, PDA, etc.) may be used during examinations or tests unless explicitly authorized.
    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 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
    U.Vic guidelines and policy concerning fraud and academic integrity are at


    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.