In this section of the course we will consider applications to computer science in the design of logic circuits and adders and use of induction to prove algorithms correct. Next we take up the art of organizing situations so that underlying structure can be expoloited to count distinct possibilities. Here there are a small number of tools which can be combined in many different ways. Functions let us get from one set to another and form the basis for much of mathematics. We consider major properties of functions and conditions guaranteeing the existence of an inverse.
Applications here are to finite state automata.
We then consider the relative growth rate of functions. Understanding growth rates of functions is essential for judging the comparitive merits of different algorithms for the same task. The course ends with an exploration of relations and their properties. We focus primarily on equivalence relations and their use in simplifying finite state automata. I will grade selected problems for a total giving one fourth of the grade.