Attempt the following problems and bring your solutions to class:
Section 1.1 (page 7) 4, 5, 6a
Section 1.2 (page 17) 1, 2
Implement the sieve algorithm on pages 6--7 of the textbook in Python. Your algorithm should be expressed as a function definition. Include a main program that tests the function. The program should prompt the user for n and output a list of primes up to n.
Reminder: on Monday our class meets from 8:45 to 9:35 due to the compressed schedule.
Attempt the following problems and bring your solutions to class:
Section 1.3 (page 23) 1
Section 1.4 (page 37) 3, 4, 7 (describe find_max operation)
Have this problem from page 8 suitable for hand-in at the beginning of class.
During the semester we will be doing empricial testing of various sorting algorithms. This first project is a "warm-up" for a complete sort testing framework that will be developed later on. For now we will just do an "ad hoc" analysis of the comparison_cound sort from exercise 1.3.1.
You should implement the comparison_count_sort as a function that takes a list of floats as a parameter and returns a new list that is in sorted order (since it is not an in-place sort). Then create a main program that allows a user to empirically test the efficiency of the algorithm. Here is an example run:
Welcome to the Comparison Count Sorter
Enter the list size: 20000
Enter the number of trials: 3
trial 1: 26.57
trial 2: 26.86
trial 3: 26.53
total: 79.95
average: 26.65
Note: you can use the time function from the time module to do simple timing tests:
import time
start = time.time()
# do some work here
end = time.time()
elapsed_time = end-start
We'll start the period on Friday with a 30 minute quiz. It will cover Chapter 1 plus class material on loop invariants. The quiz material will focus on things that we have covered in class.
Attempt the following problems and bring your solutions to class:
Section 2.1 (page 50) 1, 7, 8, 9
Section 2.2 (page 58) 2, 3 (proof not necessary), 5
Attempt the following problems and bring your solutions to class:
Section 2.3 (page 67) 4, 5, 6, 11, 12
Section 2.6 (page 89) 4
Prepare a nice solution to this problem. Use a precise formulation of the C(n) function to justify your theta analysis in part a.
Implement the selection sort and bubble sort algorithms based on the algorithms in Section 3.1. Since these are in-place sorts, your function should take a list of real numbers as a parameter and actually sort that list (with no return).
Write a program that allows a user to compare several sorting algorithms. The main program should allow the user to choose from a menu of sorts. It should also allow the user to do multiple runs to generate data for a combination of sorts and list sizes.
If a bubble sort makes no exchanges on its pass through a list, then the list is sorted and the algorithm can stop. Implement this enhanced version of bubble sort. Then do some experiments to create a short write up comparing its performance to the oringinal version. Is this enhancement worthwile for random lists?
A broader version of the bubble sort experiment. Do experiments and write a short report to answer the question "What is our 'best' sorting algorithm so far?" (comparison_count, selection sort, bubble sort). Is there a best? Can you find situations in which "best" changes?
We'll start the period on Friday with a 30 minute quiz. It will cover Sections 2.1, 2.2, 2.3, 2.6, and 3.1.
Be ready to discuss/apply this material.
Read section 3.4 and try exercises 6 and 7 (page 121). I will collect these. Bring any questions to class and be ready to discuss. We will try to get through both 3.3 and 3.4.
Finish up the remaining problems on the study guide on your own. I will give you about 10 minutes at the start of class to "vet" your answers with your group before turning in the group version of the answers.
Due by midnight.
Read section 3.5 and do problems: 1, 2, 4, 8a, 11
You are to create a general Graph class that will allow you to easily implement and test various graph algorithms from the textbook. The Graph constructor takes a list of vertex labels and a Boolean value indicating whether the graph is directed (default False). It will also have an add_edge method to add an edge to the graph.
class Graph: def __init__(self, vertices, directed=False): pass def add_edge(self, vertex1, vertex2, weight=1): pass
You should add other attributes (public instance variables and methods) as needed to conveniently implement and test graph algorithms. For starters, I would suggest these methods:
def has_edge(self, v1, v2): "returns a Boolean indicating v1 is adjacent to v2" def weight(self, v1, v2): "returns the weight of edge from v2 to v1" def vertex_iter(self): "returns an iterator for vertices def edge_iter(self): "returns an iterator for edges" def adjacent(self, v): "returns adjacency list for v as a dictionary"
Usually a graph will be created from a file. The file format
is as follows:
Line 1: contains either "directed" or
"undirected"
Line 2: vertex labels separated by spaces
Remaining lines are edges: vertex1 vertex2 weight
Note that the weight is optional, and when
present, it will be an int. Your graph.py module
should contain a fromfile(filename) function that
returns a Graph read from a file.
The handouts/graphs folder has a couple of example
graph files.
By using a Python dictionary of dictionaries, we can get the advantages of both the adjacency matrix and adjacency list graph representations. Create an adjacency list using a dictionary where the key is the first vertex of an edge. The value is another dictionary that maps the second vertex of the edge to a weight. For example, suppose that self.edges is the structure just described. To see whether the edge (v1, v2) is in the graph we just check: v2 in self.edges[v1]. Retrieving the weight associated with that edge is simply: self.edges[v1][v2].
Create a graphalgs.py file that uses your graph module. This file MUST contain at least the brute-force solution to the k-clique problem. Check out the Python itertools module for some functions that can generate permutations and combinations. For BONUS credit, you can implement other brute-force graph algorithms such as the Traveling Salesperson, DFS, BFS, and Bipartite. Note: for algorithms that require "global" variables, use a class to encapsulate a problem instance as an object.
Do complete solution write-ups for these two exercises for hand-in at the beginning of class.
The Quiz will cover material since the last quiz (Sections 3.2--3.5 and our implementation of graphs).
Be prepared to explain your team's algorithm (either team DFS or team Source removal) for topological sort.
Algorithms of interest: Binary Search, Quick Select, Binary Search Trees.
Implement and test the source-removal algorithm for topological sort. The input will be a Graph object, and the output should be a list of vertex labels of the graph in topsort order. The algorithm should return None if no topsort is possible (graph contains a cycle). The driver program for your algorithm should get the name of a file from the user and then output the topsort of the graph from that file.
Bonus extension As we left the algorithm in class, the efficiency is Theta: |V|**2 + |E|. Improve the algorithm to make it Theta: |V| + |E|. Hint: avoid having to search the indegree structure for sources.
The problem of finding all subsets of a list of items is easily formulated as a decrease-and-conquer algorithm. All subsets of n items comprise all subsets of the first n-1 items along with all those subsets with the nth item added (see discussion near the bottom of page 146 and Figure 4.10). Using this intuition, you are to write two functions, subsets_bu(lst) and subsets_td(lst) that implement the straightforward decrease and conquer algorithm to generate all "subsets" of a list of items:
def subsets_xx(items):
'''all substest of items
pre: items is a list
post: returns a list of all the "subsets" of items.
>>> subsets_bu([1,2,3])
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
''''
Notes: The "top-down" version will be recursive. You should design your functions so that they return exactly the same list ordering. This is an exercise in applying the decrease-and-conquer technique. DO NOT implement the bit string algorithms from Section 4.3. Design/write your own algorithm based on the straightforward approach.
Implement and test the insertion sort algorithm (p. 134).
Bonus: Can you verify empirically that this is the best of our various n**2 sorting algorithms?
The quiz will cover the techniques and algorithms that we have discussed from Chapter 4.
Read Chapter 5 Introduction, Section 5.1, and Section 5.2.
Implement Merge Sort and Quick Sort following the pseudocode in the textbook. For Quick Sort, I suggest using the "median of three" technique to select the pivot (see first bullet at bottom of p. 180). Do some experiments to demonstrate empirically that your implementations produce n*log(n) behavior. Make sure to include some sort of summary report in your portfolio that supports this conclusion.
Portfolio 2 is due on 3/18 accordong to the syllabus. I am extending the deadline until 3/21 to make sure everyone has time to do the last assignments.
Do Exercises 1, 5, and 7 from section 5.1
Do Exercise 1 from section 5.2 (page 181) on paper. Make your "trace" look like what is shown on p 179.
Exercises to consider: 1, 2, 5, 6, 8a
Section 5.1, Exercise 2
Section 5.2, Exercise 1
These are for hand-in at the beginning of class.
Do Exercises 5.3: 5, 6, 7 (no proof needed), 8a
Attend the MCSP Seminar (Tues, 3/22, 11:30am, SC 134) To hear Wartburg alum Eric Stahlberg talk about the future of computing and AI in Biomedical research. Write and hand-in a short reflection (1 or two paragraphs). This is worth 5 points of extra credit. If you canot make the seminar time, the session will be recorded and you can view the video later.
Implement the quickhull algorithm. The input should be a list of ordered pairs representing the points. The output should be a list of segments (pairs of points), that describe the convex hull polygon (connecting the segments in order gives the hull polygon).
You should include a driver program that demonstrates your algorithm by generating a random set of n points (where n is a user input) and then computing the convex hull and showing the results graphically by plotting the points and the convex hull polygon (zelle graphics is fine for this).
I will collect these on Monday 3/28.
It will cover Chapter 5
Do Exercise 1 from 6.1 (p.205) and this problem:
Algorithm squeeze(A, n):
// remove duplicate items from an array
// input: A an array filled from 0..n-1 with numbers
// output: The unique elements are in locations 0..i-1.
// returns: i, the number of unique elements ("new n")
// Note: the order of the unique elements does not matter.
You are to implement 2-3 Trees as described in section 6.3. Your Tree23 class should implement the following methods: insert(key), __contains__(key), __iter__(), and pretty_print(). Here is some example output that illustrates:
>>> t = Tree23([3,1,4,5,9,2,6]) >>> 5 in t True >>> 10 in t False >>> list(t) [1, 2, 3, 4, 5, 6, 9] >>> t.pretty_print() [3, 5] [1, 2] [4] [6, 9] >>> t.insert(0) >>> t.insert(10) >>> 10 in t True >>> >>> t.pretty_print() [3] [1] [0] [2] [5, 9] [4] [6] [10] >>> t2 = Tree23(range(1,16)) >>> t2.pretty_print() [8] [4] [2] [1] [3] [6] [5] [7] [12] [10] [9] [11] [14] [13] [15] >>>
Your Tree23 can use a _Node23 class that implements all of the same methods as the main class. In fact, the tree needs just a single instance variable, root that always contains the root _Node23 of the tree. Most operations will just delegate to the corresponding operation on the root. The lone exception is the insert operation, since it may require the root node to change when it splits.
The _Node23 will have an instance variable keys that stores a (Python) list of keys and trees that stores a (Python) list of the _Node23s that are the subtrees. In a leaf node, trees is empty. In interior nodes, len(self.trees) == len(self.keys)+1. So, self.trees[i] and self.trees[i+1] are the subtrees before and after self.keys[i], respectively. An empty tree is represented with a node having empty key and tree lists.
Hint: For a node, the insert operation either returns None (when the insert can be performed without promoting a key into the node) or a triple: (key, left_node, right_node). When a promotion happens, Python slice assignment provides a slick way of adjusting the node. The ith tree can be replace by the two new trees with: self.trees[i:i+1] = [left, right].
You should turn in both your code and some testing code that demonstrates that your functions are working. Be sure to tell me in the README how I can run your tests (note: they do not have to be unittest tests, just some code that demonstrates that your tree works).
Implement additional methods in your 2-3 tree to compute: a) maximum depth, b) number of nodes, c) average key depth. Write a driver program that asks a user for N and then creates a tree from N and inserts the numbers 1 through N in a randomly shuffled order (see random.shuffle), pretty prints the tree and shows the results of a), b), and c) for the tree.
Implement a PriorityQueue class using a Python list managed as a heap. Use this basic outline:
class PriorityQueue:
def __init__(self, items=[]):
self.heap = list(items)
self._build_heap()
def _largest_child(self, i):
""" returns index of node i's largest child or None when node i is a leaf """
def _bubble_up(self, i):
""" restore heap by bubbling up from node i """
def _bubble_down(self, i):
""" restore heap by bubbling down from node i """
def _build_heap(self):
""" builds an initial heap bottom-up"""
def add(self, item):
""" add item to the queue """
def get_max(self):
""" returns and removes highest priority item """
Demonstrate that your heap works by using it to implement heapsort(lst) . Your heapsort can just make a PriorityQueue from the list and then use a series of get_max calls to assign items back into the list (back to front).
Implement a version of heapsort that operates directly on the list rather than using a separate PriorityQueue object. You will probably want to recode a couple of your PriorityQueue methods as stand-alone functions that take the list as a parameter. Do some tests that demonstrate that this is another n log n sort.
The quiz will cover sections: 6.1, 6.3, 6.4, 7.3.
Write a program that uses dynamic programming to solve instances of the Knapsack problem. You program should allow the user to enter a problem instance and then print out both the maximum value that can be packed in the knapsack and the items that are selected.
This will require you to go beyond just writing the optimization function and write a method that traces back through the table to construct an optimal solution. The key is to look at the recurrence relation to see where the final anwer came from. I have posted a couple examples in the file dp_traceback.py. The interactive example below shows the generation of solutions to the first two examples in Chapter 8.
>>> # Example in Figure 8.1
>>> cr = CoinRow([5,1,2,10,6,2])
>>> cr.solution()
(17, [1, 4, 6])
>>> # Example in Figure 8.2
>>> cm = ChangeMaking([1,2,4])
>>> cm.solution(6)
(2, {1: 0, 2: 1, 4: 1})
Write a dynamic programming algorithm for the rod-cutting problem (Exercise 6, page 291) and use your algorithm in a complete program that allows the user to input the sales price chart and then get optimal cuts for various length rods.
Add any of the following to our graphs module: Transitive Closure (Warshall), All-pairs shortest path (Floyd), Minimum Spanning Tree (Prim), single-source shortest path (Dijkstra).
The CS/CIS senior project poster sesstion is from 7:00--9:00pm on the 3rd floor of the Science Center. Attending the poster session and turning in a brief reaction to your 2 favorite posters is worth up to 5 points of extra credit.
It will cover material since the midterm exam.