If time allows, check out chapter 2 and O() notation ... that's next.
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.
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
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.
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.
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.
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.
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.
Read about LZW compression on wikipedia or elsewhere.
11. project progress
due Tue Apr 23
How is your project going?
12. final project
due Fri May 3
Present your final project on the last day of classes, Tue April 30.
Submit your code and a discussion the Friday after, on May 3. Do include a bibliography and analysis of it's behavior as the size of the problem varies.