What is Algorithmic Problem Solving ?

[yUNeeC]

What is "Algorithmic Problem Solving"?

Hi all,

I'm trying to get a head start on next semester's difficult classes and am kind of confused about what a certain class entails.

I have a Computer Science course that is part of the core for my math major:

"CSCI 2310, 2311. Algorithmic Problem Solving and Programming Laboratory (4,0) - Design of algorithms and their implementation as programs in high-level language such as Java."

I was wandering if anyone here had any idea as to what exactly this entails, as well as what I should study in preparation?

Thanks for any help.

 

[Noo]

I offer no insights. Though, i do recall this;

http://www.youtube.com/view_play_list?p=8B24C31197EC371C

"Introduction To Algorithms" MIT lecture series (Very comp-sci based, apparently). Could give you an idea of what you're in for.


P.S. I did watch the first lecture at some point, and remember the guy indicating that the first half of the semester would be spent on analysing the theory of Algorithms and such, before moving on to designing algorithms in the second half of the semester.

 

[jtbell]

I think you should ask your instructor, or someone else at your university who is familiar with this course.

Based on my experience, this could mean at least two different kinds of courses:

1. A more or less standard introductory programming course in Java. The description is worded so that the instructor can use a different language if he wants, without having to get it approved by a faculty or university administrative committee, and changing the official course description.

2. A more theoretical course in algorithm design using various modeling techniques such as flowcharts or UML, in which the students can implement the algorithms in whatever programming language they happen to be familiar with. This obviously assumes you already know the basics of some programming language such as C, C++, Java, Fortan, ...

3. ?

 

[AUMathTutor]

It could be an introductory course, the course typically called "data structures" and which is a continuation of the introductory course, or the in-major algorithms course. It actually sort of sounds like the latter... that's what it sounds the most like at my school, except we did very little programming and treated it more like a regular math class.

 

[jtbell]

Are you at East Carolina University? Their catalog has a course with that number, name and description. Based on its position in the computer science degree requirements, it's almost certainly the following:

1. A more or less standard introductory programming course in Java. The description is worded so that the instructor can use a different language if he wants, without having to get it approved by a faculty or university administrative committee, and changing the official course description.

It might use something other than Java, so if you want to start studying over the summer, you'd better contact the department or instructor and make sure of which language they're going to use.

 

[yUNeeC]

Are you at East Carolina University? Their catalog has a course with that number, name and description. Based on its position in the computer science degree requirements, it's almost certainly the following:



It might use something other than Java, so if you want to start studying over the summer, you'd better contact the department or instructor and make sure of which language they're going to use.

Yeah, I'm at ECU. Interesting...I just don't understand why part of the core of the BS degree in math would be programming...but I guess that's just my luck.

Thanks for all of the help guys.

 

[AUMathTutor]

"I just don't understand why part of the core of the BS degree in math would be programming"

There's probably a CS major somewhere wondering why Calculus is part of the CS curriculum...

 

[yUNeeC]

Well, math is fundamental to pretty much everything. Computer science, at least in my opinion, is not.

 

[mXSCNT]

Theoretical CS is almost like a branch of math. If indeed this course is an introduction to algorithms course like the one I took, it is a mathematically based subject.

On the other hand if it's a less-theoretical programming course, well, mathematicians do need to know how to program.

 

[yUNeeC]

Very true. And I'm starting to take interest in robotics...so I suppose if it is programming oriented I should make the most of it.

 

[Phrak]

what, in coding, is not an algorithm?

 

[AUMathTutor]

"what, in coding, is not an algorithm?"

It depends on your definition of "algorithm".

 

[AUMathTutor]

"Well, math is fundamental to pretty much everything. Computer science, at least in my opinion, is not."

I didn't say a CS major didn't need math. I can't think of any concrete way in which calculus aids the study of (basic, core, undergraduate) computer science. Perhaps you can reference the following: http://www.acm.org//education/curricula/ComputerScience2008.pdf , find the topics where 2 to 3 semesters of calculus are required to understand 10% of the material in the course, and count how many course hours such courses total to.

If your argument is that calculus helps CS majors mature and think logically, ditto for programming.

If your argument is that calculus can be used on problems in the real world to which CS is applied, ditto for programming to mathematics.

I can't think of an argument you could make that I couldn't turn on its head.

 

[Phrak]

"what, in coding, is not an algorithm?"

It depends on your definition of "algorithm".

Is it something such as within electrical engineering where a 'bus' means "something that has the look-and-feel of what other people have called a bus."? Everything that takes a bunch of bits and deterministically produces another set of bits is an algorithm. XOR is an algorithm.

 

