CSC 482B/582B Graphs Algorithms for Chemistry

Term

Fall 2005

Course website

/~wendym/582.html

Instructor

Dr. Wendy Myrvold
Email: wendym at cs.uvic.ca
Office: EOW 317
Phone Number: 721-7224 (use e-mail for a faster response)
Office Hours: Please see course web page

Lecture Schedule

(F01) MR

11:30am- 1:00pm

MAC D114

Textbooks

References will be provided by the course instructor.

Prerequisites:

All chemistry principles required for the course will be covered in class and so there are no formal chemistry prerequisites. High school level chemistry would be an asset. Students are required to have programming, algorithm design, and algorithm analysis ability equivalent to that obtained from CSC 225. Undergraduates must have CSC 225 and 4th year standing or the permission of the instructor to enroll. Third year students with a strong interest in algorithms are welcome.

Course Objectives

There are many problems in chemistry whose solutions can be expressed in terms of graph theory or graph algorithms. The aim of this course is to provide a bridge between chemistry and graph theory and also to cover graph algorithms which can be applied to chemistry applications. The course will include both the chemistry and the graph theory basics required to understand the concepts presented.

Fullerenes are newly discovered all-carbon molecules whose molecular structures correspond to 3-regular planar graphs that have face sizes equal to five or six. There are many exciting potential applications of fullerenes, their chemical derivatives and the related carbon nanotubes which include increasing tensile strength in objects such as tennis rackets, drug delivery mechanisms, design of quantum computers, and the creation of smaller and faster computer memories. Students will investigate graph invariants of the fullerenes with the ultimate aim of providing insight into real-world applications.

Topics

The topics which will be covered (as time permits):

Basic graph theory definitions, basic chemistry and how graph theory is used in chemistry.
Symmetries of molecules, isomorphism, canonical forms, generating molecules up to isomorphism.
The adjacency matrix, and its determinant, spanning trees of a graph.
The permanent of the adjacency matrix, counting and generating perfect matchings, Kekule structures.
The eigenvalues of the adjacency matrix (used to predict molecule stability), and Huckel theory.
The distance matrix and the Wiener index.
Molecules represented by planar graphs, planar graphs, properties of planar graphs, algorithms for planar graphs.
Molecules with a mobius band structure, embedding graphs on a mobius band.
Fullerenes, generating fullerenes, vertex spirals, face spirals, graph invariants for fullerenes.
Independent sets of graphs, importance of these to fullerene chemistry, algorithms for finding a maximum independent set and for finding all independent sets up to isomorphism.

Assignments

There will be 4 assignments whose tentative due dates are:

Assignment #1:	Mon. Sept. 26
Assignment #2:	Mon. Oct. 17
Assignment #3:	Mon. Nov. 14
Assignment #4:	Mon. Nov. 28

Assignments are due at the beginning of class.

Attendance

It is expected that students attend all classes. Students who miss at most one class will receive a bonus of 2% added to their final course mark. Students who miss at most two classes will receive a bonus of 1% added to their final course mark. Students with 5 or more unexcused absences will receive a mark of N in the class.

Teaching Eigenvalues Project

Eigenvalue computations are very important to chemists. Each student will be assigned a different algorithm for computing eigenvalues of a class of graphs (or possibly a result about eigenvalues). The student should prepare overhead slides for teaching this algorithm to the class which includes sample computations and collection of 2 assignment questions plus model solutions for the topic. Each student will be given a slot (likely 15 minutes) to teach this material to the class. The written materials are due on Monday Oct. 31 and will count for 14% of the final mark. The presentations are worth 6% and will commence on Monday Nov. 21 and continue through Nov. 24, Nov. 28 and Dec. 1 as required.

Fullerene Parameter Project

Each student will be assigned a different fullerene parameter. The goal of this project is to

create working code for computing the parameter,
compute the parameter for small fullerenes as generated by the fullgen fullerene generator in a file format suitable for fuigui (a program for visualizing fullerenes).
make conjectures regarding classes of fullerenes which might maximize or minimize that parameter.
write a written report which defines the parameter, gives a short literature survey regarding the importance of the parameter, describes the algorithm implemented and summarizes the conjectures made. A preliminary draft of the written report (without code or research results) is worth 5% and is due on Monday Oct. 24. The preliminary and final drafts should be typeset with at least 1.5 spacing and a 12 point or larger font. Please print your submissions single sided. The completed project is due on Monday Dec. 12 at noon. The code must be submitted both electronically and on paper. The written part should be submitted on paper.

Animated Algorithm

CSC 582B students will each develop a different animated algorithm in JAVA to fit within the fuigui framework for visualizing fullerenes. If CSC 482B students elect to do this assignment, the mark received will replace their lowest assignment mark. This project is due at noon on Monday Dec. 19. The code must be submitted electronically.

Exams

Grading

Component	CSC 482B	CSC 582B
Assignments	60%	50%
Teaching Eigenvalues Project	20%	20%
Fullerene Parameter Project	20%	20%
Animated Algorithm	0%	10%

Final Grades are obtained by converting the numerical scores using the conversion table below. Dividing lines between letter grades may be adjusted by a maximum of 3% to account for natural breaks in the numeric scores.

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 Monday Sept. 19, 2005.

Course Policies and Guidelines

Late Assignments: Assignments are due at the beginning of class. Assignments may be handed in at the beginning of the following class instead with a 20% penalty for being late.
Coursework Mark Appeals: You can appeal your marks at any time but it would be appreciated if you would do it sooner rather than later. Express your concern in writing on the work in question 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.
Plagiarism: Submissions may be electronically checked for similarity.
Important note: 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.
Department policies: A list of department policies regarding all courses may be found at http://www.csc.uvic.ca/courses/policies/index.html