Schindler's List.

The Undergraduate Studies Committee has unanimously supported my initiative to seek a revamp the discrete math course on our campus.

Naturally, this means a straw poll!

So, tell me again, please:

Here is our current CS and IS curriculum (now undergoing revision).

Thanks!

--

Banazir

... to paraphrase a Talmudic quotation by Ben Kingsley's Itzhak Stern in the Spielberg film The Undergraduate Studies Committee has unanimously supported my initiative to seek a revamp the discrete math course on our campus.

Naturally, this means a straw poll!

So, tell me again, please:

- 1. When do you think a Discrete Math course should be taken by computer science majors at the
**latest**? - 2. Should all Information Systems (IS, not MIS!) majors take discrete math?
- 3. Should Math Secondary Ed majors take it?
- 4. What topic or topics are absolutely
**essential**in a first course in discrete math? - 5. What topics did you have in your first discrete math course, if any, that you could have done without?

**Edit**, 12:45 CDT Tue 02 May 2006:__How it currently is at K-State__Here is our current CS and IS curriculum (now undergoing revision).

- 1.
*Discrete Mathematics*(`MATH 510`

) is indicated in the fourth semester for Computer Science majors, after*Logic for Computer Science*(`CIS 310`

) and*Data Structures and Algorithms*(`CIS 300`

). There really isn't much in the way of algorithms in CIS 300 beyond searching and sorting, while CIS 301 is primarily about propositional and first-order logic. There is minimal proof theory in CIS 301: they cover natural deduction and inductive proof, but not with sets, or counting. I don't think they do much with first-order logic, even though the instructors (Huth, Banerjee, Amtoft, Howell) have all been very qualified logicians and theoretical CS reseaerchers.

Because of various anxieties,`MATH 510`

is often deferred to the fifth, sixth, or even**seventh**semester. This, IMO, is a**disaster**. Students sometimes take the**first course in discrete math**concurrently with courses such as*Introduction to Database Systems*(`CIS 560`

),*Intro to Artificial Intelligence*(`CIS 490/730`

), etc. It is a prerequisite for*Automata, Formal Languages, and Theory of Computation*(`CIS 570`

), but many students defer that until their senior year, and it is not required for the Information System (IS) major. To my knowledge, it is not a prerequisite for*Programming Language Fundamentals*(`CIS 505`

). It is not an official prerequisite for*Analysis of Algorithms*(`CIS 575`

), the Algos I course, but AFAIK nobody takes that out of order, and that is not required for IS, either. - 2. IS majors take
*Finite Applications of Mathematics*(`MATH 312`

), indicated in the second semester. As nearly as I can tell, this course exists to prevent our students from looking like complete ignoramuses should Jay Leno do a "Jaywalking" segment on our campus. In fact, its title is a misnomer: the textbook it uses is titled*Finite Mathematics and its Applications*. Neither the mathematics nor the applications are finite, though.

If I had my druthers, I would get rid of this course entirely; it's 80% redundant with College Algebra (linear systems of equations, graphing, functions), Calc I (ditto), and the first month of a real Discrete Math course. The "baby linear algebra" covered in the course is a joke; one could stand in the doorway of a linear algebra course and osmote more from the general ambience. - 3. Secondary math ed majors take
*Finite Applications of Mathematics*(`MATH 312`

). As I said, I'd like to get rid of the course and have**everyone**take a streamlined intro to discrete math (say,`MATH 310`

). I'll bet this would be a boon to HS math students taught by our graduates, too, though I expect that this will be a hard sell with Education. - 4. I'll post my draft syllabus soon.
- 5.
**I**went on to take*Combinatorics*(`550.471`

) and*Graph Theory*(`550.472`

) in my senior year at Hopkins, and we had a 100-level DM course, so I'd say "nothing". Here at K-State, though, I would say there are some topics covered that properly belong in a second (elective) course - for example: advanced combinatorics, generating functions, modern algebra, advanced number theory, and advanced graph theory.

Thanks!

--

Banazir

- Current Mood: hopeful
- Current Music:Fleetwood Mac - Let's Stay Together

## Comments

adele87banazirHere is my recommended textbook. This is just what we are going to suggest to the Math department; they may or may not go for it.

I'll be posting a draft syllabus that we are taking to the math department and Engineering/Math liaison committee soon.

--

Banazir

adele87Maybe I should make him add you. :D

fleurdelistachaosinaskirttmehlingerThere are two professors who cover the gamut of discrete math... counting principles, inclusion-exclusion principle, binomial theorem, generating functions, recurrence relations, graph theory (lots and lots of graph theory), etc. There are also some professors who seem to think a semester of boolean logic is more than enough material for one discrete math course. It's a crap shoot.

Now to answer the original questions....

1. Having been a victim of the current system, I can say that discrete math should absolutely be taken in the first year, or as soon as possible thereafter. There's too much useful stuff that would have made later courses in CS make a hell of a lot more sense.

