By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
455,434 Members | 1,878 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 455,434 IT Pros & Developers. It's quick & easy.

Please Help

P: 2
Could I please have the solutions to the following problems


1. (4 points) Your friend has to write code to make sure that the parentheses in an arithmetic expression are balanced, i.e. for every left parenthesis there is a matching right parenthesis. She wants to use a tree to do this. You argue that if all you want to do is match parentheses, then a stack will work fine. How will you use a stack to do this?

2. (6 points) A palindrome is a string that reads the same forwards as backwards.
Describe how you would implement a function that, given a string, determines whether it is a palindrome. Your function can use only one stack and one queue. Your function should return true if the string is a palindrome and false otherwise.
For example:
palindrome( “abba”) true
palindrome( “bbba” ) false

3. (20 points) For this question you are to implement a two-ended stack of ints. We will define a two-ended stack as a list in which entries can be pushed or popped from either the first or last position of the list, but no changes may be made elsewhere in the list. We will define the fundamental operations on a two-ended stack to be:
push_front – pushes an item on the front of the two-ended stack
push_back - pushes an item on the back of the two-ended stack
pop_front – removes and returns an item from the front of the two-ended stack
pop_back – removes and returns an item from the back of the two-ended stack
Your assignment is to implement the TEStack (two-ended stack) methods listed below using a singly-linked list. You should use the header file provided below. You do not need to implement copy constructors, destructors, or operator= for these classes, but otherwise the routines you implement should handle memory management appropriately.

a) (2 points) Implement the constructor for TEStack.
b) (6 points) Implement your push_back method.
c) (6 points) Implement your pop_back method.
d) (6 points) Implement your pop_front method:

4. (12 marks) Recursion
Consider the following recursive program.
//n is any positive integer
//m is a positive integer between 2 and 9
void fun(int n, int m)
{ if (n<m)
cout << n;
else { fun(n/m, m);
cout << n%m;
}
}
a) (3 marks) What is the output for fun(15, 2)?
b) (3 marks) Given the following recursive code. Point out the possible errors in the code.
//num is a positive integer
int fac(int num)
{ if (num_1)
return 1;
else {return num*fac(num+1);
}
}

c) (6 marks) Given the following function which computes Fibonacci numbers using recursive function, write a non-recursive version of function fib.
//num is a positive integer
int fib(int num)
{ if (num==0) return 0;
if (num==1) return 1;
return (fib(num − 1)+fib(num − 2));
}

5. a) (3 points) Draw the binary search tree created by inserting these values in this order:
3 4 0 2 8 6 5 1 7 9

b) (2 points) Give a pre-order traversal of your tree shown above:
c) (2 points) Give a post-order traversal of your tree shown above:
d) (3 points) Delete the root of the tree shown above using one of the two methods described in class. Draw the new tree.

6. (20 points) Tower of Hanoi

We are given a tower of n disks, initially stacked in decreasing size on one of three pegs, say A.





The objective is to transfer the entire tower to one of the other pegs, say C, using the other, say B, as a temporary peg, and obeying the following two rules of the game:
• only one disk at a time can be moved
• a larger disk can never be moved onto a smaller one
Implement the Towers of Hanoi using recursive data structures in C++. State all the assumptions you may decide to make.
Sep 16 '07 #1
Share this Question
Share on Google+
4 Replies


Ganon11
Expert 2.5K+
P: 3,652
The experts on this site are more than happy to help you with your problems but they cannot do your assignment/program for you. Attempt the assignment/program yourself first and post questions regarding any difficulties you have or about a particular function of the code that you don't know how to achieve.

Please read the Posting Guidelines and particularly the Coursework Posting Guidelines.

Then when you are ready post a new question in this thread.

MODERATOR
Sep 16 '07 #2

P: 2
I really need the solutions to the problems.Please, if you cannot provide all the solutions it's fine. Even if it is just one solution you provide, I don't mind. I really need your help because all this is jargon to me. The level at which we are taught and the level of difficulty of these questions do not coincide. If I were to show you my lecture notes and you can compare them with thesse questions you would understand what I mean.

these questions were taken off the internet from an American college's website. Now the thing is I am in Africa at a university where facilities are limited. This is a research I am conducting PLEASE HELP








I really need the solutions to the problems.Please, if you cannot provide all the solutions it's fine. Even if it is just one solution you provide, I don't mind. I really need your help because all this is jargon to me. The level at which we are taught and the level of difficulty of these questions do not coincide. If I were to show you my lecture notes and you can compare them with thesse questions you would understand what I mean.

these questions were taken off the internet from an American college's website. Now the thing is I am in Africa at a university where facilities are limited. This is a research I am conducting PLEASE HELP
Sep 16 '07 #3

sicarie
Expert Mod 2.5K+
P: 4,677
Rumbylove-

The contributors of this forum will not do any of your homework for you. Please read Ganon11's reply. You can try it yourself, and we can help you with it, but right now you have copied and pasted your homework and asked for us to give you answers, twice.

You must show that you have attempted the problem. It looks like your first two problems don't even require any code, just an algorithm (instructions of how to solve the problem without a computer). And your third, you are given many of the function names you need to implement - that shows you how your teacher wants it implemented. Try working on one at a time and posting what you have tried.
Sep 16 '07 #4

P: 1
spoonfeeding removed
Oct 1 '07 #5

Post your reply

Sign in to post your reply or Sign up for a free account.