?

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

( 22 comments — Leave a comment )
casecob
Mar. 3rd, 2006 03:41 am (UTC)
do you mean like induction, set theory, formal concept analysis, and the like?
banazir
Mar. 3rd, 2006 04:22 am (UTC)
All of the above
Yes, just so.

--
Banazir
casecob
Mar. 3rd, 2006 11:59 am (UTC)
Re: All of the above
ahh, and a classic project - implementation of the RSA algorithm with SML.

does it count if I vote for these things as a biology major (CS minor)?
mapjunkie
Mar. 3rd, 2006 03:19 pm (UTC)
Re: All of the above
for a first class on discrete math they should implement RSA in SML?

that sounds rather severe...
casecob
Mar. 3rd, 2006 03:22 pm (UTC)
Re: All of the above
hehehe - that's what we do at Case ;)

It wasn't so bad.

Implementing the AKS algorithm to solve for primes in polynomial time was a OVERLY severe - especially because it still hasn't been done!!!

Really though, it wasn't so bad.
mapjunkie
Mar. 3rd, 2006 03:30 pm (UTC)
Re: All of the above
Are you sure we are talking about the same class? Not intro to data structures, but the class before that, the one that doesn't even have a programming requirement?
casecob
Mar. 3rd, 2006 06:29 pm (UTC)
Re: All of the above
Truth be told - I didn't recall.

Here's the course description for our Discrete Math:
A general introduction to basic mathematical terminology and the techniques of abstract mathematics in the context of discrete mathematics. Topics introduced are mathematical reasoning, Boolean connectives, deduction, mathematical induction, sets, functions and relations, algorithms, graphs, combinatorial reasoning. Prereq: MATH 122 or MATH 126.

The only listed pre-reqs are calc 2.

Thing is - the only people who take it are CS majors (generally) and most have had that kind of programming. I think, also, that the function to find the inverse modulus of a number was provided by our instructor. But yeah, I mean, from what I gather, we're discussing the same class.
mapjunkie
Mar. 3rd, 2006 07:53 pm (UTC)
Re: All of the above
In that case, that's mad hardcorez!!!
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?
mapjunkie
Mar. 3rd, 2006 03:29 pm (UTC)
Proof techniques (to be used throughout)
Induction (in tandem with "proof by induction")
Recursive definition (in tandem with "induction")
Logic (in tandem with learning "proof by contradiction")
Basic Set Theory (following from logic and recursive definition)
Mathematical notiation (following from set notation; summation and the like work well with similar notation from sets; might also be taught as part of induction)
Functions, their notations, and their terminology (isomorphism, image, pre-image, etc.)
Combinitorics and counting arguments
Graphs
Trees (in tandem with the tree definition in graphs)
mapjunkie
Mar. 3rd, 2006 03:31 pm (UTC)
Oh, and of course asymptotic notations and definitions, including O,o,Omega,omega,Theta
banazir
Mar. 7th, 2006 12:22 pm (UTC)
Asymptotic analysis
Absolutely. I think in the first year or two, basic analysis of algorithms is many times more important for a CS major, or for a mathematical computing or statistical computing person, than covering fundamentals of real and complex analysis.

Being able to do fancy things with limits and abstract algebra, even number theory beyond modulo arithmetic, relative primaility, and concepts such as the Sieve of Eratosthenes for finding primes, can wait, IMO. A math major might learn it at the same time; but even she doesn't have to have it before understanding the most basic things about analyzing and dissecting algorithms to comprehend how to prove them correct and characterize their running time in a formal way.

--
Banazir
banazir
Mar. 7th, 2006 12:05 pm (UTC)
Discrete math curricula: thanks for the list
Here is an explanation for my query. I'll follow up in a couple of days.

Thanks again,
Banazir
mapjunkie
Mar. 7th, 2006 02:31 pm (UTC)
Re: Discrete math curricula: thanks for the list
Glad to help.

My list is informed by two factors.

1 By my first discrete math class, which I loved (was taught by Jeff Erickson, who rocks the house down), and found excessively helpful.

