assignments

1. getting started due Tue Jan 22

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.

Readings :
- Read chapter 3 in the text.
- Also check out this chapter on Basic Data Structures
- Also read about hash tables, at for example wikipedia's Hash Table article - we're going to explore those next week.
- Optional : we may also look at heaps, which you can read about at wikipedia: heap
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.

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.

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?

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.

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.

Read about dynamic programming in our textbook or any of the resources in Thursday's lecture notes.
Choose any two problems from the long list at https://www.sanfoundry.com/dynamic-programming-problems-solutions/ (which has explanations and solutions).
For those two, (1) describe what's going on and (2) write and test a python implementation.
Come to class on Tuesday ready to share with the class.
And/OR : For Thursday, try the coin sums problem .

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.
Read about Huffman coding (for example at Duke's CS2 assignment or the wikipedia page), which we'll discuss and implement next week.

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.

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.