Description
Assignment:
- (20 points) Every node in a binary tree can have 0, 1 or 2 children. A leaf node has no children. Write a Python function to decide whether all nodes, except leaves, in a tree have exactly two children.
# Input: a node which is the root of the tree
# Output: True if all nodes in the tree have either 0 or 2 children.
# False if some node has only one child.
# (leaves) or exactly two children (internal nodes).
def is_full_house( root_node ):
# your code…
- (10 points) Given the following function
# Input: a list of numbers, L.
# Output: a number
def do_something( L ):
s = 0
for x in L:
s = s + x
print(s)
for y in L:
s = s + y
print(s, x, y)
for z in L:
s = s + z
s = s*5
return s
Let T(n) be the running time function of do_something. What is n?
- (15 points) Continuing with problem 2. Write down T(n) as accurately as you can, with specific numbers.
- (10 points) Continuing with problem 3. Describe T(n) using big-O notation.
- (15 points) Given the following function
# Input: a list of numbers L
# Output: a number
def foo(L):
s = 0
for x in L:
j = len(L)
while j > 1:
j = j / 2
s = s + x
print(s)
return s
Let T(n) be the running time function of foo. Write down T(n) as accurately as you can, with specific numbers.
- (10 points) Describe T(n) using big-O notation.
- (10 points) Describe 20n + 5n2 using big-O notation.
- (10 points) Describe 10n3 + 20n2 using big-O notation.
Plagiarism Policy:
You can discuss how to solve the problems with your classmates, but the solution must be your own. Using other people’s solution will result in a zero for the assignment and possible additional penalties.
Submission:
Put Python code in one Python (.py) file. Put other work in a separate text file.
Put your name as part of the file name. For example: If your name is John Smith, name your files like this: JohnSmith_hw2.pyand JohnSmith_hw2.txt (or JohnSmith_hw2.docx).
Upload your submission to the Assignment 2 folder in theeCourseware Dropbox.