Class 26 - Complexity and Subclassing

Syncing Repositories

I've made some updates to the provided code for Project 5. You can see all the changes in bitbucket: https://bitbucket.org/cs1120/project5/commits/506eea0e7d6929e374fa2a3d00d45d8c5b114530.

You can syncronize your forked repository with these changes by following these directions in SourceTree:

  1. Select Repository | Repository Settings from the menu.

  2. You should see the Remotes pane, which will have one repository in it now. Click Add to add a new remote.

  3. Give it a name (like upstream). For the URL, enter https://bitbucket.org/cs1120/project5. Click Ok to finish adding the remote repository.

  4. Click Pull in the main window, and for the repository in Pull from repository select upstream (the name you used in step 3).

This should update your version to match the provided code. If there are any changes that cannot be automatically merged with your version, there will be conflicts that you will need to resolve by manually editing the conflicting files (this shouldn't happend, unless you modified the provided code files that have been updated).

Slides

Problems

The complexity of a problem is a short way of saying "the runtime cost of the least expensive algorithm possible solving the problem for the most expensive input of a given size".

For most problems, it is very difficult to get a tight (Θ) bound on the complexity of the problem since this requires reasoning about the best possible algorithm. Sorting is a rare exception where we know the complexity is in Ω(N log N) and know of algorithms that solve the sorting problem with average-case running time in Θ(N log N), so can say the complexity of the problem is in Θ(N log N) where N is the number of elements in the input.

Even for (seemingly) simple problems like multiplcation, we do not yet know a tight bound on the complexity of the problem.