mojo666's Profile User Rating: -----

Reputation: 374 Architect
Group:
Expert
Active Posts:
811 (0.39 per day)
Joined:
27-June 09
Profile Views:
12,473
Last Active:
User is offline Yesterday, 02:06 PM
Currently:
Offline

Previous Fields

Country:
US
OS Preference:
Windows
Favorite Browser:
Mozilla
Favorite Processor:
Who Cares
Favorite Gaming Platform:
PC
Your Car:
Who Cares
Dream Kudos:
0
Expert In:
Computer Science

Latest Visitors

Icon   mojo666 has not set their status

Posts I've Made

  1. In Topic: Formal Theory of Complexity Analysis in Specific ProgrammingLanguages?

    Posted 22 Mar 2015

    Quote

    The thing is that "the number of steps the algorithm will take" and "input parameter" are too abstract for most problems. For instance, it assumes we are dealing with an imperative language, that has a sequence of "steps" that the program can follow.

    Can you provide an example? The best I can think of are declaritive languages that aren't used for implementing algorithms. Rather they use prebuilt algorithms to accomplish specific tasks (SQL, XSLT). Analysis cannot be done in such cases...which has caused quite a bit of problems for me.

    Quote

    Second, it assumes you can easily define what the "input parameter" is, which at times may be almost impossible (specially if it's not a real number/integer/natural)

    If I don't know what the input is, how can I even write a program?

    Quote

    This program above is the easiest program ever, but when you deal with other complexities, specially ones that are inherent to a specific model of computation, or programming language (like recursion, side effects, mutability, and even something as simple as dynamic conditionals) trying to do a "direct argument" is not feasible.

    What can we do with an implementation that we cannot do with an algorithm. Big-o is fine for all the things you listed. You are coming up with a function that tells you how many times the program repeats basic tasks with varying input. We are basically asking "how long will my algorithm run as the input gets bigger" or "Will my program still be effective when I have twice as many customers/vendors/users/products/etc".

    Quote

    Is this ideal? This assumes your problem has a nice mathematical abstraction to it (graphs, matrices, vectors, etc). What if it doesn't?

    Then you can't write an algorithm or a program for it.

    Quote

    So in the end, you would still need to have a 2nd auxiliary analysis of your implementation, to see whether it checks with the "ideal algorithm complexity" or not.
    Why not cut the middle man and do the analysis right there on the "implementation"?


    You can't write a program (implementation) before you have an algorithm. If the implementation is failing, you now have to see if it is a problem with the implementation or the algorithm, which means you need to perform analysis on the algorithm anyways. If it turns out the algorithm sucks, then you just wasted a lot of money having a programmer working on a fruitless idea. You can get away with this for simpler problems, but you seem to be implying more complex problems.

    Quote

    Or straight up define a new system to analize the complexity of programs....Forget about Big O, we'd be talking about a completely new system here....That kind of tutorial is what I'm talking about. It is specifically discussing how to determine Big O for a specific programming language, it's not discussing it about how to do it abstractly. Almost all "Big O tutorials" do the same


    specific programming language (c++) implementation: for(int i=0; i<=n; i++){cout<<n;}
    "abstract": loop from 0 to n and print each number

    Analysis is the same process for both. Can you give an example of a problem that is drastically different between different programming languages or even the abstraction.

    Quote

    Imagine I'm a developer at Facebook. Now I have to find a way to get all the likes a user has, but only the likes of the 15 most popular friends he has, but only of those who have visited at most 2 pages who the original user has visited in the last 2 months.
    What is the input of this algorithm? As in, what is the "n" if this algorithm has O(f(n)) complexity?


    O(f(likes_u, pages_u, friends_u, pages_f[, likes_p])). Big-O can have multiple variables. For example, radix sort is O(k*n)

    Quote

    But I don't think it's ideal to try and blame the "problem" for not fitting into this nice little model, instead of modifying the model to make it adapt to the problem instead.


    What problem doesn't fit into the model?
  2. In Topic: left of '.value' must have class/struct/union

    Posted 20 Mar 2015

    "this" is a pointer so you have to use pointer syntax. this->value=value
  3. In Topic: Prime Factorization

    Posted 19 Mar 2015

    The name of the function is irrelevant. Call it "prime", "divisors", or even "myfun" but just pick a name and stick with it or you will confuse yourself.

    The algorithm is finding the first divisor (which is automatically prime) of the current input. It then divides the input by that divisor and passes the result into the recursion.

    myfun(int n) needs to print all prime factors of n

    myfun(144) should print "2, 2, 2, 2, 3, 3"

    myfun(144/2) should print "2, 2, 2, 3, 3"

    so, myfun(144) should print "2," and then call myfun(144/2)
    Alltogether, these actions print "2, " and "2, 2, 2, 3, 3,"

    That is all myfun(144) needs to do.

    Your version of the function does the following with input 144:

    print "2, " and call myfun(144/2) which is correct...but then you proceed to

    print "3, " and call myfun(144/3)

    print "4, " and call myfun(144/4)

    print "6, " and call myfun(144/6)

    print "8, " and call myfun(144/8)

    print "9, " and call myfun(144/9)

    print "12, " and call myfun(144/12)

    The first time you successfully find a divisor, you are done and need to stop the loop from moving on to the next one.

    Quote

    cout << n << " is a prime number \n";


    should just be cout << n;. This special case is basically for printing the last prime factor.
  4. In Topic: Prime Factorization

    Posted 19 Mar 2015

    You're check prime is incorrect. You need to print p when nothing divides it. you print if anything divides it.

    I think you might benefit if you take a step back and understand the algorithm. You are making an algorithm that will Print all prime factors of n. The algorithm accomplishes this by print smallest prime factor "i" and then Print all prime factors of (n/i). So, back to your code...

    void prime(int n) /**Prints all divisors of n**/     
    {  
        int result;  
        result = 0;  
    
        for (int i = 2; i <= sqrt(n); ++i)     
        {  
            result = n%i;  
            if (result == 0)  
            {  
                   
                cout << i << ",";  //The first i that divides n is guaranteed to be prime so you can print it.
                prime(n / i); /**Prints all divisors of (n/i)**/ 
                //Right now the algorithm should have printed everything you need, so you need to stop the for loop.
                //If n=12, we would print 2 and then call prime(6) which itself should print 2 and 3.
                //As written, if n=12 this loop will call prime(6), prime(4), prime(3), and then prime(2) as well as printing corresponding "i" values.
            }   
        }
        //the above will take care of everything except the special case where n is a prime number and has no divisors
        //you need to add code to print n if it was not divisible by any "i" in the loop.
        //this can be a check prime function or you can just add some flag in the above for loop that gets set when result==0 and print n based on the value of the flag.
    } 
    
    
  5. In Topic: Prime Factorization

    Posted 18 Mar 2015

    View Postpatriotaki, on 18 March 2015 - 11:26 PM, said:

    I need to find the numbers that when you n%i is equal to 0 . Then if you multiply those numbers you get the n number.

    how can i do this ?


    You already have the algorithm. You just need to implement it correctly. For example, see comments.

    #include "std_lib_facilities.h";
    
    void prime(int n) /**Prints all divisors of n**/
    
    {
    	int result;
    	result = 0;
    	
    
    	for (int i = 2; i <= n*n; ++i)// This loops from 2 to n squared.  You are supposed to loop to sqrt n.
    	
    	{
    		result = n%i;
    		if (result == 0)
    		{
    			
    			cout << i << ",";
    			prime(n / i); /**Prints all divisors of n/i**/
    			//At this point you need to stop the for loop since the recursion will print all other divisors
    		}
    		//and what if there are no divisors for the current input?
    	}
    	
    }
    
    

My Information

Member Title:
D.I.C Addict
Age:
30 years old
Birthday:
July 23, 1984
Gender:
Interests:
Chess, math, computers, AI
Years Programming:
6
Programming Languages:
C++, C#, VB.net, SQL, OCAML, LISP, MIPS

Contact Information

E-mail:
Private
Website URL:
Website URL  http://

Friends

Comments

mojo666 has no profile comments yet. Why not say hello?