From dinitz@uvm-gen.EMBA.UVM.EDU Fri Jun 18 09:15:30 1999
Greetings from Jeff Dinitz in Vermont,
I have been asked to be on a panel discussion at the British Combinatorial Conference next month, the topic is "Combinatorics in Undergraduate Courses". (I know -- I should have told them I had laryngitis, but I didn't). Being the only represenative not from Britain, I thought it might be interesting if I did a very informal poll of mathematicians at colleges and universities in North America asking the question, "Tell me about combinatorics in undergraduate classes at your institution". So to make it easy for you and take up as little of your time as possible, I have listed combinatorics classes below that I know are taught at the undergraduate level at some institutions. I'd appreciate it if you would indicate below which of these are taught at your school.
I have only one additional question, "What is the most innovative/interesting/different combinatorics class that is taught at your institiution ?"
Please reply to me via e-mail at Jeff.Dinitz(at)uvm.edu at your earliest convenience. You can forget about this after July 5. Also, please do not e-mail me with any questions or requests for clarification, this is not a scientific survey, just do your best to answer the questions.
Thanks for your time, have a great summer, maybe I'll see you in England,
Regards,
Jeff
Jeff Dinitz
Professor and Department Chair
Department of Mathematics and Statistics
University of Vermont
Burlington, Vt 05405
---------------------------------------------
---------------------------------------------
---------------------------------------------
Name:
Institution:
Mark an X before each class that is taught more-or-less regularly at your institution (anywhere on campus) for at least 2/3 of a term. Mark XX if it is a full year course. Put an R if it is required for a degree.
discrete math (sophomore, typically CS)
combinatorics (roughly 1/2 enumeration, 1/2 graph theory)
combinatorics (broad 1 year course)
enumeration
graph theory
coding theory
cryptography
linear optimization
integer programming
design theory
combinatorial algorithms
information theory
data compression
network flow theory
others??
-----------------------------------------------
What is the most innovative/interesting/different combinatorics course at your institution and what material does it cover?
------------------------------------------------
Thanks,
Jeff
I received 38 responses to my solicitation and I would like to thank each of those people for taking the time to respond. Here is a tally of the results. I have listed the class and on the left listed the number of institutions (out of 38) that teach that class.
31 -- discrete math (sophomore, typically CS)
22 -- combinatorics (roughly 1/2 enumeration, 1/2 graph theory)
3 -- combinatorics (broad 1 year course)
6 -- enumeration
25 -- graph theory
10 -- coding theory
8 -- cryptography (and data security)
17 -- linear optimization
6 -- integer programming
4 -- design theory
14 -- combinatorial algorithms
3 -- information theory
1 -- data compression
7 -- network flow theory
Others Mentioned:
1 -- game theory
2 -- introduction to proofs in discrete math context
1 -- advanced topics
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From grossman@Oakland.edu Fri Jun 18 09:18:53 1999
> I have only one additional question, "What is the most
> innovative/interesting/different combinatorics class that is taught at
> your institiution ?"
We have a summer camp for bright high school students, in which we
offer college level classes for credit. One year we offered them a
traditional "discrete math" course (which is about half combinatorics
and graph theory), and this year we are offering them a course in
mathematical programming (close?).
Name: Jerry Grossman
Institution: Oakland University
Mark an X before each class that is taught more-or-less regularly at
your institution (anywhere on campus) for at least 2/3 of a term. Mark
XX if it is a full year course. Put an R if it is required for a
degree.
XR discrete math (sophomore, typically CS)
X combinatorics (roughly 1/2 enumeration, 1/2 graph theory)
combinatorics (broad 1 year course)
enumeration
X graph theory
X coding theory
cryptography
X linear optimization
integer programming
design theory
X combinatorial algorithms
information theory
data compression
network flow theory
The discrete math course is required for a CS major, but is an elective
for a math major (that may change -- we may start to require it for math
majors who want to teach high school).
The algorithms course covers all algorithms, but it is about half
combinatorial.
best regards,
jerry
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From adean@skidmore.edu Fri Jun 18 09:18:40 1999
>
>Name: Alice Dean
>Institution: Skidmore College, Saratoga Springs, NY
>
>Mark an X before each class that is taught more-or-less regularly at
>your institution (anywhere on campus) for at least 2/3 of a term. Mark
>XX if it is a full year course. Put an R if it is required for a
>degree.
>
>
> R (required for CS major) discrete math (sophomore, typically CS)
> combinatorics (roughly 1/2 enumeration, 1/2 graph theory)
> combinatorics (broad 1 year course)
> enumeration
> X graph theory
> coding theory
> cryptography
> linear optimization
> integer programming
> design theory
> combinatorial algorithms
> information theory
> data compression
> network flow theory
>
>
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From CHARTRAND@wmich.edu Fri Jun 18 09:15:52 1999
Name: Gary Chartrand
Institution: Western Michigan University
Mark an X before each class that is taught more-or-less regularly at
your institution (anywhere on campus) for at least 2/3 of a term. Mark
XX if it is a full year course. Put an R if it is required for a
degree.
X,R discrete math (sophomore, typically CS)
combinatorics (roughly 1/2 enumeration, 1/2 graph theory)
combinatorics (broad 1 year course)
enumeration
X graph theory
coding theory
cryptography
linear optimization
integer programming
design theory
combinatorial algorithms
information theory
data compression
network flow theory
-----------------------------------------------------------
What is the most innovative/interesting/different combinatorics course
at your institution and what topics does it cover?
We have been teaching graph theory at the undergraduate level for about 25
years and it remaind the most popular elective among majors. It covers trees,
hamiltonian and eulerian graphs, coloring, planarity, digraphs (especially
tournaments), games and puzzles.
MANY of the courses listed above are taught here at the graduate level both in
the Math Dept (and CS).
Gary Chartrand
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From vince@fileserver.math.ufl.edu Fri Jun 18 09:24:17 1999
>
> Name: Andy Vince
> Institution: University of Florida
>
> Mark an X before each class that is taught more-or-less regularly at
> your institution (anywhere on campus) for at least 2/3 of a term. Mark
> XX if it is a full year course. Put an R if it is required for a
> degree.
>
>
> X discrete math (sophomore, typically CS)
> X combinatorics (roughly 1/2 enumeration, 1/2 graph theory)
> X combinatorics (broad 1 year course)
> enumeration
> graph theory
> coding theory
> cryptography
> X linear optimization
> integer programming
> design theory
> combinatorial algorithms
> information theory
> data compression
> network flow theory
>
>
> others?? SOME OF THE ABOVE ARE TAUGHT AS GRADUATE COURSES (open to
qualified undergraduates)
>
>
> -----------------------------------------------------------
>
> What is the most innovative/interesting/different combinatorics course
> at your institution and what topics does it cover?
>
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From rg@rgsun.mathcs.emory.edu Fri Jun 18 09:58:51 1999
From: Ron Gould
Jeff, Here is what we do at Emory at the undergraduate level.
discrete math (freshman level for CS students)
combinatorics (roughly 1/2 enumeration, 1/2 graph theory)
graph theory (runs on an irregular schedule while combinatorics runs
very regularly)
coding theory (again on an irregular schedule - when we can fit it in)
linear optimization (regular offering each year)
ron
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From combin@cs.toronto.edu Fri Jun 18 09:51:40 1999
From: Rudi Mathon
Name: Rudi Mathon
Institution: University of Toronto
XR discrete math (sophomore, typically CS)
X combinatorics (roughly 1/2 enumeration, 1/2 graph theory)
combinatorics (broad 1 year course)
enumeration
graph theory
coding theory
cryptography
linear optimization
integer programming
design theory
combinatorial algorithms
information theory
data compression
network flow theory
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From rosa@mcmail.cis.McMaster.CA Fri Jun 18 09:48:28 1999
From: Alexander Rosa
Hi Jeff,
there are only two undergraduate combinatorics classes that are being
taught at McMaster:
4C3 Combinatorics (covers basic counting, SDRs and designs - basically
everything other than graph theory)
4J3 Graph Theory
Both are one-term courses. However, our chairman is trying to eliminate
any traces of combinatorics or discrete mathematics. Because of some
ridiculous excuses, graph theory is not being offered next year, despite
consistently high enrollment numbers.vBy contrast, courses which are
taken by less than five students, are
being offered!
I don't think any of these courses are too innovative - just standard
basic stuff.
Best regards, Alex
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From albertson@neal.smith.edu Fri Jun 18 10:13:59 1999
From: Mike Albertson
>
> Mark an X before each class that is taught more-or-less regularly at
> your institution (anywhere on campus) for at least 2/3 of a term. Mark
> XX if it is a full year course. Put an R if it is required for a
> degree.
>
>
> X R discrete math (sophomore, typically CS)
required for both math and cs majors
> combinatorics (roughly 1/2 enumeration, 1/2 graph theory)
> combinatorics (broad 1 year course)
> X enumeration and designs one semester - alternate years
> X graph theory one semester - alternate years
> coding theory
> cryptography
> linear optimization
> integer programming
> design theory
> combinatorial algorithms
> information theory
> data compression
> network flow theory
X advanced topics in discrete applied mathematics one semester -
alternate years
The most recent topic has been computational complexity using
Papadimitriou's text of the same name.
Other topics have included linear programming and operations research.
> What is the most innovative/interesting/different combinatorics course
> at your institution and what topics does it cover?
Our initial introductory course is the most unusual of any of our courses.
It emphasizes beginning proof writing and real applications (e.g. RSA
cryptography (we prove the necessary number theory results), minimum
weight spanning trees.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From nfi3979u@postoffice.uri.edu Fri Jun 18 11:19:23 1999
From: "Norman J. Finizio"
Hi Jeff
We have two undergraduate combinatorics courses here at URI. Both of
them are one semester courses, each for 3 credits. One course is
considered "junior-level" (in our system the numbering begins with a
3) and the other is "senior-level" (... 4). The latter is primarily
graph theory (typical text "Pearls of Graph Theory) and the former is
somewhat "catch-all" (typical text Grimaldi's, Bogart's).
We also have a "pseudo-combinatorics" course that I would place in
your most interesting category. Namely we have a course for general
audiences (virtually no prerequisites, most students take it to
satisfy general education requirements) titled "Topics in
Mathematics". Frequently the course consists of the combinatorics
materials (plus some non combinatorics materials) that are found in
the text "For All Practical Purposes" by COMAP (a group of authors) In
my opinion it is great fun both for the students and the instructor.
Norm
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From hnw@cms1.mail.virginia.edu Fri Jun 18 10:56:48 1999
From: "Harold N. Ward"
| Name: Harold N. (Thann) Ward
| Institution: University of Virginia, Charlottesville, VA 22903
|
| Mark an X before each class that is taught more-or-less regularly at
| your institution (anywhere on campus) for at least 2/3 of a term. Mark
| XX if it is a full year course. Put an R if it is required for a
| degree.
|
|
| X discrete math (sophomore, typically CS) Recent text: Discrete
Mathematics, by H. F. Mattson. The course tends to be more
combinatorics, although some CS people take it. I've used Norman Biggs's
book on occasion.
| X coding theory Recent texts: Introduction to the Theory of
Error-Correcting codes, by Vera Pless; A First Course on Coding Theory,
by Ray Hill. We require the beginning abstract algebra course as a
prerequisite.
| X linear optimization This is given as an operations research course.
| integer programming
| X combinatorial algorithms A course on algorithms in general, combined
with C++.
| others??
| We teach a geometry course that varies in content. When I teach it, it
is finite affine and projective geometry. I've used Lynn Batten's book,
Combinatorics of Finite Geometries.
| What is the most innovative/interesting/different combinatorics course
| at your institution? The ones above are pretty routine. At the graduate
level we teach courses on coding theory and design theory, but not on a
regular basis.
I hope you enjoy the conference dinner in the castle!
Harold N. (Thann) Ward Office: Kerchof Hall, Room 304
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From erc@cs.uga.edu Fri Jun 18 11:08:51 1999
Name: Rod Canfield (Computer Science Dept)
Institution: University of Georgia
Mark an X before each class that is taught more-or-less regularly at
your institution (anywhere on campus) for at least 2/3 of a term. Mark
XX if it is a full year course. Put an R if it is required for a
degree.
xR discrete math (sophomore, typically CS)
combinatorics (roughly 1/2 enumeration, 1/2 graph theory)
combinatorics (broad 1 year course)
x I ADDED THIS LINE: combinatorics (w/o graph theory) semester course
enumeration
x graph theory
coding theory
x cryptography
linear optimization
integer programming
design theory
x combinatorial algorithms
information theory
data compression
network flow theory
others?? In CS, of course, we teach an "undergraduate theory" course
which is automata: regular languages, context free languages,
recursive, and recursively enumerable languages.
We also teach complexity.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From dijen@math.ohio-state.edu Fri Jun 18 10:48:09 1999
From: Dijen Ray-Chaudhuri
>
> Name: Dijen Ray-Chaudhuri
> Institution: Ohio State University
>
> Mark an X before each class that is taught more-or-less regularly at
> your institution (anywhere on campus) for at least 2/3 of a term. Mark
> XX if it is a full year course. Put an R if it is required for a
> degree.
>
>
> discrete math (sophomore, typically CS) X
> combinatorics (roughly 1/2 enumeration, 1/2 graph theory) X
> combinatorics (broad 1 year course)
> enumeration
> graph theory
> coding theory x
> cryptography
> linear optimization x
> integer programming x
> design theory
> combinatorial algorithms
> information theory
> data compression
> network flow theory
>
>
> others??
In our Math 575 we teach some Coding Theory, Design Theory and network
flow. Combinatorial algorithms is , I believe, taught in CIS. Codin
theory and probably Information Theory are taught in Electrical
Engineering. In Sustem Engineering ( Operations Research ) there are
several courses on Linear Programming, Integer programming and network
flow theory. best regards, Dijen.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From vanrees@cs.umanitoba.ca Fri Jun 18 12:04:59 1999
From: John Van Rees
>
> Name: John van Rees
> Institution:University of Manitoba Dept. of Computer Science
(If you want math contact Lynne Batten)
>
> Mark an X before each class that is taught more-or-less regularly at
> your institution (anywhere on campus) for at least 2/3 of a term. Mark
> XX if it is a full year course. Put an R if it is required for a
> degree.
>
>
o = occasionally
>R discrete math (sophomore, typically CS)
> combinatorics (roughly 1/2 enumeration, 1/2 graph theory)
> combinatorics (broad 1 year course)
> enumeration
>x graph theory(for CS)
>o real graph theory
> coding theory
>x cryptography
>o linear optimization
> integer programming
>0 design theory & coding theory
> combinatorial algorithms
> information theory
> data compression
> network flow theory
>
There are several computer science courses that have combinatorics in
them. Like second year computing, analysis and design of algorithms,
networks, formal languages
>
> -----------------------------------------------------------
>
> What is the most innovative/interesting/different combinatorics course
> at your institution and what material does it cover?
>
Sometimes formal languages is taught as labelled graph theory. It gets
tedious after a while but almost everything can be done this way.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From hadi@imra.cs.uleth.ca Fri Jun 18 13:34:18 1999
From: Hadi Kharaghani
Name: Hadi Kharaghani
Institution: University of Lethbridge
Mark an X before each class that is taught more-or-less regularly at
your institution (anywhere on campus) for at least 2/3 of a term. Mark
XX if it is a full year course. Put an R if it is required for a
degree.
discrete math (sophomore, typically CS)
XR combinatorics (roughly 1/2 enumeration, 1/2 graph theory)
combinatorics (broad 1 year course)
enumeration
graph theory
coding theory
X cryptography
linear optimization
X integer programming
design theory
combinatorial algorithms
information theory
data compression
network flow theory
others??
Jeff,
that is all we do here. University of Lethbridge is a mainly undergraduate
university with 6,000 students.
Hadi Kharaghani
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From Kenneth.P.Bogart@Dartmouth.EDU Fri Jun 18 13:36:38 1999
Name: Ken Bogart
Institution: Dartmouth
Mark an X before each class that is taught more-or-less regularly at
your institution (anywhere on campus) for at least 2/3 of a term. Mark
XX if it is a full year course. Put an R if it is required for a
degree.
X discrete math (sophomore, typically CS)
X combinatorics (roughly 1/2 enumeration, 1/2 graph theory)
combinatorics (broad 1 year course)
X enumeration
X graph theory
coding theory
cryptography
X linear optimization
integer programming
? design theory---part of combinatorics course marked above
combinatorial algorithms
information theory
data compression
network flow theory
others??
combinatorial algorithms are taught in our CS department's algorithms course
They also regularly have a course in network flows
-----------------------------------------------------------
What is the most innovative/interesting/different combinatorics course
at your institution and what topics does it cover?
Algebraic Combinatorics is a course that starts with counting things
like circular arrangements as counting equivalence classes of an
equivalence relation and ends with Polya Theory and Mobius Inversion.
What makes it unique and fun to teach is that the students work from a
list of about 100 exercises (revised each time) with maybe five pages
worth of exposition woven in. Most of the time in class is spent
working in groups figuring out how to do problems. For progblems that
are not obvious to everyone someone in a group that has solved it goes
to the board with an explanation. They keep a problem notebook and
must rewrite solutions until they are acceptable. My expereince is
that they actually learn Polya theory, for example, and can derive
Polya's theorem in an oral exam without advance warning that a
derivation will be (very casually) asked for. I purposely ask them in
such a way that it is clearly optional to give me a derivation.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From gross@diamond.cs.columbia.edu Fri Jun 18 15:42:33 1999
From: J L Gross
Jonathan L. Gross
Professor of Computer Science
Columbia University
New York, NY 10027
>
> Mark an X before each class that is taught more-or-less regularly at
> your institution (anywhere on campus) for at least 2/3 of a term. Mark
> XX if it is a full year course. Put an R if it is required for a
> degree.
>
>
>X discrete math (sophomore, typically CS)
> combinatorics (roughly 1/2 enumeration, 1/2 graph theory)
> combinatorics (broad 1 year course)
> enumeration
>X graph theory
> coding theory
> cryptography
>X linear optimization
> integer programming
> design theory
>X combinatorial algorithms
> information theory
> data compression
>X network flow theory
>
>
> others??
>X one-smester general combinatorics
(from Graham, Knuth, Patashnik: CONCRETE MATH)
>
> -----------------------------------------------------------
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From blr@math.ucla.edu Fri Jun 18 15:45:00 1999
From: Bruce Rothschild
Name: Bruce Rothschild
Institution: UCLA
Mark an X before each class that is taught more-or-less regularly at
your institution (anywhere on campus) for at least 2/3 of a term. Mark
XX if it is a full year course. Put an R if it is required for a
degree.
X discrete math (sophomore, typically CS)
X combinatorics (roughly 1/2 enumeration, 1/2 graph theory)
combinatorics (broad 1 year course)
enumeration
graph theory
coding theory
cryptography
X linear optimization
integer programming
design theory
X combinatorial algorithms
information theory
data compression
network flow theory
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From martin@UWinnipeg.ca Fri Jun 18 15:57:04 1999
From: Bill Martin
Hi Jeff, Gee, you sure have a knack for getting more work dumped on you.
Sincerely, though, nice project. -Bill
Bill Martin
U. of Winnipeg (Canada)
X enumeration
X graph theory
1/2 coding theory
1/2 cryptography
X linear optimization
X network flow theory
others??
X first-year discrete math (intro to proofs in discrete math context)
-----------------------------------------------------------
What is the most innovative/interesting/different combinatorics course
at your institution and what material does it cover?
Applied Algebra (2nd year): half coding theory, half crypto (as listed
above). Sales pitch for modern algebra. So the students enter knowing
little more than Z_n. Ideally, they leave willing to learn groups, etc.
One year teaching this course, I got frustrated that I couldn't cover
much material, so I gave each of the 17 students a project. They read
either a research paper or (more likely) a chapter in an advanced book.
Then they wrote a ten page report and gave a 20 min. oral presentation.
They loved it. Topics included: MacWilliams THm, Assmus-Mattson,
El Gamal, MacEliece cryptosystem, factoring, projective planes,
compression.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From Rick.Vitray@Rollins.Edu Fri Jun 18 15:47:36 1999
From: Rick Vitray
Name: Rick Vitray
Institution: Rollins College
Mark an X before each class that is taught more-or-less regularly at
your institution (anywhere on campus) for at least 2/3 of a term. Mark
XX if it is a full year course. Put an R if it is required for a
degree.
X discrete math (sophomore, typically CS)
combinatorics (roughly 1/2 enumeration, 1/2 graph theory)
combinatorics (broad 1 year course)
enumeration
X graph theory
coding theory
cryptography
linear optimization
integer programming
design theory
X combinatorial algorithms ?? (We have a couple of courses that
might fall in this category)
information theory
data compression
network flow theory
others??
-----------------------------------------------------------
What is the most innovative/interesting/different combinatorics course
at your institution and what topics does it cover?
The most interesting course is the Graph Theory course for our junior
and senior math majors. We have used "Pearls in Graph Theory" in the
past and are able to get the students thinking about open questions
very quickly.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From craigen@fresno.edu Fri Jun 18 18:27:43 1999
In my responses, F = at FPC, L = at Lethbridge, to reflect the two
institutions I have recently taught at (I am moving this summer to
Winnipeg, MB, though to teach at U of M.) I ignore your letter conventions
because precious little is done at either institution.
>-------------------------------------------------------
>-------------------------------------------------------
>-------------------------------------------------------
>
>Name: Rob Craigen
>Institution:
>
>Mark an X before each class that is taught more-or-less regularly at
>your institution (anywhere on campus) for at least 2/3 of a term. Mark
>XX if it is a full year course. Put an R if it is required for a
>degree.
>
>
> F discrete math (sophomore, typically CS)
> L combinatorics (roughly 1/2 enumeration, 1/2 graph theory)
> combinatorics (broad 1 year course)
> enumeration
> graph theory
> coding theory
> cryptography
> linear optimization
> integer programming
> design theory
> combinatorial algorithms
> information theory
> data compression
> network flow theory
>
>
>others??
>
>
>-----------------------------------------------------------
>
>What is the most innovative/interesting/different combinatorics course
>at your institution and what material does it cover?
>
>
The one labelled F above is taught hear annually by Jim Wilson, who is
not a mathematician or a computer scientist, but a dabbler in science
for teachers. He does some interesting things, including enough
circuit design to construct a full adder. Nevertheless, there is
precious little in the way of traditional combinatorics in the course.
Students come out of the class enthralled, but not much the wiser as
to the basics of discrete math.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From anstee@math.ubc.ca Fri Jun 18 17:39:35 1999
From: Richard Anstee
Dear Jeff,
Our combinatorics/discrete math offerings are spread around.
At the undergrad level:
CPSC 220 proof techniques via discrete math
MATH 340 Linear Programming
MATH 441 modelling solving large scale integer lp's using
software as a tool
MATH 442 Network Flows
MATH 443 Graph Theory
no cryptography/design theory etc
reasonable student numbers from CompSci so algorithmics important
>
>Name: Richard Anstee
>Institution: University of British Columbia
>
>Mark an X before each class that is taught more-or-less regularly at
>your institution (anywhere on campus) for at least 2/3 of a term. Mark
>XX if it is a full year course. Put an R if it is required for a
>degree.
>
>
> X discrete math (sophomore, typically CS)
> combinatorics (roughly 1/2 enumeration, 1/2 graph theory)
> combinatorics (broad 1 year course)
> enumeration
> X graph theory
> coding theory
> cryptography
> X linear optimization
> X integer programming
> design theory
> combinatorial algorithms
> information theory
> data compression
> X network flow theory
>
>What is the most innovative/interesting/different combinatorics course
>at your institution and what material does it cover?
Modelling course mainly involving Integer Linear Programming applied
to `real world' problems in a case study way.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From mullen@math.psu.edu Mon Jun 21 08:37:54 1999
From: Gary L Mullen
Name: Gary Mullen
Institution: Penn State University
Mark an X before each class that is taught more-or-less regularly at
your institution (anywhere on campus) for at least 2/3 of a term. Mark
XX if it is a full year course. Put an R if it is required for a
degree.
X discrete math (sophomore, typically CS)
X combinatorics (roughly 1/2 enumeration, 1/2 graph theory)
combinatorics (broad 1 year course)
enumeration
graph theory
X coding theory
cryptography
linear optimization
X integer programming
design theory
X combinatorial algorithms
information theory
data compression
network flow theory
others??
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From nshalaby@math.mun.ca Sat Jun 19 22:26:42 1999
From: Nabil Shalaby
>
> Name: Nabil Shalaby
> Institution:Memorial University of NF, Canada.
>
> Mark an X before each class that is taught more-or-less regularly at
> your institution (anywhere on campus) for at least 2/3 of a term. Mark
> XX if it is a full year course. Put an R if it is required for a
> degree.
>
>
> discrete math (sophomore, typically CS) X, R
> combinatorics (roughly 1/2 enumeration, 1/2 graph theory) X,(partly R)
> combinatorics (broad 1 year course)
> enumeration X ( 4th year)
> graph theory X
> coding theory
> cryptography
> linear optimization
> integer programming
> design theory X
> combinatorial algorithms
> information theory
> data compression
> network flow theory
>
>
> others??
>
>
> -----------------------------------------------------------
>
> What is the most innovative/interesting/different combinatorics course
> at your institution and what material does it cover?
>
The 4th year combinatorial design course which is an elective but
sometime we get as many as 30 students enrolled. The text I used for
The last two years is (Ian Anderson's : Combinatorial designs). The
material covered is: Basics of finite fields, BIBDs, MOLs Room
squares, cyclic STSs, Kirkman triple systems and applications.
I think what make this subject interesting to the students are the
assignments and projects that involve constructing these objects
(using the difference method) thus the students appreciate and
understand these objects and thus it is easier for them to prove more
results about these objects.
I feel that it will be much easier for me if there is a complete set
of solutions given to the instructor, this will give me some choice to
mix some of the exercises from the text and from other sources without
spending too much time especially at the end of term (year). It seems
true to me that the majority of the 3rd and 4th year combinatorics
text books come without solutions with the added inconveniences of
errors in the text and the statements of some of the problems.
Best Regards
Nabil
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From SARVATED@cofc.edu Sat Jun 19 13:20:25 1999
Dear Jeff,
I wrote and requested the chair of CS dept to let me know about your
various course listing. He took time and replied , so I am forwarding his
mail. sorry, it is not in the format you would have liked.
We teach two discrete math classes 207 and 307 in math dept (comp. SC
studnets ae required these course. We use Rosen's discrete math book or
Johnsonbough's book. We cover the whole book in two semester. Don't forget
to read what is in the chair's mail below.
Regards and good wishes for your trip.
Dinesh.
DINESH G. SARVATE, sarvated@ashley.cofc.edu
Department of mathematics (843) 953 5736 work
---------- Forwarded message ----------
Date: Fri, 18 Jun 1999 10:46:56 -0400
From: Chris Starr
To: sarvated@cofc.edu
Subject: Re: A question Please.
>Dear Chris,
>One of my friends and a wellknown mathematician Jeff Dinitz is going to
>Britain for a panel discussions on discrete math. He wanted to know which
>of the following courses we teach at the college. As many of the courses
>can be taught in your dept. Can you please let me know which of the
>following courses are regularly offered in your dept.?
>Which ones are required? I am giving the whole list, though I know some
>will not be taught in comp. sc.
>discrete math (sophomore, typically CS)
> combinatorics (roughly 1/2 enumeration, 1/2 graph theory)
Enumeration not taught in CS
Graph theory, algorithms and analysis covered in CSCI 330 (Data
Structures and Algorithm Analysis)
> combinatorics (broad 1 year course)
Not taught in CS
> enumeration
Binary, octal, and hex systems covered in CSCI 250 (Intro. to
Computer Organization and Assembly Language Programming)
> graph theory
Graph theory, algorithms and analysis covered in CSCI 330 (Data
Structures and Algorithm Analysis)
> coding theory
Brief introduction in CSCI 330 (Data Structures and Algorithm Analysis)
Extensive coverage in Special Topics course on Digital Security and
Cryptography
> cryptography
Extensive coverage in Special Topics course on Digital Security and
Cryptography
> linear optimization
Not taught in CS
> integer programming
Not taught in CS
> design theory
Covered in and as applicable to object-oriented programming and
design throughout the curriculum in CSCI 220, 221, 222, 320, 330, 460 and
461.
> combinatorial algorithms
Not taught in CS
> information theory
Some coverage in Special Topics course on Digital Security and
Cryptography and in CSCI 330.
> data compression
Some coverage in Special Topics course on Digital Security and
Cryptography and in CSCI 330 as associated with coding.
> network flow theory
Covered in CSCI 490 (Networking theory)
Let me know if you need more details or additional information. Hope this
helps some.
Chris
-------------------------------------
Christopher W. Starr, Ph.D., Chairman
Department of Computer Science
College of Charleston
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From jkahn@math.rutgers.edu Fri Jun 18 20:09:34 1999
From: Jeff Kahn
Hey mr panelist,
The shameful answer is I dunno (partial excuse: I'm not involved in
any of this stuff).
I think (but may be out of date) we have
1 semester comb, probably mostly enum, and
1 semester graph th,
probably no full year courses and no
coding theory
cryptography
design theory
info theory
Some of the ones below could well be done in CS or
RUTCOR (= center for O.R.), not done in math as
far as I know (which ain't that far).
linear optimization
integer programming
combinatorial algorithms
data compression
network flow theory
What is the most innovative/interesting/different combinatorics course
at your institution and what material does it cover?
Don't know this one either.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From mendelso@math.toronto.edu Sat Jun 19 19:27:40 1999
From: Eric Mendelsohn
> Name: Eric Mendelsohn
> Institution:University of Toronto
>
> Mark an X before each class that is taught more-or-less regularly at
> your institution (anywhere on campus) for at least 2/3 of a term. Mark
> XX if it is a full year course. Put an R if it is required for a
> degree.
>
>
R discrete math (sophomore, typically CS)
X combinatorics (roughly 1/2 enumeration, 1/2 graph theory)
> combinatorics (broad 1 year course)
> enumeration
> graph theory
> coding theory
> cryptography
X linear optimization
> integer programming
> design theory
X combinatorial algorithms
> information theory
> data compression
> network flow theory
>
>
> others??
>
>
> -----------------------------------------------------------
>
> What is the most innovative/interesting/different combinatorics course
> at your institution and what material does it cover?
University of Toronto? LOL ( Perhaps the most innovate and different
combinatirics course is PDE's --as it has no combinatorics (:-)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From ATRENK@WELLESLEY.EDU Mon Jun 21 10:30:31 1999
Name: Ann Trenk
Institution: Wellesley College
Mark an X before each class that is taught more-or-less regularly at
your institution (anywhere on campus) for at least 2/3 of a term. Mark
XX if it is a full year course. Put an R if it is required for a
degree.
discrete math (sophomore, typically CS)
X combinatorics (roughly 1/2 enumeration, 1/2 graph theory)
combinatorics (broad 1 year course)
enumeration
X graph theory -- every 3 or 4 years.
coding theory
cryptography
linear optimization
integer programming
design theory
combinatorial algorithms
information theory
data compression
network flow theory
others??
We teacg a discrete math course designed for non-science majors.
-----------------------------------------------------------
What is the most innovative/interesting/different combinatorics course
at your institution and what topics does it cover?
We only have one regularly offered combinatorics course at Wellesley.
It is 2/3 enumeration, 1/3 graph theory and lasts for only one
semester. It is required for the CS major, but math math majors take
it as a an "introduction to proofs" course before taking abstract
algebra. It works extremely well as an introduction to proofs and
mathematical thinking course. I use Brualdi's book (but don't follow
it too closely after the enumaration part) and the class is composed
largely of sophomores and juniors.
The course has become very popular (perhaps because the number of CS
majors is way up). This year we had 3 sections offered (1 fall, 2
spring) with each section having 20 -- 25 students enrooled.
-- Ann
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From janssen@mscs.dal.ca Mon Jun 21 11:02:39 1999
From: Jeannette Janssen
>
> Name: Jeannette Janssen
> Institution: Dalhousie University
>
> Mark an X before each class that is taught more-or-less regularly at
> your institution (anywhere on campus) for at least 2/3 of a term. Mark
> XX if it is a full year course. Put an R if it is required for a
> degree.
>
>
XX discrete math (sophomore, typically CS)
combinatorics (roughly 1/2 enumeration, 1/2 graph theory)
combinatorics (broad 1 year course)
enumeration
X graph theory
coding theory
* cryptography: this year new CS course Computer security
X linear optimization
X integer programming **as part of Optimization II, not separate
course)
design theory
X combinatorial algorithms
information theory
data compression
X network flow theory **also part of Optimization II
(Combinatorial) Game Theory
> -----------------------------------------------------------
What is the most innovative/interesting/different combinatorics course
at your institution and what material does it cover?
>
Game Theory. Starts with the classical economics stuff, but also has
the kind of stuff covered in Berlekamp et al: Winning Ways.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From carother@bgnet.bgsu.edu Mon Jun 21 12:20:29 1999
From: "Neal L. Carothers"
* Name: Neal Carothers
* Institution: Bowling Green State University
*
* Mark an X before each class that is taught more-or-less regularly at
* your institution (anywhere on campus) for at least 2/3 of a term. Mark
* XX if it is a full year course. Put an R if it is required for a
* degree.
*
*
* R discrete math (sophomore, typically CS)
* combinatorics (roughly 1/2 enumeration, 1/2 graph theory)
* combinatorics (broad 1 year course)
* enumeration
* graph theory
* coding theory
* cryptography
* linear optimization
* integer programming
* design theory
* combinatorial algorithms
* information theory
* data compression
* network flow theory
*
*
* others?? ** various other topics taught only occasionally **
* (sad, isn't it?) some of these topics are taught by other
* departments (CS, OR, etc.), but not in any real depth
* -----------------------------------------------------------
*
* What is the most innovative/interesting/different combinatorics course
* at your institution and what material does it cover?
*
We've recently started offering a new course that may
ultimately fit the description of an innovation -- for
now it's just an experimental course containing a
combinatorics component. I'm hesitant to say more at
this time.
Let me know if you learn anything interesting at the
conference. If the panel comes up with specific recommendations,
I'd like to hear them.
-- Neal
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From claywine@spartan.ac.brocku.ca Mon Jun 21 11:53:29 1999
>
>Name: Chuck Laywine
>Institution: Brock University, St. Catharines ON
>
>Mark an X before each class that is taught more-or-less regularly at
>your institution (anywhere on campus) for at least 2/3 of a term. Mark
>XX if it is a full year course. Put an R if it is required for a
>degree.
>
>
> discrete math (sophomore, typically CS) XX freshman (R for CS)
> combinatorics (roughly 1/2 enumeration, 1/2 graph theory) X R
> combinatorics (broad 1 year course)
> enumeration
> graph theory
> coding theory
> cryptography
> linear optimization
> integer programming
> design theory X
> combinatorial algorithms X
> information theory
> data compression
> network flow theory X
>
>
>others??
NP- completeness X (this, together with the last 2 X's above, form a
full year course primarily for CS.)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From danziger@scs.Ryerson.CA Tue Jun 22 11:24:50 1999
From: Peter Danziger
> Name: Peter Danziger
> Institution: Ryerson University
>
> Mark an X before each class that is taught more-or-less regularly at
> your institution (anywhere on campus) for at least 2/3 of a term. Mark
> XX if it is a full year course. Put an R if it is required for a
> degree.
>
>
> X discrete math (sophomore, typically CS)
> combinatorics (roughly 1/2 enumeration, 1/2 graph theory)
> combinatorics (broad 1 year course)
> enumeration
> X graph theory (Never actually run but on the books)
> coding theory
> cryptography
> linear optimization
> integer programming
> design theory
> combinatorial algorithms
> information theory
> data compression
> network flow theory
>
>
> others??
>
>
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From heinrich@cs.sfu.ca Tue Jun 22 21:38:09 1999
>Name: Kathy Heinrich
>Institution: SFU
>
>Mark an X before each class that is taught more-or-less regularly at
>your institution (anywhere on campus) for at least 2/3 of a term. Mark
>XX if it is a full year course. Put an R if it is required for a
>degree.
x means one semester - 13 weeks, 3 hours per week
>
>
> x discrete math (sophomore, typically CS)
> x combinatorics (roughly 1/2 enumeration, 1/2 graph theory)
> combinatorics (broad 1 year course)
> enumeration
> x graph theory
> x coding theory
> cryptography
> x linear optimization
> x integer programming
> design theory
> x combinatorial algorithms
> information theory
> data compression
> network flow theory
>
>
>others?? X COMBINATORICS - A FOURTH YEAR COURSE
>
>
>-----------------------------------------------------------
>
>What is the most innovative/interesting/different combinatorics course
>at your institution and what material does it cover?
>
NOT SURE WE HAVE SUCH A THING. PERHAPS COMBINATORIAL ALGORITHMS - NEED
TO TALK TO LUIS OR BRIAN FOR MORE INFOMRATION.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From goldberg@cs.rpi.edu Tue Jun 22 16:54:35 1999
From: Mark Goldberg
Dear Jeff,
Here is my answer:
I am a part of a project supported by NSF, called Links.
The project's goal is to develop a set of MODULES in different
areas of Math and Engineering.
Graph Theory is one of them. This answers your question
> "Tell me about combinatorics in undergraduate
> classes at your institution".
I believe this is pretty innovative in teaching Graph Theory. Currently, one
module is finished (most of it). Two more will be finished soon. It is done
by me and a CS graduate student Jan Kratky. Please look at
http://links.math.edu/devmodules/graph_theory
If you decide to mention this, please retain the copyright notice and
its identity as a "Project Links" module.
Thanks,
-Mark
> -------------------------------------------------------
> -------------------------------------------------------
>
> Name: Mark Goldberg
> Institution: Rensselaer Polytechnic Institute
>
> discrete math (sophomore, typically CS) *
> combinatorics (roughly 1/2 enumeration, 1/2 graph theory)
> combinatorics (broad 1 year course)
> enumeration
> graph theory .............................*
> cryptography
> linear optimization
> integer programming
> design theory
> combinatorial algorithms
> information theory
> data compression
> network flow theory
>
>
> What is the most innovative/interesting/different combinatorics course
> at your institution and what topics does it cover?
>
Graph Theory: see
http://links.math.rpi.edu/devmodules/graph_theory
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From kreher@mtu.edu Thu Jun 24 13:16:04 1999
From: "Donald L. Kreher"
Jeff,
I am not certain what 2/3 of a term means. Curerently we have 3 terms
perm year (quarters). Next year we go to 2 terms per year (semesters).
I put capitals for quarters and lower case for semesters.
I also asume you meant undergrad courses only!
Name: Don Kreher
Institution: MTU.
Mark an X before each class that is taught more-or-less regularly at
your institution (anywhere on campus) for at least 2/3 of a term. Mark
XX if it is a full year course. Put an R if it is required for a
degree.
R discrete math (sophomore, typically CS)
r combinatorics (roughly 1/2 enumeration, 1/2 graph theory)
combinatorics (broad 1 year course)
enumeration
R graph theory
r coding theory
r cryptography
linear optimization
integer programming
design theory
combinatorial algorithms
information theory
data compression
network flow theory
others??
r combinatorial Otimization/Graph Algorithms
r information theory/data compression
-----------------------------------------------------------
What is the most innovative/interesting/different combinatorics course
at your institution and what material does it cover?
My graduate course on Combinatorial Algorithms of course!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From pal@math.la.asu.edu Wed Jun 30 09:02:52 1999
From: "Philip A. Leonard"
>
> Name: Phil Leonard
> Institution: Arizona State University
>
> Mark an X before each class that is taught more-or-less regularly at
> your institution (anywhere on campus) for at least 2/3 of a term. Mark
> XX if it is a full year course. Put an R if it is required for a
> degree.
>
>
> X/R(for CS degree) discrete math (sophomore, typically CS)
> combinatorics (roughly 1/2 enumeration, 1/2 graph theory)
> XXcombinatorics (broad 1 year course)
> enumeration
> X graph theory
> coding theory
> X cryptography
> X linear optimization
> integer programming
> design theory
> X (in CS) combinatorial algorithms
> information theory
> data compression
> network flow theory
>
>
> others?
not for undergraduates
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From mne@math.Vanderbilt.Edu Tue Jun 29 13:03:05 1999
From: Mark Ellingham
Name: Mark Ellingham
Institution: Vanderbilt University, Nashville, Tennessee
Mark an X before each class that is taught more-or-less regularly at
your institution (anywhere on campus) for at least 2/3 of a term. Mark
XX if it is a full year course. Put an R if it is required for a
degree.
X discrete math (sophomore, typically CS)
[R for CS degree, not for math]
X combinatorics (roughly 1/2 enumeration, 1/2 graph theory)
X combinatorics (broad 1 year course)
enumeration
X graph theory
X coding theory
cryptography
X linear optimization
[incorporates some integer programming/combinatorial optimization]
integer programming
design theory
combinatorial algorithms
information theory
data compression
network flow theory
others??
Occasional special topics courses at graduate level that are also open
to talented undergraduates, e.g. in Fall 1999 Mike Plummer will give a
course on packings and coverings in graphs.
-----------------------------------------------------------
What is the most innovative/interesting/different combinatorics course
at your institution and what topics does it cover?
They're all pretty standard, except for the special topics
courses. The linear optimization course is still in a state of
flux, so I guess it's the most "innovative"; it involves:
Simplex method and basic LP theory (based on first few
chapters of Chvatal): about 7 weeks
Ellipsoid method and interior point methods: about 2
weeks
Integer programming (about 5 weeks):
Integer program models of combinatorial
optimization problems
LP relaxations
Total unimodularity
Gomory cutting planes
[Branch and bound, Dynamic programming if have time]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From mewatkin@syr.edu Sun Jun 27 12:47:07 1999
From: Mark Watkins
Name: Mark Watkins
Institution: Syracuse University
UNDERGRADUATE COURSES:
XR discrete math (sophomore, typically CS)
X combinatorics (roughly 1/2 enumeration, 1/2 graph theory)
GRADUATE COURSES:
X graph theory
X a 1-semester course that covers enumeration, design theory, and matroids.
X a "topics" course
-----------------------------------------------------------
>
>What is the most innovative/interesting/different combinatorics course
>at your institution and what topics does it cover?
Most recently the graduate topics course covered some background in
permutation group theory, followed by automorphism groups of graphs and
maps.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From west@math.uiuc.edu Sun Jun 27 15:58:41 1999
From: Douglas West
Name: Douglas West
Institution: University of Illinois
Mark an X before each class that is taught more-or-less regularly at
your institution (anywhere on campus) for at least 2/3 of a term. Mark
XX if it is a full year course. Put an R if it is required for a
degree.
X discrete math (sophomore, typically CS)
? combinatorics (roughly 1/2 enumeration, 1/2 graph theory)
combinatorics (broad 1 year course)
X enumeration
X graph theory
X coding theory
? cryptography
X linear optimization
X integer programming
? design theory (see math 470, 474)
X combinatorial algorithms
X information theory
? data compression
X network flow theory
math department:
213 discrete structures, killed as 319, resurrected a few years later
at the behest of computer engineering
283 linear programming service course, taught as 383 until now.
312 graph theory
313 combinatorics, enumeration and a smattering of other things, dying due
to CS courses, may be saveable
373 (see CS 373)
375 (see CS 375)
382 linear programming and combinatorial optimization, a solid mathematical
course taught once, to be invigorated by renumbering 383 to 283
417 extremal graph theory (distance, matching, coloring, perfect graphs, turan)
418 structure of graphs (encodings, connectivity, embeddings, minors, algebraic)
470 combinatorics, broad 1-semester course, precedes 417, 418, 473, 474
473 partial orders and optimization (antichains, extensions, int prog, matroids)
474 methods of combinatorics (enumeration, prob meth, Ramsey, design theory)
475 topic in combinatorics (e.g., probabilistic methods, linear algebraic
methods, algebraic graph theory, geometric combinatorics, etc.)
476 (see ECE 456)
479 (see ECE 479)
480 optimization by vector space methods
483 network optimization (non-standard approach)
484 conjugate duality and optimization (convex analysis, etc.)
Computer Science
173 discrete mathematical structures (competes with math)
273 theory of computation (includes recurrences, etc.)
373 combinatorial algorithms
375 automata, formal languages, and complexity
473 topics in analysis of algorithms
Electrical and Computer Engineering
456 coding theory
463 information theory
474 topics in graph and geometric algorithms
479 computational complexity
Business Administration
479 mathematical programming
Mechanical and Industrial Engineering
403 integer programming
-----------------------------------------------------------
What is the most innovative/interesting/different combinatorics course
at your institution and what material does it cover?
Math 382 and Math 470 are particularly interesting courses. Math 417,
418, 473, 474 are subsequent rotating courses that thoroughly cover a
large amount of advance combinatorics.
Math 382 is a rigorous introduction to linear and integer programming,
linear complementarity, networks, and polyhedral methods. It has only
been taught once, but should revive with the renumbering of 383 to
283.
Math 470 moves quickly and covers a 1-semester selection from a 1-year
course. The graph theory is treated a bit briefly since our other
courses treat it thoroughly.
enumeration: bijections, gen fcns, recurrences, inclusion-exclusion,
and a brief mention of young tableaux and polya theory
graph theory: matching, connectivity, coloring, planarity
sets: pigeonhole, ramsey, kruskal-katona, dilworth, sperner, dimension
methods: probabilistic (basics), algebraic (often skipped)
designs: latin squares & projective planes, a hint of triple systems
optimization: time only for an introduction to matroids
We have the courses, send us students! :-)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%