assignments

Euclid's algorithm

• Read at least through section 1.1 of the text.
• Do # 8 from Exercises 1.1, pg 8.
• Implement gcd(m,n) using either Euclid's algorithm (pg 4) or "consecutive integer checking" (pg 5) in a programming language of your choice. (In part this is to let me see the state of your programming skills.)

Fundamentals and Data Structures

• Finish reading chapter 1, through pg 40.
• Read the C tutorial (if C is new to you) from the resources page.
• Read wikipedia: pointer (computing)
• Do at least four of these six problems: 1.2 : #2 #5 #8; 1.3 : #3 ; 1.4 : #8, #10 . (You may write some code if you'd like but it isn't required.)
• Write a short C program that implements a binary tree data structure as described on page 25 of the text, using a "struct" for node with pointers to other nodes. Just to choose a simple tree, let's say that the nodes represent a series of coin tosses, and that each one contains the number of heads and number of tails, where each left or right branch from the top is a head or tail. Include a subroutine that can walk the tree and print out a brief description of each node.

Algorithm Eficiency and O(f(x))

• Read chapter 2 - but don't sweat the math details too much
• Do 2.1 #8, #9 (pg 52)
• 2.2 #1, #5, #10 (*)
• 2.3 # 6
• 2.5 #10 (use any language)
• 2.6 #2 (ditto)

Brute Force

• Read chapter 3.
• Do exercises
  • 3.1 #1, #11
  • 3.2 #4
  • 3.3 #7
  • 3.4 #6.
• None of these require writing code, though of course you can do so as an aid if you wish.

O(?) project

• This one is for a grade. (I'm thinking of it as part of the Brute Force chapter's work, but I've given you an extra weekend and put it due on a Monday. Note however that there will still be a weekly assignment due Thurs.)
• Your task is to describe an algorithm to solve one of the following problems, and analyze its O(?) average efficiency with both (a) a verbal discussion and (b) a programming "experiment" including a graph of n vs solution steps with a fitted curve, as I have shown in class.
• The problems you can choose from are all described in chapter 3 of the text:
  • Word Find (3.2 #10)
  • Battleship (3.2 #11)
  • Magic squares (3.4 #9)
  • Alphametics (3.4 #10)
• You'll have to describe (or invent) a way to do the problem for different sizes and decide what to count. Whatever choices you make, be clear about what you mean by "n" (the size of the problem) and "f(n)" (the number of steps your algorithm takes to solve it.)
• You can use any programming language and graphing tools (Excel, gnuplot, Mathematica, ...) you like.
• You are allowed to use other sources (books, internet, but not other people) to find an algorithm. However, make sure that say where your method came from, and make sure you understand and can explain it. Clarity is more important for this assignment than cleverness.
• The code should be your own work. External libraries and packages are OK as long as you aren't just loading something to do the whole thing for you: the algorithm being analyzed should be implemented in your code.
• Document and explain your work, including how to compile it, run it, and what the output looks like.

Divide and Conquer

• 4.1 #6, #7
• 4.2 #1, #3, #9 (dutch flag)
• 4.3 #4
• 4.4 #10 (breaking chocolate bars)
• 4.5 #2
• 4.6 #1
• implement one of these (in a language of your choice) and check its O(?) behavior experimentally:
  • quicksort (4.2 #10)
  • binary search
  • closest pair (4.6 #3)

Decrease and Conquer

• Read chapter 5
• 5.1 #10 (shellsort)
• 5.2 #1
• 5.2 #10 (maze as graph search)
• 5.4 #11 (Gray codes and Towers of Hanoi)
• 5.5 #3 (fake coin)
• 5.6 either #9 or #11

Transform and Conquer

• Read chapter 6, but skip 6.2 (we won't do matrices), and Horner's rule in 6.5 (I don't expect to do much with polynomials, either).
• 6.1 #1, #7
• 6.3 #4, #9
• 6.4 #2, #7
• 6.5 #6a
• 6.6 #9
• any one of the following coding problems :
  • 6.1 #11 (anagrams; use for example /usr/share/dict/american-english on cs.marlboro.edu)
  • 6.4 #10 (sort algorithm comparison)
  • 6.3 #6 (implement AVL tree construction)
  • 6.3 #10 (implement 2-3 tree construction)

Time and Space

• Read chapter 7.
• Do these exercises. (I've kept this brief because of the midterm project.)
  • 7.1 #5
  • 7.3 #1, #5
  • 7.4 #3

midterm heap project

• In a language of your choice, implement, discuss, and analyze a heap "package".
• Your heap should be able to at least
1. insert elements
2. delete elements
3. build a heap from an input list
4. find an element corresponding to a given key
5. return the maximum key
6. delete the maxiumu key
7. return a list of the sorted keys
• Describe what you expect the efficiency O() behavior of each of these, and why.
• Test experimentally on various values of n items in the heap (using randomly generated keys) to confirm this efficiency behavior.
• Include a clean API, some tests, and documentation.
• You may implement the binary heap described in the text, or any of the modern variations described in the Wikipedia article.
• As always, cite your sources clearly.

Greedy

• Read chapter 9
• Do the following three graph problems, all relating to the same graph, either by hand or with a program.
  • 9.1 #7 (b) (min spanning tree with Prim's algorithm)
  • 9.2 #1 (b) (min spanning tree with Kruskal's algorithm)
  • 9.3 #2 (b) (single source shortest path with Dijkstra's algorithm)
• Do the following Huffman coding exercises by hand.
  • 9.4 #2, looking at variations among Huffman codes.
  • 9.4 #10, analyzing the card guessing game
• Write a program (in a language of your choice) to do problem 9.4 #9

Iterative Improvement

• Read chapter 10; skim linear programming (10.1, 10.2)
• Start reading chapter 11, sections 11.1 and 11.2
• Do
  • 10.1 #1a (linear programming)
  • 10.2 #2a (network flow)
  • 10.3 #5
  • 10.4 #1 and #3
• Do 11.2 #8 (fake coin problem)

Limitations of Algorithms

• Finish reading chapter 11
• Browse some P vs NP articles on wikipedia :
  • wikipedia: complexity classes P and NP
  • wikipedia: NP-complete
  • wikipedia: list of NP-complete problems
  • wikipedia: boolean satisfiability problem
• To see how far this business extends, check out the Complexity Zoo and its introduction.
  • http://qwiki.caltech.edu/wiki/Complexity_Zoo
  • http://qwiki.caltech.edu/wiki/Zoo_Intro
• Do these exercises from chapter 11 :
  • 11.3 #1, #2, #6, #10
  • 11.4 #2, #10
• Give a specific example of a CNF-satisfiability problem , a brute force algorithm to solve it, and an O() estimate of the efficiency of your algorithm. (CNF means "conjuctive normal form"; look it up in wikipedia if the text explanation isn't enough.)

Approximate techniques

• Read chapter 12
• 12.1 #1 (code a backtracking solution to the Puzzle Pegs problem)
• 12.3 #1 (nearest-neighbor TSP problem for 5 cities; estimate accuracy ratio)

Final

• take-home final

Term grade

• This is a placeholder for the term grade, along with my comments on your overall work work this semester.