Win a copy of Programmer's Guide to Java SE 8 Oracle Certified Associate (OCA) this week in the OCAJP forum!

# Advice requested: Data Structures and Algorithms in Java

M Burke
Ranch Hand
Posts: 406
I signed up for a class on this subject and picked up the book today.

I notice there is....math involved.

I have not taken a math class in many years, so I wonder how concerned I should be over this. The school has no math prerequisite to take this class.

This is the course description:
Implementation, application, and analysis of algorithms on a variety of data structures, including lists, stacks, queues, trees, and graphs. Algorithmic analysis includes computation of running times, theta notation, propositional and predicate logic, inductive proofs, and solution of divide-and-conquer recurrences.

Rahul Devgan
Greenhorn
Posts: 24
I hope the following site will be of help:

http://www.brpreiss.com/books/opus5/html/book.html

M Burke
Ranch Hand
Posts: 406
Well, I understand programmable things like linked lists and trees. What I don't get is the math behind it.

Robert Hill
Ranch Hand
Posts: 94
Big O and time complexity are not very difficult mathematically. Simple arithmetic. It is just a way to judge effiency of an algorithm without factoring in outside concerns, like hardware, and operating systems.

Logic and induction, which is a large part of the foundation of mathematics, is not all that difficult either. If you can understand basic logic principles, you should be ok. Recursion is very closely linked to induction. To get a small taste of induction, google for inductive proofs of simple series and sequences like factorials, fibonacci or towers of hanoi. They are simple, but likely are things you will see at this level of coursework. It is just basic logic and recursion. Google Big O notation as well. It should ease your mind a tad.

Other then analzying the data structures, there is not a whole lot of math to worry about.

Well, I understand programmable things like linked lists and trees. What I don't get is the math behind it.

That is like saying you understand math, but not proofs, which is very contradictory. Understanding the mathematics of computer science(Calculus, proofs, linear algebra, ect) can only help you. Have you ever written a data structure, or have you always relied on API's to do the work for you?

Data Structures is a very important topic, and I think anyone who calls themselves a programmer should know how to write efficient implementations of them. Even if you never need to write them in the real world, it will make you a better programmer. Same thing goes for higher level, more mathematically intensive courses like finite state automata, compilers and programming languages. Certificates are fine and all, but they don't give you the breadth and scope that you can get in a formal setting.

I know I ranted a bit, and I apologize, it is disheartening to see so many people in the industry who lack the theoretical knowlege of computers and the mathematics, they dip their toes in and get a certificate or two and call it good, so I tend to ramble on a bit more then necessary. It is nice to see someone diving in.

Paul Clapham
Sheriff
Posts: 21316
32
Well, based on that description I would say there's no math prerequisite because the math is all pretty straightforward. You're going to have to know what a polynomial is, and what an exponential function is. Nothing nearly as complicated as calculus. I would say, if you don't even know those things then the instructor should be able to get you up to speed in a few minutes.

(Disclaimer: I have an advanced degree in mathematics, so obviously it looks easy to me. But I still think that if you are a competent programmer then you should have the right kind of mind to deal with that sort of math.)

Henry Wong
author
Marshal
Posts: 21390
84
I am assuming that you are not going for a computer science degree. Not trying to insult you, just implying from the question that the "data structures" class is not a requirement, as you have an out. For comp sci, the advice would be moot, as the course would be required. Maybe it is an engineering degree?

Anyway, as everyone else said, the math is minor. Certainly minor compared to some of the math involved in more complex classes like encryption algorithms, process controls, or graphics.

But my advice is this, even if you have an out, don't drop the class. Classes like Servlets and EJBs, would be useful to you til say, something else better comes along. The Data Structures and Algorithm class teaches you the basics and gives you some experience that could be useful to you forever.

Henry
[ March 21, 2006: Message edited by: Henry Wong ]

Steve Fahlbusch
Bartender
Posts: 605
7
Do yourself a favor. Talk to the Professor/Instructor. Ask them what they want you to know, math wise, for the course. Very few teach directly to the text, the have items they want you to know.

It maybe simple stuff, like approximation of O() or it maybe more complex where you will be expected to evaluate the O() of recursive algorithms using the Masters Therom (probably not as this is both an algorithms and data structures class, but just ask - you be more at ease, your instructor will know at level you are and just might make sure to introduce the necessary math background in the course).

