Courses

CS 344: Foundations of Computing

Objective	To introduce the fundamental mathematical tools needed in the study of algorithm correctness and the analysis of algorithm performance.
Pre-Conditions	[Math243] Logic ... truth table, direct proof, contrapositive, induction, propositional [Math243] Set notation [Math243] Relations and Functions [Math243] Introduction to graphs and trees
Post-Conditions (Topics)	[3 weeks] Induction and Recursion [CS445] [CS473] [1 week] Review of graphs and trees¹ [1.5 weeks] Methods of Logic ... propositional, predicate [CS445] [CS460] [2 weeks] Program development and Verification [1.5 weeks] Recurrence relations [CS445] [1 week] Regular expressions [3 weeks] Combinatorics [2 weeks] Elementary Discrete Probability: probability space, random variables, events, expected value [CS445]

1 The review of graphs and trees is needed because Math243 is supposed to cover these topicsl, but currently does not. Once it does they can be removed from CS344.

Last revised on 27 February 1997 by John Hartman.