When solving these problems, you should keep the following common-sense principles in mind.
You cannot solve a problem until you know what the problem is. Therefore, resolve to read the problem before starting to solve it. This does not take much time.
You cannot explain an algorithm to a computer unless you first understand the algorithm. Therefore, resolve to think about an algorithm before you start coding. Use an example. This does not take much time.
If you start off concerned with how you are going to code the solution, you will lose track of what you are trying to accomplish. It is better to write a solution that follows the correct principles but has some minor syntactic issues than to write something that looks syntactically correct but is heading in the wrong direction.
Strive for simplicity. The more code you write, the more chances you have to make mistakes. Keep it simple.
Write a definition of function twice(s) that takes a null-terminated string s and yields a new null-terminated string that consists of s twice in a row. For example, twice("abc") = "abcabc" and twice("hound") = "houndhound". The new string must be in memory allocated in the heap. You can use functions from the cstring library. Pay attention to correctness.
This problem can be broken down into 3 main steps and one small step. As an example, suppose that s is "abc".
Allocate an array large enough to hold the result string. Let's call that array cpy. Notice that, for the example s = "abc", the result is "abcabc", and that requires 7 bytes (6 characters and a null-terminator).
Copy s into array cpy. Now cpy holds string "abc".
Copy s onto the end of cpy. Now cpy holds "abcabc".
Return cpy.
Generalizing step 1, if s has length n then cpy must have size 2n+1. In C++ notation, that is 2*n+1. Statement
char* cpy = new char[2*n+1];allocates an array of 2*n+1 bytes in the heap.
Solution 1. Suppose we have thought to write down a few standard string functions on our prepared sheet of paper. Step 2 can be achieved by
strncpy(cpy, s, n+1);Step 3 can be achieved by
strncat(cpy, s, n+1);Here is the full definition of twice.
char* twice(const char* s)
{
int n = strlen(s);
char* cpy = new char[2*n + 1];
strncpy(cpy, s, n+1);
strncat(cpy, s, n+1);
return cpy;
}
Solution 2. Suppose we remember strlen and strcat, but that is all. It suffices to store an empty string into cpy and then to do two concatenations.
char* twice(const char* s)
{
int n = strlen(s);
char* cpy = new char[2*n + 1];
cpy[0] = '\0';
strcpy(cpy, s);
strcat(cpy, s);
return cpy;
}
Solution 3. Suppose we remember strlen and strcpy, but that is all. Concatenation can be achieved by copying s at the end of the string in cpy.
char* twice(const char* s)
{
int n = strlen(s);
char* cpy = new char[2*n + 1];
strcpy(cpy, s);
strcpy(cpy + n, s);
return cpy;
}
Solution 4 Suppose we don't remember any functions but we do remember that there is a function that returns the length of a null-terminated string. There is a boilerplate loop for looping over a null-terminated string s.
for(int i = s; s[i] != '\0'; i++)
{
...
}
At a minimum, standard tools like that should be on your
prepared sheet of paper.
Doing this by hand shows that, if you use your own loops to do the copying, you need to store the null-terminator in cpy yourself. Since cpy has size 2*n+1, its last index is 2*n. (The last index in an array of size k is k−1.)
char* twice(const char* s)
{
int n = length(s); // wrong function, but obvious intent
char* cpy = new char[2*n + 1];
for(int i = 0; s[i] != '\0'; i++)
{
cpy[i] = s[i];
}
for(int i = 0; s[i] != '\0'; i++)
{
cpy[n+i] = s[i];
}
cpy[2*n] = '\0';
return cpy;
}
Types ListCell, List and ConstList are as defined as follows. You can assume that constant emptyList and functions isEmpty(L), head(L), tail(L) and cons(x, L) have been defined as in class.
struct ListCell
{
int head;
ListCell* tail;
ListCell(int h, ListCell* t)
{
head = h;
tail = t;
}
};
typedef ListCell* List;
typedef const ListCell* ConstList;
Using a loop, and not recursion, write a definition of function member(x, L), which returns true if x is in linked list L, and false if x is not in L.
This is a search problem. We want to look at each number in list L. If and when we see one that is equal to x, we know that x is in L, so we return true. If we have looked at all of the members of L and none of them are equal to x, we return false.
There is a boilerplate loop for looking at every member of a linked list L.
for(List p = L; p != NULL; p = p->tail)
{
...
}
Inside the loop body, p->head is the current value in L
that we want to look at.
You should have this standard loop on your prepared piece of
paper. Write down things that are broadly useful.
For this problem, L has type ConstList, so the loop is
for(ConstList p = L; p != NULL; p = p->tail)
{
...
}
Here is a definition of member using a loop.
bool member(int x, ConstList L)
{
for(ConstList p = L; p != NULL; p = p->tail)
{
if(p->head == x)
{
return true;
}
}
return false;
}
Write a definition of function numBig(t) that returns the number of values in tree t that are greater than 100. The tree is not necessarily ordered like a binary search tree.
If a function only needs to look at one of the two subtrees of a tree, then it might be easy to write using a loop. But if, at least sometimes, the function needs to look at both subtrees, then a loop is a poor choice and you definitely want to use recursion. Since the numbers that are larger than 100 can be anywhere in the tree, we need to look inside both subtrees, so we use recursion.
It appears that many students are uncomfortable passing NULL to a function, even if the function can handle NULL without a problem, so they go to lengths to prevent passing NULL to it. Some students appear to believe that nobody should pass NULL to the function, so they don't handle NULL. Then they go to great lengths to avoid passing NULL to it.
But with simplicity in mind, a much better idea is to make the function handle NULL. Then, don't be worried about passing NULL to it. It will work correctly on NULL.
There are two kinds of binary tree: (1) an empty tree (NULL), and (2) a nonempty tree that has an item in its root and has two subtrees, a left subtree and a right subtree. It suffices to handle each kind of tree.
An empty tree has no numbers in it. Obviously, it contains no numbers that are greater than 100. So numBig(NULL) should return 0.
A nonempty tree has an item (a number) and two subtrees. We need to count how many numbers that are greater than 100 occur in each subtree. If the item in the root is greater than 100, then we need to count that too.
Here is a definition of numBig.
int numBig(const Node* t)
{
if(t == NULL)
{
return 0;
}
else if(t->item > 100)
{
return 1 + numBig(t->left) + numBig(t->right);
}
else
{
return numBig(t->left) + numBig(t->right);
}
}