final
- This is a week long, take home exam.
- You may use any books or online sources as long as you cite them specifically. However, you're trying to convince me you understand what's going on - just pointing at someone else's answer may not be enough.
- Clarity counts. That means for full credit you should document and/or explain what's going on and make what you're doing clear to the reader.
1
In a language of your choice, write a program that solves a sudoku puzzle. Explain clearly how your algorithm works, and why you chose that one.
2
Suppose you're asked to create a program which is given as input N numbers, and is asked to perform M searches on that data. As we discussed earlier this semesters, different algorithms (for example direct linear search vs sorting followed by binary search) are best depending on the sizes of N and M. Your task is to show this explicitly.
Implement an algorithm that switches appropriately between two aproaches (those described above or something similar), and show explicitly using randomly generated collections of numbers what the O() behavior is as a function of M and N.
A graph is not required, but it wouldn't hurt, either. A numerical demonstration *is* required; I want more than just an argument for why you think it should have a certain behavior.
Your program should generate a table of values for various (N,M) showing how many steps on average is required, and comparing that to some function f(N,M).
3
Given two algorithms that solve the same problem, one of which is O(n**2) and one of which is O(n log(n)). Is one always faster than the other? Is one always better than the other?
Discuss what factors would influence your choice. Be as specific as you can, including examples if possible.
4
We have seen a number of general algorithm ideas this term, including
- brute force
- divide-and-conquer
- space-vs-time
- greedy
- iterative improvement
- tree pruning (backtracking, branch-'n-bound, heuristics)
For each of these, give a brief description including advantages, disadvantages, typical O() behavior, and an example problem.
(Remember, your goal is to convince me you understand this stuff.
Just quoting the text may not be the best approach. You may
use other sources; just be sure to cite them.)
