ITT: Skwisgaar goes back to school

SheepHugger · Oct 25, 2014

Catch said: ↑

I don't know Skwi's age, but in my experience no one really cares how old a group member is so long as they're polite and involved.

Study groups should be primarily for study if most members are serious about their time in college. Unless you're on the same degree track as other members, you probably won't be building lasting friendships in a study group, just useful relations, so whatever hurdles might exist due to age gaps should be largely irrelevant.
Click to expand...

I agree. By college most people start to have some sense and the ones that don't by then won't likely be found in study groups. I really like the college/university atmosphere among students and the students themselves. It sort of feels like home.

If I got it right Skwi is 2 years older than me, I could be wrong though. I suppose he spoke about prospect of being 31 year old undergraduate in the original post. Kinda makes me ashamed of trying to give advice to him, I'm an infant by comparison.

Skwisgaar · Oct 25, 2014

I will be 31 in December.

SheepHugger · Oct 25, 2014

Skwisgaar said: ↑

I will be 31 in December.
Click to expand...

So you're 2 years and 3 months older than me, ye old geezer.

Dihm · Oct 25, 2014

OOOOOOOOLD. And yes, computer science. Determining time to execute various code, in this case, dealing with arrays, sorting, and partitions

Skwisgaar · Oct 25, 2014

Tuonela · Oct 25, 2014

Skwisgaar said: ↑

I will be 31 in December.
Click to expand...

I'm 8 months older than you

Lardaltef · Oct 25, 2014

Get off my lawn!

Dihm · Oct 26, 2014

This is the last question on my midterm, and how I answered it. If it looks code-y, that's cause I have to use TeXworks in order to manage all the fucking algorithms.

\paragraph{Problem 5 (25 points)}

Suppose there were three hunters who went to a private park to hunt rabbits.

At the end of the day, each hunter caught $n$ rabbits and knew the weight of every

rabbit he caught. Each hunter put the rabbits he caught on his truck bed sequentially according

to the weight of each rabbit.

When the three hunters tied to leave the park,

\textbf{the owner of the park told them that they could

only take half of the total rabbits they caught}. Assume that the monetary value of a rabbit is proportional to its

weight. In other words, the heavier a rabbit, the more valuable it is.

The hunters ask you to help to \textbf{develop an efficient algorithm

that allows the three hunters to determine which rabbits to take to maximize their profit}.

Please note that

\begin{itemize}

\item their goal is to maximize the total profit which will be equally shared

among them;

\item the total complexity of your algorithm does not need to include the time

for each hunter to sort the rabbits on his own truck.

\end{itemize}

\paragraph{Solution 5 \newline}

This problem provides us with three arrays that must be compared to provide the maximum return. We know that the size of all arrays are identical, at $n$. We also know the value of each number within the array, the weight of the rabbit $w$.\\

\paragraph{Assumptions: \newline}

\begin{itemize}

\item {All hunters caught the same number of rabbits, $n$}

\item {All hunters sorted their array of rabbits, but we do not know if they sorted from low to high or high to low}

\item {We can only keep $\lceil{\frac{n}{2}}\rceil$ rabbits}

\item {We have a fourth location in which we can hold rabbits as we compare them}

\item {We are a fourth party who is not able to talk to the hunters in order to know their method of sorting prior to execution}

