MATH 472AProgram Correctness and Complexity
- Faculty
- Mathematics
- Last listed
- 1975–76
No longer offered. It’s in Waterloo’s scanned calendars from 1975–76 to 1975–76 (before that, 1969–70 to 1972–73 used the number for Introduction to Automata Theory); the 1995–96 to 2023–24 calendars are on ucalendar.
Methods of program verification. Implications for structured programming. Inductive reasoning about recursive programs and recursively defined data structures, Analysis of program running time. Models of computation for showing algorithm optimality. Lower bounds on problems related to searching and sorting. “Fast” matrix multiplication and lower bounds on the number of arithmetic operations required to compute certain functions. 3 hours lectures, Winter term Course Descriptions ’ Mathematics
As printed in the 1975–76 calendar, read by OCR; the scanned page is the original.
Requirements, as last listed
Prerequisite :Math 372b
Check it elsewhere
In the scanned calendars
How it read in each calendar from 1969–70 to 1975–76, newest first. The text is OCR of the scanned pages; years whose wording matches are shown once, from the clearest scan. Each year links to its page on uwloo and to that page of the scanned PDF.
1975–76 1 calendar
Methods of program verification. Implications for structured programming. Inductive reasoning about recursive programs and recursively defined data structures, Analysis of program running time. Models of computation for showing algorithm optimality. Lower bounds on problems related to searching and sorting. “Fast” matrix multiplication and lower bounds on the number of arithmetic operations required to compute certain functions.
3 hours lectures, Winter term
Course Descriptions ’ Mathematics
Prerequisite :Math 372b
Not in the 1973–74 to 1974–75 calendars.
1969–70 to 1972–73 4 calendars
Another title: Introduction to Automata Theory, probably a different course under the same number (or a misread scan).
Sequential machine models. Reduction of completely and incompletely specified machines. Decomposition of machines. Nondeterministic machines. Finite automata and regular events. Multitape-finite-state non-writing automata. 2 hours lectures, Fall term. Prerequisite: 132 and 329, or consent of instructor.