Concepts every computer science student must understand?

[AmiNeo]

Hey guys, this is a bit of an odd one but half way through the second year and I'm feeling a little let down by my course as they have taught us no maths whatsoever this year either.

As an aspiring Comp Sci student and wanting to take some advanced programming classes in my final year, I want to use the time I have left to catch up as much as possible.

With not having been taught any maths, I've been seeking out what the 'essentials' are for foundations in computer science, but only have a sketchy idea of the areas I need to be studying alongside this course.

Could anyone direct me to any books or websites that will give me a better understanding of the theory I will need to get under my belt before the final year commences? By theory I mean which areas of mathematics, which concepts and generally what would people who are already professional programmers say I should know before final year of a bachelors degree in Computer Science?

What we are being taught may well be enough (if you're aiming for a 2:2, lol), but me being me would rather take it that bit farther and would rather have a clear idea either way.

 

[Zetr0]

have you been taught any complex algorithms i.e.

Divide & Conquer
Bubble Sort
Quick Sort
Regressive

Have you been show how to express these in mathematics ?

Have you done any work with higher-complex algorithms such as

Dijkstra's Algorithm (aka The Traveling Sales Man)
Genetic Algorithms
Neural Nets

Have you been taught the difference between constant time and non-constant time polynomial equations?

Have they taught you how to read something like this -

or can read the following

Let me know what you can do and I will help you further.

 

[Zetr0]

You should receive an AS to A level math for a BSc, if not then it will be a BA degree.

You can get AS to A level books that will help you with things like

Quadratic equations, Vectors, Polynomials, reduction, integration, matrix maths, as well as other principles that help immensely when developing algorithms and programming.

I am surprised to be honest Data Structures an Algorithms are core components of most 2nd year BSc courses.

I would suggest to anyone whom only did GCSE level Maths to pick up the AS-Level course books -

You can get these books from £3 + Postage (click here for amazon link)

Since we are on Amazon I would also suggest the following -

Schaums's Outline of essential computer mathematics
(from £1.08 and up)

Concrete Mathematics: Foundation for Computer Science
(from £18.00 *paper back)


Depending on your focus of discipline (mine was AI and 3D Graphics) - if you are looking at getting into doing some 3D graphics then I suggest a good quality book that deals with Matrix Mathematics as well as Vector Mathematics.

 

[BLTCON0]

@AmiNeo
A sound math background for a programmer would be:

1) Calculous: Single-variable functions (basic limits and integration), sequences & series (=sums of sequences)
2) Linear algebra: Notion of vector space, some basic results on linear mappings and their representation via matrices. If interested in computer graphics, analytic geometry and the use of matrices there to implement vector transformations.
3) Basic number theory (working with integers and related problems)
4) Numerical analysis (understanding the limitations of representing the real numbers within a machine and choosing efficient approximation methods for calculation problems).

5) Discrete mathematics: This is actually an "umbrella" term which typically encompasses knowledge from a range of sunjects (feel free to expand as much as you want on any as they're individual mathematical fields on their own, but a basic working knowledge on each should suffice):
5.1 - Combinatorics (the art of counting)
5.2 - Graph theory
5.3 - Boole Algebra and its application in basic logic-gate design
5.4 - Formal power series (too many applications to list)
5.5 - Elements of formal logic and set theory (the beauty in math)
possibly other topics such as decision theory, ergodics, discrete analogues to continuous problems etc but these are more "high tech" and specialised.

6) Computational complexity: This is where it gets interesting - Turing & register machines, analysing the cost in time and space of particular algorithms, proving that a given algorithm is the best possible, deciding on the type of algorithm to use to solve a particular problem etc.
The subject of Data Structures is also closely related to this. This topic is perhaps the more balanced one between theory and practice from a programmer's point of view.

7) Theory of programming languages (could also be presented as an introduction to compilers, depending on a more theoretical or practical orientation): Understanding the concept of formal grammars used to define a language and solving the decision problem: Is a given program a valid one?
This could also be a good place to learn about automata.

8 ) (Primitive) recursion - computability theory, but if you reach here you're more of a mathematician than a programmer, as the abstraction level is quite high and not closely related to any particular language or programming techniques.


Textbook wise, a good read on discrete math and some introductory algorithms book (with good analysis of the examples) will provide a kickstart and also point out particular deficiencies, serving as a guide for further strengthening on particular areas as the need arises.

But the most important part is to take it slow - math has the peculiarity of being absolutely unsuitable for learning with simple memorisation. Also for being unable to progress if you permit "gaps" in your understanding of gradually evolving concepts.
So, leaving aside for a moment the list presented above, of even higher importance is to build for yourself the so-called "mathematical confidence" - know what you already can/can't/should be able to solve and why. This part of mathematical capacity has nothing to do with programming in aprticular - it's a cognitive invariant, applicable everywhere, and once someone builds his mathematical confidence, he usually takes off with ease, having "learned how to learn".

 