[AUMathTutor]

"Everything that takes a bunch of bits and deterministically produces another set of bits is an algorithm. XOR is an algorithm."

If that's your definition of algorithm, it's almost trivial to write a fully-functioning program which contains no algorithms.

 

[yUNeeC]

I can't think of an argument you could make that I couldn't turn on its head.

Math = natural science
CS ≠ natural science

Math is more fundamental to logical development than is computer science. Therefore, I would venture to say that a CS major would benefit from math more than a pure mathematician would benefit from CS.

Your opinion doesn't turn my opinion on it's head.

Edit: You seem to be misunderstanding what I was stating. I was wandering why a CS course was part of the CORE for a math degree at my school...not why it was required. For instance, Calculus I-III and Differential Equations are not considered part of the core for my physics major...they are just requisites that don't count toward my major GPA. The "that's my luck" refers to the CS course being in the core, and consequently counting towards my major GPA for math.

 

[AUMathTutor]

"CS ≠ natural science"
Would you care to back that up?

"Math is more fundamental to logical development than is computer science."
Differences of opinion are what makes the world a wonderful place, I guess.

"Your opinion doesn't turn my opinion on it's head."
That's the pot calling the kettle black.

CS majors at my school take a discrete math class in the math department and it's part of the core. While it should be required of CS majors, why make it a core class? Most of the stuff is rehashed in the CS courses anyway.

So you're just complaining about the politics of what counts towards your major GPA at your school? I guess I thought you were questioning the merit of a mathematician knowing how to program.

I think any college that doesn't make math majors learn how to program is doing their students a great disservice. Ditto for CS majors not learning calculus. I think it's really more your prejudices than any reasoned opinion that leads to your position.

You can be a great computer scientist without knowing calculus, and you can be a great mathematician without knowing how to program. But why would you want to do that? CS and Math majors should have a fair amount of interest in both, as they are pretty fundamental to what constitutes an educated scientist / mathematician / engineer.

 

[yUNeeC]

You have got to be kidding me.

CS is not a natural science. Sure, a good amount of logic is involved, but it is logic geared towards implementing a man-made system (hence it not being natural.) Mathematics is a pure language used to explain natural phenomena, while computer science has a heavily invented component.

I've never said programming is not important. Stop inventing arguments...and quit being so fricken arrogant. Just because an opinion differs from your own doesn't make it the byproduct of prejudices.

I've even agreed that programming is an important thing to know, yet because I don't think it should be the only non-pure math course that is considered a part of my major-GPA I have unfounded bias? Nice.

 

[mXSCNT]

Neither mathematics nor computer science is a natural science, because they do not study the physical world.

 

[yUNeeC]

Neither mathematics nor computer science is a natural science, because they do not study the physical world.

Mathematics can be used to study the natural world. I suppose this would be under the "physics" category...but it is mathematics nonetheless. Also, I suppose "natural mathematics" has realms outside of physics (modeling, etc.)

 

[Phrak]

"Everything that takes a bunch of bits and deterministically produces another set of bits is an algorithm. XOR is an algorithm."

If that's your definition of algorithm, it's almost trivial to write a fully-functioning program which contains no algorithms.

That could be. I'd like to see one. Could you explain a small example?

 

[AUMathTutor]

Consider the following C program(s):

int main()
{
// x could be anything...
// hardly deterministic.
int x;
cout << x << endl;
}

int main()
{
// this doesn't take anything in
cout << "Cool" << endl;
}

int main()
{
// or do nothing at all?
}

Anything with randomization would not constitute an algorithm. There are other examples, for instance...

int main()
{
cout << time() << endl;
}

int main()
{
cout << date() << endl;
}

int main()
{
cout << file.read() << endl;
}

etc.

 

[AUMathTutor]

"You have got to be kidding me. "
Do you hear yourself?

"CS is not a natural science. Sure, a good amount of logic is involved, but it is logic geared towards implementing a man-made system (hence it not being natural.)"
Do you know what CS is about? If CS is not a natural science, neither is Math. Remember, computers are to a CS what telescopes are to an astronomer...

"Mathematics is a pure language used to explain natural phenomena, while computer science has a heavily invented component. "
CS is used to explain natural phenomena too. You don't need people to carry out computation; if you say you do, you have to accept that you need people for math to exist as well.

"I've never said programming is not important. Stop inventing arguments...and quit being so fricken arrogant."
Granted. I already acknowledged that I initially thought you were calling into question the importance of programming for a math major. As far as the arrogance thing goes... I think you need an attitude adjustment.