2. No. I have no justification for this besides my opinion that IS students would probably never use it.

3. GOD NO, GET THEM OUT OF HIGHER LEVEL MATH COURSES, THEY'RE KILLING US. Yes, I have a bias against secondary ed students. Truthfully though, it's probably not going to be all that useful for them (unless they have ambitions of teaching discrete math in high school... yeah, right). We learned some neat tricks that might be useful for secondary ed, but nothing that you couldn't pick up by merely paying attention in other courses.

4. Graph theory is absolutely essential, and counting principles are pretty handy too. After that, everything is just cool stuff that's fun to know.

5. None. It was all useful. Granted, I'm a bit biased because I'm a math major too, but hey....

chaosinaskirtchaosinaskirtI believe that abstract algebra is one of the cornerstones to really understanding what math is. The tools one learns in an abstract algebra class IMO play a significant role in other mathematics courses, even ones that may not seem related (like analysis or numerical analysis).

I also believe that understanding abstract algebra is critical for many engineering roles (including circuit development, digital design, and programming). Things like permutations, recurrance functions, sets, fields, etc come up again and again - and one of the reasons why I have had a significantly easier time in engineering graduate school than other engineers is simple: I have had the rigorous background in mathematics, with an undergraduate degree and half a MS in applied mathematics (15 credits worth). The short segways into, say, field theory are familiar, even if I can't prove how to do x, y, or z with them... but the basics are there.

1. When do you think a Discrete Math course should be taken by computer science majors at the latest?

2. Should all Information Systems (IS, not MIS!) majors take discrete math?

3. Should Math Secondary Ed majors take it?

I'm pairing these three together because my answer is completely different than how things are now, and in this view, they would all take the course together.

In the world of undergraduate analysis, things are done completely differently - in a way that, to me, makes WAY more sense than the way abstract algebra/discrete math is handled. As an undergraduate maths major, you usually first take the calculus series, and then a course on how to do proofs, and then you take real analysis - a series that is essentially showing you the rigorous mathematical background behind those ideas you learned in calculus and proof creation.

In the world of abstract algebra, you're plopped right in the thick of it.

I believe that abstract algebra should likewise be split up into a discrete math course - which is truly an introduction to the ideas behind abstract algebra the way calculus is an introduction to the ideas behind analysis - and then a rigorous, senior-level course dealing with the proofs and requiring a linear algebra course first. Minimal proofs would be involved in the first one, and it would have real-world examples of the kinds of things you can do with abstract algebra.

In this fantasy world, EVERYONE (engineers, math majors, math sec ed majors, computer scientists) would take discrete math in addition to calculus. Then, only those that truly need it (primarily the math majors) would take the rigorous proof course in the mathematics department, and if there was information missing from that course for the purposes of CS, there could be a half semester or 1hr/wk class picking up the rest (perhaps going into more detail about graph theory).

I would go so far as to say that it should be taken no later than semester

2for math, math ed, and computer science majors and semester3by engineers.4. What topic or topics are absolutely essential in a first course in discrete math?

Set theory through groups.

Basic proofs, but nothing as rigorous as a real introductions to proofs course would be.

Cyclic groups, and associated major theorems.

Function tables (eg, A x B means ... A + B means ...) and their relationship to boolean logic. The function tables have a real name, but I can't think of it for the life of me.

Combinatorics.

An introduction to recurrance.

An introduction to generating functions.

5. What topics did you have in your first discrete math course, if any, that you could have done without?

I didn't take discrete math but abstract algebra ... so this isn't really applicable. But from what was said above, graph theory is really unnecessary.

ruakhcasecobtold me I should weigh in here, even though I know nothing about your school . . .1. I think Computer-Science majors should take Discrete Math in their third semester, if not before — there are just so many classes it's useful for, and it's a waste if they wait much past that. That said, depending on when people at your school tend to declare their majors, it might make sense to allow some leeway, and allow it to be taken in the fourth semester.

2. I have no idea, as I don't know what Information Systems means at your school.

3. I do think Math Secondary Ed majors should take it, as it's a fairly fundamental field of math, and a lot of high schools do offer it (often paired with Precalculus).

4. I think a bit of set theory (including functions and relations), boolean algebra, proof techniques (including Mathematical Induction), combinatorics/counting, and graph theory are all essential, though I don't think a rigorous grounding is necessarily needed for all of them (e.g., I don't think Discrete Math students need to understand that a graph is actually a particular kind of set).

5. Sorry, I took it so long ago that I don't really remember anymore. But the Discrete Math class where I am now devotes a huge chunk of the course to ML, which I'm not sure is a good idea; I think ML is great, but I'm not convinced it really helps the students learn Discrete Math. (Computer-Science majors will get the concepts of ML when they study Lisp, and Math majors don't need ML.)