Week 6
- Analyze bubble
sort, as defined in Wikipedia; this is not a great algorithm, as
Obama has said.
- Argue that worst case complexity is \(O(n^2)\), where \(n\) is the length of the array.
- Use the notion of a loop invariant (see
page 19 of the Algorithms book) to demonstrate correctness; in
particular, find a loop invariant(s), that satisfies:
- Initialization
- Maintenance
- Termination
- Show that multiplying two \(nxn\)
matrices can be accomplished in \(O(n^3)\) steps.
Week 7
- Consider Horner’s
method for evaluating polynomials. Derive the stated complexities in the
article.
- Code a bottom up version of merge sort
- Suppose you have a linked list of say \(10\) nodes, how would you add/insert data
into a new node at position \(5\) say?.
To be concrete you can use this linked list. Your method should only assume you
have access to header; that is, it should start from the header.
Version: 16 October 2026