Synopsis of Course Introduction ------------------------------- Perhaps the two most hated courses in the CS curriculum at UCF are the Discrete Structures courses. Two reasons I think these are students' least favorite classes are: 1) They seem useless to your future job. 2) They are hard. While I can't do anything about #2 except for try to explain ideas as clearly as possible and not get bogged down in boring details, I can give some reasons as to why #1 is a myth. Students seem to think that unless they directly use a fact they learned from school in their future job, that fact was useless. However it's impossible to make school chalk full of facts and items you directly use for your job. The reason for this is that jobs CS majors get vary greatly!!! Some work on cell phones, some work with art, some work with robots, some even become teachers =) Clearly the subset of CS knowledge most relevant to each of these different types of jobs is very different. Although it's unlikely you will use the material from this class directly in your future work, it's not useless. Here's why: 1) We will essentially learn rules for different types of machines and then talk about the power of those machines. In doing so, you will have practice solving problems using a certain set of tools. This sort of practice will often make you a better problem solver in a different domain. Ultimately, many jobs can be done better if one is a good problem solver. In work environments, I have seen employees comment, "Oh, that class was useless." But I have also observed that these are the same employees that can't solve a problem that utilizes the skills necessary from this class. (Or maybe they solve the problem, but in a much less efficient manner. Or maybe they tell their boss that something is impossible and then that part of the project is abandoned.) 2) Specifically, we will talk about what types of problems are solvable by what types of machines and what types of problems are unsolvable by what types of machines. One of the models we will use is as powerful as a computer can be. The rammification is that by studying the Turing Machine model, we will learn the limits of the computer. For example, if you know that a problem take a very long time to solve on a Turing Machine, that's a good indication that you should try to find an approximate solution in a reasonable amount of time, as long as that fits the specification given. Here's a very broad outline of the course: 1) Determinstic Finite Automata(DFA) and Regular Languages DFAs are machines that work without memory essentially. Their job is to decide whether or not a string belongs in a language or not. Regular languages is the set of languages that can be described using some basic intuitive symbols, which will be explained later. We will show that and language that can be described with a DFA can also be described as a regular language and vice versa. 2) Pushdown Automata(PDA) Context-Free Languages Context-Free Grammars describe languages that have a similar complexity to computer languages. It's interesting to note that all regular languages are also context free languages. PDA's are machines with a limited memory model that can accept more langauges than DFAs. It turns out that the languages PDAs can accept are the set of Context Free Languages which can be described by another set of intuitive rules. 3) Turing Machines (TM) This is our model that is as powerful as a computer. We will discuss various TM models, whether they are equivalent, as well as what a decidable languages is versus a recognizable language. Also, we will talk about the notion of reducibility. Although this section is esoteric, we humans typically use the notion of reducibility in our daily lives. 4) Complexity Theory We will discuss the famous P vs. NP question and learn the difference between the two and the rammifications for the perceived difference.