a huge favor plzplzplz

dr. carbon · #1 09-16-2011, 03:46 AM

I know there are a lot of programmers in the community, and I was wondering if someone could give me some quick help.

I'm taking ap compsci with data structures and i would like someone to give me a nice definition and explanation for big O, pointers, and linked lists. Plz no wiki pages or anything, I want a more understandable definition, and I would appreciate it if code used to explain the concepts were in Java.

I really need this!!1 (I must get a 100% on my next test!)

Any help is appreciated

malakas · #2 09-16-2011, 03:59 AM

you want help with a big O?

dr. carbon · #3 09-16-2011, 03:59 AM

The Big O Measure for runtime

malakas · #4 09-16-2011, 04:00 AM

so you want someone to help you measure the duration of the big O?

mikesol · #5 09-16-2011, 04:14 AM

For big-o basics I'd strongly encourage you to read this: http://rob-bell.net/2009/06/a-beginn...ig-o-notation/. It's a super simplistic - super easy to understand guide that you should be able to understand.

As far as pointers go - Java doesn't really have pointers in the way that C++ does. You don't really define a pointer to some data location - Java does all the work for you. What's your question with this? Do you not understand what a pointer is?

Linked lists are a little bit more complicated. I don't think code will help you out too much here but if you're interested a simpler version of a linked list in java can be found here: http://stackoverflow.com/questions/1...d-list-in-java. Java has a wonderful built-in linked list class that you should use if you ever wanted to use a linked list.

For a good explanation of what a linked list *is* I'd check out this website: http://cis.stvincent.edu/html/tutori...sts/lists.html. It has some good pictures that really make it clear.

Hope that helps!

dr. carbon · #6 09-16-2011, 05:16 AM

Mike, thank you so much for your help!

By pointers, I meant I am sketchy with the concept as I am weak on the whole object oriented programming side of things.

Furthermore, my tests involve me writing code on paper, which I struggle at, while I am fine doing it on computer (esp. b/c i can test it and see what is wrong).

Can you please give me some advice on how to solve this problem?

Kennedy · #7 09-16-2011, 05:56 AM

Quote:

Originally Posted by malakas

so you want someone to help you measure the duration of the big O?

I lol'd for about a minute.

Tekn0 · #8 09-16-2011, 10:15 AM

Quote:

Originally Posted by dr. carbon

By pointers, I meant I am sketchy with the concept as I am weak on the whole object oriented programming side of things.

Do NOT confuse object oriented programming with pointers. It has nothing to do with pointers.

If you want to have a good idea of pointers start with basic, simple C tutorials.

C++ and C are *NOT* the same languages, if you know what happens under the hood and the details of the code emitted by C and C++ compilers you'll realize they are rather different.

Tekn0 · #9 09-16-2011, 10:22 AM

Quote:

Originally Posted by dr. carbon

Furthermore, my tests involve me writing code on paper, which I struggle at, while I am fine doing it on computer (esp. b/c i can test it and see what is wrong).

Over time while writing code you need to think like a compiler (or interpreter). This takes practise. There's no easy way around it. There are scenarios in real life where such a skill is useful.

Also, once you have a clear idea of what you're doing, briging it out on paper is more about language semantics. The algorithm should never be a problem to express.

Ribilla · #10 09-16-2011, 03:06 PM

I had to do a little of this on my firest year course, though with simplistic code. I don't think there are any quick fixes, you just have to imagine you are a single run of the code and see how that scales with the inputs.

If you can't manage that, then look for loops and loops within loops. Each loop gives you a factor of n on your big O, so a loop within a loop within a loop gives you an algorithmic complexity of n^3. For good examples, I would work through from first principals the complexity of sorting algorithms. Quicksort would be a good place to start.

dr. carbon · #11 09-17-2011, 09:58 PM

Hmm, I don't think i'm confusing it with obj. programming, I just need to now the concept of how pointers work b/c I am using an abstraction of Java right now which requires me to use pointers. Furthermore, for me to understand how link lists work, I need to know how pointers work.

@Rib, I know how the basic bigO cases work, I want to know how to test for the worst case since bigO tests for the upper bounds. My teacher did some algebra in the board for some examples to test for worst case, but i was completely lost.

