assignments

getting started

• Anagram warm-up.
  • Describe in words an algorithm to decide if two words or phrases are anagrams. Be very specific.
  • How did you come up with this? Are there any "special cases" or issues to worry about? Could this be used to find words in a dictionary which are anagrams? Could it be used to find word phrases from a dictionary that are anagrams of a given phrase?
  • Implement your algorithm in a programming language of your choice, and test it on some anagrams. (The wikipedia article gives some, for example.)

• Start reading chapter 1 in the text, at least up through section 1.1 on Euclid's algorithm.
• Do exercise 5 on page 8.

• Start exploring the C programming language, or review it if you already know it. (The resources page has some references that may be helpful.)
• Write, compile, and test a C program that asks for an input line, and then prints how many characters were in that line.

• Give me some feedback on your programming background, math background, and experience (if any) with C.

structures in C

• Write a C program that creates a tree data structure and traverses it.
• We discussed this in some detail in class, including notions such as depth-first vs breadth-first, nodes, pointers, a "fringe" to manage the search, and so on. Use as much of that as you like.
• You are allowed to re-use code from class, or other places for that matter. As always, give proper attribution. And as always, the goal is to gain facility and demonstrate your understanding of the material.
• What tree you use is up to you, as is what traversal is trying to accomplish (find something, visit each node and print something, or whatever). Fit the scale of the problem to your background and skills. Two trees mentioned in class were
  • coin flipping, with each node corresponding to a sequence of flips.
  • the SpinOut puzzle (or different size variation) with the nodes of the tree corresponding to possible move sequences.
• Questions? Ask.

analysis fundamentals

• Read up through the end of chapter 2 in the text.
• Do problem 3 in Ex 2.2 on page 60. (bounding order of functions0
• Do problem 10 in Ex 2.2 on page 61. (This one is tricky.)
• Do problem 4 and 6 in Ex 2.3 on page 68. (algorithm analysis)
• Do problem 5 in Ex 2.4 on page 77.
• Do problem 10 in Ex 2.6 on page 91, based on our work with GCD from the first assignment.
• (As always, put in a reasonable amount of time, e.g. approx 9 hrs/week outside class), and bail on any given problem with a discussion your partial work if need be.

brute force

• read chap 3, on brute force
• start chap 4, on divide-and-conquer
• Do exercises:
  • pg 102, ex 3.1, numbers 6 and 11
  • pg 106, ex 3.2, number 5
  • pg 113, ex 3.3, number 7 (linear time extreme points)
  • pg 119, ex 3.4, number 7 (clique problem)
• Do any one programming problems :
  • word find, pg 106 number 10
  • battleship, pg 107 number 11
  • magic squares, pg 119 number 9

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
• Propose a problem (or problems) for the midterm project. (See below.)
• Do the following exercises from 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

midterm project

• This one is for a grade.
• 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.
• Any of the algorithms we've been discussing in class so far is fair game: a sorting algorithm (or perhaps two, if you'd like to do a comparison), convex hull, closest points, etc.
• Whichever one you choose, 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. (I have an example of C code with gnuplot analysis here.)
• 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.

transform and conquer - part 1

• 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
• 6.4 #2, #7

space and time

• Read chapter 7
• Do 7.1 #5
• Do 7.3 #1, #5
• Do 7.4 #3

dynamic programming and greedy

• skim chapter 8; read chapter 9
• Do 8.4 #1
• 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

iterative improvement

• Read chapter 10. Skim the simplex bits; peruse the rest.
• Do 10.2 #2a
• Do 10.3 #5
• Do 10.4 #1, #3
• Start reading chapter 11
• Propose a final project.
  • Comparable to a 5-10 page paper's worth of effort.
  • Either a problem that you don't have a specific "good" approach ahead of time, in which you investigate different algorithmic approaches, or
  • a problem that you do know a "good" way to do it, and compare that one with another way (perhaps brute force).
  • In any case, as in the midterm project, you should do both an analytic and numerical (i.e. programming) analysis.

project presentation

• Discuss in class the status of your project.

final project

• Turn in the final project described above.

course grade

• a place for Jim to record your term grade.