## Computer Science Education

Discussions on everything related to the software, electronic, and mechanical components of information systems and instruments.

### Computer Science Education

I'd say more about applied computer science than computer engineering. And getting anything into the theory of computation would be quite, quite advanced for anyone not doing an undergraduate degree. I do agree with getting into specific algorithms though.

I guess my quarrel would be that, to expect someone to know what big O notation is and the theory behind why certain algorithms perform better than others is much too advanced, however learning at the very basic level how algorithms work would be great. My first year programming course in University could've been taught to grade 7 students.
smokeybob

### Re: Raspberry Pi

smokeybob wrote:I'd say more about applied computer science than computer engineering. And getting anything into the theory of computation would be quite, quite advanced for anyone not doing an undergraduate degree. I do agree with getting into specific algorithms though.

What do you consider theory of computation exactly? I mean I agree with you, I think, kids in high-school are not going to be ready to learn Myhill's isomorphism theorem or the arithmetical hierarchy.

But you can teach high school kids big O notation. I mean, my high school teacher did.

smokeybob wrote:I guess my quarrel would be that, to expect someone to know what big O notation is and the theory behind why certain algorithms perform better than others is much too advanced, however learning at the very basic level how algorithms work would be great. My first year programming course in University could've been taught to grade 7 students.

I disagree. Here's some stuff I saw in high school:

• We covered reaction rates in my AP chemistry class, and had to do a bunch of elementary calculations. In all honesty, understanding basic chemical kinematics at a high school level is no harder than understanding computational complexity.
• We covered Newton's method in my AP calculus class, showed it was a generalization of Heron's method for calculating square roots, and talked about quadratic convergence in general.

These things are standard to the AP curriculum, right?

And the rudiments of basic complexity theory are all there. Combined with a computer science course, it wouldn't make any sense not to teach it, since it connects nicely with everything else.

We could of course go much deeper in high school, but we don't, because American high school students aren't pushed very hard. As a point of comparison, I have some German friends I met in grad school who told me about learning Euler's method for solving differential equations in high school. It's rather tragic how low American expectations are...
xcthulhu

### Re: Raspberry Pi

Wow. Yeah I mean in high school we basically got integration through up until, not including, inverse trig. Newton's Method yes. Euler's - hell no. What mental steroids are the German kids on? haha

I guess if you take the time to dedicate, you can teach them which functions are actually faster than the others, big O can be fair game. I was just assuming that it'd be too much to know to derive Stirling's Approximation or to understand better methods of multiplying matrices or improving the performance of complex number multiplication. Permutation theory, infinite series representations... out of the question. Airthmetical hierarchy of course being out of the question. I'm looking through Wilf's textbook on Algorithm's and Complexity and beyond the bare, bare basics - you're stuck.

Yeah, I guess you could show them big O for different sort algorithms - get into things a little bit. But not much at all. Maybe tease their eager young minds.
smokeybob

### Re: Raspberry Pi

Personally, I think the biggest problem with high school students is that we don't challenge them. The kids will rise to the challenge IF we provide it. Instead, we patronise them and make them feel entitled to doing essentially nothing in their high school years. For so many reasons, I feel that I have missed out on a lot in life by being given an American education in my pre-college years.
linford86

### Re: Raspberry Pi

smokeybob wrote:Yeah, I guess you could show them big O for different sort algorithms - get into things a little bit. But not much at all. Maybe tease their eager young minds.

Well, that's all my high school teacher did - he had us write bubble sort, merge sort, quick sort and raddix sort and had us see how the differences, and taught us basic big O notation. But that's comparable to the depth I got in my AP chemistry class or AP calculus. Kids won't learn chemical kinematics in high school to much depth. But they aren't to be ready for developing analysis from the axioms of a real closed field, either.

So: what would you put in your high school curriculum for computer science?
xcthulhu

### Re: Raspberry Pi

Oh I agree wholeheartedly. Imagine, I never knew about things like the Goldbach or Twin Primes conjecture until university, having not had a math teacher who ever cared to push the limits.

Even Fermat's last theorem - hearing about how Wiles read it as a 10 year old... I'm sitting here going "lucky... I just heard about it 3 years ago".

I really like Lockhart's Lament, which I'm sure you've read. If only math could be put into better chunks of "look how easy this actually is" and the never-ending creativity of kids actually used to push the frontiers? There was an episode of ST:TNG in which a 12-year-old was having problems with his calculus homework and mentioned it to Picard (I believe). If only somebody'd taught me that shit at 12.
smokeybob

### Re: Computer Science Education

