c++ cZar

Wednesday, April 7, 2010

C aptitude 1

void main()

{

int const * p=5;

printf("%d",++(*p));

}

Answer:
Compiler error: Cannot modify a constant value.
Explanation:
p is a pointer to a "constant integer". But we tried to change the value of the "constant integer".

Sunday, April 4, 2010

//p104
// Find the Fibonacci sequence for which the first nine digits and the last nine digits are 1-9 pandigital

#include
#include

char number_string[100000];

char isPandigital( unsigned long int num )
{
 if ( num < 123456789 )
 {
 return 0;
 }

 char num_of_unique_digits = 0;

 char number_array[9];

 unsigned long int temp = num;

 int i;
 int j;

 for ( i = 0; i < 9; i++ )
 {
 number_array[i] = temp - ((temp / 10) * 10);
 if ( number_array[i] == 0 )
 {
 return 0;
 }

 temp /= 10;
 }

 char is_unique = 1;

 for ( i = 0; i < 9; i++ )
 {
 for ( j = 0; j < 9; j++ )
 {
 if ( i != j )
 {
 if ( number_array[i] == number_array[j] )
 {
 is_unique = 0;
 }
 }
 }

 if ( is_unique )
 {
 num_of_unique_digits++;
 }

 is_unique = 1;
 }

 if ( num_of_unique_digits == 9 )
 {
 return 1;
 }
 else
 {
 return 0;
 }
}

int numOfDigits( mpz_t num )
{
 int num_of_digits = 0;

 char *number_pointer;
 mpz_get_str( number_string, 10, num );

 number_pointer = number_string;

 while( *number_pointer != '\0' )
 {
 num_of_digits++;
 number_pointer++;
 }

 return num_of_digits;
}

char areBothSidesPandigital( mpz_t num )
{
 mpz_t mod;
 mpz_init_set_str( mod, "1000000000", 10 );

 mpz_t temp;
 mpz_init( temp );

 unsigned long int number_group = 0;

 mpz_mod( temp, num, mod );

 number_group = mpz_get_ui( temp );

 if ( isPandigital( number_group ) )
 {
 mpz_ui_pow_ui( temp, 10, (numOfDigits( num ) - 9) );

 mpz_tdiv_q( temp, num, temp );

 number_group = mpz_get_ui( temp );

 if ( isPandigital( number_group ) )
 {
 mpz_clear( temp );
 mpz_clear( mod );

 return 1;
 }
 }

 mpz_clear( temp );
 mpz_clear( mod );

 return 0;
}

int main()
{
 mpz_t num1;
 mpz_init_set_str( num1, "1", 10 );

 mpz_t num2;
 mpz_init_set_str( num2, "1", 10 );

 char add_to_first = 1;
 char are_we_up_to_ten_digits = 0;
 int current_sequence = 2;

 while( 1 )
 {
 current_sequence++;

 if ( add_to_first )
 {
 mpz_add( num1, num1, num2 );
 add_to_first = 0;
 }
 else
 {
 mpz_add( num2, num1, num2 );
 add_to_first = 1;
 }

 if ( add_to_first )
 {
 // printf( "\nNumber of digits: %d\n", numOfDigits( num2 ) );
 if ( areBothSidesPandigital( num2 ) )
 {
 printf( "\n\nThe double pandigital Fibonacci sequence was found at: %d\n\n", current_sequence );
 return 0;
 }
 }
 else
 {
 //printf( "\nNumber of digits: %d\n", numOfDigits( num1 ) );
 if ( areBothSidesPandigital( num1 ) )
 {
 printf( "\n\nThe double pandigital Fibonacci sequence was found at: %d\n\n", current_sequence );
 return 0;
 }
 }
 }

 //mpz_ui_pow_ui( temp, base, exp );

 //mpz_out_str( out_file, 10, temp );

 //printf("\n");
 //mpz_out_str( stdout, 10, temp );
 //printf("\n\n");

 printf("\n\n");

 return 0;
}

Saturday, March 27, 2010

Simplified IP Addressing

