Spring 2019

# assignments

## 1. getting started due Tue Jan 22

• Read chapter 1 in the textbook.
• Try exercises 1-5 b & c , 1-25, and 1-29.
• Come to class Tuesday ready to discuss.
• If time allows, check out chapter 2 and O() notation ... that's next.

## 2. O() due Tue Jan 29

• Read chapter 2 in the text. (Chap 3 is coming next...)
• Do exercises 2-19 and 2-47 from the text.
• Make a plot of the points x=[1, 3, 10, 30, 100, 300, 1000, 3000] , y=[10100, 270100, 10000100, 270000100, 10000000100, 270000000100, 10000000000100, 270000000000100]. Estimate the O() behavior by finding a curve that fits them.
• Explain the algorithms power1(a,b,c) and power2(a,b,c). If a and c are held fixed and b gets larger, what do you expect their O(b) to be? Verify this by running the the code with some timing or step counting.

## 3. data structures 1 due Tue Feb 5

• Use the stack API and its implementation using python lists to validate balanced symbols. In other words, download their code and test it on some strings like '<>' and '<<))' Explain what's going on.
• Now create a different implementation of the same API using a linked list instead of python's built-in list, and show that this too can validate those strings. Let the stack keep track of the first and last node, where a node is
class Node:
def __init__(self, value):
self.value = value
self.next = None

• Using a similar apprach, implement a binary tree using a different Node class which has two children - left and right, say. Using that implementation, create this binary tree : .
• Write and test a recursive algorithm to count the nodes in that tree.

## 4. sorting due Tue Feb 12

• Read chapter 4 in the text, on sorting. It tends to ramble a bit ... topics to understand (from that or other sources) include insertion sort, heap sort, quick sort, and merge sort, non-comparison sorts (bucket or radix), which have which which O() behavior and why.
• Also check out wikipedia's sorting article.
• Implement and test a data structure, either a hash table (with at least set and get methods) or a min heap (with at least push and pop methods).
• Implement two sorting algorithms with different O() behavior, for example insert and merge Try them on some big lists to show explicitly the difference in number of steps or run time.

## 5. graphs 1 due Tue Feb 19

• Read chapter 5 on graphs, or explore that material (look for key words) in other sources. Make sure that you understand depth-first and breadth-first traversals of graphs in particular.
• Come to class Tuesday ready to discuss "topological sorting" and what that's all about.
• Study the code that I showed in class on Thursday.
• Do problem 5-1 in the text (traversal order for breadth and depth first search). Be careful about what "picking alphabetically" means ... that behavior may not be quite the same for the Stack vs Queue implementation I discussed in class. (You're welcome to do this either by hand or with code including using the code I showed ... but be prepared to defend your result on Tuesday.)
• Explain what a "back edge" is. In the traversal that I showed in class on Thursday, which are back edges and which are not? What does that notion depend on?

## 6. knight or ladder due Tue Feb 26

• For Thursday's class, start thinking about either the Knight's Tour or the Word Ladder problem. Bring some code to class to share.
• For Tuesday : code something that does one of these problems and discusses your approach, what it can do, and what you think its O(n) behavior is. You can work with a partner if you want. If so, submit things twice, on each of your assignments page, and make it clear who did what. You are allowed use the code that I've posted or other stuff you find. Do quote your sources.

## 7. midterm project due Fri Mar 8

• Explore numerically one of the graph algorithms we've been discussing in class, including
• a discussion of how it works along with any needed data structures, with your sources
• working code that implements the algorithm
• tests on different size randomly generated graphs that demonstrate its O() behavior
• While the due date is the Friday before spring break, you may submit your work anytime before the Monday we return without penalty.
• For Tue March 5, describe which algorithm you're going to do.

## 9. huffman due Tue Apr 9

• You are given ten different items with values [505, 352, 458, 220, 354, 414, 498, 545, 473, 543] and weights [23, 26, 20, 18, 32, 27, 29, 26, 30, 27]. What is the largest value you can get while keeping the weight under 67? This is small enough that you can do it by brute force ... but the really cool kids use dynamic programming. Give it a try, and we'll discuss on Tuesday as our last example of this sort of problem.

## 10. project proposal due Tue Apr 16

• Propose an end of the term project. You can choose any algorithm or classic problem to research, implement, evaluate O() numericall, and discuss in a short paper with sources. The material in the second part of the textbook is one possible source of ideas.
• Download moby dick as a text file from gutenberg.org. Count the frequency of each letter, and with that run my huffman python program to generate a Huffman Code. Explain how much compression (as a percentage) this code would give when applied to this file.
• Compress the same moby dick text file with any built-in archive or standard compression tool (gzip, zip, apple os "compress this file", ...), and see how much smaller the file gets. Compare with the huffman result.