Another Question for Computer Programmers :)

[GoldenRatio]

I just completed Intermediate Programming (C#) this last quarter. During the quarter some of the topics we covered were recursion and search/sorting algorithms. On the final our teacher asked us (written out on paper) to write a few different abstract methods using what we learned in algorithms. Normally, I do just fine on tests, but when asked to take a dynamic approach to this problem, I was highly confused and unable to fully answer it in the time given. The way I studied for the test was by memorizing each algorithm, but this did not seemed to help (which really confused me because I have no issues with math or physics). Would any of you recommend helpful ways to study, as to hopefully overcome this default in my thinking, or is this something I am stuck with? During fall quarter I am taking advanced programming and want to be better prepared so that I am very comfortable with these. I should also state that I will be essentially redoing a lot of the problems in our book, so my intentions are to practice practice practice.

 

[pacman]

When it comes to programming, practice, practice, practice is the way to go. In terms of memorization for a class, it's probably best to memorize function prototypes/type signatures and maybe the general idea of an algorithm. Take the quicksort for example. A quicksort of an empty list is an empty list. A quicksort of a finite and non-empty list a qucksort of all of the items less than or equal to the first item in the list plus the first item in the list plus a quicksort of all items greater than the first item in the list. From this implementing a quicksort should be easy and I will give an example in C and python. I'm using dots since it appears that the forum software removes indentation.

C: (using a list of integers)
void quicksort (int *list, int size)
{
int *smaller, *larger;
int nsmall, nlarge, i, pivot;
if (size){
....smaller = (int *)malloc(size*sizeof(int));
....larger = (int *)malloc(size*sizeof(int));
....nsmall = 0;
....nlarge = 0;
....pivot = *list;
....for (i = 1; i < size; i++){
........if (*(list + i) <= pivot){
............*(smaller + nsmall) = *(list + i);
............nsmall++;
........} else {
............*(larger + nlarge) = *(list + i);
............nlarge++;
........}
....}
....quicksort(smaller, nsmall);
....quicksort(larger, nlarge);
....for (i = 0; i < nsmall; i++)
........*(list + i) = *(smaller + i);
....*(list + nsmall) = pivot;
....for (i = 0; i < nlarge; i++)
........*(list + nsmall + 1 + i) = *(larger + i);
....}
}

Python:
def quicksort(numbers):
....if numbers == []:
........return []
....else:
........pivot = numbers[0]
........smaller = quicksort(filter(lambda x: x <= pivot, numbers))
........larger = quicksort(filter(lambda x: x > pivot, numbers))
........return smaller + [x] + larger


When I took C programming, I studied by making my own problems and then solving them.

 

[Loomis]

Golden Ratio: your atavar puzzles me. Why is the integral of e to the -px power and equal to the inverse of p squared called a golden ratio?

 

[GoldenRatio]

Golden Ratio: your atavar puzzles me. Why is the integral of e to the -px power and equal to the inverse of p squared called a golden ratio?

Haha, that is very confusing and I did not even see it as such. I'm sure you know it is a Laplace Transformation. I should actually use an avatar that is fitting to my title, would make a lot more sense

 

[Loomis]

Haha, that is very confusing and I did not even see it as such. I'm sure you know it is a Laplace Transformation. I should actually use an avatar that is fitting to my title, would make a lot more sense

Thank you. No I did not recognize it as a Laplace Transformation. My calculus skills are rusty.

 

[GoldenRatio]

When it comes to programming, practice, practice, practice is the way to go. In terms of memorization for a class, it's probably best to memorize function prototypes/type signatures and maybe the general idea of an algorithm. Take the quicksort for example. A quicksort of an empty list is an empty list. A quicksort of a finite and non-empty list a qucksort of all of the items less than or equal to the first item in the list plus the first item in the list plus a quicksort of all items greater than the first item in the list. From this implementing a quicksort should be easy and I will give an example in C and python. I'm using dots since it appears that the forum software removes indentation.

When I took C programming, I studied by making my own problems and then solving them.

Thank you very much for the advice. I never thought to make up my own problems. Sometimes the simplest things elude me. I also noticed you referenced Python, do you find this an easier language to work with? I downloaded 2.7 but, have yet to use it. So far, my experience with programming is limited to Java and C#.

 

[pacman]

Thank you very much for the advice. I never thought to make up my own problems. Sometimes the simplest things elude me. I also noticed you referenced Python, do you find this an easier language to work with? I downloaded 2.7 but, have yet to use it. So far, my experience with programming is limited to Java and C#.

I do find python a lot easier than C. Most people do. In C, you have to do a a lot of things that python does under the hood for you (mainly memory allocation type stuff). The main downside to python is that it is not compiled and is thus slower. It's still a highly useful language and there are professional researchers who use it for work.

A site with math oriented programming problems is projecteuler.net. I like that site.

 

[GoldenRatio]

I do find python a lot easier than C. Most people do. In C, you have to do a a lot of things that python does under the hood for you (mainly memory allocation type stuff). The main downside to python is that it is not compiled and is thus slower. It's still a highly useful language and there are professional researchers who use it for work.

A site with math oriented programming problems is projecteuler.net. I like that site.

I just signed up for the projecteuler. This looks like a lot of fun, lol. For our midterm (and practice), our teacher had us write out a bunch of small methods to calculate problems like this. Really enjoy that stuff.

 

[pacman]

Quick quiz:
While the C version of quicksort I wrote works, it actually has a pretty huge problem. What is it?

 

[GoldenRatio]

Quick quiz:
While the C version of quicksort I wrote works, it actually has a pretty huge problem. What is it?

When I get home tomorrow I will sit down and take a look at this!!

 

[GoldenRatio]

Quick quiz:
While the C version of quicksort I wrote works, it actually has a pretty huge problem. What is it?

Well, I guess I have a question first about the language before I proceed. Are you allocating two list's with malloc, one for larger and one for smaller?

if (size){
....smaller = (int *)malloc(size*sizeof(int));
....larger = (int *)malloc(size*sizeof(int));
....nsmall = 0;
....nlarge = 0;
....pivot = *list;

This is my first time using quicksort, so I am going through and creating my own in C# and comparing it with yours. I do not want to make a comment on something that is only a difference of language and not the problem you are referencing. One thing that is standing out to me now is that you only increment (++). For example, separating the array to sort into two subarrays, increment one subarray, and decrement the other.

 

[pacman]

Well, I guess I have a question first about the language before I proceed. Are you allocating two list's with malloc, one for larger and one for smaller?

if (size){
....smaller = (int *)malloc(size*sizeof(int));
....larger = (int *)malloc(size*sizeof(int));
....nsmall = 0;
....nlarge = 0;
....pivot = *list;

This is my first time using quicksort, so I am going through and creating my own in C# and comparing it with yours. I do not want to make a comment on something that is only a difference of language and not the problem you are referencing. One thing that is standing out to me now is that you only increment (++). For example, separating the array to sort into two subarrays, increment one subarray, and decrement the other.

I am allocating two arrays the size of the initial array. Not only that, I am not freeing the memory when I am done. To top it off, the memory complexity of my implementation kind of sucks. Quicksort has great time complexity, but not so great memory complexity. I was really illustrating a proof of concept, as opposed to go for the most optimized solution.

In the places where I increment, I am tracking the size of the two arrays. Decrementing wouldn't make sense there. C arrays aren't like C++ vectors in the sense that there are member functions that do things like tracking size. You have to do that yourself.

 

[GoldenRatio]

I am allocating two arrays the size of the initial array. Not only that, I am not freeing the memory when I am done. To top it off, the memory complexity of my implementation kind of sucks. Quicksort has great time complexity, but not so great memory complexity. I was really illustrating a proof of concept, as opposed to go for the most optimized solution.

In the places where I increment, I am tracking the size of the two arrays. Decrementing wouldn't make sense there. C arrays aren't like C++ vectors in the sense that there are member functions that do things like tracking size. You have to do that yourself.

Ahhh. I have to do more reading on this, in regards to C. I appreciate the help! My friend and I are taking advanced programming this fall together. We are going to get together after summer quarter and work on the algorithms posted on projecteuler.