Posts by mrnutty

Should the proper output be 5?

>>Which array-based operations are O(1)?
>>inserting item or deleting item in unsorted array

not quite, what happens if we insert in the middle of the array. How about accessing the data?

>>Which linked-list operations are O(1)?
>>inserting and deleteing item in unsorted lsit
true.

>>Which array-based operations are O(n)?
>>traversing through the list or adding or deleting in a sorted array
its asking you about arrays, why are you mentioning lists?
Whats the difference from "adding" in an array then "inserting" in an array?
In general, inserting and deleting can take up O(n).

>>Which linked-list operations are O(n)?
traversing through the list or adding or deleting in a sorted list
true.

Bad choice of data structures. Go with std::map

>>I'm aware of the std::map container, and I had considered it. The problem is the strict weak ordering that it requires is not appropriate for the problem domain as the ordering is based on the first member of the pairs and I need the values sorted based on the second member of the pairs.

you can supply the map with a comparion function in its constructor. And can you explain why strict ordering would fail with your data set?

Also your problem is that member function pointer are very different from regular pointer function. With member function pointer you have to provide it with an instance. Try something like std::sort(v.begin(),v.end(),&(this->Descending))

>> if((node -> data %2) != 0)
bad coding. Make a bool isOdd(int n){ return n % 2 == 1; } function
and use it like so if( isOdd(node->data) ){ ...}

Ok, does the tower of happiness has all the happiness that I need ? Does it include megan fox in there? How about the best food in the world? How about a infinite power machine? So seriously, whats your problem?

try cout << setprecision(10); where you need to include iomanip as a header

Note: bool sayi[10] = {false}; will initialize the whole array to false. So there is no need for sifirla function. Its hard for me to understand your code.

I suggest you do something like the following :

int randRange(int min, int max){
 return rand() % (max-min) + min;
}

//returns a vector with unique random number int range [minValue,maxValue)
//the size parameter declares the size of the vector being returned
std::vector<int> generateUniqueRandom(int minValue, int maxValue, int size){
 assert(minValue >= 0 && maxValue >= 0);
 assert(minValue < maxValue);
 assert(size <= maxValue - minValue ); 
 assert(size >= 0);

 std::vector<int> randomValueList;

 //populate vector with possible random values
 for(int i = minValue; i != maxValue; ++i)
    randomValueList.push_back(minValue);

 //now distort their position randomly
 std::random_shuffle(randomValueList.begin(), randomValueList.end());  

 //now make randomValueList the appropriate size
 int cuttofRange = randomValueList.size() - size;

 randomValueList.erase( randomValueList.begin() + cuttofRange, randomValueList.end() );

 return randomValueList;
}

The code above is not compiled, but it gives you a way to approach it. It might need some tweaking though.

The key idea is to use the modulo operation.

For example if(num % 2 == 0){...} means that num is evenly divided by 2, thus checks if num is even. Use that idea. Your algorithm is more complicated than it needs to be.

Java is a good source of code that is event driven. For example, when you click a button and event is created, and parties are notified of such events.

You are not able to create a large array because there isn't enough memory in stack memory. So you have to allocate it and use heap memory like so :

int size = 10e10;
int array = new int[size];

//..utilize array

delete [] array; //release memory for later use

But usually, you might want to do something like this :

std::vector<int> array(10e10,0); //create an array of size 10e10, initialize to 0

Something else to consider :

template<typename T, int ROW, int COLUMN>
class Array2D{
private:
   T _array[ROW][COLUMN];
public:
 Array2D(){/*initialize _array*/}
 //Array2D methods/operations
};

int main(){
 Array2D<int,5,5> array;
}

Your saying this doesn't work :

struct GrowableArray{
 unsigned size;
 double *array;
}
void initialize(GrowableArray& g){
 g.size = 0;
 g.array = 0;
}

What errors do you get? Post some actual code.

The pointers makes me weary. I don't see a reason why you need to use pointers. Remove
all instance of them, and use proper data structures like std::vector or std::list.

What type of runtime exception do you get? Stack overflow? Invalid index ? writing into memory exception?

Also, do not use code life fgets and fscan. Use proper C++ objects like cin or some iostream object.

Yea, sorry to tell you but std::vector is based on arrays not linked list. It provides those functionalities to be consistent.

>>all the vector class is, is a linked list
Are you implying that a std::vector class is implemented using a linked list data structure?

Example :

template<typename T>
class SpecialList : std::list<T>{
public:
 //add functionalities here
};

Or use composition :

class SpecialList{
 private: std::list<int> listOfInts;
 public: 
  void push_back(int i){ listOfInts.push_back(i); }
  //..more list functions, delegate the job to list;
  //add your functionalities here.
};

Use matlab. Its made for these kinds of things. Choose the correct language.