Mt.Vesuvius · #12 09-17-2011, 10:37 PM

Quote:

Originally Posted by malakas

so you want someone to help you measure the duration of the big O?

Hahahahaha

lemon · #13 09-17-2011, 11:02 PM

Quote:

Originally Posted by dr. carbon

Hmm, I don't think i'm confusing it with obj. programming, I just need to now the concept of how pointers work b/c I am using an abstraction of Java right now which requires me to use pointers. Furthermore, for me to understand how link lists work, I need to know how pointers work.

@Rib, I know how the basic bigO cases work, I want to know how to test for the worst case since bigO tests for the upper bounds. My teacher did some algebra in the board for some examples to test for worst case, but i was completely lost.

Errr, you definately seem confused about some things, or terms at the very least. And as others have said, In Java you just can't work with pointers as such so your task can't possibly require you to use them. Maybe you could give us the actual task and then we could help you out better?

Tekn0 · #14 09-17-2011, 11:23 PM

Quote:

Originally Posted by dr. carbon

Hmm, I don't think i'm confusing it with obj. programming, I just need to now the concept of how pointers work b/c I am using an abstraction of Java right now which requires me to use pointers. Furthermore, for me to understand how link lists work, I need to know how pointers work.

Like I said before, start with C for pointers. The concepts of linked lists is extremely simple, don't worry once you learn it you'll be like "duh! this is so ez & yet cool!"

dr. carbon · #15 09-18-2011, 04:55 AM

@lemon I told you, i'm using an abstraction called javatown where its a little different.

dr. carbon · #16 09-18-2011, 04:56 AM

And I have no real tasks, just a test to take in a week.
Thanks for the help though, guys

dr. carbon · #17 09-18-2011, 05:23 AM

What are good methods of figuring out recursive algorithms without wasting time thinking through the whole process (my teacher tells me to avoid this), or is it just something people develop naturally.

All I do right now is 1) Identify base case and 2) figure out what changes every time, but I still struggle with this. Idk if this will simply be solved with more practice.

Boko · #18 09-19-2011, 03:07 PM

Lol, just as it happens I'm getting a course about algorithms this semester. Just wanted to say that the stuff in here actually helped me, because the teacher is a total retard who can't explain anything and just uses random powerpoint sheets he found.

Tekn0 · #19 09-19-2011, 03:46 PM

Quote:

Originally Posted by dr. carbon

What are good methods of figuring out recursive algorithms without wasting time thinking through the whole process (my teacher tells me to avoid this), or is it just something people develop naturally.

Don't worry too much about the recursive functions. In practice you will find many times, iterative implementations being preferred over recursive ones, mostly because of the call-stack memory overhead (unless they're implemented without using a stack frame for each invocation and provide sufficiently more clarity over other implementations).

Quote:

All I do right now is 1) Identify base case and 2) figure out what changes every time, but I still struggle with this. Idk if this will simply be solved with more practice.

With recursion there are 3 things:

1. Identify that the problem can be expressed as a function of itself.

2. Knowing when to stop the recursion.

3. Is it worth doing recursively in terms of performance (for now, for academic purposes you don't need to bother with this)

Start with simple recursive functions like Factorial and Quicksort. And over time you will be able to identify "similarity" that allows you to do things using recursive functions.

Sometimes for complex cases you will know only after you've written the code 90%... "Duh! wait.. i can do this recursively". It does take practice.

dr. carbon · #20 09-20-2011, 03:49 AM

Quote:

Originally Posted by Boko

Lol, just as it happens I'm getting a course about algorithms this semester. Just wanted to say that the stuff in here actually helped me, because the teacher is a total retard who can't explain anything and just uses random powerpoint sheets he found.

haha, I don't really understand my teacher very well either, and I have no idea what he teaches off, but I can't find it on the internet.

Boko · #21 09-20-2011, 05:17 AM

Quote:

Originally Posted by dr. carbon

haha, I don't really understand my teacher very well either, and I have no idea what he teaches off, but I can't find it on the internet.

It's not about the part that we don't understand what he's saying.. It's about the fact that he himself does not know what he's saying. He's just retarded.