assignments

Assignment 0

• Read chapter 0 of the prologue of the textbook.
• Do exercise 0.1, looking at the meaning of O() notation.
• In a programming language of your choice, without using any built-in ordering functions or looking up other people's recipes, write a function that sorts a list of numbers. (Your function does not need to be fast. Hint: think about how you might do it by hand.) What is the O() behavior of your function? (We'll come back to this sorting problem later; it's a classic.)

assignment 1

• Read 2.3, 2.4 in the text, on "divide and conquer" algorithms. Read 2.3 carefully; google "quick sort" and read about it, too. (Described briefly in text at end of 2.4).
• Do problems 2.12, 2.14
• Either :
  • Implement one of quicksort, merge sort, or radix sort in C. Do some numerical experiments to see what the time/space behavior is as a function of n.
  • If your C doesn't feel ready, do the sorting assignment in another language (e.g. python), and do as well some smaller, practice C programming. Which part of the problem is difficult for you to do in C?

assignment 2

• After looking at (and borrowing from) my C examples from this week, pick a sorting algorithm and implement it in C. You can use one we haven't done yet from wikipedia's "sort" page, or re-write your own code. This doesn't have to an O(n log(n)) algorithm. Discuss briefly what's going on in the comments, and the algorithm efficiency.
• Read about the math behind the fourier stuff in one of your own math texts, or from the wikipedia articles I pointed to, or from any "complex numbers", "fourier series", "inner product" google you like.
• Start reading Jims Fourier Notes.pdf
• Practice your math with fourier warmup.pdf

assignment 3

