SE120 - Discrete Structures II

SE120 homepage.

Course text: James L. Hein, Discrete Structures, Logic, and Computability, second edition, Jones and Bartlett, Sudbury, Massachusetts, 2002.

Course Outline

Program correctness: Hoare triples, assignment, consequence, composition, if-then, if-then-else, while

Ordered structures: tuples, words over alphabets, languages over alphabets, lexicographical ordering, relations, representing arbitrary problems as language acceptance problems

Set theory: cardinality, countable sets, uncountable sets, diagonalisation, limits on computability

Graphs: graphs, paths, traversals, trees

Relations: binary relations, equivalence relations, equivalence classes, partitions, order relations, partial orders, topological sorting