[AmiNeo]

Finally some clarification...


@ Keith no and no on the first post, I know i=1 in a programming context, which would assign a variable i the value of 1 (or more accurately set a pointer labeled i to an area in memory holding the value of 1) but that's all. The only other familiar thing there is Dijkstra's algorithm, which has been mentioned in networking, a few routing protocols use it to determine their route metrics, but the closest to it we've been taught is a little on binary tree's which isn't really much at all.

I have already purchased that exact AS level book you directed me to so looks like I'm off to a fair start. I've not had it long though and I'm currently brushing up on the basics (running through a GCSE revision book before I start on it) since its been a while since I've had to do any maths beyond binary calculations in networking for things like variable length subnet masks.

My chosen modules next year will be... Advanced Programming, Modern Database Management Systems, Intelligent Technologies (AI, hence why I was looking for logic reading material) and Multimedia Games Programming. Then of course, the dissertation project. I'm so far also the only one taking that much programming on in my final year, so you can see where my concerns are coming from.



Based on the above responses, I think I'm going to have my spare time nicely mapped out over the summer, well between now and September really.

 

[Zetr0]

@AmiSonicNeo

As BLTCON0 has pretty much laid out a GCSE to AS/A level Math paradigm. its pretty much on the numbers. The truth is the more math you understand the better your algorithms will be as well as the formulation of your programs (irrespective of language).

Fundamentals of computing science should also include OSKA module (Operating Systems Kernal Architecture) this will give you the needed fundamentals of CPU scheduling and processing paradigms.

I have a course recommend book Modern Operating Systems that I used for Uni, we pretty muched lived out of this book for the OSKA module and the Advanced Kernal Architecture module that I also did.

Sadly the front cover is ripped - but its readable and bar the front cover is in good condition - Its yours for postage if you want it =)

 

[AmiNeo]

@AmiSonicNeo

As BLTCON0 has pretty much laid out a GCSE to AS/A level Math paradigm. its pretty much on the numbers. The truth is the more math you understand the better your algorithms will be as well as the formulation of your programs (irrespective of language).

Fundamentals of computing science should also include OSKA module (Operating Systems Kernal Architecture) this will give you the needed fundamentals of CPU scheduling and processing paradigms.

I have a course recommend book Modern Operating Systems that I used for Uni, we pretty muched lived out of this book for the OSKA module and the Advanced Kernal Architecture module that I also did.

Sadly the front cover is ripped - but its readable and bar the front cover is in good condition - Its yours for postage if you want it =)

I'd appreciate that L33tZeets I'll take any help I can get at this point

Sending PM...

 

[AmiNeo]

Oh and thanks BLTCON0

---------- Post added at 20:36 ---------- Previous post was at 20:33 ----------

@Zetr0 - I've taken your advice and ordered the recommended books. Took me a little over budget for the holiday season but will definitely be worth it in the long run

 

[AmiNeo]

Just heard back from our main tutor after sending an inquisitive email, there are apparently optional maths units along side final year... Sees a bit late in the course to me...

 

[Zetr0]

Wow...... just a tad...

tell you what my friend, since math can be a very dry subject - if you want I can give you phone call and we go through some stuff when you need to.

I even think there's some kinda white-board on google+ we can use as well

 

[AmiNeo]

Not familiar with google+ as I've not used it but I'm sure I can familiarise myself with it fast enough. I will be up for that over the weekend if you have a little time.

Skype or something may also be cheaper and easier if you can run that along side it? I think I could hear you much better through VOIP than my cruddy phone, too.

 

[AndyLandy]

Hang on,

You've not done any computing theory or maths at all? Where are you studying again?

Concepts like recursion and O are pretty key to any programming course. And you've not done any data structures & algorithms either?

Anyway, it looks like you've got a few pointers here, but feel free to hit me up on PM if you want any advice or assistance. I still work in a CS department, so I've not completely lost touch!

 

[Brian]

@AmiNeo: Sorry to jump in late, but BLTCON0 summarized things pretty well. Although I'm not doing a great deal of programming right now as I changed jobs last year, I was regularly using statistical analysis, calculus, and finite mathematics. The sorting algorithms, searches, etc., are definitely a must as well. I just (re)started into my Computer Information Systems BS; our Programming II course this session is covering a lot of sorting and searches using C++. If I can remember the material I've used in the past for self-taught knowledge, I'll drop you a line to let you know. Good luck!

 

[ColourWheel64]

definitely practice denery to binary conversion. It should be as easy to calculate in base 2 as it is in base 10.

Also, get hold of the instruction reference sheets for Intel 64 and ARM processors and read them to yourself until they make sense.