xcthulhu wrote:So: what would you put in your high school curriculum for computer science?
In high school, we actually had programming classes. It was in Pascal and Visual Basic - one class for each. I felt they were the most brutal classes ever. Visual basic was too old, even at that time, and didn't have _much_ practical application.

In high school, I see no problem jumping right in to C, C++ or C#. It's going to be the most useful down the road as a general purpose "here's what's out there". C for the non-object oriented, but still gives a lot of complexity, dealing with variables in different parts of memory; C++ for the object oriented where you can really see some power in the languages.

For me it's a fine balance - a balance between being able to program something practical, and being able to understand how computers work in principle. Considering I took my computer architecture course from my TA in a 2 hour review session, I think that an overview is absolutely do-able, so that it's known that the computer runs on clock cycles with limited bus widths, fixed timing to perform certain operations; which memory is fast and slow, etc. So learning this stuff can be done in high school - but do you really just want to get kids to have the skills to think about how programs are run, and build algorithms and test them out?
smokeybob

### Re: Computer Science Education

smokeybob wrote:
xcthulhu wrote:So: what would you put in your high school curriculum for computer science?
In high school, we actually had programming classes. It was in Pascal and Visual Basic - one class for each. I felt they were the most brutal classes ever. Visual basic was too old, even at that time, and didn't have _much_ practical application.

In high school, I see no problem jumping right in to C, C++ or C#. It's going to be the most useful down the road as a general purpose "here's what's out there". C for the non-object oriented, but still gives a lot of complexity, dealing with variables in different parts of memory; C++ for the object oriented where you can really see some power in the languages.

I took C in high school, along with Unix on an antique SunOS machine (I'm not that old, our school was just a little ghetto this way). These classes were electives -- it was tough but I loved that stuff.

Anyway, while I agree with you about C, C++ is awful. Here's post I wrote articulating its design flaws (which are deep and numerous): http://www.sciencechatforum.com/viewtop ... 92#p174558

Also, you can do object oriented programming in C, although it's a bit subtle. Linux device driver hacking is the best example of the practice if you are familiar with it. But I think that if you want to teach kids to do proper object oriented programming they should just start with Python (this is the first language in MIT and CMU's freshman curricula now). Python has many other virtues that make it an excellent choice.

smokeybob wrote:For me it's a fine balance - a balance between being able to program something practical, and being able to understand how computers work in principle. Considering I took my computer architecture course from my TA in a 2 hour review session, I think that an overview is absolutely do-able, so that it's known that the computer runs on clock cycles with limited bus widths, fixed timing to perform certain operations; which memory is fast and slow, etc. So learning this stuff can be done in high school - but do you really just want to get kids to have the skills to think about how programs are run, and build algorithms and test them out?

I learned a lot of that stuff in high school, because it's natural to learn if you study C.

But times are changing. CUDA/OpenCL are already making people rethink single instruction-per-cycle computation (FPGA hacking even more so, although it's less common). Even if you don't buy into that hype, note that your computer probably has 2 or more cores in it, which is a growing number, and you have got to admit that concurrency will escalate in importance in the future.

Now, I happen to be part of a modern Pythagorean-type cult of Haskell fanatics. I feel there's a lot of good philosophy to be taken from this community - if you are trained to program/think abstractly to begin with then you have less to fear from fundamental architecture sea changes. A program is ideally a purely mathematical object, defined by its behavior rather than it's implementation. Maybe try catching Simon Peyton Jones' talks if you aren't already a convert.

You might object and say "That kind of programming is too abstract for kids to learn in high school!"... but I have my doubts. After all, everyone learns calculus in high school and never bothers with Cauchy sequences or Dedekind cuts or the other tedious model theory of the real numbers. If we don't worry about implementation details all that much in regular math classes, then why should we worry in high school programming? [And the truth is that if they're teaching JAVA, which many do, then they already decided not to care a long time ago]
xcthulhu

### Re: Computer Science Education

xcthulhu wrote:if you are trained to program/think abstractly to begin with then you have less to fear from fundamental architecture sea changes. A program is ideally a purely mathematical object, defined by its behavior rather than it's implementation....You might object and say "That kind of programming is too abstract for kids to learn in high school!"... but I have my doubts.

I would object, but on entirely different grounds.

For instance, I think this slashdot post summarizes how I feel about programming as a "purely mathematical object":

Some random dude on Slashdot wrote:A bit off topic, but you triggered something I've been thinking about for a couple of years. That "spark" is fluency.

