- Theory of Computational Complexity
- I’m Doug Baldwin
- Prime numbers
- Given n…
- See if any number ≤ n divides n
- If so, n is not prime
- Or given n…
- See if any number ≤ √n divides n
- If so, n is not prime
- These are example of algorithms
- Different algorithms for same problem can take significantly different times
- limn→∞(√n / n ) = 0
- Given n…
- Problems have lower bounds on solution time
- Problems group into compexity classes
based on lower bounds
- e.g., partition problem (can you partition a set of values
into 2 subsets with equal sums of their values)
- Simple algorithm: try all possible subsets
- Takes 2n steps
- Primality is a member of class P
- Partition is a member of NP, and NP-Complete
- e.g., partition problem (can you partition a set of values
into 2 subsets with equal sums of their values)
- This course will look at algorithms and their analysis, lower bounds,
and complexity classes
- Text is required
- Collaboration: cite help, but free to work in groups
- Problem sets every 1 - 2 weeks, 3 - 5 questions
- Grading
- Coarser scale than you’re used to
- More generous curving
- Syllabus etc. online
- Algorithms and problems
- Read section 1.1 and “Pseudocode notation” part of section 2.1
- (“Insertion sort” algorithm on page 18 is example of pseudocode)