A good way I found to program your brain into remembering is to read a manual out loud, recording it into sections and playing it back to yourself.

Upload them to YouTube for those times when you're stuck in front of the internet and having the world at your fingertips isn't enough to prize you from boredom

 

[AndyLandy]

To be honest, I think the programming principles are far more valuable than a lot of the mathematics. Basic algebra and logic are very useful for any programming, but the more advanced maths is only useful for certain applications. I don't think I've ever had to care too much about calculus, linear algebra or matrices for any programming I've ever done. That's not to say they aren't valuable concepts to understand, but that they may not be essential.

Having a thorough understanding of programming concepts is most important. Conditionals (if, then, else) loops (for, while), variable scoping, functions, recursion and data structures to name a few.

It's nice to know how a hash table or a self-balancing AVL tree works under the hood, but knowing how to use them is arguably far more useful. I still only know the very basics of machine code and assembly language.

The best analogy I can come up with is this: You don't have to understand how to design a refrigerator, washing machine or toaster to use them successfully. Understanding them may give you greater flexibility to use them in clever ways, or repair them if faulty, but most of what you need to achieve can be done without knowing. You have to decide how much you want to invest in learning aspects in greater depth.

In many ways, the best approach if you do want to specialise in any specific aspect, is to find the areas that interest you the most. There's a lot of stuff that you could get your teeth into if you wanted, but there aren't enough hours in the day to learn everything. So find the stuff that really floats your boat and get into the depths of it.

 

[ColourWheel64]

You don't have to understand how to design a refrigerator

Yeah, its a different sort of knowledge.

A refrigerator is a good example because when designing a fridge, you're trying to maintain a temperature inside it, while making it look all futuristic and cheap as chips to manufacture.

When you're using it, you've paid your money, and now you're working with the design. Its warmer at the top, colder at the bottom.

Very similar to a computer. It won't always respond in the way you expect because corners are cut to keep costs down, but as a programmer you have to learn the best way to use your machine.

 

[AmiNeo]

definitely practice denery to binary conversion. It should be as easy to calculate in base 2 as it is in base 10.

Also, get hold of the instruction reference sheets for Intel 64 and ARM processors and read them to yourself until they make sense.

A good way I found to program your brain into remembering is to read a manual out loud, recording it into sections and playing it back to yourself.

Upload them to YouTube for those times when you're stuck in front of the internet and having the world at your fingertips isn't enough to prize you from boredom

Decimal to binary I'm already quite fluent in thanks to 3 years networking experience and a CCNA course under my belt I'm a bit rusty but I can do VLSM okay. Just had to for my networking assignment, lol.

 

[MrD]

What is it exactly that you want to know?

Maths can mean a whole bunch of different things. Computer Science™ doesn't have a lot of numerical maths, as it's about the theory of computation.

Things like set theory and formal logic are maths which are needed to understand certain algorithms relating to formal verification of software, for example.

If your course covers information theory (and maybe some practical data compression stuff), you'll need to know how to manipulate probability and logarithms if you want to be able to deal with entropy values. The theory of encryption works in fields and rings which are like numbers but work by their own rules.

The above stuff (apart from probability) is sort of not-everyday stuff, and any decent course will devote time to primers and the staff should recommend books (and the books will probably have primers too).

But if you're looking at maths as in super heavy number crunching for simulation, kinematics and graphics you'll need to know calculus, vectors, matrices, properties of spaces and how to manipulate them. The book Engineering Mathematics by KA Stroud is a very comprehensive guide to all things practical and numerically mathsy.

 

[AmiNeo]

What is it exactly that you want to know?

Maths can mean a whole bunch of different things. Computer Science™ doesn't have a lot of numerical maths, as it's about the theory of computation.

Things like set theory and formal logic are maths which are needed to understand certain algorithms relating to formal verification of software, for example.

If your course covers information theory (and maybe some practical data compression stuff), you'll need to know how to manipulate probability and logarithms if you want to be able to deal with entropy values. The theory of encryption works in fields and rings which are like numbers but work by their own rules.

The above stuff (apart from probability) is sort of not-everyday stuff, and any decent course will devote time to primers and the staff should recommend books (and the books will probably have primers too).

But if you're looking at maths as in super heavy number crunching for simulation, kinematics and graphics you'll need to know calculus, vectors, matrices, properties of spaces and how to manipulate them. The book Engineering Mathematics by KA Stroud is a very comprehensive guide to all things practical and numerically mathsy.

I'm just concerned that my lack of maths background will leave me disadvantaged during my final year. Nothing in particular, just generally and want to take the opportunity to get ahead of where I'm at before I need it.

 

[Zetr0]

Its a shame you don't live closer my friend, I could have you writing algorithms using equations within a week =)

I will have a look to see if there is any on-line white-boarding type software that we could use.