Well you can check after each answer if the time has been exceeded.

Its not possible to do this with just C++. But you can approximate it like so :

#include <iostream>
#include <string>
#include <ctime>
using namespace std;

int ask(const string& question){
  cout << question;
  int ans = 0;
  cin >> ans;
  return ans;
}

int main(){
  const int MAX_TIME_LIMIT = 10000; //10 seconds or 10 * 1000 milliseconds
  long start_time = clock();
  
  int ans = ask("What is 2 + 2 * 5 = ");
  int ans2 = ask("What is 6 mod 2 = ");
  int numOfCorrect = 0;
  long end_time = clock();
  if( end_time - start_time > MAX_TIME_LIMIT){ 
      cout << "Time limit exceeded\n"; 
   }
  if( ans == 12){ numOfCorrect++; }
  if( ans2 == 0){ numOfCorrect++; }

  cout << "You got " << numOfCorrect << " correct answer out of 2 question\n";
  cout << "Your percentage is " << 100*(numOfCorrect/2.0f) << endl;

 return 0;
}

No guarantees in the above code.

Ok and the code OP showed should be similarly proved right? Like so :

Summation from i = 1 to N
Summation from j = x, where x = 2^i

Thus N * Summation from j = x, where x = 2^i = {1,2,4,8,16...}

If you look on wiki_summation. In the growth rate section it tells you that: Summation from i to N of c^i = THETA(c^n).
In our case c = 2, thus Summation from i to N of 2^i = THETA(2^n);

Thus N * Summation from j = x, where x = 2^i
= N * THETA(2^n)
= THETA(n*2^n)

Just for Fun, and for reference to the web searchers, lets start a series of problems in computer science thats ranges in difficulty from [1,10], where 1 is easy, and 10 is harder. Maybe I and others will learn something useful from this. The following exercise is meant as an mental exercise relative to computer science subject. So without further ado, here are 3 problems for fun. Anyone is welcome to post their solution. It would be interesting to see different way of approaching to solve the same problem.

Questions:

Difficulty level = 2
1) What is the runtime of the following algorithm? Prove it!

for(int i = 0; i < N; ++i){
 for(int j = 0; j < i; ++j){
   for(int k = 0; k < j; ++k){
      print( sqrt( i*i + j*j + k*k) ); //assume this takes O(1)
   }
 }
}

Difficulty level = 3
2) Prove by induction that the series 1 + 2 + 3 + 4 + ... + n = n(n-1)/2

Difficulty level = 3
3) Prove that max{ f(n) , g(n) } = THETA( f(n) + g(n) ), where max function returns the max value of f(n) or g(n) for some natural number n. Assume that f(n) and g(n) are time complexities, therefore postive.

@firstPerson:

Its BigOh(N^2)

Just to see what you are thinking, can you explain how you got that in terms of summation, as you did in your proof couple of post ago. I just want to see exactly where we differ and see if I am wrong or if you are wrong.

@CSurfer
What is the runtime of this :

for i = 0 to N - 1
 for j = 0 to N - 1

First to print all the values, you can just use a for loop and print out each element inside the array. And for the pre and post condition, what are the condition to be meet Is this an assignment? Post the exact problem.

oh my gosh, that fixed it! yay! I have just one more question. the program is supposed is supposed to print all the values to the main screen and i need to add pre- and post conditions to the function prototype. I have no idea what pre and post conditions are, let alone how to add them to the prototype. any ideas?

I'm not sure exactly what you are trying to accomplish here. Can you explain again?

You need to define the input function. Put the for loop inside the input function like so :

void input (int array[], int arraySize){
  //for loop code
}

You need to tell it like so :

void inpit(int array[], int arraySize){
  for(int i = 0; i < arraySize; ++i){
    //code goes here
  }
}
int main(){
 const int ARRAY_SIZE = 10; //create a constant number 
 int array[ARRAY_SIZE] = {0}; //create an array of ARRAY_SIZE and initialize it to 0
 input(array, ARRAY_SIZE);
}

Almost. First you need the curly braces so that you can include multiple statements like so :

for(i = 0; i < 10; ++i){
 //code goes here
}

Now you can put that "cout << "Please ..." inside the loop. But you also have to get the user input by using cin.

Does the getTail() return the last element or one passed the last element? Is it valid to do this cout << (a.getTail())->Coeff << endl; Also what is the exact error message?

Ok now you need to use a for loop. Have you used it before? Give it a try.
Inside the for loop, you ask the user for a number and insert it into the array.

What do you mean? As a background? Or just save the file in desktop?

>>Summation of 2^i + 1 from i = 0 to n-2.

That shows right there that its O(n*2^n);

Are you guys sure about that runtime?

