I need math examples in computer science
 

Hi all, I am an adjunct instructor at a college and I am teaching a course in mathematics. I am writing you because I have a lot of students in my class that are computer science (CS) majors. I want to provide mathematical examples from CS that apply to my class. I am currently teaching lessons in logarithms and exponential functions followed by law of sines and cosine. I was wondering if any of you use the following math concepts in CS:

trigonometric functions.
log and exponential functions
oblique triangle law of cosine and sine
Polar coordinates
complex numbers
vectors
sequences and summations
permutation and combinations.
probability

So far I have shown them how to convert from decimal to binary and vice versa but I would love to have other examples of how math is used in this field. If possible, I would like practical examples that are actually used and the consequence of not using a given math technique.

with warm regards
Ronald Cross

It is helpful to have a good understanding of exponential / logarithmic functions and sequences / summations in order to calculate the time complexity of a function and/or program.

For example, searching an AVL binary search tree for a certain element has a time complexity of O(log_2 n)*, where n represents the number of elements in the tree. Searching a linked list for a particular element has a time complexity O(n). Summations can be used to understand the general time complexity when the time complexity of particular cases are known or can be easily determined.

Not all functions have a constant time complexity. If someone wanted to, I am fairly certain that probability could be used to determine the average time complexity of a function. For example, different sorting algorithms have time complexities between O(n^2) for worst case, and O(log_2 n) for best case. However, in practice, some are more efficient than others. My untested hypothesis is that the better sorting methods are able to achieve near best case results from a data set initially ordered in any one of a wider variety of permutations.

Additionally, most anything that can be expressed in summation form can be expressed as a for loop. Summations of summations can be easily expressed as nested for loops.

A very basic example:

summation (1, n, 1, 10) (using the form summation ( expression, index variable, initial index value, maximum index value)

is the same as
I hope this is helpful. I'm sure there are more applications for math in CS, but I've only just completed CS1.

-jc

* log_2 == log base 2

Why not use computer games as an example? Everything from 3D shooters to golf games, flight simulators, even something as simple as the old Asteroids game, all use trig, vectors, and possibly polar coordinates (some could use Cartesian coordinates) as well as the laws of projectile motion and the effects of friction to create believable simulations.

Permutation and combinations, as well as probability apply to card game simulations like Texas Hold'em.

I suppose it depends on what part of computer work you go into...the only math I've ever used is simple binary rules for IP addressing. I remember being told in school that I'd need to know all this advanced math to work with computers, which has proven false.

So from my perspective, everyone in computer work should understand binary and hexadecimal. It's so hard to figure out IP networking until you thoroughly understand that. Unfortunately, nobody taught me that in school.

So how would this work in the case of O(log_2n) or O(n^2)?

What is O(log_2n) equal to in terms of its summation or log?
What is O(n^2) equal to in terms of its summation or log?

This seems like some form of discrete mathematics. To keep it simple for my students and me, what would these time complexities O(log_2n) and O(n^2) be equal to if there are only 3 elements in decimal notation in a tree labeled 0, 1, 2 that originate from one brach so that you have

and you are interested in finding any one element?

Is there a solution for this? it seems relevant to what I want to show them. Anytime you can link math to what they are interested in, they become more focused.

Most of the students are interested in Network and not gaming so I don't want to go in that direction unless it is specifically and intrinsically related to computer science, but thanks for the suggestion.

You could have them calculate the throughput for each machine on networks that consist of various numbers of wireless and ethernet connected devices and varying types of internet connections.

How much RAM is really enough for a given system and user? Studying the number of page ins/outs on different configurations for the same user will give them a good appreciation of the importance of probability theory.

For different applications, how much more performance can you really expect from an 8 core system vs a quad core? Dual core? Single core? Would spending the extra money on more RAM for a dual core system be better spent than getting a stock quad core or 8 core?

I'd be curious to see the results from a mathematical study of the various platforms and their respective rates of vulnerabilities discovered versus the number of actual exploits deployed and their severity. The 'security' companies are begining to look at routers and other devices as potential security markets. Studying their rates can determine whether this will be a profitable avenue for these companies. Presumably, these companies have already done studies that say they will be profitable, and it's possible that your students may be called on to do similar studies in the future.

How much better is a 256kbps recorded AAC song than one at 192kbps? Is it really within the average human's hearing range to tell the difference, and what is the extra bandwith needed to accomodate the larger files?

Math is in everything. You just need to look around.

possibly a little too physics oriented, but there's a guy that made a java collection called MyPhysicsLab. good overview of differential equations and sinusoidal functions, coordinate graphing, and vectors, if I remember correctly. worth a look, anyway - good thing in its own right.

Also (believe it or not) os X ships with an awesome app called Grapher - look in '/Applications/Utilities'. I don't really know why they think it's a utility, but there you go. just look through the examples; I swear, the sucker is almost as powerful as MatLab.

I've seen others, but I can't recall them off-hand. if I do I'll post again.

In networking, there's nothing at all useful from math except the ability to understand binary/hex addressing in IP. And that training is sorely lacking, as I've never met anyone who understands it outside of other Cisco-bred geeks like me. Comp-sci graduates with masters don't get it. So that's the most valuable thing you could offer, presuming that you understand it yourself.

There is a little more than that. It isn't difficult math, but it can be useful to calculate transmission rates. Just knowing the difference between mbps and MBps can be important! Toss in overhead, and the calculations can get tricky.

192.168.0.1 != 192.168.0.2

Network math for real!

After a brief search I realized computer science wasn't for me, because I can do anything with them except program.

Ok, I will give them something simple tomorrow in geometric sequence. If one computer is connected to two other computers and those computers are connected to two other computers how many computers will you have by the time you have 10 such connection? 15 connections?


How much storage space will each computer have if the storage space is 1Tb for each case of 10 and 15 connections of computers?

I know it's easy but this is the kind of examples they need to see so they can relate it to their field of study even those this can be applied to anything else geometrically. These students are always asking how does this apply to what I am going to be doing on the job?

lol - you can always tell them what I tell them when they give me that hackneyed line. "There's only one tool in the world that matters, and that's your own brain. if you learn how to apply your brain to any problem, you'll know how to apply it to every problem. if you don't learn how to apply your brain, then you can get the best education in the world and you'll still end up waiting tables."

not very effective, really, but morally satisfying. :D

as an afterthought, have you thought about teaching them the Fibonacci sequence? more applicable to nature than to employment, but at least you can show them an easy to calculate mathy thing which shows up in real life all over the place...

My thoughts exactly. But simple examples do work and help to motivate them so that they show some interest in the topic even though they may never use it in real life. It's the thought process of learning that counts.

When I was doing embedded control systems programming I implemented both trigonometric function generation libraries and Fast Fourier Transforms in assembly language. Does that count?

And as far as networks are concerned, the branch of combinatorial topology known as Graph Theory is pretty fundamental to the design and optimization of large networks. Data compression/decompression, encryption/decryption and error correction algorithms rely heavily on algebra and statistical communication theory.

The entire range of SQL databases and AI employ both algebra and symbolic logic from the ground up. And entire fields like bioinformatics use some advanced string manipulation algorithms (again, algebra and logic) and probability and statistics.

The point being it's not so much what you might use as a tech, but what doors can be opened up for you to go beyond being a tech. It would be worth it for the students to be open to as many options as they can, yes?

The speed at which the industry evolves says the more you know, the longer it will be before you become obsolete. And since the learning is a continuing process, you might as well get used to it early in the game. :cool:

Here's one that crops up on this site every once in a while:

Have them calculate the difference between two hundred gigabytes and a two hundred gygabyte hard drive. It' really boils down to the difference between using 2^10 and 10^3, but it adds up to a big difference when somebody thinks they'll be able to store 200 GB and their empty hard drive says that far less than 181 GB is free. They start calculating overhead and they quickly see that about 19 GB of storage they thought they had is missing!

Trigonometric function generation may work but Fast Fourier Transforms is beyond the scope of the class. Do you have a simple example of how using trigonometric function generation library may solve a problem and what the solution might be using such library? Sorry, but I am really green in this area so I am not sure how I would present this to them.

Agreed, you never know how something you learned in the past will benefit you in the future. Another way of saying this is you never know how something you failed to learn will be a liability to you in the future.


Very good points. Another way of putting it is if you don't continue to educate yourself, you will be waiting tables as stated earlier by tw.

Next topics will be probability, combinations, permutation. With respect to probability, I will probably give them an example on IP addresses, Something like, if the IP address takes the forms 192.168.1.100 where it is a made up of 4 numbers that range from 0-255, how many computers can you support? What would you do to extend this number beyond 256^4 to support more computers?

Each number in the IP address is made up of 8 Bits, using the summation formula, sum the number of bits to get to 255 (Show your work)?

No, it's not apart of the curriculum.

Ok, you got me, what is a gygabyte?

It's poor spelling!

1 KB:
1,000 Hard drive makers
1,024 OS, RAM & should be hard drives

That 24 byte difference really adds up!

I believe the suggested nomenclature for 2^30 is gibibyte, with gigabyte being used for 10^9, per the IEEE 1541 standard.

http://en.wikipedia.org/wiki/IEEE_1541

It seems like the drive makers, rather than admit that their marketing departments have been over-inflating drive capacities, have found a way to claim that they're right:
From the same Wiki page:
In any case, it's important for students of any computer science class to understand the differences.

You mention trig functions and sequences and series.

Sin(x) can be expressed as a series: x - (x^3)/3! + (x^5)/5! - ...

Similarly, Cos(x) = 1 - (x^2)/2! + (x^4)/4! - ...

Both converge briskly because of the factorials, and the first (Sine) is fairly accurate for small angles (in radians) using only the first term.

Yes ok, but how does this relate to computer science? Is this the way computers calculate cos(x) and sin(x) using 4 or so terms? If so, this may also be a good example.

In CS, most engines use FDLIBM's version which is an approximate polynomial of degree 13 on the range 0 to pi/4 with six coefficients since only even powers of x are considered. All other ranges can be found using identities.

Since the exact polynomial converges so quickly, however, not too many terms are required to converge within a given tolerance. Have them figure that out.

let me add that as far as computers go, usually the logic of a problem is more difficult for students than the actual math. for instance, I run across students (more often than I like) who are capable of understanding fairly sophisticated calculations so long as they are step-by-step, but throw in anything conditional (where they have to keep two potential program flows in mind, as opposed to one actual program flow, or figure out the behavior of a conditional loop) and they get lost. heck, I have students are in a world of hurt trying to parse out a phrase like:

if ((var1<var2 && var2<var3) || var1>var3) ...

they just don't seem to be able to track the ORs and ANDs.

maybe get them to program a craps game - not too difficult, good conditionals and some basic statistics, and they'll find it entertaining... :)

Here's one you could create lots of variations on:

If the probability of making a coding error is XX per hour of programming, and the probability that any given error will not be detected until after the final release is YY, how many undetected errors can be expected in an application that required ZZ man-hours of programming?

You could also do something similar with network security: If a hacker with a certain skill level can expect to find XX flaws in YY hours of searching, and the probability of a flaw being exploitable is ZZ, what are the odds that they will find an exploitable flaw if they pull an all nighter? That ought to hold their attention. ;)

the programming one and the hacker problems are good examples and a good use of probability. Thanks...

I want to thank everyone for their advice on math examples. The students really love the computer examples that involve summation and permutation in relationship to networking. I will be teaching the same course next quarter so if you have examples or come up with examples, please post so that I have them available for them. It is really appreciated.