CMPT 225 Assignment 2


Start by downloading the assignment files. This zipfile contains a makefile, a test script and inputs/ground truths, and stubs for all of the .cpp files you need. Please do not create any additional .h and .cpp files.


Part 1 - Words

Consider the function shown below. The function returns true if the letters in the word are in alphabetical order, false otherwise.

bool alpha(string s){
	int ln = s.size();
	for (int i = 0; i < ln - 1; ++i){
		if (s[i] > s[i+1]){
			return false;
		}
	}
	return true;
}

Your task

Consider the character comparison as the barometer instruction (s[i] > s[i+1]). Implement this function in C++ in the file words.cpp. The makefile contains a definition for words. You can build the executable words for this part of the assignment by running "make words". ("make" or "make all" will build both words and the executable for the second part of the assignment.)

Determine the following for English words, using the provided list in file wordlist (do not convert to lowercase).

  1. The average length of a word
  2. The average number of character comparisons performed by alpha
  3. The average number of character comparisons as a function of n
  4. The O notation average case running time of alpha
  5. The O notation best case running time of alpha. Give an example input for when this case occurs.
  6. The O notation worst case the running time of alpha. Give an example input for when this case occurs.

Note words.cpp contains code for reading wordlist.

Submit word_answers.txt and the gnuplot output average_comps.png.

Part 2 - Mode

Write a C++ function that obtains the mode of a set of integers stored in an array. Recall that the mode of a set is the most frequently occurring element.

Please use the provided file mode.cpp, and fill in the function mode. Note: you must write any auxialliary functions you use, and may not include any external libraries to help (other than iostream and fstream). The makefile contains a definition for mode. You can build the executable mode for this part of the assignment by running "make mode".

Testing

The zipfile contains a testing script, test.py. You should run this, and other test cases, to verify correctness of your mode function.


Grading

The assignment is worth 3% and marks are allocated to the assignment as follows:

Submission

You should submit your assignment online to the CourSys submission server. You should submit the following:

Please read the documentation on the submission site for further information. The assignment is due at 11:59pm on March 1.


Back to the CMPT 225 homepage.