Also, you will probably find that the most difficult math will be proof by induction, but most DS instructors cover this, so again ask. You have nothing to lose but your doubts.

-steve

M Burke
Ranch Hand
Posts: 406
Thanks for all the advice. I will see if I can talk to the instructor.

This class is a prerequisite for the Masters in CS. They have no math requirement.

I have a BS in Management, so I am light on academic-based tech. But I have a strong background in applied software development in the real world. I understand the principals of programming. I build my own linked lists (In C) and other data structures. I understand memory and how to build collections. So it's a matter of cross-referencing the math to the actual algorithms I have been writing for years. So I understand the concepts, I am just not familiar with the mathematical notation.

I wonder if there is a "primer" I can use to get up to speed.

Robert Hill
Ranch Hand
Posts: 94
Maybe I am just misunderstanding. You are going into a CS masters program that doesn't require a solid mathematical background? Run far away.

It sounds like the much lighterweight CIS programs will be more up your alley, given your background.

M Burke
Ranch Hand
Posts: 406
Well, this is the program. DePaul has a good rep. I could also do the Software Eng option to.

M Burke
Ranch Hand
Posts: 406
Would someone tell me what I need to go over to get up to speed on the math?

I see some functions in the book called 'log', and 'f(n)'and 'O(n)'.

College algebra? Trig? Calculus? Statistics?

Henry Wong
author
Marshal
Posts: 21390
84
Originally posted by M Burke:
Would someone tell me what I need to go over to get up to speed on the math?

I see some functions in the book called 'log', and 'f(n)'and 'O(n)'.

College algebra? Trig? Calculus? Statistics?

It's not that bad, it is actually more notation than math...

f(n) basically means a function (an algorithm) that processes n values.

O(n) is the "order of n" -- which is some way to measure of the "timing" of an algorithm.

For example, if you have an algorithm, f(n), that has an order, O(n), that is equal to n^2... it means that if you double the number of values, it will take 4 times longer to process the values through the algorithm.

If the order is n, then when you double the number of values, it will take twice as long to process. And if the order is n * log(n), it will be a value somewhere in between.

Henry

Rusty Shackleford
Ranch Hand
Posts: 490
log = logarithm = inverse of exponential functions. In big O notation, base 2, not 10.

In general log notation:

10^3 = 1000 is written in log notation as log 1000 = 3, and there is an implicit 10 as a subscript right after log.

I am a CS major(senior), and if you want to get a masters in CS, I would strongly recommend getting a strong mathematical background. For you class, simple logic and algebra will suffice, but you will likely need much more for other classes. How much depends on your actual course of study. You might want to consider having a chat with the masters advisor to see what you need to know and what classes you should take to fill the void. CS is a mathematical discpline, not as much as physics or engineering, but you still need a good math background.

My program requires a minor in math, as do most CS programs that I have seen, or at least close to a minor. For me that means 3 calculus courses, 1 linear algebra, 1 statistics(calc based), and a very weird and tough class that taught proofs while learning basic advanced mathematics and its foundations: set theory, relations, functions, cardinality, and a bit of abstract algebra. I have seen others require a similar class, but not as mathematically rigorous, my school calls it discrete math. I have also seen differential equations as a requirement.

Like I said, talk to your counselor and see what you will need. Your grades and sanity may depend on it.
[ March 21, 2006: Message edited by: Rusty Shackleford ]

Steve Fahlbusch
Bartender
Posts: 605
7
Go back and look at the BS in computer science. I found that it had four math courses: decrete math I and II and calc I and II. It is a safe bet that you are expected to know the concepts from those courses.

And again talk with the professor - A little over a year ago, I was taking the Graduate Level algorithms course (part of the courses needed for my phd - but this was the masters level course) and since it had been a little while ~20 years since I had taken an algorithms course, I also sat in on the undergraduate course. -- the take-away here is that we used the same book.

But as one would expect, the math efforts for the two courses were dramatically different.

Another course I took Networking - the text was again the same as the undergraduate course, but it was just background material for us (we were expected to know all the concepts from the text) we spent all of our time on current research papers on high speed routing, QoS, IPv6 and the like.

So, don't anticipate the content of the course based on the text.