assignments
due Tue Jan 29
getting started
- Make sure you can log into this website. Send an email to mahoney@marlboro.edu if you're not on my roster yet.
- Read chapter 1 in Skienna's "The Algorithm Design Manual". Come to class Tues ready to discuss the concepts and the exercises at the end of the chapter, particularly 5, 9, 20, 25, 26.
- Review your existing coding & math chops, with the following problem, using any software tools you like. (I'll show an example of doing this with python and R.)
- Generate a table of the Fibonnaci numbers fib[n] for twenty of 'em, every 7th starting at 100: n=(100, 107, 114, ...).
- Make a plot of n vs fib[n] for these numbers.
- Fit a curve to that data of the form \( y = b x^a \) .
- Anything interesting going on? (Hint: you'll want to use logarithms for the plot and the fit.)
due Tue Feb 5
algorithm analysis
- Read chapter 2 in the text, on O() and algorithm analysis.
- Do exercises
- 1-17 (an induction proof)
- 1-25 (practical O() notation)
- Is log_2(n) the same as log_10(n) as far as O() is concerned? Explain.
- 2-7 (O() algebra)
- 2-18 (lots of O() examples ... if in doubt, put in some numbers and try it)
- 2-46 dropping marbles
- Re-do the numerical exercise we did in class with a sorting algorithm of your choice. (Pick a simple one to implement from, say wikipedia's "sorting algorithm" article; not one we've already done. Comb sort, for example.) So the task is
- implement (and test) the algorithm (you're welcome to adopt the wikipedia pseudo code)
- add a step counter, and modify the sort to return that count.
- apply the sort to randomly generated lists of sizes (say) 30, 100, 300, 3000, 10000
- plot the results in a way that shows it has the expected O() behavior
- explain what's going on.
due Tue Feb 12
data structures 101
- Implement and test a linked list in python, using any of the methods discussed in class. (You can use C if you prefer, but if things aren't working in fairly short order, switch to python.) You'll use this in several of the following exercises.
- Write a program to reverse the direction of a linked list. In other words, if the initial list is "a -> b -> c", then after reversal it should be "c -> b -> a". It should take linear time.
- Write a program to determine whether a linked list contains a loop, and to identify the location of the loop. What is it's O() runtime?
- Implement and test (in python) a binary tree with an API that's either
# with a python object classes, and instances of something as nodes
tree = BinaryTree()
tree.insert(string)
true_or_false = tree.contains(string)
or
# with python dictionaries as nodes
tree = binary_tree()
insert(tree, string)
true_or_false = contains(tree, string)
(You do *not* need to balance the tree.)
Hint: use alphabetic ordering and recursion to
traverse the tree. For example, inserting "cat", "dog", "alpha", "beta"
could give
cat
/ \
alpha dog
/ \
beta
- If time allows, use that binary tree to count the number of different words in a large file. Discuss and measure the O() performance of this task with this data structure.
due Tue Feb 19
sorting
- Read about three sorting algorithms: heapsort, merge sort, and quicksort, in chapter 4 of the text and/or online sources (i.e. wikipedia).
- Describe the layout of a possible min-heap containing the numbers [2, 8, 12, 6, 7, 8, 3, 5, 1, 15].
- Explain (in words; code isn't needed) the steps taken and how that structure changes when the number 11 is pushed onto the heap. How many operations does that take?
- Explain (again in words) what happens when the smallest element is removed. How many operations does that take?
- Explain in your own words how merge sort works, and why it is O(n log(n)).
- What does the partition function in quicksort do? When a list of n elements is sorted, how many times is partition() called?
- Finally, choose one of these three to implement and test.
- You may get code from an online source. If so, make sure you understand how it works and how to use it, and quote your source.
- Demonstrate with a numerical experiment on a random list or two (you don't need the whole "do many and plot" thing; a few examples is enough) of (say) size 1024 that this algorithm behaves with the expected O() behavior. (To do so, you'll need to insert counters into the code to count the number of 'steps', after deciding what a 'step' is.)
due Tue Feb 26
graph basics
- Read chapter 5 in the text, on graphs.
Here is a tree
and a cyclic graph
- Write down two computer representations for each of these, using (a) an adjacency matrix and (b) an adjacency list as defined in class and our text. (That's four representations altogether, using some computerish pseudo-code or Python or whatever.)
- Write down the order that the vertices will be visited for both of these, for both (a) a depth-first and (b) a breadth-first search (i.e. traversal), starting at "A" and "a". (You can do this by hand if you like; writing code is not needed.) Now do the same starting at "D" and "d". Which edges are "back" edges? Are they always the same?
- Define the "diameter" of a graph as a the longest of the shortest paths between vertices. Here's one algorithm that tries to find the diameter:
Pick any node, call it X. From X, do a depth-first search, and from
that find the maximum depth and a vertex furtherst down, call it A.
Now starting at A, do another depth first search, and find the
deepest node from A, call it B. Return the diameter (we hope) as
the depth from A to B.
Consider running this on a tree (an acyclic undirected connected graph)
and a cyclic graph, like the two illustrated above. Does the algorithm
work in either of these cases? Explain why you think so. What is it's
O() behavior? Extra credit: prove your claim in both cases.
- If time allows, implement any of the tasks above, probably by extending the code we started in class.
due Tue Mar 5
midterm
- Pick a sorting algorithm that haven't covered in class, as described in an online source such as wikipedia: sorting algorithm .
- Write a short description (in words and/or pseudocode) of how it works, what its O() behavior is, and why. (As always, quote your sources, and make clear what is and isn't your work. Your goal should be to make me see that you understand, not just to copy and paste someone else's explanation.)
- Implement and test it in a language of your choice (e.g. Python).
- Demonstrate explicitly with numerical experiments on random lists of varying lists and a plot that it has the expected O() behavior.
due Fri Mar 15
shortest path
- Implement, test, and explain either Dijkstra's or Floyd's algorithm.
- You can use my code graph and data structure libraries in the prims algorithm folder as a starting point.
- There may be some exercises coming as well...
due Tue Apr 9
search
- Read chapter 7 in the text.
- Finish a backtrack search of the N-queens problem, writing up the collaboration that you started on Tuesday.
- Do exercise 7.4 in the text, search for an anagram of a sentence using a dictionary of words, combinatorial search, and sentences of your choosing. (You can find a dictionary in http://cs.marlboro.edu/courses/spring2013/algorithms/code/words/ ). One approach would be to choose letters from those remaining, see if what you have is the start of (at least one) word in the dictionary, and abandon that branch when it isn't.
- Try setting up at least one other problem with a backtrack or heuristic search. You're welcome to do any of the ones he mentions in the chapter. The Sudoku problem is a good one for backtrack, and the traveling salesman (with random 2D points) is a good one for local search or simulated annealing (swapping pairs of points to get a different closed path to try to get a shorter circuit). Another (more challenging, I think) choice would be to try something with a genetic algorithm approach ... even the N-queens.
- If time allows, start reading about game searches; google "minmax algorithm" and "alpha beta pruning"
due Tue Apr 16
game search
- Using the code and articles discussed in class this week, write a game search engine for a simple two-player game of your choice. (You can find a list of reasonable canidates at wikipedia's list of abstract strategy games.)
- You can use any of the search algorithms discussed: alpha/beta, min/max, negamax, ... . Don't spend a lot of time on the user interface - that's not the point.
- Questions? Email me.
due Tue Apr 23
final project proposal
- Work on either 8.6 or 8.7 in the text, both on making change with coins, and in particular the (1,6,10) coin problems. Feel free to think about both brute force, dynamic programming, and greedy (get as close to the goal as you can in each step) approaches. Please come to class next Tuesday ready to discuss.
- Think about what you want to do your final project on, and put down an idea or two. Start in.
- You should pick a fairly well know algorithmic problem, do some reading on it, and then
- Implement and test an algorithm that solves the problem
- Do some numerical experiments on different sizes of inputs
- Discuss it's runtime behavior, both theoretical and measured by your experiments.
- Ideally a problem related to something we've done in the 2nd half of the course ... but it can be something else.
- some reasonable choices might include
- searching a simple game for the best move (like what I did with chomp.py)
- a graph search problem (perhaps from Skiena's lists at the end of his text)
- a hash table implementation (we'll discuss that next week)
- generate a maze (with some set of properties) or solve a maze (another type of graph search)
- solve sudoko puzzles (perhaps with backtrack search)
- something that intrigues you on at http://en.wikipedia.org/wiki/Algorithm or one of the pages linked from there (binary search, divide and conquer, brute force, greedy, ...)
- Next week we'll be talking about hash tables and how they're implemented ... so to get a head start, read about 'em online by googling "hash table tutorial" or similar, e.g.
due Tue Apr 30
crypto
- Work on your final projects
- Catch up on any missing old homework (submit a brief note here & the bulk on that page)
- Read about crypto from the links on the class notes for Apr 26
due Fri May 10
final projects
- Submit your final algorithm project. (See earlier proposal assignment.)
- (This can also be a place to post your stuff for the 7th class presentations.)
- Extensions to Monday available upon request.
course grade
- a place for Jim's end of term comments
