- Math Educators Forum
- New student club re K-12 math certification
- Interest meeting Tuesday, Sept. 15, 7:30 PM, South 328
- Parallelism?
- Generally anything can be parallelized, but there are sometimes limits on how much
- Small vs big problem instances?
- Distinction is empirical, depends on specific languages, machines, etc.
- Pseudocode?
- Not standard - for communication between people
- We’ll probably evolve our own
- Loop invariants?
- Condition true on every iteration of loop
- Useful in proving correctness of loops
- Convex hull?
- Given set of points in plane, find subset that form vertices of convex polygon containing all of the points
- (Knowledge of convex hulls isn’t essential to understanding algorithms, computing them just turns out to be a problem with some elegant algorithms to solve it.)
- Given set of points in plane, find subset that form vertices of convex polygon containing all of the points
- “Problem” = function to be computed
- Mapping from input to output
- Different possible input values are instances of the problem
- Technicality: functions from strings to strings
- Implication: from countable sets to countable sets
- So you can’t really have computing problems with real numbers as input or output (at least not with all reals); use finite approximations to reals instead.
- Section 1.1 + “Pseudocode”
- Algorithm = well-defined procedure that turns inputs to
problem (i.e., function) into outputs
- Steps are unambiguous, definable to arbitrary precision
- Example algorithm (insertion sort) in a reasonble form for us
- Numbers to sort are “keys”
- Data structure - organizing data can dictate algorithms, influence efficiency
- Analyzing speed can be independent of machine/person executing algorithm
- NP-complete problems
- No-one knows if efficient algorithms exist for them
- Efficient algorithm for one implies efficient algorithms for all
- Differences between Matlab and pseudocode or other languages
- e.g., // = comment
- Algorithm = well-defined procedure that turns inputs to
problem (i.e., function) into outputs
- Examples
- Primality testing
- Function? p : natural -> boolean
- p(n) = true iff n is prime
isprime( n ) r = floor( √n ) for i = 2 to r if n mod i = 0 return false end of for return true
- p(n) = true iff n is prime
- Function? p : natural -> boolean
- Sieve of Eratosthenes
- Ideas
- Loop inside loop
- Use vector of numbers, “cross off” = set to 0
- Or use 2 vectors, one of 2 .. n and the other of primes
- To build list…
a = empty vector for i = 2 to n a[i] = i
- Ideas
- Primality testing
- Problem set
- Extra credit (up to 2 points): finish sieve algorithm
- Time analysis
- Read section 2.2