"Just because an opinion differs from your own doesn't make it the byproduct of prejudices."
So why shouldn't programming count towards a math major GPA? Shouldn't math majors know how to program? Will that not be expected of them upon graduation? Isn't the purpose of a GPA to help tell employers how much of what you're supposed to know you actually do? etc.

"I've even agreed that programming is an important thing to know, yet because I don't think it should be the only non-pure math course that is considered a part of my major-GPA I have unfounded bias? Nice."
What's your basis, then? Most college majors include in the major GPA courses offered in other departments. Check your local listings. What right do you have to complain about it? Surely you knew about it when you signed on. If not, most univeristies will not hold you to the new requirements.

Excuse me, but what's your freaking point? Is there one? What's the problem?

 

[Phrak]

Consider the following C program(s):

int main()
{
// x could be anything...
// hardly deterministic.
int x;
cout << x << endl;
}

This takes data embedded in the code in format f, uses some built-in algorithms and outputs something to the console in format g.

int main()
{
// this doesn't take anything in
cout << "Cool" << endl;
}

This moves thousands of bytes around, changing, rechanging, and resetting a bunch of registers before halting without having external effect in principle, but actuallity scrolling the screen in some cases, which is more than doing nothing.

int main()
{
// or do nothing at all?
}

Same as above.

Anything with randomization would not constitute an algorithm. There are other examples, for instance...

int main()
{
cout << time() << endl;
}

int main()
{
cout << date() << endl;
}

int main()
{
cout << file.read() << endl;
}

etc.

Mia copa. My adjective 'deterministic' was just wrong. Other than that, our apparent point of departure is that you assume 'produce' to be something sent out of the machine, where I haven't. Interestingly, I assumed external input to be an element to be included in deterministic. I'll have to refine my definition. Thanks for the help. Nobody I know personally would have a clue.

 

[AUMathTutor]

In the first one, the indeterminacy comes from the fact that I don't initialize x.

In the second one, no input is provided, although a functionality is provided (I would call what cout does an algorithm, sure).

In the third one, it fails to "take in a bunch of bits", one of your conditions.

And I believe the expression is "mia colpa" in Italian, the closest to what you wrote. Unless you were going for "my cup" in Spanish.

 

[Phrak]

In the third one, it fails to "take in a bunch of bits", one of your conditions.

I'm thrilled you found ammunition in a typo.

It takes a bunch of bits from disk, interns them in memory, changes several registers. After pointers are generated by the supervisor. Maybe you could find something far simpler than int main{}.

 

[AUMathTutor]

First of all, a "typo" is where you misspell something, like you did with "mia copa". It's not where you say something you later regret having written. That's just called an error, and we all make them, so don't get so defensive about it.

Generally speaking, one does not say that an algorithm takes its code as input. It's sort of just *there* in the context of the algorithm. Also, one does not usually consider what the algorithm requests as input to the algorithm. An algorithm's input is what you give it when you invoke it.

For instance...

CalculateSquare(x)
1   result := x
2   result := result * x
3   return result

Is an "algorithm" in that it's completely deterministic (at least in theory), whereas

CalculateSquare()
1   x = readFromConsole()
2   result = x * x
3   writeToConsole(result)

Is not an algorithm, at least, in the restricted technical sense I think is usually intended. Who knows? Do you like these better than my main()'s above?

 

[yoran]

Mathematics can be used to study the natural world. I suppose this would be under the "physics" category...but it is mathematics nonetheless. Also, I suppose "natural mathematics" has realms outside of physics (modeling, etc.)

I think mathematics is just as "unnatural" as computer science. All of mathematics is based on axioms and who invented those axioms? Right, people did. Those axioms aren't to be found in nature. In the same way, you can say that the Turing machine (or any equivalent machine) is the basis for computer science , which I guess you could see as a set of axioms, defining clear rules of what is allowed in the system and what isn't. So, in that way, mathematics and computer science are kind of equivalent so if you call computer science "unnatural" then mathematics is also "unnatural".

Of course, mathematics can be used to describe the real world but it only allows an approximation of what is really going on. Therefore, you cannot say that mathematics fully describes nature. For example, almost all of physics is based on differential equations, in which you make the assumptions that the functions you try to find are continuous. However, all things in nature are discrete (can you find me an infinitesimally small charge $$dq$$?)? A very interesting document related to this is http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/real.pdf" by Doron Zeilberger.

So I think that saying that mathematics is natural is silly.

 

[AUMathTutor]

Wow, a nice post, yoran. I tend to agree.

Although I would consider both mathematics AND computer science natural (or at least physical) sciences in the sense that they're (a) sciences, (b) not life sciences (nothing to do with biology), and (c) not social sciences (nothing to do with how people behave). They describe, in theory, things that occur naturally... or in the realm of thought.