Basics
The first question concerns what constitutes a Class A, or a Class B, etc. network. Novices have trouble remembering where each class begins and ends. Table 3 shows a schema to help with this. First, let's discuss some basics of binary numbers.
A byte is a grouping of eight binary bits. Since a binary bit is either a 0 or a 1, a byte consists of eight 0s and/or 1s. No mystery here. So 10010101 is one byte and 11100000 is another. How do we convert these to decimal numbers? It turns out that the right-most bit has a weight of 1 (2<+>0<+>). The next bit to its left has a weight of 2 (2<+>1<+>), the next has a weight of 4 (2<+>2<+>), i.e., two raised to the second power and so on:

or equivalently:

128  64  32  16  8  4  2  1     : decimal weights

Thus, the binary number 10101001 has a decimal equivalent of

1x1 + 1x8 + 1x32 + 1x128 = 169

If you assign contiguous 1s starting from the right, the above diagram can be used as a kind of calculator. Let's say you have 00001111 binary bits. To get the decimal equivalent, you could do the calculations the hard way, that is:

1x1 + 1x2 + 1x4 + 1x8 = 15

or you could note the following (taking our number):

128  64  32  16  8  4  2  1     :decimal weights
  0  0  0  0  1  1  1  1 :binary number

If you have all ones starting at the right side, you can simply take the weight of the first 0 bit (16 in this case), subtract 1, and you have 15—the decimal equivalent—without having to use a calculator. Thus, if all the bits on the right are 1s, you can determine the decimal value by using the above diagram as a kind of calculator. Note that the bits go up in powers of 2, so the ninth bit has a decimal weight of 256. So if you have a byte with all ones, i.e., 11111111, then it has a decimal value of 255 (256 -1). 255 appears many times in IP addressing.

Table 1. Decimal Equivalents for Netmasking

128 64 32 16 8 4 2 1	decimal
1 0 0 0 0 0 0 0	128
1 1 0 0 0 0 0 0	192
1 1 1 0 0 0 0 0	224
1 1 1 1 0 0 0 0	240
1 1 1 1 1 0 0 0	248
1 1 1 1 1 1 0 0	252
1 1 1 1 1 1 1 0	254
1 1 1 1 1 1 1 1	255

Now we need to construct another calculator for handy reference (see Table 1). There is a thing called netmasking, which I will discuss later on. Standard procedure says to start the masking from the left and work down. So, if you make the eighth, or high-order bit, 1 and the rest equal to 0, the decimal equivalent is 128; if you made the first three bits 1 and the rest 0, the decimal equivalent is 224, etc.

Table 2. Shortened Netmask Table

128 64 32 16 8 4 2 1	Binary
128 192 224 240 248 252 254 255	Decimal

This table works fine, but is a bit unwieldy. Table 2 shows a short version. It says that if your byte is 11100000, then the decimal equivalent value is 224. If this bothers you, just use Table 1.

IP Addresses

We have set the groundwork for IP addressing, and I will now discuss the standard IPv4 addresses. The IP addresses are sometimes called “dotted quad” numbers. There are five classes of IP addresses, i.e., A, B, C, D and E. Classes D and E are reserved so you can work with classes A, B and C. However, I will show all five here. The class is determined from the first byte. Thus, an IP address of 205.140.187.31 is a class C address, since the first byte is 205. How do I know that? Well, let's look at Table 3.

Table 3. Classes of IP Addresses

	High-Ordered Byte
Class	Binary	Decimal	Decimal
	Starting	Starting	Ending
	Point	Point	Point
A	0	0	126
			127 (loop-back)
B	10	128	191
C	110	192	223
D	1110	224	239
E	11110	240	247

How did I get Table 3? I had to remember only a couple of pieces of information, then I constructed the rest. I know there are five classes of IP addresses, and the first byte of the IP address tells you to which class it belongs. I also know the schema for the binary starting value of the first byte, i.e., 0, 10, 110, etc. Because of the way it follows a schema, the second column is easy to construct. Now, using Table 2, it was easy to construct the third column.
Next, note that the fourth column (ending point) follows naturally by simply subtracting one from the beginning of the next class. A class C begins at 192, while a class D begins at 224. Hence, a class C must end at 223. Now you have no excuses about forgetting the beginning and ending points of each class; merely remember the binary schema, and take a minute to construct the table. On a side note, you don't have to worry about Classes D and E, except that the beginning of Class D tells you where Class C ends by subtracting 1.

