/sci/ - Science & Math

>>7043437
Been out of college over 6 years and did no programming since so relearning as I go, any such advice would be appreciated.

>graduate course in computer science
>doing an introductory course to algorithms

What is this?
What the fuck is this?
Are American graduate courses normally designed for children like this who don't even have rudimentary undergraduate knowledge of the course they're studying?

This can't be normal.

There's no way to understand completely except by doing. I recommend doing a few steps of each sort by hand to see what's going on.

Numerical Recipes is your friend.
> http://www.nr.com/
The C version is free and will be more or less compatible with your C++ stuff.

>>7043464
Fair point, but as stated had knowledge and lost it due to mental erosion of time spent not programming. Passed the intro to program test (P/F).
That said, being a math background I get the algorithms a bit better atm than the csci students but not the background they're coming from.

>>7043467
Thanks

>>7043464
Often, you can get into grad school in any subject as long as you have some related background in another subject. So math to comp sci is reasonable if OP intends to, for example, develop computational methods for automatically analysing group structures.

Your first year will be sort of a catch up year, doing basically four years' worth of undergrad comp sci in one year. (As a grad student, this should be reasonable to achieve.) You don't get credit toward your graduate requirements for these courses. But you're doing other things in this time, like writing your thesis proposal and doing your background research, so it's not all lost time.

Before you go on about how stupid this is, realize that this is the only reasonable way to get cross-disciplinary work done. It's not unique to America, but occurs worldwide.

>>7043437
Isn't this covered in the undergrad complexity/data structures/algorithm courses?

>Try doing it by hand.
>Look at youtube videos that step through it.
>Go to coursera and sign up for the algorithms course so you can access their lectures. The lectures give an explanation of each sort, step through some examples, and then show how to calculate the runtime using empirical methods (granted you will actually be more interested in using asymptotic analysis instead of empirical analysis).
>Read through the Algorithm Analysis chapter chapter of Shaffer's data structures book (the PDF is free but you can also buy a cheap Dover copy). Note that the way Shaffer does it will probably be simpler than the way you are doing it in your class since you are probably computing them by using limits. However, you can easily prove that all of the properties Shaffer provides actually hold and then use that approach.
http://people.cs.vt.edu/shaffer/Book/
>Look at the wikipedia pages for each sort.
>Implement some of them. Note that many of these algorithms have multiple different implementations. Some implementations are shorter and easier to write and others are longer but easier to understand. In particular, if you don't have an intuition for recursive programming then maybe avoid the recursive implementations of those algorithms.
>If all else fails search for random lecture notes and slides on the subject and in the meanwhile implement everything using sleep sort.
http://www.cs.princeton.edu/courses/archive/fall13/cos226/lectures/52Tries.pdf

>>7043477
>being a math background I get the algorithms a bit better atm than the csci students
>can't figure out sorting algorithms
>mfw
Dude sorting algos are babby shit.

>>7043437
why are you learning level 2000 undergraduate stuff in graduate school classes?

stackexchange and github has every piece of code you could ever want. or just google "insertion sort algorithm c++" and one of the top five links will give you the code and explain it to you.

>>7043437
Insertion: Consider the first m elements to be sorted, and insert the m+1st element in them by moving all the elements higher then the m+1st element down and then putting the m+1st element in place. For m from 1 to n-1.
Selection: Find the smallest of the m remaining elements and swap it for the n-mth element. For m from n down to 1.
Bubble: you say you understand this; super
Shell: Ignore it, everyone else does
Merge: You say you understand this; super
Heap: You won't really understand this without understanding the heap data structure. If you understand this, then the rest will follow.
Quick: Take the first element out and consider it the "pivot". Imagine one person going up from element 1 and another going down from element n; when the first person finds an element greater than pivot they pause; when the second person finds an element less than pivot they pause; when both are paused, they exchange elements then resume; they meet at some random point in the array; that's the right place for the pivot, so drop it in there and then sort what comes before and what comes after recursively.

Sorting is just dancing, and you can train a monkey to dance.
https://www.youtube.com/watch?v=EdIKIf9mHk0&list=PLOmdoKois7_FK-ySGwHBkltzB11snW7KQ

Also seconding numerical recipes.

>insertion sort
Sorted partial list, add next element where it belongs in that list, repeat
>selection sort
Find the n-th smallest and place it in spot n
>bubble
Repeatedly fix the order of the elements. Notice that the last place you stop swapping in each iteration marks where the list is full sorted and don't rescan it.
>merge
Repeatedly divide till you get singlets. Merge 2 lists at a time by going linearly in the order of the 2 list's smallest elements.
>heap
Put them into a heap and balance it
>quick
Pick an element as a pivot and put everything smaller to the left and bigger to the right. Repeat on both sides

>>7043467
>There's no way to understand completely except by doing

Retard detected. Sorting algos are simple as fuck.

>>7044397
>Romanian

Get the fuck out you filthy gypsy

>>7044451
They give the slowest algos to the romanian and gypsy dances.