Morning wibble: 
zengeneral sent me an IM last night asking for problems that "tickle" students' interest. By this, as I later learned, he meant foundational topic areas in CS for algorithm analysis and design, software engineering methodology, and mathematical problem solving as applied to CS.
This morning, therefore, I created a new section on one of my office whiteboards: The KDD Tickle Spot.
Topics he suggested, and that came out:
ETA, 12:55 CDT Sat 30 Oct 2004: I should mention that whatzengeneral calls "ticklish" and what I consider an interesting current topic of research do not necessarily coincide. As you can see from the above, zengeneral is looking at methodologies of proof and algorithm (and equation) derivation. It's the "showcase of problems" (including open ones such as "P == NP?") that are good for drawing and holding the attention of beginning CS students, he asserts.
Our department (Computing and Information Sciences at Kansas State University) is hosting its Alumni Advisory Council this homecoming week. Class is therefore relocated to the library (Nichols 233) - I hope you see this before 15:30,masaga, megruder, and zengeneral, and before 16:30, istari_ala.
Edit, 12:45 CDT: And now I realize that I am using LJ instead of verbal speech to announce meeting venue changes. Gah!zengeneral is sitting right in front of me and asked where the meeting is. Oops.
Later (c. 17:30), we will be giving a demo on our
bayesnets software package, Bayesian Network tools in Java (BNJ) v3.
--
Banazir
zengeneral sent me an IM last night asking for problems that "tickle" students' interest. By this, as I later learned, he meant foundational topic areas in CS for algorithm analysis and design, software engineering methodology, and mathematical problem solving as applied to CS.This morning, therefore, I created a new section on one of my office whiteboards: The KDD Tickle Spot.
- Computational Learning Theory (COLT): particularly computational geometry and information retrieval and extraction (IR/IE)
- Dynamic Decision Networks (DDNs) for Reinforcement Learning (RL): market driven policy learning
- Technique Selection in Critiquing-Based Tutoring: secondary and tertiary math education - formal rewrite systems for error diagnosis in algebra, plane geometry, precalculus (analytic geometry and trigonometry), calculus (AP Calc AB and BC or Calc I and II), vector analysis ("Calc III"), differential equations and linear algebra
- RoboSim Applications: partially-observable Markov Decision Processes (POMDPs) and procedural representations
- Probabilistic Relational Models for clustering: class identification and concept discovery - intra-configuration and inter-configuration in NSF ITR project
- Graphics models and kernel methods for time series learning (bioinformatics)
Topics he suggested, and that came out:
- Fundamental topics: e.g., entropy (data compression, learning, etc.)
- Computability and complexity theory: reductions for semidecidable (recursive enumerable but not recursive) and undecidable (non-recursive enumerable), and NP-hard, decision problems - namely, how to do them
- Proof patterns: diagonalization, structural induction, the "black art" of widget design (see above)
- Understanding solution approaches: cf. Polya's How To Solve It
- Recognizing algorithm patterns: divide-and-conquer (synthetic use of the Master Theorem), greedy, "radix sort"-type cleverness, approximation
- Applying algorithm patterns: analytical use of the Master Theorem, amortized, expected case, confidence (delta), error (epsilon), and ratio (rho) bounds
- Factoring methods: modularity by design, cohesion by systematic analysis of control structure boundaries and functional interfaces
ETA, 12:55 CDT Sat 30 Oct 2004: I should mention that what
zengeneral calls "ticklish" and what I consider an interesting current topic of research do not necessarily coincide. As you can see from the above, zengeneral is looking at methodologies of proof and algorithm (and equation) derivation. It's the "showcase of problems" (including open ones such as "P == NP?") that are good for drawing and holding the attention of beginning CS students, he asserts.Our department (Computing and Information Sciences at Kansas State University) is hosting its Alumni Advisory Council this homecoming week. Class is therefore relocated to the library (Nichols 233) - I hope you see this before 15:30,
masaga, megruder, and zengeneral, and before 16:30, istari_ala.Edit, 12:45 CDT: And now I realize that I am using LJ instead of verbal speech to announce meeting venue changes. Gah!
zengeneral is sitting right in front of me and asked where the meeting is. Oops.Later (c. 17:30), we will be giving a demo on our
bayesnets software package, Bayesian Network tools in Java (BNJ) v3.zengeneral: Privacy? What's that? All hail Patriot Act!
banazir: Verbal speech? What's that? All hail ascetic hermitage!--
Banazir
- Current Mood:
creative
Profile
- banazir
- Banazîr the Jedi Hobbit
- Unusual Nut-Case Lays of Ea (U.N.C.L.E.): Tolkien Humor
Comments
--
Banazir
Question (I should know this, but I admit, I don't): are Perl regexps the same as UNIX regexps? i.e., not really regular?
--
Banazir
And UNIX regular expressions are not really regular because... I just don't see this one, that is, I don't see why UNIX regular expressions are not regular... but would like to know why...
Truthfully, I'm not so sure what you mean by "not really regular". As far as I can tell, Perl regular expressions are very similar to sed and awk, but I generally have to google for tutorials if I want to do something fancy with those two tools.
BTW, I friended you. You can friend me also if you wish. Also, is it ok to post discussions about CS education in
Welcome!
CS education discussions in
I believe Perl's regexps are a superset of Unix's, which are a superset of the regexps you learn in CS theory that are equivalent to finite automata.
Yes, I'm pretty sure this is what Rod Howell meant when he said it.
--
Banazir
hmmmm... well, first of all, I would like to clarify a few things here. The set of problems above named semidecidable, are actually known as undecidable. Although I also like the term semidecidable, because it actually reflects the fact that they have decidable regions, the literature usually names them undecidable. That being said, in the set of decision problems known as RE, the RE actually stands for Recursively Enumerable, not Recursive Enumerable. I might seem to be too picky in noting this, but in fact the meaning conveyed the expression "Recursive Enumerable" is totally different to what the Recursively Enumerable decision problems are.
Secondly, reduction techniques for undecidable problems are not that exciting or tickling. To begin with, Rice's theorem tells us that any non-trivial decision problem for Turing Machines is undecidable (the latter expression is an abuse of terminology, but is used for the sake of clarity). So, all you need to show is that a problem is non-trivial and that's it, you get it for free. What is a non-trivial problem? This is the best part :-) Basically, any predicate that does not accept all turing machines, or reject all of them, defines a non-trivial decision problem. So, the question "is this a program?" is a trivial problem because the set of all programs that satisfies that property is actually, the set of all programs :-) But, as long as there is some discrimination, you're screwed: the problem is undecidable.
As far as patterns go, the most widely used pattern to show that a problem is undecidable, is the reduction to the halting problem. So for example, for programs, the template goes like:
statement1;
possiblyDivergingStatement;
statement2;
where possiblyDivergingStatement is a statement that might or not terminate. statement2 usually will make some computation that will determine whether or not your program has the property in question. So the reasoning is as follows: "If possiblyDivergingStatement terminates, then statement2 is reached, and the property holds. If possiblyDivergingStatement runs and doesn't return, then statement2 is never reached, and the property doesn't hold, but we can't be sure of that, because we don't know whether possiblyDivergingStatement will return in the next instant". There are other patterns, but this one usually works quite fine. In general, a proof that some property is undecidable is not even considered interesting because of what I mentioned before. I can tell whether a problem is undecidable without even have to make any proof...