Home
Syllabus
Assignments
Tests
printable version
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11]
In your own words, describe how merge sort works. What is the base case?
The base case is when the array has one element; in this case, nothing happens.
When there is more than one element, merge sort consists of
three major steps.
First, we split the array into two halves.
Then we sort each half through recursively applying the merge
sort algorithm to each.
And finally, we merge the two halves together by successively
removing
the lesser of the two halves' first elements
and placing the removed item into the array holding our
result.
Suppose we have the Node class as defined in the
classroom.
class Node():
def __init__(self, value, next):
self.data = value
self.next = next
Suppose, moreover, that we have a variable head
that references the first Node in a list where each node
contains a reference to a word.
Below, write a program fragment that counts how many of the words
in the list have exactly four letters.
count = 0
cur_loc = first
while cur_loc != None:
if len(cur_loc.data) == 4:
count += 1
cur_loc = cur_loc.next
print 'There are', count, 'four-letter words.'
Suppose we have a variable first that refers to
the first Node in a linked list of strings, using
the Node class for linked lists that we studied, listed below.
Write a program
fragment that displays the final string in the list.
class Node():
def __init__(self, value, next):
self.data = value
self.next = next
cur_loc = first
while cur_loc.next != None:
cur_loc = cur_loc.next
print cur_loc.data
Suppose we have the Node class as defined in the classroom.
Complete the following function so that, given a reference to the
first Node of a list, removes the list's final node (i.e., the
node with nothing after it).
def remove_last(head):
def remove_last(head):
cur_loc = head
while cur_loc.next.next != None:
cur_loc = cur_loc.next
cur_loc.next = None
Suppose we have the Node class as defined
in the classroom, and we are implementing a class
WordList that uses this to store a sequence of words.
class WordList():
def __init__(self):
self.head = None
# ...
Write the following instance methods as they should appear within the
WordList class.
get(index)Returns the string at index (numbered from
0). The method may assume that index is
at least 0 and less than the length of the list.
remove_first()Removes the first value in this list, and returns the value removed (not the node removed). This method may assume that prior to invocation the list contains at least one node.
class WordList():
def __init__(self):
self.head = None
def get(self, index):
cur_loc = self.head
for i in range(index):
cur_loc = cur_loc.next
return cur_loc.data
def remove_first(self):
old_head = self.head
self.head = old_head.next
return old_head.data
Write the following instance methods as they should appear within the
WordList class of the preceding problem.
add(index, val)Inserts val into position index of
this list. (Don't worry about what happens if index is
invalid.)
index_of(val)Returns the index of the first occurrence of val in
this list, or −1 if it doesn't occur in the list at
all.
class WordList():
def __init__(self):
self.head = None
def add(self, index, val):
if index == 0:
new_head = Node(val, self.head)
self.head = new_head
else:
cur_loc = self.head
for i in range(index - 1):
cur_loc = cur_loc.next
after = Node(val, cur_loc.next)
cur_loc.next = after
def index_of(self, val):
index = 0
cur_loc = self.head
while cur_loc != None:
if cur_loc.data == val:
return index
index += 1
cur_loc = cur_loc.next
return -1
Write the following instance method as it should appear within the
WordList class of the preceding problem.
add_after(at, add)Locates the first node in our list containing
the word at_value and inserts a new node
referencing new_value just after it.
The method may assume that at indeed appears in
the list.
class WordList():
def __init__(self):
self.head = None
def add_after(self, at_value, new_value):
cur_loc = self.head
while cur_loc != None:
if cur_loc.data == at_value:
after = Node(new_value, cur_loc.next)
cur_loc.next = after
return
cur_loc = cur_loc.next
The game of Nim proceeds by players taking turns selecting a pile and removing 1 or more stones from that pile. The player removing the last stone wins.
Draw a complete game tree for the game of Nim beginning with two piles,
both containing two stones.
To draw a node, list the number of stones in each pile; for
example, the top node will be 2,2.
Do not include the minimax values assigned to each node in your tree.
Label all internal nodes of the following tic-tac-toe game tree with the value that minimax search would compute. I've already labeled the leaves.
Suppose a game player has constructed a game tree as given at right. In this tree, high numbers represent good boards for X, and it is currently X's move. (As you can see, X has three possible moves from which to choose, labeled A, B, and C.)
| a. |  |
b. | B |
Suppose we have developed the below game tree through recursive evaluation, in an attempt to find the value of node A. According to alpha-beta search, node C need not be evaluated. Explain why. (In this example, we are imagining that at A, it is X's turn, and larger numbers denote a more positive situation for X.)
Let's start by considering B. At B it is O's turn, and O will choose the smaller of 0 and C's value. Thus, the value of B will be 0 or less. At A it is X's turn, and X choose the larger of 3 and whatever B's value will turn out to be. But since we know B will be 0 or less, so it will inevitably choose 3, regardless of whatever C might turn out to be. So if we simply want to know A's value, we need not bother with determining C's value.