Bitwise AND

We need to discuss netmasking, but first, let's digress for a moment. A Boolean AND is just like an “and” in English. You tell Johnny you will buy him an ice cream cone if he puts out the trash “and” makes his bed. If he does neither or only one of them, he doesn't get an ice cream cone. If he does both, he gets the cone.

Table 4. Bit-Wise Logical AND Truth Table

First	Second	Result
Bit	Bit
0	0	0
0	1	0
1	0	0
1	1	1

Bitwise ANDs work bit by bit. So, if you AND a 1 with a 1, you get a 1. If you AND two 0s, a 1 and a 0, or a 0 and a 1, however, you get a 0. Table 4 illustrates this operation.
Now let's take a whole byte and do a Logical AND with another byte. Suppose the first byte is 10110010 and the second byte is 01100111. Working from the right, note that the first byte has a decimal value of

0*1 + 1*2 + 0*4 + 0*8 + 1*16 + 1*32 + 0*64 + 1*128 = 178

while the second byte has a decimal value of

1*1 + 1*2 + 1*4 + 0*8 + 0*16 + 1*32 + 1*64 + 0*128 = 103.

Now, AND the two bytes:

1 0 1 1 0 0 1 0         178 decimal, ANDed with
0 1 1 0 0 1 1 1         103 decimal
---------------             gives
0 0 1 0 0 0 1 0         34 decimal

As a second example, let's AND 178 with 255.

1 0 1 1 0 0 1 0         178 decimal, ANDed with
1 1 1 1 1 1 1 1         255 decimal
---------------             gives
1 0 1 1 0 0 1 0         178 decimal

We know, then, that when you bit-wise AND any byte (number) with 255, you get the number dropping through, i.e., the result is merely the number again.

Netmasking

The default netmasks for the various classes are shown in Table 5 with some sample host IP addresses. Simply put, a host is anything that has an IP address. This includes servers, workstations, routers, etc.

Table 5. Default Netmasks, etc.

Class	Default	Meaning of	Sample	Sample
	Net-Mask	IP (Host)	Host	Network
		Address	Address	Address
A	255.0.0.0	N.H.H.H	10.0.1.23	10.0.0.0
B	255.255.0.0	N.N.H.H	146.87.12.250	146.87.0.0
C	255.255.255.0	N.N.N.H	200.150.189.31	200.150.189.0

So, what does this mean and what do we do with it? Let's work through Table 5. If we take the sample Class A address, 10.0.1.23 and bit-wise AND it with its default netmask, we obtain 10.0.0.0. What is 10.0.0.0? It's the network address—look at the last column.
Notice that the first byte gives the network address when ANDing a Class A network with its default netmask, while the first two bytes give the network address when ANDing a Class B IP address with the default Class B netmask. Hence, we say that the first byte of a Class A IP address gives the network address, and the three remaining bytes give the host addresses, i.e., a Class A address has the form N.H.H.H where N stands for Network and H stands for Host. Likewise, the first two bytes of a Class B IP address pertain to the network, and the last two bytes pertain to the host address, i.e., N.N.H.H. Finally, the first three bytes of a Class C IP address pertain to the network, while the last byte pertains to the host, i.e., N.N.N.H.

Subnetting

