This page contains various short problems that you can work on to help you gain an understandin of the concepts that we have discussed in class.
Problem #1 - Tracing - I said in class that tracing code is one of hte most important skills you can learn. It can be challenging though, especially with many function calls and loops. These problems will give you a chance to trace some code. I recommend building a table of values that change in loops or one of function call arguments and return values.
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;
}
Here is a table that you might use to help you solve this. You move to a new row for each iteration of the loop or something along those lines.
| Variable | val | i |
| Iteration 1 | ||
| Iteration 2 | ||
| Iteration 3 | ||
| ... |
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);
}
Here is the type of table that might help here. Keep in mind that you might not be able to fill in a full row at a time. You might have to go down the table before you can fill things in higher in the table. You can't evaluate an expression until you know the value of all sub-expressions, including function calls.
| Argument value (n) | Return value | |
| Iteration 1 | ||
| Iteration 2 | ||
| Iteration 3 | ||
| ... |
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.
b. Write an expression to check if either i, j, or their sum is zero.
c. Write an expression to see if i is in the range between 60 and 100 or j is negative.
Problem #3 - if/else structures
a. Check if a number is zero and of not use it to divide another number.
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.
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).
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'.
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).
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.
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.
c. Print the multiples of 5 between 0 and 100.
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.
e. Write a loop to print out the powers of 2 less then 1000 starting with 1.
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.
a. Given an array a[] of length len, print out all the elements of a[].
b. Given an array num[] of length len, find the product of all the elements of num[].
c. Given an array num[] and an array rev[] both of length len, put the elements of num into rev in reverse order.
d. Given an array num[] of length len, reverse the order of the elements in num.
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.
b. Add an element newElem to the end of the list.
c. Insert an element newElem at location newPos in the list.
d. Search for an element elem in the list and delete it if found.
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
b. *b
c. *c
d. *(d.w)
e. e->v
f. &(d.getComp()->x)
g. *(e->getComp())
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.
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?
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;
};
c. Write a linked list based implementation of a stack.
d. Write a linked list based implementation of a queue.
Problem #14 - Inheritance
a. Inheritance serves two distinct roles in programming. Tell me what these roles are and give examples of how they work.
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, mke sure you could pass either LinkedList or ArrayList to a function that expects a List and have the right thing happen.
Problem #15 - Polymorphism
a. Explain polymorphism in English, how does it help us.
b. What are the two main types of polymorphism? Which one is more powerful and what two subcatagories can we break it down into?