2. There is something to be said for being exposed to notations and diagramatic techniques, that what you are trying to do in this class is give them the ability to read these kinds of materials. Just the notations of combinitorics, and then showing how the arguement "selecting a president, and then selecting 4 more for the executive committee can be done in the same number of ways as selecting 5 executives, and then a president from among them" is written, is something rather helpful. I know that likely the largest trouble I had in math classes (but not in CS, due to my introduction) was that I learned to think about the ideas, but in my own terminology, and then I had impedence mismatches later.

mapjunkie
Mar. 7th, 2006 11:16 pm (UTC)
Re: Discrete math curricula: thanks for the list
gregbo
Mar. 4th, 2006 07:53 am (UTC)
Hmmm ... I'm not sure that specific topics should be covered, as much as general approaches to solving discrete math problems.
banazir
Mar. 7th, 2006 12:14 pm (UTC)
Proof, problem solving, and programming techniques - YES!
Oh, yes. At Hopkins we had a course 600.140 (Programming Techniques) between 600.108 (Intro to Programming in Pascal, later C++) and 600.327 (Data Structures, later 600.227). It was taught using Abelson, Sussman, and Sussman (first edition at the time), and often taken concurrently with 600.118 (Intermediate Programming in a Unix Environment).

So you see, we had two programming-intensive courses between CS1 and Data Structures. IMO this is a good thing. I actually took a third one (600.119 IIRC, Intermediate Programming in C++) as senior, because I didn't know C++. My advisor, Steve Salzberg (who later became Ventner's hire as bioinformatics director of TIGR and one of the HGP principals), said I'd be bored. I got together with three of my classmates - two seniors and one sophomore (Jeremy Elson, author of CircleMUD) - and we made it our capstone project in software engineering (we didn't have an official one at the time, so it was craft-your-own-program in a sort of liberal arts style after 2 years). I wasn't the least bit bored.

Here is an explanation for why I asked. At K-State we go from CS1 (CIS 200) to Data Structures (CIS 300) and Logic for Computer Science (CIS 301). The theoretical foundation is firm, or would be, if there was a programming-inetnsive foundation to go with it.

I'll follow up in a couple of days.

Thanks for your cogent comment,
Banazir
bojojoti
Mar. 4th, 2006 10:26 pm (UTC)
Hello! Just popped in from a link from a friend of a friend. I definitely have nothing to say concerning discrete mathematical structures, as my math skills are exceptionally discreet!

However, I really enjoyed your wibbles on my favorite shows on Friday night. May I friend you?
banazir
Mar. 7th, 2006 11:48 am (UTC)
Hail and well met (spoilers for latest BSG)
Oh, certainly, be my guest. I've added you back.

Sorry I haven't responded - things have been hectic.
I do watch Sci-Fi Friday every week, but sometimes it takes me 3-4 days to get up-to-date.

Huh, and I just remembered that I forgot to tape the rerun of BSG. I was about 20 minutes short (2:40 instead of 3:00) and missed taping the ending. I saw that Kara met up with Anders again, and that Baltar managed to score some points on Roslin, but what happened at the very end?

--
Banazir
bojojoti
Mar. 11th, 2006 07:42 am (UTC)
Re: Hail and well met (spoilers for latest BSG)
Roslin's people rigged the election, but the fraud was uncovered. Adama urged Roslin to allow the democratic process to go forward, and Baltar was elected President. As Baltar is being sworn in, the blonde cylon who'd been tortured blew up a nuclear device vaporizing Cloud Nine.

After this, a colony was established on New Caprica. Only the military remained on the ships. A year passes, and the Cylon fleet returns in full force. The cylons were drawn to New Caprica because of the radiation left by the nuclear bomb. Adama orders the ships to jump, and they leave the colonists on their own. Baltar surrenders the colony.

BSG always keeps me guessing.

(Deleted comment)
banazir
Mar. 7th, 2006 12:24 pm (UTC)
Discrete math basic syllabus - very good
Here is an explanation for why I asked, with additional commentary here and here. I'll summarize this thread and the rationale for my suggested improvements within a few days.

Thanks again,
Banazir
( 22 comments — Leave a comment )

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