|
Chris Pollett > Old Classes > PIC10B Lec 1&2 ( Print View ) Lecture Notes-PDF. Enrollment info. Course Info:
Practice Exams: PIC: |
Fall 2000 PIC 10b HW5 Solutions Page
//
// pic10bhw5file1.cpp
//
// A program that uses memoization to compute the number of combinations
// of two user supplied integers.
//
#include<iostream>
static const int maxSize=50; // this constant is used to control the
// size of the array for memoization
int choose(int N, int k); // this function computes C(N,k)
// Function name: main()
//
// Purpose: Driver of combinations program. Call gets N, k from the user
// then calls choose(N,k) to compute C(N,k) and prints out the
// result. Allows the user to do another computation of C(N,k)
// if desired.
//
//
// Known Bugs: none
int main()
{
bool flag = true;
int N,k;
char c;
cout << "Welcome to the combinations calculator program.\n";
cout << "===============================================\n\n";
while(flag)
{
flag=false;
cout << "Please enter a first integer: ";
cin >> N;
cout << "\nPlease enter a second integer: ";
cin >> k;
cout << "\nC(N,k) is: " << choose(N,k) << endl;
cout << "If you would like to run the program again type y/Y \n";
cin >> c;
if( c == 'y' || c== 'Y') flag=true;
}
return 0;
}
// Function name: choose(N,k)
//
// Purpose computes C(N,k) the number of ways to choose k items from a set of
// size k. Uses Pascal's Triangle and memoization to do the
// computation.
//
// Known Bugs: none
int choose(int N, int k)
{
static int C[maxSize][maxSize]; // where we store the memoized values
if(N < k || k < 0) return 0; // handles some exceptional cases
if(k == 0 || N == k) return 1; // base case
if(C[N][k] !=0) return C[N][k]; // check if number has already
// been computed
return C[N][k]=choose(N-1,k)+choose(N-1,k-1); // if not
// compute it, store it and
// return result
}
//
//
// pic10bhw5file2.txt
//
//
5.63 Draw the ordered tree that corresponds to the string:
( (() (()()) ()) (() () ()) )
The tree one gets is:
*
/ \
/ \
* *
/|\ /|\
* * * * * *
/ \
* *
5.69 Give upper and lower bounds on the height of an M-ary tree with N
internal nodes. (We define height to be max level of trees internal
nodes.)
An upper bound is N-1.
Proof by induction. The only tree with 1 internal node looks like
[]
/ |...|...| \ (M many external children)
* * * * * (using [] to denote internal node and *'s
to denote external one's)
It has height 0 = 1-1. Suppose any tree of k< N internal nodes
has height at most k-1. Consider a tree T with N nodes. It must have a
leaf. Replacing this leaf with an external node creates a tree T'
with N-1 internal nodes of height at most one less than T.
By the induction hypothesis, the height of T' is at most N-2, so the height
of T is at most N-1. Q.E.D.
The upper bound can be achieved by the tree on N nodes that looks
[]
//..| \
* * * [] (with N internal nodes along
//..| \ rightmost branch)
* * * []
//..| \
* * * .
.
.
\
[]
//..|\
* * * *
A lower bound is logM(N).
Proof by induction. In the case of the tree with 1 internal the
height is 0 = logM1. Suppose true of tree with fewer
that N internal nodes. Consider any tree T with N nodes.
[]
/|...|\
T1T2..TM-1TM
Here Ti is the ith subtree of T. Let ki be the
number of internal nodes in the ith subtree. Since T has N internal nodes
and the root is an internal node, ki < N for all i.
So the induction hypothesis implies the height of Ti
is at least logM(ki). So T must have height at least
max(logM(k1),...,logM(kM))+1
This is smallest when each of the Ti's have same number of
internal nodes. In which case the above equation equals
logM(N/M) + 1 = logM(N) - logM(M) +1
= logM(N) -1 +1
= logM(N)
which proves the induction step. QED
The lower bound can be achieved when the M-ary tree is completely
balanced.
5.71 Give upper and lower bounds on the number of leaves in a binary
tree with N nodes.
Well, the M=2 case of the tree with maximal height given in 5.69
has only 1 leaf. So this is the best we can do for a lower bound.
For an upper bound, we use property 5.5 from the book which say
that the number of external nodes in a binary tree is one more
than the number of internal nodes.
So if there are N nodes total then there at most (N-1)/2 + 1
= (N+1)/2 external nodes.
A leaf is connected to two external nodes. So if all the external
nodes were connected to leaves we would have (N+1)/4 leaves.
Thus, this upper bounded the number of leaves we could have.
//
// File: pic10bhw5file3.cpp
//
// Contents: program to test out various tree traversals;
//
#include<iostream>
//
//
// Typedef's & struct's
//
//
typedef int Item; //C style typedefs used on this homework
struct node {Item item; node *l, *r;}; //here is our struct for a binary tree
//node
typedef node* link;
//
//
// Functions used for visiting nodes
//
//
// Function name: vis1
//
// Purpose: prints out the item of the current node
//
// Known Bugs: none
void vis1(link h)
{
cout << h->item << " ";
};
// Function name: vis2
//
// Purpose: prints out the item mod 5 of the current node
//
// Known Bugs: none
void vis2(link h)
{
cout << (h->item)%5 << " ";
};
//
//
// PROTOTYPES
//
//
void PreOrder(link h, void visit(link)); //does preorder traversal of tree
void InOrder(link h, void visit(link)); //does inorder traversal of tree
void PostOrder(link h, void visit(link));//does postorder traversal of tree
// Function name: main()
//
// Purpose: Driver program to test out various tree traversals.
// first creates the tree given in the hw specification
// then does preorder, inorder and postorder traversal on
// this tree using the functions vis1 and vis2 when visiting nodes.
//
// Known Bugs: none
int main()
{
//create tree from HW description
link h= new node(); //default constructor initializes everything to 0
h->item = 12;
h->l = new node();
h->r = new node();
h->l->item = 9;
h->r->item = 16;
h->l->l = new node();
h->l->l->item = 7;
h->r->l = new node();
h->r->l->item = 13;
h->r->r = new node();
h->r->r->item = 18;
// now print out various traversals
cout << "Welcome to the traversal testing program.\n";
cout << "=========================================\n";
cout << "\nFirst we do a preorder traversal using vis1:\n\n";
PreOrder(h,vis1);
cout << "\n\n2nd we do a preorder traversal using vis2:\n\n";
PreOrder(h,vis2);
cout << "\n\n3rd we do a inorder traversal using vis1:\n\n";
InOrder(h,vis1);
cout << "\n\n4th we do a inorder traversal using vis2:\n\n";
InOrder(h,vis2);
cout << "\n\n5th we do a postorder traversal using vis1:\n\n";
PostOrder(h,vis1);
cout << "\n\n6th we do a postorder traversal using vis2:\n\n";
PostOrder(h,vis2);
cout << "\n\nThat was fun but now this program is all done. Have"
<< " a nice day!\n";
return 0;
}
// Function name: PreOrder
//
// Purpose: Does a PreOrder traversal of the tree pointed to by h
// using the function visit to visit a node
//
// Known Bugs: none
void PreOrder(link h, void visit(link))
{
if(h == NULL) return;
visit(h);
PreOrder(h->l, visit);
PreOrder(h->r, visit);
}
// Function name: InOrder
//
// Purpose: Does a InOrder traversal of the tree pointed to by h
// using the function visit to visit a node
//
// Known Bugs: none
void InOrder(link h, void visit(link))
{
if(h == NULL) return;
InOrder(h->l, visit);
visit(h);
InOrder(h->r, visit);
}
// Function name: PostOrder
//
// Purpose: Does a PostOrder traversal of the tree pointed to by h
// using the function visit to visit a node
//
// Known Bugs: none
void PostOrder(link h, void visit(link))
{
if(h == NULL) return;
PostOrder(h->l, visit);
PostOrder(h->r, visit);
visit(h);
}
|