CS 251 Data structures ( OR ECE 368 OR EE 368 ), and one of ( MA 265 OR MA 350 OR MA 351 OR MA 262 OR MA 272 OR STAT 350 OR STAT 511 )

If you are an undergraduate student at Purdue, then you may enroll in CS 355 if and only if you have taken these courses (and passed them).

To succeed in CS 355 you will need the following knowledge and skills:

Arithmetic: Know what even and odd integers are. Understand the mod function and greatest common divisor. Understand divisibility (of integers) and the division algorithm with quotient and remainder. Know about prime and composite numbers and factoring (small) integers. Know about positional number systems: binary and decimal, at least, and arithmetic with such numbers.

Calculus: Can integrate and differentiate polynomials, e^x and log x. Can find extreme values of functions. Can graph functions and find lines of symmetry.

Probability: Understand equally likely events, mutually exclusive events, conditional probability, coin tossing, dice, the standard deck of playing cards, random variables, probability distribution functions, mean, median, uniform distribution, factorial, binomial coefficients.

Linear algebra: Can multiply matrices. Can solve n linear equations in n unknowns by an efficient algorithm. Understand vectors: addition, scalar and dot products.

Data structures: Understand trees, traversals, Huffman codes and logical bit operations: AND, OR, NOT, EXCLUSIVE-OR.

Analysis of algorithms: Know big-Oh, big-Theta and big-Omega notations for asymptotic time and space complexity as a function of input size. Know how to sort n things in O(n log n) time. Understand deterministic versus probabilistic algorithms. Have heard of polynomial time (P) algorithms, NP-hard and NP-complete problems. Can see easily what this function does and find its time complexity:

real f(real x, positive integer n) {
real y, z; integer m;
y = 1.0;
z = x;
m = n;
while (m > 0) {
if ((m AND 1) == 1) y = y*z;
z = z*z;
m = floor(m/2);
}
return y;
}