\item {The weights of each rabbit have been recorded for us to access, and we don't manage to switch rabbits and weights accidentally. No human error}

\end{itemize}

Since we don't know how each hunter sorted and we aren't computers, we will attempt to make life easy for ourselves.\\

First, we compare the first and last rabbit in each array, to determine whether they are sorted from highest to lowest, or lowest to highest. We will remember which way the hunter sorted, so that we can either increment or decrement our selection.\\

Now, we create a new array (a holding area for rabbits) that is $\lceil{\frac{n}{2}}\rceil$ in length.\\

We take the largest rabbit from the first array (the first hunter) and place it within our "keep" array that we have just created. We place this rabbit into the array in order from highest to lowest.\\

Moving on to the next array, we take the largest rabbit, and place it within our new array, again sorting as we go. We do this again for the third array.\\

Now that one rabbit has been taken from each hunter and sorted into our keep array, we continue to loop through each hunter's array, sorting our list as we go.\\

We continue to fill up our keep array until it reaches its maximum number of entries. Once this happens, we begin to perform a delete operation on the final value within the array whenever an unsorted rabbit is encountered that needs to be entered into the keep array. The deleted rabbit is handed to the owner of the park\\

Once an array has a rabbit that is no longer entered into our "keep" array, we will ignore the remaineder of that hunter's rabbits. They will not be larger than the rabbits we already have decided to keep and can be handed over to the park owner.\\

This process continues until we reach a point where there are no more rabbits from any of the three hunters that can fill our catch.\\

\paragraph{Analysis: \newline}

\begin{itemize}

\item Our first execution will be $h$ comparisons, one for each array, or hunter. In this case, $h = 3$.

\item We now most through all $h$ arrays, selecting the first element. Each time we select an element, we are performing a linear sort on our keep array, $K$. The length of our keep array $= hi$ with a maximum value of $\lceil{\frac{n}{2}}\rceil$. It will take $i = \lceil{\frac{n}{2h}}\rceil$ iterations of this to fill our keep array.

\item We must perform a sort on our array $K$ each time we add a new rabbit. This will be a comparison sort, which we know has a lower bound of $\Omega(n\lg n)$

\item So far, $T(n) = 3+ \Omega(\frac{n}{6}(n\lg n))$

\item We now have our initial set of rabbits, but we have not ensured that some hunters did not have better days than others, catching rabbits of a larger size. We must continue through our $h$ arrays, comparing rabbits to array $K$.

\item We have $\frac{5n}{6}$ rabbits remaining that have not been compared. Since we are only keeping half of the rabbits, this leaves us with $\frac{5n}{12}$ remaining that we need to take into consideration.

\item Our worst case after all recurssive calls is now $T(n) = 3+ \Omega(\frac{n}{6}(n\lg n)) + \Omega(\frac{5n}{12}(n\lg n)) = 3 + \Omega(\frac{7n}{12}(n\lg n))$

\item At this point, the hunters have imbibed all of the beer, leaving none remaining for the lowly sorter.

\end{itemize}
Click to expand...

Wolf Clearwater · Oct 26, 2014

You got this bro, I just got my first associates degree last semester and was the graduation speaker. I am getting a second at the end of this semester. I was a high school dropout who quit to go work. I am 37, community college rules.

SteelBear · Oct 26, 2014

Dihm said: ↑

This is the last question on my midterm, and how I answered it. If it looks code-y, that's cause I have to use TeXworks in order to manage all the fucking algorithms.
Click to expand...

Some wordy ass shit about rabbits and beer.
Click to expand...

God damn min/maxer.

Hepatitis TK · Oct 26, 2014

SteelBear said: ↑

God damn min/maxer.
Click to expand...

jChopper · Oct 27, 2014

When I was an undergrad straight outta HS...I thought all the mature age students were douches. If I went back now, I would think all the young undergrads were douches. Conclusion : Anyone not in my age range is a douche!

Log in or Sign up

ITT: Skwisgaar goes back to school

SheepHugger Well Liked Viking

Skwisgaar XO Thrall

SheepHugger Well Liked Viking

Dihm Speaker of the Word Staff Member Gothi SC Thane

Skwisgaar XO Thrall

Tuonela Well Liked Berserker

Lardaltef Well Liked Berserker

Dihm Speaker of the Word Staff Member Gothi SC Thane

Wolf Clearwater Bullet Magnet Viking

SteelBear Veteran Dovahbear Viking

Hepatitis TK Decorative Flounce Berserker

jChopper Well Liked Berserker

Log in or Sign up

ITT: Skwisgaar goes back to school

SheepHugger Well Liked Viking

Skwisgaar XO Thrall

SheepHugger Well Liked Viking

Dihm Speaker of the Word Staff Member Gothi SC Thane

Skwisgaar XO Thrall

Tuonela Well Liked Berserker

Lardaltef Well Liked Berserker

Dihm Speaker of the Word Staff Member Gothi SC Thane

Wolf Clearwater Bullet Magnet Viking

SteelBear Veteran Dovahbear Viking

Hepatitis TK Decorative Flounce Berserker

jChopper Well Liked Berserker

Useful Searches