Discrete Math

Fall 1997

This course was developed in conjunction with Dr. David Dennis (UTEP) with support from the Model Institutions for Excellence (MIE) initiative, funded at UTEP by the National Science Foundation Change in location!!! Starting immediately, this class will meet in PSCI 216


Instructor: Dr. Art Duval

Please feel free to come by any time during scheduled office hours. You are welcome to come at other times, but in that case you might want to make an appointment, just to make sure that I will be there then. You can make an appointment simply by talking to me before or after class, by calling me at my office or at home, or by sending e-mail.


The course may be roughly divided into two halves, combinatorics and graph theory, with a few topics on the edges of these. Combinatorics will include induction, permutations, combinations, recurrences and more difficult counting problems. Graph theory will include basic graph definitions, trees, and graph algorithms. We will also see modular arithmetic and ``big-O'' notation (order of magnitude). There is no textbook.


The course grade will be based entirely on projects. Each project will have an initial due date (approximately weekly), by which time some work (however partial) must be turned in. These will be returned as soon as possible with questions and comments, after which you may respond, revise, amend, and then resubmit the project. Resubmitted solutions will again be returned with comments and may again be revised and resubmitted. No more than five projects will be accepted during the last two weeks of the course, so please pace yourself in a reasonable way. Your final grade will depend on a portfolio of all your submissions for the semester; therefore, keep all your submissions (even after turning in subsequent resubmissions for the same project).

Each project will be returned with one of three marks:

"check minus"
Some engagement with the project, but substantial questions remain.
A well reasoned explanation, but some questions remain.
"check plus"
A complete and thorough explanation, no further questions.
Some projects will have an asterisked (*) part that can count for an extra "plus".

For a D, you must eventually get at least a "check" on 50% of the projects. For a C, you must eventually get at least a "check" on all the projects. For a B, you must eventually get at least a "check" on all the projects, and a "check plus" on 40% of the projects. For an A, you must eventually get at least a "check" on all the projects, and a "check plus" on 80% of the projects.

Note: A "check minus" is cancelled by a "check plus" (so one "check minus" and one "check plus" is the same as two "check"s).

Attendance Policy:

Because of the experimental nature of this class, attendance is mandatory at all times. If you have more than three unexcused absences, you will be dropped from the class with an F. I will usually excuse an absence if you tell me about it in advance, or, in cases of emergencies, as soon as possible afterwards.

Drop date:

The deadline for student initiated drops with an automatic W is Fri. Oct. 17. There is no longer a separate ``faculty drop date''!


The purpose of this course is for you to become involved with a wide variety of situations and contexts which give rise to mathematical concepts essential for computer science. You will be expected to engage in a dialogue between grounded activity and systematic inquiry. Grounded activities will include situations arising from physical activity with games, puzzles, coins, dominoes, paper, rubber bands, and other physical objects. Systematic inquiry will involve the fullest possible use of linguistic tools (such as words, numbers, symbols, drawings, diagrams, tables, graphs, and computer software), usually using measurements made with the positive integers (i.e., counting).

Usually working in small groups with your classmates, you will engage each problem or situation presented in class and will attempt to describe and explain the results of that engagement in a written report. You must write your report yourself (a private oral exam is always possible, in case of irregularities). A description, experiment, explanation or proof is anything which is both meaningful to you and convinces other people of the validity of your thoughts, words and activities. Reports may incorporate any available media including written words, symbols, pictures, diagrams, models, tables, graphs, videos, computer discs, etc. I will be evaluating the written parts of your reports for grammar and other elements of writing.

After the initial reports are returned, selected students will be chosen to present their work in class. After such presentations others may still continue to resubmit those same projects in their own personal way making full or partial use of what has been presented. Originality and diversity of expression will always be encouraged.


We hope to use the results of this course as a model for the reform of this and similar math courses here at UTEP. For this reason some of our classes may be videotaped. Such videotapes will be used for research purposes only, and will not be shown in any public forum without the prior written consent of those who appear in those tapes.

Final Word:

Mathematics is not a march down any particular road, but rather a walk in a garden with many branching paths that circle and wind back onto themselves. Visitors stroll in many different ways, pausing to look down at a single small flower, or gaze out over an enchanting vista, or perhaps even to water, weed or plant (for a garden is a human creation constructed within the constraints of life). Each new return brings its own special set of views and experiences. - David Dennis