The first loop runs n times. And for each n, it runs 2^n. Thus the total runtime is O(n*2^n)

Just realized that my function is wrong. It needs an offset of 1, and it needs to be printed backwards. But the general idea stands.

I didn't test the below code, but there is no need for the vector in your code. Just
go directly to string.

//supports only positive numbers
string convertToBase(long num, int radix){
 assert( radix > 0 && radix < 36); //base range[1,36)
 assert( num > 0);
 string ans = "";
 string values = "123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
 while(abs(num)){
   ans.push_back(values[num % radix]);
   num /= radix;
 }
 return ans;
}

>>Data Abstraction: we hide away the implementation details ie we do NOT show how a particular function is implemented

Thats exactly what data encapsulation is.

Data Abstraction means that we factor out common functions from a class and make a separate class thats abstract, so that the other classes can inherit form it.

Data Abstraction means something like this :

//Shape provides no implementation of the draw functions
//It abstracts the draw function from other shapes meaning that it
//defines functions that all type of shapes should necessarily have.
class Shape{
  public: virtual void draw()const=0;
};
class Ellipse : Shape{
 public: void draw()const{ API.drawEllipse(); }
};

Data Encapsulation :

class Info{
 string name;
 int uniqueId;
//....
public:
 string getName(){ return name; }
 int getId(){ return uniqueId; }
};

Notice that we do NOT provide public access for the variables name and uniqueId;
Instead we hide them or encapsulate them, and rather make a function that returns
a copy of them.

Huh? I think we have a miscommunication here ;)
By aligned I mean that the start of the variable names are at the same column.
I guess you meant aligned in memory?

// Not like:
int test;
string test2;

// But:
int    test
string test2;

string name;
float value;
int id;

vs.

string    name;
float     value;
int       id;

And for me the second one is harder to maintain, because say you wanted to add a vector iterator like so :

string name;
float value;
int id;
vector<int>::iterator it;

vs:

string    name;
float     value;
int       id;
vector<int>::iterator it;

but notice that they aren't all aligned. So you would have to now re-tab the other variables like so :

string                name;
float                 value;
int                   id;
vector<int>::iterator it;

yea for me that doesn't sound like an advantage. Just an opinion though.

>>firstPerson posted a recursive algorithm which however only prints binary once
oops, the doIt() is supposed to go inside the if statement.

>>firstPerson i got it

Good job.

easy way out :

void doIt(int start, int end){
  if(start < end){
      printBinaryRepresentation(start);
   }
  else doIt(start+1,end);
}

$100 dollars per homework, plus extra depending on the assignment. Or else you need to do this on your own, with some of us giving you hints.

Some styles that I use :

class Class{ //Classes start with capital letter
 m_var;
};

bool func(){ //notice the '{' being in the same line as the function 
}

int *p = 0;

string firstNameList; //naming convention

I use the "//" inline comment usually, for short and concise code. And use the "/**/" multiple line comment for larger functions when necessary.

There is always this :

struct A{
  void methodA(){...};
};
class B{
 A a;
 void methodA(){ a.methodA(); }
}

But thats retarded.

while(! (cin >> theNumber) )
And remove the cin before that line

Its not possible to do what you are doing. The best you can get is :

template<typename T> class CategoricalStats { ... }
template<typename T> struct QualitativeStats{
 typedef CategoricalStats<T> Type;
}
//...
QualitativeStats<float>::Type qstats;

You have that ugly extra level of indirection, but it gets the job done. See here for more details.

use this simple function, :

int getInt(const char *msg){
 cout << msg ;
 int n = 0;
 while(!(cin >> n)){
    cout <<  "Input failed...try again\n";
    cin.clear();
    while(cin.get() != '\n');
 }
 return n;
}

Basically, the while(!(cin>>n)) checks the cin gets what we are expecting it to get. We are expecting it to get an int, so if a letter is entered, cin will fail and set its fail flags. Thus the reason why we did cin.clear(). That clears the flags, and resets the stream. Now all thats left is to discard the invalid input in the stream. To do that, we did while(cin.get() != '\n');. That code discards the invalid character inputted until it reads a newline character.

is it possible to make an array of variables?

Its not only possible, its also possible to make an arrays of arrays of arrays of pointers to an arrays of arrays that takes values.

Also, there are some problems with your letterGrade function. It should look something like this :

char letterGrade(int score){
 char grade = 0;
  if(score >= 90) grade = 'A'; 
  else if(score >= 80) grade = 'B';
  else if(score >= 70) grade = 'C';
  else grade = 'F';
 return grade;
}

>>Look up C++ for dummies
HAHAHAHAHA...

We can't inherit constructors, so there is no need for them to be virtual.

Do this

queue<state> stateQueue;
state s; 
//initialize s
stateQueue.push( s );
//...blah blah a blah