I swtiched jobs from being a computer programmer to being an ESL teacher in Japan. Japan is somewhat famous for churning out students who know a lot *about* English, but can't order a drink at Mac Donald's. We used to have a name for those kinds of people with regard to programming languages: language laywers. They can answer any question you put to them *about* a programming language, but couldn't program to save their life. These people often make it past job interviews easily, but then turn out to be huge disappointments when they actually get down to work. I've read a lot about this problem, but the more I look at it, the more I realise that these disabled programmers are just like my students. They have a vocabulary of 5000 words, know every grammar rule in the book but just can't speak.

My current theory is that programming is quite literally writing. The vast majority of programming is not conceptually difficult (contrary to what a lot of people would have you believe). We only make it difficult because we suck at writing. The vast majority of programmers aren't fluent, and don't even have a desire to be fluent. They don't read other people's code. They don't recognise or use idioms. They don't think *in the programming language*. Most code sucks because we have the fluency equivalent of 3 year olds trying to write a novel. And so our programs are needlessly complex.

Those programmers with a "spark" are programmers who have an innate talent for the language. Or they are people who have read and read and read code. Or both. We teach programming wrong. We teach it the way Japanese teachers have been teaching English. We teach about programming and expect that students will spontaneously learn to write from this collection of facts.

In language acquisition there is a hypothesis called the "Input Hypothesis". It states that *all* language acquisition comes from "comprehensible input". That is, if you hear or read language that you can understand based on what you already know and from context, you will acquire it. Explanation does not help you acquire language. I believe the same is true of programming. We should be immersing students in good code. We should be burying them in idiom after idiom after idiom, allowing them to acquire the ability to program without explanation.

I think a perfect example of this would be my response to some posted code in a previous thread--there is a lot of trashy code out there that is "mathematically" correct and completely shitty all at the same time. You write it in a manner that isn't idiotic, and suddenly everything's just so much more clear.

In many respects, I think programming is more like writing a good essay than solving a math problem--there's a dozen different ways to write it, and most of the methods have various tradeoffs and considerations with regard to efficiency, readability, brevity, maintainability and so forth. Most of this falls under the general rubric of "fluency." You can't take a class that shows you how to write a good essay or be a good writer; you just have to write (and read!) enough before you really understand your target audience and the proper use of your various literary devices. I think the same applies to programming.

kidjan
Active Member

Posts: 1921
Joined: 25 Jul 2007
Location: Earth.

### Re: Computer Science Education

kidjan wrote:
xcthulhu wrote:if you are trained to program/think abstractly to begin with then you have less to fear from fundamental architecture sea changes. A program is ideally a purely mathematical object, defined by its behavior rather than it's implementation....You might object and say "That kind of programming is too abstract for kids to learn in high school!"... but I have my doubts.

I would object, but on entirely different grounds.

TL;DR: I agree with you on all of your points - I think you've misunderstood me.

Well... I don't see the below as a really an objection, because I think you have a misconception of what I am talking about when I talk about mathematics.

When I say that a "computer program is like a mathematical object" - I mean it is like a mathematical proof. Formally this is reflected in Curry Howard Isomorphism, which asserts that the programs one can write in the pure typed lambda calculus (ie, baby Haskell) correspond exactly to proofs in the implicational fragment of intuitionistic logic. But that's just theory of course, and these results end quickly as you leave toy sublanguages of OCaml and Haskell - still, I believe in the metaphor.

Writing a mathematical proof is exactly the same as writing an essay - a "good" mathematical proof is pithy, parsimonious, easy-to-read, bullet-proof, and elegant.

kidjan wrote:For instance, I think this slashdot post summarizes how I feel about programming as a "purely mathematical object":

lol. I saw that, except I noticed it when it made it to reddit.com/r/programming/ first. Slashdot = ~1 day old reddit posts

kidjan wrote:In many respects, I think programming is more like writing a good essay than solving a math problem--there's a dozen different ways to write it, and most of the methods have various tradeoffs and considerations with regard to efficiency, readability, brevity, maintainability and so forth. Most of this falls under the general rubric of "fluency." You can't take a class that shows you how to write a good essay or be a good writer; you just have to write (and read!) enough before you really understand your target audience and the proper use of your various literary devices. I think the same applies to programming.