Let's illustrate this with a Class B IP address such as 142.168.25.100. From Table 5, we know that the default netmask for a Class B network is 255.255.0.0. Hence, ANDing the default mask with the IP address yields the address of the network that particular host is on, i.e., 142.168.0.0. So, a host with an IP address of 142.168.25.100 finds itself on a network with an IP address of 142.168.0.0 if a default Class B net-mask is used.
If you are granted a full Class B suite of addresses with a network address of 142.168.0.0, what do you do with them? Remember, a Class B network has the form of N.N.H.H, i.e., the last two bytes can be used for assigning host IP addresses. This yields a network with 2<+>16<+> - 2 host addresses. The -2 comes from the fact that 142.168.0.0 is the network address, so it can't be assigned to a host; the last address on the network, 142.168.255.255, is used for broadcasts, so it also can't be assigned to a host.
This would be a very big network (65,534 host addresses), far too big to be practical. A very simple approach is to “borrow” one byte's worth of host addresses and assign them as network addresses. That would yield 2<+>8<+> = 256 networks with 254 hosts on each. Even here, these are large networks. This process of borrowing host addresses and using them for networks is called subnetting. We accomplish this by using a sub-netmask (SNM). In this case, we would use a sub-netmask of 255.255.255.0, which is the default Class C netmask. Hence, we have taken one Class B network and turned it into 256 Class C networks.
If we AND 142.168.25.100 with 255.255.255.0, we get a network address of 142.168.25.0 with the first available host address of 142.168.25.1 and the last of 142.168.25.254, since 142.168.25.255 is reserved for broadcasts. Another way of doing this is to start with the network address (142.168.25.0 in this case), turn all host bits into 1s, and obtain the broadcast address. Here, the last byte is used for host addresses, so turning them to ones gives 142.168.25.255. This type of broadcast is called a directed broadcast, meaning that it jumps routers while a local broadcast (which doesn't jump routers) has the form 255.255.255.255 no matter which class of network is involved.
If you're not too stunned at this point, you may wonder if you can subnet only on byte boundaries or if you can subnet a Class C network. The answers are “no” and “yes”, respectively; i.e., you can work in the middle of a byte.

Subnetting on Non-Byte Boundaries

Let's say you are granted a full Class C suite of addresses, e.g., 210.168.94.0 as your network address. You are allowed to assign the host addresses (the last byte) as you please. If you use the default Class C netmask of 255.255.255.0 (see Table 5), you can assign host addresses of 210.168.94.1 through 210.168.94.254 on a single network. That's feasible of course, but you may want to break this up into multiple networks of perhaps 25 hosts each.
Let's do some mathematics. If we have 4 bits for hosts, will it be enough? 2<+>4<+>-2 = 14 and is not enough. So, let's use 5 bits for hosts: 2<+>5<+>-2 = 30 which will work. However, we have 8 bits in the last byte for hosts, so let's borrow three bits for subnetworks; then we still have the requisite 5 bits for hosts. Great, but how many subnets do we have? How about 2<+>3<+> = 8? We have, then, eight subnetworks with 30 host addresses on each. If you are doing the math, you are probably saying, “but 8x30 is only 240 addresses; what happened to the others?” Valid question! Oops, don't get sore, but it's time to construct another table. Note that each address will have the form of 210.168.94.last byte, and the SNM (sub-netmask) will have the form 255.255.255.last byte. Let's just work with the last byte.

Table 6. Subnetworks for Class C Network (shows the last byte)

Binary	Decimal
Number	Equivalent
00000000	0
00100000	32
01000000	64
01100000	96
10000000	128
10100000	160
11000000	192
11100000	224

From Table 2 (or Table 1), we see the SNM will be 255.255.255.224. The 224 comes from the last byte being 11100000. So what are the subnets? Table 6 shows them (last byte only).
Let's detail a few. First, take the smallest. The full subnetwork address of the smallest is 210.168.94.0. The next one up is 210.168.94.32, and so on. Remember that with three bits to work with, we get 2<+>3<+> = 8 subnets, and looking at Table 6, you see them.

Table 7. Analysis of 256 Values of Last Byte

Last Byte	What	Why
Addresses	Happens
	to Them
0	invalid	first subnet address
1-30	valid	hosts on first subnet
31	invalid	broadcast address of first subnet
32	invalid	second subnet address
33-62	valid	hosts for second subnet
63	invalid	broadcast address of second subnet
64	invalid	third subnet address
65-94	valid	hosts for third subnet
95	invalid	broadcast address of third subnet
96	invalid	fourth subnet address
97-126	valid	hosts for fourth subnet
127	invalid	broadcast address of fourth subnet
128	invalid	fifth subnet address
129-158	valid	hosts for fifth subnet
159	invalid	broadcast address of fifth subnet
160	invalid	sixth subnet address
161-190	valid	hosts for sixth subnet
191	invalid	broadcast address of sixth subnet
192	invalid	seventh subnet address
193-222	valid	hosts for seventh subnet
223	invalid	broadcast address of seventh subnet
224	invalid	eighth subnet address
225-254	valid	hosts for eighth subnet
255	invalid	broadcast for eighth subnet

Back to the question of why we get only 240 host addresses. “(Gasp)—another table!” Looking at the last byte, we get Table 7.
Now let's answer the question of what happened to the other addresses. To do this, tally all the “invalid addresses”, i.e., those that can't be used for host addresses.
First, we have eight subnets, each with a subnetwork address and a broadcast address. So we lose 8*2 = 16 addresses here. Now if we subtract these 16 from 256, we get 240 available host addresses.
Doing it the other way is much easier. We have eight subnetworks, each with 30 valid IP addresses; this gives us 8*30=240 valid IP addresses total, the magic number.
For fun, let's do one more thing: analyze the sixth subnetwork in a little more detail. The last byte is 10100000 binary or 160 decimal. The full subnet address is 210.168.94.160 decimal, and we use an SNM of 255.255.255.224. Remember, I said to take the subnet address, set all the host bits to 1s and add them to get the broadcast address. If we do this correctly, it should give the same result as Table 7.
We use five bits for host addresses, so the decimal value of the sixth bit is 32. Subtracting 1 gives 31. Thus, setting the five host bits to 1s, i.e., 00011111, gives a value of 31 decimal. Adding this to the last byte of the subnet address (160) gives 191 for the broadcast address, agreeing with Table 7. Here is the “whole Megillah”:
210.168.94.160 The Sub-Network address210.168.94.161-190 Valid host addresses210.168.94.191 Directed Broadcast address
One final point. Some authors use the term “sub-netmask” even when referring to the default netmasks—they are being just a tad loose with their terms. Happy IP addressing, and remember, Linux is inevitable.

Friday, March 5, 2010

Write a recursive function that, given the number of distinct values, computes the number of structurally unique binary search trees that store values from 1.....N.

Wednesday, February 3, 2010

Wednesday, January 6, 2010

Anagram program implentation

#include 
using namespace std;

#include "anaword.h"

static const int ALPH_SIZE = 26;

Anaword::Anaword(const string & word)
    : myWord(word),
      myCounts(ALPH_SIZE,0)
// postcondition: constructed    
{
    normalize();
}

Anaword::Anaword()
    : myWord(""),
      myCounts(ALPH_SIZE,0)
{
    
}

void Anaword::normalize()
// postcondition: myCounts represents the letter signture of myWord
{
    
}

string Anaword::toString() const
// postcondition: return "bagel" or "gable", regular form of string
{
    return myWord;
}

ostream & operator << (ostream & out, const Anaword & a)
// postcondition: a printed t stream out, out returned    
{
    out << a.toString();
    return out;
}

bool Anaword::equal(const Anaword & rhs) const
// postcondition: returns true if and only if *this == rhs
//                canonical/normalized form of word used for comparisons    
{
    return false;
}

bool operator == (const Anaword & lhs, const Anaword & rhs)
// postcondition: returns true if and only if lhs == rhs
{
    return lhs.equal(rhs);
}

bool operator != (const Anaword & lhs, const Anaword & rhs)
// postcondition: returns true if and only if lhs != rhs
{
    return ! lhs.equal(rhs);
}


bool Anaword::less(const Anaword & rhs) const
// postcondition: returns true if and only if *this < rhs
//                canonical/normalized form of word used for comparison    
{
    return false;
}

bool operator <  (const Anaword & lhs,const Anaword & rhs)
// postcondition: returns true if and only if *this < rhs    
{
    return lhs.less(rhs);
}

bool operator <=  (const Anaword & lhs,const Anaword & rhs)
// postcondition: returns true if and only if *this <= rhs
{
    return ! rhs.less(lhs);
}

Anagram class

#ifndef _ANAWORD_H
#define _ANAWORD_H

#include 
#include 
using namespace std;
#include "tvector.h"

// Used for finding anagrams: words with the same letters
// but which are different words, e.g., "bagel" a "gable"
// author: Owen Astrachan
//
// an Anaword object prints as a regular string, but
// compares using a normalized (also called canonicalized) form
//
// Example: the Anaword version of the string "bagel"
//          prints as bagle, but will be compared with
//          other Anawords as a vector of counts
//          of one 'a', one 'b', one 'e', one 'g', one 'l'
//          Since the counts for "gable" are the same, "gable"
//          and "bagel" will be equal when compared using operator ==
//
// basically an Anaword takes a string and converts it to a twenty-six
// digit number based on the counts of a's, b's, c's, ... z's so that
// aardvark is represented as:
//
//  3 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 2 0 0 0 1 0 0 0 0
//
//
// operations:
//
// Anaword(const string & word)      -- construct from a string
//
// bool equal(const Anaword & rhs)   -- compare rhs for equality
// bool operator == (lhs, rhs)       -- compare Anawords lhs == rhs
//
// bool less(const Anaword & rhs)    -- compare rhs for inequality <
// bool operator < (lhs,rhs)         -- compare Anawords lhs < rhs
// bool operator <= (lhs,rhs)        -- compare Anawords lhs <= rhs
//
// string toString()                 -- returns uncanonicalized "bagel"
// ostream & << operator(ostream,    -- print using <<
//                       Anaword)

class Anaword
{
  public:
    Anaword(const string & word);             // construct from string
    Anaword();                                // default (for vector)
    bool equal(const Anaword & rhs) const;    // compare for ==
    bool less(const Anaword & rhs)  const;    // compare for <    
    string toString()               const;    // return "bagel" or "gable"

  private:  

    void normalize();                         // helper function, sorts
    string myWord;                            // regular string: "bagel"
    tvector myCounts;                    // canonicalized form
};

bool operator == (const Anaword & lhs, const Anaword & rhs);
bool operator != (const Anaword & lhs, const Anaword & rhs);
bool operator <  (const Anaword & lhs, const Anaword & rhs);
bool operator <= (const Anaword & lhs, const Anaword & rhs);
ostream & operator << (ostream & out,  const Anaword & a);

#endif

#include 
#include 
#include 
using namespace std;

#include "anaword.h"
#include "prompt.h"
#include "tvector.h"
#include "sortall.h"



void FindAnagrams(tvector& list)
// pre: list contains list.size() elements
// post: all anagrams in list printed, one set of anagrams per line
{
    QuickSort(list,list.size());
}

int main(int argc, char * argv[])
{
    tvector list;
    ifstream input;
    string filename,word;
    // use command line argument if it exists, else prompt user
    
    if (argc > 1)
    {
 filename = argv[1];
    }
    else
    {
 filename = PromptString("enter file name "); 
    }
    
    input.open(filename.c_str());
    if (input.fail())
    {
 cerr << "could not open " << filename << endl;
 exit(1);
    }

    while (input >> word)
    {
 list.push_back(Anaword(word));
    }
    cout << endl << "read " << list.size() << " words" << endl;

    FindAnagrams(list);

    return 0;
}

Do not run the program as it is (without implementing) Anaword::equal and Anaword::less since the call to QuickSort will cause an infinite loop.

Program Description

You'll write a program, part of which is given to you, that reads a file of words and generates as output all the anagrams in the file. Each line of output should contain words that are anagrams of each other, for example:
gazer graze gases sages heals leash shale heaps phase shape hares hears share shear earth hater heart haste hates heats haves shave arise raise lakes leaks Your program should deal with words that contain punctuation. You can ignore these words, but your program should not die/stop if such a word is encountered. You should make your own small test files, but check your final program with the input file words accessible on acpub as ~ola/data/words. (This file is /usr/dict/words from Linux.)

Coding and Algorithm

You must use the class Anaword whose declaration is given in the file anaword.h. You will need to write the implementation of this class in the file anaword.cpp although this has been started for you. An Anaword object is constructed from a string, and prints as the string, but is compared using a normalized or canonical form created by counting the number of times each letter in the word occurs (more on this below). For example, the code fragment below prints the two lines of output shown. Anaword a("bagel"); Anaword b("gable"); cout &amp;lt;&amp;lt; a &amp;lt;&amp;lt; " " &amp;lt;&amp;lt; b &amp;lt;&amp;lt; endl; if (a == b) cout &amp;lt;&amp;lt; "they're ananagrams!" &amp;lt;&amp;lt; endl; Output as shown:
bagel gable they're anagrams! The objects a and b are equal because the operator == is overloaded for Anaword objects and returns true for "bagel" and "gable" since both words have the same normalized/canonical form of letter-signature: 1 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 which indicates one 'a', one 'b', one 'e', one 'g', and one 'l'. The signature of aardvark, for example, is 3 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 2 0 0 0 1 0 0 0 0 You must implement the member functions declared and described in anaword.h so that the real word (e.g., "bagel") is used for printing, but the canonical/normal form of the letter-signature is used for comparison using == and <
To do this you'll need to implement all the functions declared in anaword.hthat are not implemented in the anaword.cpp file you're given. This includes

Anaword::normalize which creates the signature for an Anaword
Anaword::equal which determines if two Anawords are equal
Anaword::less which determines if one Anaword is less than another.

For your program to run efficiently your implementations of Anaword::equal and Anaword::less should return true/false after making the minimal number of comparisons possible. Treat the vector myCounts as a 26-digit number so that, for example, "egg" > "ego" since the signatures are
egg: 00001020000000000000000000 ego: 00001010000000100000000000 The determination that "egg" is larger can be made after seven comparisons (the count of g's in egg is greater than the count of g's in ego and 'g' is the seventh letter of the alphabet).

A Working Program

You'll need to add code to doana.cpp to yield a working anagram program. This requires completing the function FindAnagrams using the idea below

Sort the vector of Anaword objects using quicksort. You can do this with because Anaword ojbects can be compared using <, ==, and <=. Access to QuickSort is via #include "sortall.h".
All anagrams are now adjacent in the vector. Make one pass over the elements looking for adjacent elements that are equal. You must write code to determine when two or more adjacent words are equal and print anagrams one set per line as shown at the beginning of this assignment.

Faster Anagrams

You'll now develop another method of canonicalizing an Anaword that's faster than the letter-signature method. First, when you've got the program working, you should add code to time how long it takes to find and print all anagrams in ~ola/data/words which is words, a file of 45,402 words. Write down the name of the machine you used and the time it takes and include these in your README file you submit. You should then create copies of both anaword.h and anaword.cpp by typing cp anaword.h anawordfinger.h cp anaword.cpp anawordfinger.cpp Now you have a copy of your (hopefully) correct Anaword class and implementation. You'll be re-implementing Anaword using another technique, but you'll need to submit both versions so you must make a copy. Instead of using the letter-signature method you'll store a sorted form of the word and use this to compare Anawords. For example, the sorted form of "bagel" and "gable" is the same, it's the string "abegl". This string is used for relational comparisons. To do this you'll need to make a few changes:

Remove the declaration below from the private section of Anaword. Then you'll add a new declaration for the sorted word:
The function Anaword::equal is now one line:
The function Anaword::less is similar:
The only other change needed is the function Anaword::normalize In this function you should sort the letters in mySortedWord which is a copy of myWord. To sort, use the code from selection sort which can be found in both the Sedgwick and Astrachan texts.
Be sure to change the comments in anaword.h to reflect the new method used.

When the program works, time it again on the same machine you timed the original program. Write the time in the README file you create. You should also write a paragraph or explaining why you think the timings are different.

Grading

This assignment is worth 15 points. Style of the code/program counts for 5/15, correctness is 8/10 and the README is 2/10.

Submit

You'll submit a README that describes the timings of both versions of the program, includes information about how much time you spent on the assignment, and a list of people with whom you discussed the program. Submit all .h and .cpp files and the README file. You do not need to submit the Makefile unless you modified it.
To submit use
submit_cps100 anagram README *.h *.cpp If submit_cps100 doesn't work, try ~ola/bin/submit100

Extra Credit

This is worth four points. Instead of sorting using < and == for Anawords, create a different ordering so that when anagrams are printed shorter words are printed first and longer words printed last. To do this, create a function object as described in pages 543-549 of the Tapestry text. This object will be used when sorting the vector of Anawords, e.g., you'll write AnaLenComparer analen; ... QuickSort(list,list.size(), analen); 
The struct/class AnaLenComparer should compare two Anaword objects, using the length of the strings in the objects as the first criteria of comparison, and using Anaword::less only if the strings have the same length. For example: Anaword a("tear"); Anaword b("ace"); Anaword c("race"); Here we want b to be "less" than a since it has fewer characters, but c is less than a since although they have the same number of characters, the canonicalized forms show that "acer" < "aert".