• I have added a "Fourier stuff" section to the resources page; check out the links there, particularly my example of working with and plotting complex numbers in python. If need be, look back on my fourier warmup.pdf problems and do them in python.
• In the definition of the Discrete Fourier Transform at wikipedia: Discrete Fourier Transform, all the sum indices are from 0 to N-1, rather than the (-N/2 + 1) to (N/2) that I described in class. This isn't a mistake: it turns out that it doesn't matter; you get the same result either way. Explain clearly what's going on, and why. (Hint: what does exp(i theta) do when theta is bigger than 2 pi?)
• Implement in Discrete Fourier Transform (*not* the fast one; just do the full sum) in python, and use it to calculate the transform of a these few examples. Plot two graphs: the real part, the imaginary part on one, and the length, angle on another. (This should be a pretty short python program: you're using its complex numbers, doing something like what I did in my example here, and looping over the input.) How many multiplications does each of these take?
  • N = 8, x = [ 0, 1, 2, 5, 0, 0, 0, 0]
  • N = 16, x = [ 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 ]
• What happens with the four 1's in that previous example shifts to a different start index?
• Similarly, implement the reverse transform and verify that the numbers return to the originals.
• Finally, implement in python the Fast Fourier transform as described in the pseudo-code here. Again, this should be a short python program which for N=1 leaves the vector alone, and otherwise splits it into two odd/even pieces and calls itself recursively. Only do the case were N is a multiple of 2. Test it with the vectors and results from the previous problem; it should give the same numbers. How many multiplications does this algorithm take?
• Optionally, if you still have time :
  • Describe in words why the FFT is so much faster, and
  • Get some more realistic data (N=4096 audio sample, say) and generate a realistic frequency spectrum. What is the number of mulitiplications for the DFT vs FFT in this case?

assignment 4

• Explore the links and topics from the Feb 17 notes.
• Download, compile, and run my n_queens C code mentioned there. Pay particular attention to queens.h and test.c in the n_queens/ folder. (You can download the files individually, or use mercurial to grab a clone of the repository; see http://code.google.com/p/jimmahoney/source/checkout for details.)
• In that n_queens code, the boards structure contains explicitly the number of boards in its linked list. Without using that "count" field, write a recursive procedure "int boards_size(board)" that finds the number of elements in a boards structure. In test.c, solutions is such a boards structure. Call boards_size in test.c on solutions, just before it's freed near the end of the code, and verify that your function gives the same result as the solutions size reported in the "number of solutions = " line.
• Depending on your level of experience with this stuff, write some C code to implement either (a) a linked list of strings or (b) a binary tree of strings. In either case, include a function to recursively print all the strings. (And if you're really looking for some practice, something to print the binary tree as a tree.) If this C stuff is really not clicking yet, then do this in another language of your choice.

Assignment 5

• Read chapter 3 (graphs) and 4 (graphs with distance) in Dasgupta
• Look at the Python code I posted in class last week, which is a starting point for an implementation of the chapter 3 algorithms.
• From chapter 3, do these exercises:
  • 3.2, 3.10, 3.12
• Read about binary heap, say at wikipedia: binary heap and in our text. Implement one in python to use in Dijkstra’s algorithm, including the makequeue(), deletemin(), decreasekey() methods needed for the pseudo-code on pg 121.
• Do problem 4.1 by hand and with a python program, using your binary heap and Dasgupta's pseudo-code on pg 121.

midterm project

• Choose a classic algorithm/problem to explore using the techniques we've been discussing this semester.
• Write a short paper describing the general approach (i.e. divide-and-conquer, brute-force, ...), explaining its expected O() behavior, and the data structures used.
• Write a computer program in C or Python (using only simple python data structures) that solves the problem, using a published approach or one of your own. Do some numerical experiments on various size inputs, and graphically show that the O() behavior is as expected.
• Some problems you might consider include
  • Prim's algorithm (minimum graph spanning tree)
  • numerical algorithms (FFT, matrix operations, etc)
  • The traveling salesman problem (brute-force approach is fine)
  • "maze solving" or "maze generating algorithms" (Aaron: the Wikipedia articles wit these names are reasonable starting places for either)
  • Knuth's "Dancing Links" algorithm (sudoko, crosswords; a backtracking search)
  • string searching algorithms (more to say than you might think)
• As I discussed in class, this may be turned in after break without penalty if you prefer.
• If you have any questions, ask.

Assignment 6

• Read about Huffman and LZW encoding from the links in my class notes from last week.
• By hand, encode and decode "she sells sea shells" and "her sphere goes here" using both methods. Explain where the codes come from, the intermediate data structures, and how these things work.
• Choose one of the two algorithms to implement, either in C or Python. You may use ships of code from outside sources; if so, quote them, and make sure you understand what they're doing and how to use them. In any case, test the code and explore how much compression it can get, and in what cases it works well or not so well.

Assignment 7

• Read up on hash tables from the sources in my notes from this week.
• Using the C files in code/hash_table (my utilities, moby dick, and Kristensson's C Hash Table implementation, count the number of occurances of each word in moby dick.
• From looking at Kristensson's code,
  • What hash function is used? Why is that a good choice? (Or is it a good choice?)
  • What collision mechanism is used? What does that imply about the O() behavior when there are a) few, b) many collisions?
• Modify Kristesson's code to count the number of collisions for the moby dick word count. How does this vary with the size of the table that you choose?

Assignment 8

• Propose a final project; see the May 6 assignment for details. This should be something like what you did for a midterm, but on a different topic.
• Read about number theory, primes, and crypto , sections 1.2, 1.3, 1.4 in our textbook and the resources from this week's lecture notes.
• In Thu April 14's I gave code for (a**b mod c). Using that or a similar implementation in a language of your choice,
  • find two primes each in the 10**8 range using Fermat's little theorem and a probabilistic approach, and
  • use them as (p,q) in an simple version RSA algorithm. Either by hand or in code, find (n,d,e) and use them to encode and decode a short message.

Assignment 9

• Work on your final projects, and drop a note as to how it's going.
• Finish primes/rsa assignment from last week, if you haven't yet.
• Google and read about "Boyer-Moore search" ; we'll talk about it in class.
• Play around with openssl on the command line:
  • generate a public/private key pair
  • use the public key to encrypt a file of your choice
  • use the private key to decrypt a file of your choice
  • also do encryption with a symmetric key (make up a secret word)
  • and find the sha1 digest of the file

Last class

• Come to class ready to present your final project.

Final Project

• Explore an algorithm using the ideas we discussed in class this term. See the midterm project assignment for some ideas, or choose one of your own.
• Explain in words and equations how this algorithm works, what its O() efficiency is, why it's an interesting solution to a problem worthy of attention, and how it compares to other solutions.
• In a language of your choice, implement and test the algorithm. Show the results of your numerical investigation with some sort of graphic, and compare with the theoretical result.
• (Extensions until Monday are possible; talk to me if you need one.)

term grade

• A place for Jim's final remarks.