Well... I agree, in part. I think back to my favorite professors and they did teach me how to prove theorems effectively. Certainly, when you are being graded on your proofs, you tend to be graded on your efficiency, readability, and brevity. Maintainability not-so-much -- the fact that software writing is a group based engineering effort is part of where the metaphor starts to break down (the other part is the fact that pure mathematics indulges in trickery such as axiom of choice, infinitary complete metric spaces and other non-constructive trickery which can't be implemented in silicon).

You can also learn by being a TA, and getting your nose rubbed in everyone's else's mistakes. One could do the same with software although I think it's rare - my high school teacher, who I suppose was the best programming teacher I ever had, made the students who completed his exercises the quickest then go around and debug everyone else's code. My high school English teacher did the same thing, sort of, only we had to proof read other people's essays (and then she graded our proof-reading).

So in summary, I really do agree with you that programming is like essay writing. But I think that theorem proving is like that, too. I have attached Proofs from the Book for you to glance at to get a sense of what I am talking about.

----------------------

Now, you deserve an explanation of what I really meant in my post, which I haven't said. Maybe I'll post later on this. But as a hint, training students to think in terms of pure functions versus IO monads or monadic side-effects in general ultimately helps to abstract away from details like whether they are in sequential architectures to concurrent ones. That's what I mean by "programs are mathematical objects"...
xcthulhu

### Re: Computer Science Education

No, I understood you precisely. I still disagree.

Programming is not--in my opinion--a purely mathematical endeavor. Some facets of it are. But a huge amount of programming is A) understanding the problem you're trying to solve and B) writing an effective solution to solve that problem. For large programs, overall architecture is as important--if not more so--than some of the nuances of individual algorithms. For example, a program that bases itself around an incorrect data structure will manifest that error throughout the entire codebase. A program that bases itself around the correct data structure, or uses the correct model/design pattern--will not.

This may not be clear, so maybe at some point I'll try to clarify, but the bottom line is there are hundreds of ways to write any program out there. The real trick is writing it in a way that really addresses the problem at hand, in a method that naturally grows as the problem evolves.

kidjan
Active Member

Posts: 1921
Joined: 25 Jul 2007
Location: Earth.

### Re: Computer Science Education

kidjan wrote:Programming is not--in my opinion--a purely mathematical endeavor. Some facets of it are. But a huge amount of programming is A) understanding the problem you're trying to solve and B) writing an effective solution to solve that problem. For large programs, overall architecture is as important--if not more so--than some of the nuances of individual algorithms. For example, a program that bases itself around an incorrect data structure will manifest that error throughout the entire codebase. A program that bases itself around the correct data structure, or uses the correct model/design pattern--will not.

Well... I'll cling to my analogy, and try to show you how design considerations emerge in mathematics.

Take Bourbaki's classic Elements of Sets. In this the Bourbaki invent their own formalism for representing natural numbers. They estimated that to represent the number "1" in fully expanded form, it would take several thousand digits. Now, skipping to the 21st century, one logician heard this and thought "That can't be right! Surely it only takes a couple hundred!" So the logician sat down and did a careful calculation of how many glyphs were actually necessary. It's over 4 trillion.[1]

In ZF set theory, 1 is represented by $\{\emptyset\}$ using von Neumann's/Frege's formalism. So, a mere 3 glyphs. The representation still grows with O(n2) glyphs for the number n, but it's nice in other ways which make it convenient to prove and extend numbers. Bourbaki's formalism was ultimately an impedement, because their representations of numbers (ie, fundamental data structures) was garbage.

Another example is Richard Feynman's approach to QM: legend has it that using his path integral formulation of quantum mechanics, Feynman was able to solve in one evening a problem that had been vexing his colleagues, who had been using a hodge-podge of Taylor expansions and operator theory in Hilbert spaces, months to solve. This is in Surely You're Joking, Mr. Feynman.

If you want a nice historical overview of how mathematicians struggled with representations, you might try reading A Radical Approach to Real Analysis, which tries to teach the subject from an historical perspective. Proofs in 19th century were often loaded with special assumptions and were not proven in full generality. Likewise, there was fundamental ambiguity over the definitions of the real numbers (Cauchy Sequences or Dedekind cuts?), the definition of a function (which was historically just thought be be an expression), and the fallacy that every function can be uniquely identified by its Taylor series expansion.

kidjan wrote:This may not be clear, so maybe at some point I'll try to clarify, but the bottom line is there are hundreds of ways to write any program out there. The real trick is writing it in a way that really addresses the problem at hand, in a method that naturally grows as the problem evolves.

There's hundreds of ways to formulate mathematics and solve problems in that field. And "the real trick" to formulating mathematics is the same for mathematicians and for programmers.
_________________________
[1] A. Mathias, A term of length 4,523,659,424,929, Synthese (2002)
xcthulhu

### Re: Computer Science Education

Okay, but by that same token, you could basically say programming is a "written" endeavor, since all of what you stated above still applies (i.e. would Crime and Punishment have been better written in English? Could Dostoyevsky have conveyed his ideas more succinctly?).

In other words, I see your point, but I think it's a narrow field of view to ascribe it as a purely mathematical endeavor.

kidjan
Active Member

Posts: 1921
Joined: 25 Jul 2007
Location: Earth.

### Who is online

Users browsing this forum: Google [Bot] and 4 guests