This page contains the answers to the drill problems. It is intended to help you get the most out of the drill problems. My recommendation is that you not look at the code here until after you have tried to write it yourself and just want to compare to your own answer.
Problem #1 - Tracing
a. Trace this loop and figure out what it prints.
void main() {
int val=1;
for(int i=0; i<10; i+=2) {val=2*val+i;
}
cout << val << endl;
}
| Variable | val | i |
| Iteration 1 | 2*1+0=2 | 0 |
| Iteration 2 | 2*2+2=6 | 2 |
| Iteration 3 | 2*6+4=16 | 4 |
| Iteration 4 | 2*16+6=38 | 6 |
| Iteration 5 | 2*38+8=84 | 8 |
| Iteration 6 | prints 84 | 10 |
Note that the "6th iteration" doesn't really go through the loop because th conditional is false.
b. Trace this recursive function call and figure out what it prints.
int recurFunc(int n) {
if(n<1) return 5;
if(n>3) return n+recurFunc(n-1);
return 1+recurFunc(n-1);
}
void main() {
recurFunc(6);
}
To fill in this table you go down the argument column then move up the return column filling in what it returned from that call.
| Argument value (n) | Return value |
| 6 | 6+17=23 |
| 5 | 5+12=17 |
| 4 | 4+8=12 |
| 3 | 1+7=8 |
| 2 | 1+6=7 |
| 1 | 1+5=6 |
| 0 | 5 |
Problem #2 - Boolean expressions
a. Write a boolean expression to see if the value of an integer n is odd and in the range between 75 and 105.
(n%2==1) && (n>=75) && (n<=105)
b. Write an expression to check if either i, j, or their sum is zero.
(i==0) || (j==0) || (i+j==0)
c. Write an expression to see if i is in the range between 60 and 100 or j is negative.
((i>=60) && (i<=100)) || (j<0)
Problem #3 - if/else structures
a. Check if a number is zero and of not use it to divide another number.
if(n!=0) a=b/n;
b. If you put down 20% on a home purchase you don't have to pay mortage insurance. Write the code to input a house cost and the downpayment then print whether or not they have to pay mortage insurance.
double cost,down;
cin >> cost >> down;
if(down>=0.2*cost) {
cout << "No insurance required\n";
} else {
cout << "You must pay mortage insurnace.\n";
c. In a program to calculate how much a person owes in state taxes for a particular state you have to do different things depending on their annual income. If they made less than $25,000 they pay no state taxes. Between $25,000 and $50,000 they pay 3% to the state. Over $50,000 they pay 4%. Write code to do this (use your own variable names that make sense).
double income,tax;
cin >> income;
if(income<25000.0) {
tax=0.0;
} else if(income<50000.0) {
tax=0.03*income;
} else {
tax=0.04*income;
}
cout << "Your state tax is " << tax << endl;
Problem #4 - switch statements
a. Write a switch statement that takes the numbers 1-5 and sets a character variable to a value of a-e depending on the integer input. For example if the number is 1 the character gets set to 'a'.
switch(val) {
case 1:
c='a';
break;
case 2:
c='b';
break;
case 3:
c='c';
break;
case 4:
c='d';
break;
case 5:
c='e';
break;
}
b. Write a function double calc(char opt,double n1,double n2) that uses a switch statement. If the value of opt is 'a' it returns the sum of numbers (add), 's' returns the difference (subtract), 'm' returns their product (multiply), and 'd' returns their quotient (divide).
double calc(char opt,double n1,double n2) {
switch(opt) {
case 'a':return n1+n2;
case 's':
return n1-n2;case 'm':
return n1*n2;case 'd':
return n1/n2;default:
cout << "Bad option. Returning second number.\n";
return n2;}
}
Problem #5 - Loops (Try writing these using all 3 styles of loops.)
a. Write a loop to print out the numbers between 0 and 99 inclusive.
for(int i=0; i<100; i++) cout << i << endl;
b. Write a loop to print out the odd numbers between 0 and 99 that loops through all values and only prints the odd ones. It will have an if statement in it.
for(int i=0; i<100; i++)
if(i%2==1) cout << i << endl;
c. Print the multiples of 5 between 0 and 100.
for(int i=0; i<=100; i+=5) cout << i << endl;
d. Now go back and do the problem of printing out odd numbers between 0 and 99 but now only loop through the odd values.
for(int i=1; i<100; i+=2) cout << i << endl;
e. Write a loop to print out the powers of 2 less then 1000 starting with 1.
for(int i=1; i<1000; i*=2) cout << i << endl;
f. Quiz 3 used a recursive function to do the "3*n+1" problem. This problem produces a series of numbers beginning with an input value and in theory ending with 1. At each point in the series, if a value is even the next value is half that value. Otherwise it is one more than three times the value. Write a loop to print out this sequence for a given input.
int i;
cin >> i;
while(i>1) {
if(i%2==0) i=i/2;
else i=3*i+1;
cout << i << endl;
}
a. Given an array a[] of length len, print out all the elements of a[].
for(int i=0; i<len; i++) {
cout << a[i] << endl;
}
b. Given an array num[] of length len, find the product of all the elements of num[].
int prod=1; // Assuming
it is an array of ints.
for(int i=0; i<len; i++) {
prod*=a[i]; // or prod=prod*a[i];
}
c. Given an array num[] and an array rev[] both of length len, put the elements of num into rev in reverse order.
for(int i=0; i<len; i++) {
rev[i]=num[len-i-1]; // Think about why it needs that -1 there.
}
d. Given an array num[] of length len, reverse the order of the elements in num.
for(int i=0; i<len/2; i++) {
int tmp=num[i]; // again assuming it is an int array.
num[i]=num[len-i-1];
num[len-i-1]=tmp;
}
Problem #7 - Array Implementation of Lists
For these problems assume that you have a "list" stored in an array named alist[]. The number of elements in alist[] is numElems and the total number of elements in the array is maxElems.
a. Search for an element elem and return the index of the first occurence of it. Return -1 if it wasn't found.
// This assumes we are
dealing with a list of doubles.
int findFirst(double elem) {
for(int i=0; i<numElems; i++) {
if(alist[i]==elem) return i;}return -1;
}
b. Add an element newElem to the end of the list.
// This assumes we
are dealing with a list of doubles.
int addElement(double newElem) {
if(numElems>=maxElems) return -1;
alist[numElems]=newElem;
numElems++;
return numElems;
}
c. Insert an element newElem at location newPos in the list.
// This assumes we
are dealing with a list of doubles.
int insertElementAt(double newElem,int newPos) {
if(numElems>=maxElems) return -1;
if((newPos<0) || (newPos>numElems)) return -1;for(int i=numElems; i>newPos; i--) {
alist[i]=alist[i-1];}
alist[newPos]=newElem;
numElems++;return -1;
}
d. Search for an element elem in the list and delete it if found.
// This assumes we
are dealing with a list of doubles.
int findFirstAndDelete(double elem) {
int loc=-1;
for(int i=0; (i<numElems) && (loc==-1); i++) {if(alist[i]==elem) loc=i;}if(loc==-1) return -1;
for(int i=loc; i<numElems-1; i++) {
alist[i]=alist[i+1];}
numElems--;
}
Problem #8 - Sorting
a. Comparison of number of operations. For each of the data
sets below, count how many comparisons and how many copies each of the 3
O(n^2) algorithms has to do. Note that a swap is 3 copies. Also note that
for some of the sorting methods you can do this quite quickly once you figure
out what they are doing because the way these things scale is more strongly
linked to input size than to exact input.
1. [3,4,5,6,7]
2. [9,5,8]
3. [9,5,8,2,3]
4. [9,5,8,2,3,6,1]
b. Make sure you can trace the sorting of the above arrays. You should have had to do that for the above question, but this one is probably more important.
c. Write code to do a sort WITHOUT looking up the code that I have given you. You should be able to do this just from the description of how a sort works.
Problem #9 - Classes
a. Imagine you have to write a class for a bicycle. You want instances of this class to be able to do the things that bicycles can do. What is the public interface? What type of data needs to be stored inside the class?
b. The class video game Pac-Man is a great example of the use of classes. It can be broken into classes in a number of different ways. Before reading the next question think about what types of objects you might use for that game.
c. Did you really think about it before reading on? Hopefully so. If I were to write that game here are the objects that I would use for it: pac-man, ghost, board, pellet, and maybe power-pellet. Given a break-up like this, think of what each one of those classes needs inside it. This is really a two part question. First, what functionality do they need. That functionality includes both internal things and what they need to interact with one another. Then think about what type of data each one needs.
d. I said maybe a power-pellet. Is I didn't have a separate class for that what would I do instead?
e. Pick your favorite sport and write class declarations for classes that represent a player, a team, and a league. The classes should have the ability to store stats from multiple games and calculate and return statistic for a player team, etc.
Problem #10 - Stacks and Queues
a. Write code that uses a stack of doubles to implement a reverse polish calculator. This is a menu driven program much like the calculator program I showed in class earlier in the semester only this can have more functionality without much more work. Just assume you have a DoubleStack class with push and pop methods that work appropriately for a stack of doubles.
b. Write an "e-mail reader" class. This is just going to be a helper class that can accept and dispatch e-mail messages. It should handle them in a FIFO type of manner. The main functions your class has are
void newMessage(string
message);
string getNextMessage();
Don't worry too much about the details here. You are implementing a standard data structure here.
Problem #11 - Pointers
Given these declarations, tell me the type of each of the
following expression. Note that the expressions are valid expressions, but
might not work with only the code that is shown. I'm not initializing pointers
here.
class Complex {
public:
double x,y;
};
class TestClass {
public:
double *w,*v;
Complex *getComp();
};
int a, *b, **c;
TestClass d,*e;
a. &a is an int*
b. *b is an int
c. *c is an int*
d. *(d.w) is a double
e. e->v is a double*
f. &(d.getComp()->x) is a double*
g. *(e->getComp()) is a Complex
Problem #12 - Dynamic Arrays
a. Write a class that uses a dynamic array of doubles. Make sure it has methods (possibly the constructor and destructor) that deal with the dynamic memory. Include a method setValue(int index,double val) that sets values in the array. This function should do bounds checking. Also write a method to return the sum of all the elements in the array.
class DynamicDouble {
public:
DynamicDouble(int s);
~DynamicDouble();
void setValue (int index,double val);
double getSum();private:
int size;
double *array;
};
DynamicDouble::DynamicDouble(int s) {
size=s;
arry=new double[size];
}
DynamicDouble::~DynamicDouble() {
delete[] array;
array=0;
}
void DynamicDouble::setValue(int index,double val) {
if((index>=0) && (index<size)) array[index]=val;
}
double DynamicDouble::getSum() {
double sum=0.0;
for(int i=0; i<size; i++) sum+=array[i];
}
Problem #13 - Recursive Types and Linked Lists
a. Describe in English what a linked list is. In what ways can it be superior to an array based list? In what ways is it inferior?
A linked list is a method of storing a list where no single entity knows what the entire list is, but each element in the list knows about the one or ones around it. For a singly linked list, each element knows about the next one and you keep track of the list by keeping track of the first element. They are superior to array based lists in that you can efficiently insert and delete elements from them. They are inferior in that you can't randomly access them, you have to walk through the list to find any given element.
b. Given the following class declarations, write the removeAll method in the list class. This method should go through the list and remove ALL occurances of the given value.
class Link {
public:
friend class List;private:
int x;
Link *next;
};
class List {
public:
void removeAll(int val);private:
Link *head;
};
void List::removeAll(int val) {
Link *rover=head,*prev=0;
while(rover!=0) {for(; (rover!=0) && (val!=rover->x); prev=rover, rover=rover->next);
if(rover!=0) {if(prev==0) {head=rover->next;
} else {
prev->next=rover->next;}
Link *tmp=rover;
rover=rover->next;
delete tmp;}}
}
c. Write a linked list based implementation of a stack.
class Link {
public:
friend class LStack;private:
int x;
Link *next;
};
class LStack {
public:
LStack();
void push(int num);
int pop();private:
Link *head;
};
LStack::LStack() {
head=0;
}
void LStack::push(int num) {
Link *newLink=new Link;
newLink.x=num;
newLink.next=head;
head=newLink;
}
int LStack::pop() {
if(head==0) return -1;
Link *tmp=head;
head=head->next;
int ret=tmp->x;
delete tmp;
return ret;
}
d. Write a linked list based implementation of a queue.
class Link {
public:
friend class LQueue;private:
int x;
Link *next;
};
class LQueue {
public:
LQueue();
void push(int num); // Also called enqueue
int pop(); // Also called dequeueprivate:
Link *head,*tail;
};
LStack::LStack() {
head=0;
tail=0;
}
void LStack::push(int num) {
Link *newLink=new Link;
newLink.x=num;
newLink.next=0;
if(tail!=0) tail->next=newLink;
if(head==0) head=newLink;
tail=newLink;
}
int LStack::pop() {
if(head==0) return -1;
Link *tmp=head;
head=head->next;
if(head==0) tail=0;
int ret=tmp->x;
delete tmp;
return ret;
}
Problem #14 - Inheritance
a. Inheritance serves two distinct roles in programming. Tell me what these roles are and give examples of how they work.
Inheritance serves the role of subtyping as well as allowing for some code reuse between classes. For subtyping they allow us to specify the obvious, that one class is a subtype of another class. This implies that the subtype can be used any place where the supertype is expected. For example, a function that is supposed to operate on an automobile can be passed a Honda or a Ford and still work just fine. Code reuse comes from the fact that methods and members of the super class are "passed down" to the subclass. The only time this is not the case is when a method is virtual and the subclass overrides what had been defined for the superclass. We used code reuse for the move function in our PacMan code because all the MovingObjects needed to do the same checks for whether there was a wall in the way or not and move to the new position if there wasn't.
b. Consider having two classes: LinkedList and ArrayList. Both of these classes implement lists, only they do it in different ways. For this reasons it would be logical to make both of them inherit from a base class List. Write the class declarations for these classes. These need to include significant methods and member data. Think carefully about the details here, make sure you could pass either LinkedList or ArrayList to a function that expects a List and have the right thing happen.
This will not be posted.
Problem #15 - Polymorphism
a. Explain polymorphism in English, how does it help us.
Polymorphism is the ability of a function or class to operate on many different types. It allows us to have greatly improved code reuse because we don't have to rewrite the same functions for different types when what is done in the function is exactly the same. This can also be said for data structures where it becomes quite significant when the data structure is large.
b. What are the two main types of polymorphism? Which one is more powerful and what two subcatagories can we break it down into?
Polymorphism is typically broken into ad hoc and universal groups. The universal group is more powerful because it can work with a potentially infinite number of subtypes while ad hoc works only with a small group of them. Universal polymorphism is broken down into inclusion polymorphism (which uses inheritance) and parametric polymorphism.