Perhaps a better characterization is that Math and CS constitute a separate category altogether. Difficulties arise since there exist machines which can approximate things discussed in CS (computers), so things can be tested... whereas in math, there is not really an idea of "testing" things in an empirical way (the existence of experimental mathematics makes some mathematicians very angry...)

Still, I think that basic programming is a tool that should be common to all scientists, engineers, and mathematicians.

As far as the GPA issue... if people will expect you to know it, and it's not something you are expected to know from high school, you should probably put it in the major requirements. Why? Because otherwise there's no guarantee the person will know anything about it. It seems fair to me. The real question is this: should a math major who cannot make a satisfactory grade in an introductory programming course be allowed to graduate from a math program? Should a computer scientist who cannot make an acceptable grade in calculus be allowed to graduate? etc.

 

[mXSCNT]

Mathematics and CS are not sciences, except in the third sense of the word ("a systematically organized body of knowledge of any kind"). They do not study the natural world. The use of mathematics to study the natural world is physics (or chemistry, or biology, etc.), not strictly mathematics. CS does not study the natural world either, because it instead studies man-made formal systems.

There is no single definition of algorithm. Some people say algorithms have to terminate, some people say algorithms have to express pure functions (in other words no randomization or i/o), and some people drop all restrictions and simply describe an algorithm as a series of operations.

 

[AUMathTutor]

It is well to point out that "algorithm" is a loaded word. Still, one should be consistent with the definition they give, at least in the context it is given. Ergo my providing examples of simple programs that did not constitute algorithms according to the definition given.

I think that any definition of "algorithm" should be consistent, coherent, and useful. I'm not sure defining algorithms as an arbitrary series of operations is useful... but I can definitely see what you're getting at.

 

[yoran]

Still, I think that basic programming is a tool that should be common to all scientists, engineers, and mathematicians.

I agree with that. Computers are so ubiquitous to anything related to science or engineering. You can't do science or engineering research anymore without using a computer. Even some pure mathematicians at my university use mathematical software to test hypotheses and gain insight in problems. Needless to say, these mathematical software packets require lots of scripting.

It is well to point out that "algorithm" is a loaded word. Still, one should be consistent with the definition they give, at least in the context it is given. Ergo my providing examples of simple programs that did not constitute algorithms according to the definition given.

I think that any definition of "algorithm" should be consistent, coherent, and useful. I'm not sure defining algorithms as an arbitrary series of operations is useful... but I can definitely see what you're getting at.

Yes, apparently there is no standard definition for "algorithm". Even on Wikipedia, there is no formal definition. I've always been taught that an algorithm is a finite sequence of operations which takes an input and produces an output. Furthermore, for any input, the program must produce an output after a finite number of steps. There is no notion of usefulness in that definition. I think it is difficult to include usefulness in the definition because it is has a subjective meaning. You can't define usefulness formally.

 

[AUMathTutor]

Well, I think that the definition you provide is useful.

Useful how? It lends itself to proving things about algorithms. There may be no formal definition of usefulness, but it's like porn in that you know it when you see it.

I think any good definition of algorithm should require that the algorithm be as referentially transparent as regular mathematical functions. This excludes certain kinds of things as algorithms, but isn't that the point of definitions?

I am wary of using Wikipedia as a resource in these matters. Their discussion of termination is very misleading, at least in my opinion. They seem to be saying that you can not know for sure whether a certain algorithm will terminate, which I don't believe has ever been shown. Alan Turing showed there's no algorithm to do it, but that doesn't mean we can't do it.

 

[yoran]

I am wary of using Wikipedia as a resource in these matters. Their discussion of termination is very misleading, at least in my opinion. They seem to be saying that you can not know for sure whether a certain algorithm will terminate, which I don't believe has ever been shown. Alan Turing showed there's no algorithm to do it, but that doesn't mean we can't do it.

Well, the part on Wikipedia about termination says this:
There is no algorithmic procedure for determining of arbitrary algorithms whether or not they terminate from given starting states.
This is exactly the Halting problem. Of course, as you say, it is possible to look at every algorithm individually (although there are infinitely many different algorithms) and mathematically proof its termination. However, there is no single method (read algorithm) which works for all of them. I don't think that the Wikipedia entry is misleading about that.

 

[AUMathTutor]

It says that, but it says other things which seem to imply that a lack of an algorithmic procedure means we can't do any better than just testing every algorithm. The presentation is sloppy... I would say Wikipedia is useful for a quick and dirty intro to fundamentals, but when it gets down to details, you should look elsewhere.