3 ms·

Nobody is talking about "infinite time" algorithms; complexity theory concerns itself with what is efficiently computable. This might not directly correspond to

Nobody is talking about "infinite time" algorithms; complexity theory concerns itself with what is efficiently computable. This might not directly correspond to "real-world" efficiency, because an algorithm, while polynomial-time, but have poor constants or a huge polynomial. However, this does not mean complexity theory is useless; it still informs us of what computers can and cannot efficiently do. It marks the limits of feasible computation. > I don't know where an uncomputable algorithm would be useful. Complexity theory also does not concern itself with uncomputable algorithms, so that point is irrelevant. As you say, starting off students with abstract theory doesn't help, because they're unlikely to use it and so it won't stick. However, the same argument goes for your "bottom-up" approach; most students of computer science will not ever have to twiddle bits and manipulate assembly; knowledge of this material would thus be quickly forgotten. My point, as stated in another comment of mine in this thread, is that it is not necessary that a "true computer scientist" know anything about low-level computer details. I suspect this holds true not only for theoreticians, but also many systems builders (like in distributed systems and such). So, having a intro course focusing on low-level details as the main component will not necessarily provide a good introduction to computer science.

gravypod 10y ago
> Complexity theory also does not concern itself with uncomputable algorithms, so that point is irrelevant. I do not think this is a correct statement from what I've seen. > As you say, starting off students with abstract theory doesn't help, because they're unlikely to use it and so it won't stick. However, the same argument goes for your "bottom-up" approach; most students of computer science will not ever have to twiddle bits and manipulate assembly; knowledge of this material would thus be quickly forgotten. If the course is organized correctly the experiance can be magical. You're pulling the curtian on the the giant talking head. You're showing the students how everything works and you should do this directly. Like all teaching the student needs to THINK they have been the ones to discover something while in reality the teacher is supposed to have errected an artificial situation where in this was the case. You don't start them off with bits right off the bat although that is one approche (That is extremely successful: see NAND 2 Tetris). Like I said in my other comment you state them off with a broken machine. You give them an artifical reason to continue. "If you want to get a grade you have to open up this machine and, with me coupled with some hand holding, diagnose the problem." That gives them a reason to learn about the different parts of the computer. That errects a situation where they FEEL that have found something that they weren't meant to. They've explored something when in reality it was all, as someone smarter then me once said, a "Head Fake". Get them looking at a nearer goal and they'll start dreaming of further ones.
- Ar-Curunir 10y ago
  But is the point of your course computer science, or computer engineering. I don't think I'm particularly special, but I have taken just the one computer architecture course as an undergrad (and I don't remember much if any of what I learnt), and now I just completed the first sem of my PhD in computer science. I haven't used the information I learnt in that class yet, even though I'm in a partially applied field (security and cryptography). All I'm pushing back is on the idea that learning the intricacies of modern computing is necessary for being good at computer science. EDIT: And wrt complexity theory and computability: there is a subfield of mathematics called computability theory that concerns itself with various notions of what is and isn't computable. Complexity theory concerns itself instead with what is efficiently computable; the problems it considers are already computable.
  - gravypod 10y ago
    Well you're not going to like when I say this. Cryptography isn't Computer Science. It uses some things that Computer Science developed but it isn't Computer Science. It's applied Math. If Cryptography is in CS then Nuclear Reactor Operations is in CS. NRO uses computers for monitoring systems and develops algorithms to detect certian... ahm... undesierable states. That doesn't mean we should move a reactor into the CS building at every college near you (although I'd love to work on one eventually, sounds like cool work). Academics may think that crypto is a CS field but the work involved has absolutly nothing to do with CS. For example, all cryptographic functions can be implemented in hardware. If you are building a cryptographic function in hardware, you're not part of the Electical Engineering department or the Mechanical Engineering department you are still in the Math department because all you're doing is implementing an abstract design. (Insert unintelegable "get off my lawn" statement)
    - Ar-Curunir 10y ago
      ... what? I am not sure what your idea aof cryptography is, but crypto relates to the most basic of questions about computation: what is and isn't efficiently computable, that is, P ?= NP. You do realise that the origin of the field of Computer Science lies in mathematics, specifically Turing's work, right? By your argument, the entire field of Theoretical Computer Science is ... not a part of computer science. Some how, I think that that's not quite right.

gravypod 10y ago

> Complexity theory also does not concern itself with uncomputable algorithms, so that point is irrelevant. I do not think this is a correct statement from what I've seen. > As you say, starting off students with abstract theory doesn't help, because they're unlikely to use it and so it won't stick. However, the same argument goes for your "bottom-up" approach; most students of computer science will not ever have to twiddle bits and manipulate assembly; knowledge of this material would thus be quickly forgotten. If the course is organized correctly the experiance can be magical. You're pulling the curtian on the the giant talking head. You're showing the students how everything works and you should do this directly. Like all teaching the student needs to THINK they have been the ones to discover something while in reality the teacher is supposed to have errected an artificial situation where in this was the case. You don't start them off with bits right off the bat although that is one approche (That is extremely successful: see NAND 2 Tetris). Like I said in my other comment you state them off with a broken machine. You give them an artifical reason to continue. "If you want to get a grade you have to open up this machine and, with me coupled with some hand holding, diagnose the problem." That gives them a reason to learn about the different parts of the computer. That errects a situation where they FEEL that have found something that they weren't meant to. They've explored something when in reality it was all, as someone smarter then me once said, a "Head Fake". Get them looking at a nearer goal and they'll start dreaming of further ones.

Ar-Curunir 10y ago
But is the point of your course computer science, or computer engineering. I don't think I'm particularly special, but I have taken just the one computer architecture course as an undergrad (and I don't remember much if any of what I learnt), and now I just completed the first sem of my PhD in computer science. I haven't used the information I learnt in that class yet, even though I'm in a partially applied field (security and cryptography). All I'm pushing back is on the idea that learning the intricacies of modern computing is necessary for being good at computer science. EDIT: And wrt complexity theory and computability: there is a subfield of mathematics called computability theory that concerns itself with various notions of what is and isn't computable. Complexity theory concerns itself instead with what is efficiently computable; the problems it considers are already computable.
- gravypod 10y ago
  Well you're not going to like when I say this. Cryptography isn't Computer Science. It uses some things that Computer Science developed but it isn't Computer Science. It's applied Math. If Cryptography is in CS then Nuclear Reactor Operations is in CS. NRO uses computers for monitoring systems and develops algorithms to detect certian... ahm... undesierable states. That doesn't mean we should move a reactor into the CS building at every college near you (although I'd love to work on one eventually, sounds like cool work). Academics may think that crypto is a CS field but the work involved has absolutly nothing to do with CS. For example, all cryptographic functions can be implemented in hardware. If you are building a cryptographic function in hardware, you're not part of the Electical Engineering department or the Mechanical Engineering department you are still in the Math department because all you're doing is implementing an abstract design. (Insert unintelegable "get off my lawn" statement)
  - Ar-Curunir 10y ago
    ... what? I am not sure what your idea aof cryptography is, but crypto relates to the most basic of questions about computation: what is and isn't efficiently computable, that is, P ?= NP. You do realise that the origin of the field of Computer Science lies in mathematics, specifically Turing's work, right? By your argument, the entire field of Theoretical Computer Science is ... not a part of computer science. Some how, I think that that's not quite right.