|
[Special Topics 489] Combinatorial Enumeration: Theory and Practice (230.489)
6 points / Semester 1
Handbook Description
THIS UNIT HAS BEEN CANCELLED FOR SEMESTER ONE 2005
Counting or enumeration is one of the most important topics in combinatorics,
because for every combinatorial structure, it is always
natural to ask how many different arrangements there are.
Combinatorial enumeration involves a wide variety of theoretical techniques,
from simple manipulation of binomial-type identities and inclusion-exclusion,
through the use of generating functions to Polya's
cycle index techniques for counting objects up to isomorphism.
Even with all these techniques, there are many problems for which no exact
theoretical solution can be obtained, and counting can only be done by
explicit computer generation involving such techniques as reverse search and
orderly algorithms.
In this unit we will introduce a signficant range of enumeration techniques -
both classical and modern, theoretical and practical,
wherever possible implementing algorithms in the computer algebra system GAP.
We will also consider the very closely related problems of
exhaustively generating or randomly sampling from the set of objects under
consideration.
All combinatorial and group-theoretical concepts will be introduced from the
beginning and so this course should be accessible to mathematics,
computer science and statistics students with some prior exposure to
discrete structures or discrete mathematics.
Prerequisites: CS227 or Maths 2DG, 3P5, 3P7, 3CC (this unit is suitable for most 3rd year students with some prior exposure to discrete mathematics).
Unit Aims
THIS UNIT HAS BEEN CANCELLED FOR SEMESTER ONE 2005
This unit will address the topic of combinatorial enumeration in both a
mathematical and computational manner, demonstrating how each viewpoint
informs and enhances the other. Students will learn a variety of
techniques and gain an understanding of their strengths and limitations.
The unit will be presented in a flexible fashion to cater for
students with different levels of prior exposure to programming
and/or discrete mathematics.
Teaching Staff
| Co-ordinator/Lecturer |
Dr. Gordon Royle |
CSSE Rm 1.5 |
Contact Hours
The lectures will be delivered in a single 2-hour block (with a
break in the middle) per week. In addition there will be a 2-hour
computer lab and a 1-hour tutorial scheduled, but these will not
be given every week, but used as required.
| Type |
Time |
Day |
Location |
| Lecture |
0900 |
Thu |
CSSE 1.24 |
| Laboratory |
1300 |
Thu |
CSSE Lab 2.9 |
| Tutorial |
1500 |
Thu |
CSSE 2.28 |
Assessment
The assessment scheme for this unit will be agreed upon by discussion
with the students in the first week. It will consist of some mixture
of written assignments, computer assignments, a presentation and
possibly a final exam.
Unsatisfactory Progress
Any student who does not demonstrate satisfactory progress in this
unit, as defined in the FECM
Policy on Assessment Practices and Procedures, may be refused admission to the
final examinations. The final deadline for notification of unsatisfactory progress is the
last day of Week 10.
Penalties
The School of Computer Science and Software Engineering has adopted a policy on
minimum penalties for late items of assessment.
This is the default policy of all units unless indicated otherwise, in writing, by the
specific unit coordinator.
This policy shall apply to all items of continuous assessment, whether
submitted either physically or electronically. Immediately after the submission deadline for an item of continuous
assessment, a penalty of 20 percent will be applied PER DAY or PART THEREOF.
The minimum mark possible for late submission is zero. The
percentage is based on the item´s total contribution to the unit´s
assessment. For example, a project contributing 40% to the unit´s
assessment will incur a penalty of 8 marks for each day late until it is submitted or
a mark of zero results.
A more detailed description is given in this School´s Policy on
Late Submission. The Faculty does have an appeals procedure, the details of which can found at the Policy for Appeals.
Plagiarism
Plagiarism is broadly defined to be when any portion
of the work presented for assessment, can be attributed
to another party. The student making the submission should acknowledge
what aspects of the presented work is not directly derived by
them. For the purposes of plagiarism it is irrelevant that you
have been given permission by someone to copy their work
and present it as your own.
You are directed to the School of Computer Science and Software Engineering Policy on Plagiarism and the Faculty of Engineering,Computing and Mathematics Policy on Plagiarism.
Faculty Scaling
Final assessment is subject to the Faculty Scaling Policy.
This information is correct as at 28-Feb-2005, but is subject
to change from time to time. In particular, The University
reserves the right to change the content and/or method of
presentation and/or the method of assessment of any unit of
study, to withdraw any unit of study or programme, and/or to
vary arrangements for any programme.
Copyright© 2005
School of Computer Science, & Software Engineering
The University of Western Australia
CRICOS Provider Code: 00126G
Last updated: 28-Feb-2005 |
