The Big Programming Thread - Page 808

On December 03 2016 01:34 travis wrote:
I scored a 64 / 70 on my last exam. yay!

I did miss one question though and I want your opinions on it.

The question was about bucket sort.

It specified "Given a range greater than N and uniform distribution", what is the big O complexity for average case and worst case.

Average case I put O(n), which is correct.
Worst case, I know is typically O(n^2) for bucket sort.

However, we never really went over this term "uniform distribution". At least not in detail, and it was never stressed. I assumed that meant that it meant that the elements were distributed equally among the buckets. But apparently it's a statistics term and that's not what it means, it just means that the probability for distribution within the range was equal.

So, during the test, I went back to this question and stared at it for like 5 minutes. I was like "uniform distribution.. uniform distribution...". And finally I put O(n) based on my assumption.

Today in class the professor pretty much threw out a disclaimer about this question. So, I assume lots of people got it wrong. He explained what uniform distribution means. But he isn't going to give points to people who put O(n). It seems unfair. Should I say something to him about it?

On December 02 2016 22:39 tofucake wrote:
that guy doesn't work at google though :|

On December 03 2016 02:12 Acrofales wrote:

Not sure how old you are and what requirements are for your course, but where I went to school, uniform distribution was taught at high school, so uni professors were allowed to assume you knew that stuff.

However, I'm confused. The O(n^2) worst-case for bucket sort is, insofar as I remember, when your data is NOT uniformly distributed, but has clusters. If your data is uniformly distributed, then bucket sort works in O(n) time (technically I think O(n + m), with m the number of buckets), because it can neatly distribute it in buckets.

EDIT: wait, what was the exact wording? Because if the wording was "distributed according to a uniform distribution", then you have a *chance* of clustering. And thus, worst case scenario is taking that chance of clustering into account. However, if it says "uniformly distributed" then you already know they are uniformly spread over the range.

On December 03 2016 08:14 Nesserev wrote:
For the worst case, the uniform probability distribution of the key values doesn't actually matter. Regardless of the probability distribution, the worst case is always the same, and it's always O(n²). It does make the worst case more improbable, but the worst case is almost always very improbable. That's not the point.

However, the uniform probability distribution of the key values is very important for the average case. If it wasn't uniformly distributed, the average case would not be O(n), but probably be O(m²), where m is the size of the bucket with the most elements.

On December 03 2016 08:43 Nesserev wrote:

No, the question is fine.

That's the thing though. Talking about worst case O, is very often nitpicking.
Quicksort has worst case O(n²)... that doesn't stop anyone from using it.

On December 03 2016 08:43 Nesserev wrote:

No, the question is fine.

That's the thing though. Talking about worst case O, is very often nitpicking.
Quicksort has worst case O(n²)... that doesn't stop anyone from using it.

On December 03 2016 08:43 Nesserev wrote:

No, the question is fine.

That's the thing though. Talking about worst case O, is very often nitpicking.
Quicksort has worst case O(n²)... that doesn't stop anyone from using it.

On December 01 2016 02:09 Prillan wrote:

Maybe I'm stupid, but how would you implement a weighted graph using the above definition of an adjacency list?

import java.util.LinkedList;
import java.util.List;

public class DirectedGraph {

    private List<Edge>[] edges;

    public DirectedGraph(int V){
        this.edges = (List<Edge>[])new Object[V];
        for (int i = 0; i < V; i++) {
            this.edges[i]  = new LinkedList<>();
        }
    }

    public void addEdge(int v, int w, int weight){
        edges[v].add(new Edge(v,w,weight));
    }

    public Iterable<Edge> adj(int v){
        return edges[v];
    }

}

class Edge{

    private int weight;
    private int v;
    private int w;

    public Edge(int weigth, int v, int w){
        this.weight = weigth;
        this.v = v;
        this.w = w;
    }

    public int getWeight(){
        return weight;
    }

    public int either(){
        return v;
    }

    public int other(int o){
        if (o == v) return w;
        else return v;
    }
}

On December 03 2016 09:16 BluzMan wrote:

Anything that allows ambiguity is not fine, and arguing against ambiguity here is very hard since many people made the same "mistake". The whole O(n) notation has been invented to be useful and nothing else. Applying it in a way that doesn't produce useful answers is a cargo cult, bad practice, teaching that is even worse.

Worst case analysis needs to answer the question "what pathological, but realistic data do I have to be aware of?" In practice "realistic pathological" often equals "malicious" and worst case analysis is mainly a form of DOS protection. There's no way to produce a malicious but uniformly distributed data that would crash bucket sort down to quadratic, because it wouldn't by definition be uniformly distributed. If your distribution guarantee is actually coming from somewhere (a statistics test, for instance), there's no way to DOS your code.