4 ms·

Algorithms and complexity theory are independent of any physical model of computation; they capture what it means to compute. The entire field of theoretical c

Algorithms and complexity theory are independent of any physical model of computation; they capture what it means to compute. The entire field of theoretical computer science stands as a counterexample to your comment. Computer science is not about software engineering.

gravypod 10y ago
An algorithm that is infinitly complex and takes infinite time is of no practical use in every day computation. Maybe in theory, in textbooks, in labcoats, but not in industry. I don't know where an uncomputable algorithm would be useful. I do know that you cannot possibly start a student out on a plane of the purely theoretical as they cannot see the value of what they are learning, they cannot understand the implications of the material, and frankly they won't remember it if they don't need it. To their minds, they don't need it if they haven't used it. It can be JFM (Just Fking Magic) to them if they haven't seen a case where it has improved their own algorithms. They will also not really understand how it works with no implementation. It is impractical to say the least. Theoretical computation is a higher level topic then real computation topic. In the same sense that you start math with addition, subtraction, multiplication, and division you should start out computer science with implementation.
- Ar-Curunir 10y ago
  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.
Klockan 10y ago
Computer science assumes that the code is run on a machine with a very specific set of operations since otherwise you wouldn't be able to calculate time complexity. The set of operations were deliberately chosen to be a reasonable abstraction of a modern computer. Thus computer science would look very differently if computers had different capabilities. For example, lets say that a new computer could switch places of two blocks of memory in constant time no matter their sizes. That would completely revolutionize computer science since many of our old results hinges on the fact that moving memory takes linear time.
- Ar-Curunir 10y ago
  The extended Turing thesis says that whatever is efficiently computable in one "reasonable" model of computation, is also efficiently computable in another reasonable model of computation. Of course, the truth of this thesis has been called into question with the advent of quantum computers, but it holds otherwise.

gravypod 10y ago

An algorithm that is infinitly complex and takes infinite time is of no practical use in every day computation. Maybe in theory, in textbooks, in labcoats, but not in industry. I don't know where an uncomputable algorithm would be useful. I do know that you cannot possibly start a student out on a plane of the purely theoretical as they cannot see the value of what they are learning, they cannot understand the implications of the material, and frankly they won't remember it if they don't need it. To their minds, they don't need it if they haven't used it. It can be JFM (Just Fking Magic) to them if they haven't seen a case where it has improved their own algorithms. They will also not really understand how it works with no implementation. It is impractical to say the least. Theoretical computation is a higher level topic then real computation topic. In the same sense that you start math with addition, subtraction, multiplication, and division you should start out computer science with implementation.

Ar-Curunir 10y ago
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.

Klockan 10y ago

Computer science assumes that the code is run on a machine with a very specific set of operations since otherwise you wouldn't be able to calculate time complexity. The set of operations were deliberately chosen to be a reasonable abstraction of a modern computer. Thus computer science would look very differently if computers had different capabilities. For example, lets say that a new computer could switch places of two blocks of memory in constant time no matter their sizes. That would completely revolutionize computer science since many of our old results hinges on the fact that moving memory takes linear time.

Ar-Curunir 10y ago
The extended Turing thesis says that whatever is efficiently computable in one "reasonable" model of computation, is also efficiently computable in another reasonable model of computation. Of course, the truth of this thesis has been called into question with the advent of quantum computers, but it holds otherwise.