?

Log in

No account? Create an account

Previous Entry | Next Entry

To anyone who has, or is earning, a degree in computer science:
What do you think is the bare minimum of topics that should be covered in a first course on discrete math or discrete mathematical structures?
Please list 3-10 topics, as specific or as as general as you like.

In other news: Today is the two-year anniversary of my GreatestJournal and the three-year anniversary of my LiveJournal.

Highlights, 27 Feb 2003 - 26 Feb 2004
(When I have more time, I will put 2004 and 2005 highlights here.)

--
Banazir

Comments

banazir
Mar. 7th, 2006 12:04 pm (UTC)
Discrete mathematical structures - sounds good...
... though perhaps a bit shallow? How much in the way of algorithms and deduction can you actually cover in a semester? Or is it just propositional (modus ponens, modus tollens, contrapositive) and "the flavor" of first-order (i.e., quantifiers, but no model theory, possible worlds semantics, resolution, sequent rules for FOPC, etc.)?

Graph theory and graph algorithms are easily semester-long courses by themselves, while the definitions and basic properties of graphs can be covered in 2-3 weeks.

What is meant by "mathematical reasoning" and "combinatorial reasoning"? Any particular proof methodology or counting techniques?

Here's why I asked this question: our discrete mathematical structures course is Math 510. Technically, this is an "upper division course" required for graduation, not a tech elective, but it is taught like a tech elective: combinatorics, generating functions, even a little modern algebra (abstract algebra: rings, fields, groups). It's supposed to be a second-year course, but no one does, and the Math department doesn't even let sophomores register for it unless there is no waiting list (which ther always is). We have students who take it in the senior year.

This has been nothing short of disastrous for our upper-level curriculum: we have people coming into the relational databases course, the AI course, and the programming languages courses without a clear understanding of one-to-one/onto/bijective functions, the definitions of relations and functions, and fundamental axiomatic set theory. The very important nuances of propositional logic as it relates to the algebra of sets are lost on many.

As a result, I've proposed that we reform the curriculum to make Discrete Mathematical Structures into a lower-level course, say Math 310, and require it by the fourth semester at the latest. A sharp first-year student with sophomore standing should be able to take it in the spring (second semester) and earn an 'A'. Nobody should be able to register for Database Systems or Intro AI without it, much less Analysis of Algorithms (which I think requires it). I'm going to recommend that it become our gateway math course, named as a prerequisite for CIS 505 (our intro programming languages course) and CIS 570 (our automata theory and formal languages course) and perhaps for other courses, too.

Thanks,
Banazir
casecob
Mar. 7th, 2006 12:29 pm (UTC)
Re: Discrete mathematical structures - sounds good...
I guess I should qualify - the course description sounds a lot loftier than what we did in that class, imvho (just that RSA in SML was one of those tasks we needed to do)

Q: How much in the way of algorithms and deduction can you actually cover in a semester?
A: Not very much. Not very much at all. This class is the pre-req for our algorithms course though, so we had a brief exposure. Actually, I think all we did was use induction to show that one algorithm was equivalent to another (they were coded in SML). As for deduction, I'm not sure we spent much time on it either.

Q: What is meant by "mathematical reasoning" and "combinatorial reasoning"?
A: Proof by induction, contradiction, etc. Also, the pidgeon-hole principle. As for proof methodology or counting techniques - I can't think of anything that stuck out. I took this class 2 years ago (and hated it, but alas, I took it).

So, you have seniors taking this? This class is required for CS students, if they want to stay on track to graduate in 4 years then they take this class no later than the fall of their jr. year. Otherwise they cannot take algorithms and all the courses with algorithms as a pre-req. Algorithms, much to my dismay, is a fall-only course (i'd planned on taking it now, but instead, i'm taking systems programming because the course is unavailable.)

Tell me: what does a bioinformatician need to know of linking loaders?

Latest Month

December 2008
S M T W T F S
 123456
78910111213
14151617181920
21222324252627
28293031   

KSU Genetic and Evolutionary Computation (GEC) Lab

Teunciness

Breakfast

Science, Technology, Engineering, Math (STEM) Communities

Fresh Pages

Tags

Powered by LiveJournal.com
Designed by Naoto Kishi