|
Instructor Email |
Dr. Feodor Dragan or by appointment |
Teaching Assistant Email |
TBA
|
We will cover the following topics.
Finite
state automata (overview): Deterministic and non-deterministic finite state machines;
regular expressions and languages. Techniques for identifying and describing
regular languages; techniques for showing that a language is not regular.
Properties of such languages.
Context-free
languages (overview): Context-free grammars, parse trees, derivations and
ambiguity. Relation to pushdown automata. Properties of such languages and
techniques for showing that a language is not context-free.
Turing
Machines: Basic definitions and relation to the notion of an algorithm
or program. Power of Turing Machines and Church`s hypothesis.
Undecidability: Recursive
and recursively enumerable languages. Universal Turing Machines. Limitations on
our ability to compute; undecidable problems.
Computational
Complexity: Decidable problems for which no `efficient` algorithms are
known. Polynomial time computability. The notion of NP-completeness and problem
reductions. Examples of `hard` problems. Lower bounds in computational
complexity.
Discrete Structures for CS
Michael Sipser,
in the preface to his textbook, Introduction to the Theory of Computation,
explains why this course is important, and exciting:
You are about to embark on the study of a
fascinating and important subject: the theory of computation. It comprises the
fundamental mathematical properties of computer hardware, software, and certain
applications thereof. In studying this subject we seek to determine what can
and cannot be computed, how quickly, with how much memory, and on which type of
computational model. The subject has obvious connections with engineering
practice, and, as in many sciences, it also has purely philosophical aspects.
...
Theory is relevant to practice. It
provides conceptual tools that practitioners use in computer engineering.
Designing a new programming language for a specialized application? What you
learned about grammars comes in handy. Dealing with string searching and
pattern matching? Remember finite automata and regular expressions. Confronted
with a problem that seems to require more computer time than you can afford?
Thank back to what you learned about NP-completeness. Various application
areas, such as modern cryptographic protocols, rely on theoretical principles
that you will learn here.
Theory is also relevant to you
because it shows you a new, simpler, and more elegant side of computers, which
we normally consider to be complicated machines. The best computer designs and
applications are conceived with elegance in mind. A theoretical course can heighten
your aesthetic sense and help you build more beautiful systems.
Finally, theory is good for you
because studying it expands your mind. Computer technology changes quickly.
Specific technical knowledge, though useful today, becomes outdated in just a
few years. Consider instead the abilities to think, to express yourself clearly
and precisely, to solve problems, and to know when you haven't solved a
problem. These abilities have lasting value. Studying theory trains you in
these areas.
Practical considerations aside,
nearly everyone working with computers is curious about these amazing
creations, their capabilities, and their limitations. A whole new branch of
mathematics has grown up in the past 30 years to answer certain basic questions.
Here's a big one that remains unsolved: If I give you a large number, say, with
500 digits, can you find its factors (the numbers that divide it evenly), in a
reasonable amount of time? Even using a supercomputer, no one presently knows
how to do that in all cases within the lifetime of the universe! The factoring
problem is connected to certain codes in modern cryptosystems. Find a fast way
to factor and fame is yours!
"I have been told by past
students that this is one of the more difficult courses in the Computer Science
curriculum, but at the same time they enjoyed it the most. Keep this in mind
when the going gets tough! The reason for the difficulty is that it covers
abstract and mathematical topics which are not very easy to grasp without
putting in a good deal of hard work. There are a number of excellent reasons
for becoming proficient with the theoretical tools that we will develop in this
course.
1. Most of what you learn in the first part of the course will be required in the design or analysis of almost any reasonably complex software or hardware system. For example, the theory of finite state machines and regular expressions is needed for the design of switching circuits, components of compilers such as lexical analysis, pattern-matching, text-editors, unification as needed in Prolog or for automated deduction, and almost any program which processes user commands. The description of programming languages and the design of parsers for them will require an intimate knowledge of context-free grammars. More interestingly, with the presence of a large amount of unstructured text on the World-wide Web, it has become increasingly important to employ techniques taught in the course to extract structured information from this chaos.
2. The second half of the course is concerned with a more philosophical approach to computer science. Here we will be concerned with the basic questions of computability and tractability. Using the concept of Turing Machines we will try to make precise the notion of an algorithm and explore its limitations. We will encounter undecidable problems, viz. those which cannot be solved by any algorithm or computer. Even if a problem is decidable it may turn out to be intractable, i.e., there does not exist any efficient algorithm to solve that problem. These notions have had (and will continue to have) a profound influence on our approach to using computers to solve problems.
3. Finally, I think the most important role of this course is to turn you into ``mathematically mature'' computer scientists. This course is quite mathematical and should develop your skills of precise and formal reasoning. These skills will prove to be extremely important in the design, analysis, and verification of complex software and hardware systems. "
|
Homework |
- |
- |
- |
40% |
|||
|
Midterm
Exam |
TBD |
March
?, 2018 |
05:30 - 06:45 p.m. |
30% |
|||
|
Final
Exam |
Monday |
May
7, 2018 |
|
30% |
Cheating
and plagiarism constitute fraudulent misrepresentation for which no credit can
be given and for which appropriate sanctions are warranted and will be applied.
The university affirms that acts of cheating and plagiarism by students
constitute a subversion of the goals of the institution, have no place in the
university and are serious offenses to academic goals and objectives, as well
as to the rights of fellow students.
"Cheat"
means to intentionally misrepresent the source, nature, or other conditions of
academic work so as to accrue undeserved credit, or to cooperate with someone
else in such misrepresentation. Cheating includes, but is not limited to:
1. Obtaining or
retaining partial or whole copies of examinations, tests or quizzes before
these are distributed for student use;
2. Using notes,
textbooks or other information in examinations, tests and quizzes, except as
expressly permitted;
3. Obtaining
confidential information about examinations, tests or quizzes other than that
released by the instructor;
4. Securing,
giving or exchanging information during examinations;
5. Presenting
data or other material gathered by another person or group as one's own;
6. Falsifying
experimental data or information;
7. Having
another person take one's place for any academic performance without the
specific knowledge and permission of the instructor;
8. Cooperating
with another to do one or more of the above;
9. Using a
substantial portion of a piece of work previously submitted for another course
or program to meet the requirements of the present course or program without notifying
the instructor to whom the work is presented; and
10. Presenting
falsified information in order to postpone or avoid examinations, tests,
quizzes, or other academic work.
"Plagiarize"
means to take and present as one's own a material portion of the ideas or words of another or to present
as one's own an idea or work derived
from an existing source without full and proper credit to the source of the
ideas, words, or works. As defined, plagiarize includes, but is not limited to:
a. The copying
of words, sentences and paragraphs directly from the work of another without
proper credit;
b. The copying
of illustrations, figures, photographs, drawings, models, or other visual and
nonverbal materials, including recordings of another without proper credit; and
c.
The presentation of work prepared by another in final or
draft form as one's own without citing the source, such as the use of purchased
research papers.
Academic Sanctions, From Section D The following
academic sanctions are provided by this rule for offenses of cheating or
plagiarism.
1. Refuse to
accept the work for credit; or
2. Assign a
grade of "F" or zero for the project, test, paper, examination or
other work in which the cheating or plagiarism took place; or
3. Assign a
grade of "F" for the course in which the cheating or plagiarism took
place; and/or;
4. Recommend to
the department chair or regional campus dean that further action specified in
the rule be taken. The department chairperson or regional campus dean shall
determine whether or not to forward to the academic dean or to the vice
president for the extended university a recommendation for further sanction
under this rule.
Procedures for invoking sanctions. (From Section E)
(1)
Academic
administrative procedures pertaining to paragraph (D)(1)(a)
of this rule. In the event that an instructor determines that it is more
probable than not that a student in a course or program under the instructor's
supervision has presented work for university credit which involves an act of
cheating, plagiarism or cooperation in either, then the instructor shall:
(a)
Inform the
student as soon as is practical, in person or by mail, of the belief that an
act of cheating or plagiarism has occurred. If the student cannot be reached in
a reasonable period of time, the instructor may proceed with sanctions,
notifying the student in writing as promptly as possible of the belief and the
procedural steps the instructor has taken.
(b)
Provide the student an opportunity to explain orally, in
writing, or both, why the student believes the evaluation of the facts is
erroneous.
(c)
If the
explanation is deemed by the instructor to be inadequate or if no explanation
is offered, the instructor may impose one of the academic sanctions listed in
paragraph (D)(1)(a) of this rule. Where appropriate,
the instructor may recommend the imposition of academic sanctions listed in
paragraph (D)(1)(b) of this rule. In addition, the
instructor may refer the matter to the dean of the college, campus, or school
in which the student is enrolled for imposition of academic sanctions listed in
paragraph (D)(1)(b) of this rule.
(d)
The instructor
shall notify the office of judicial affairs of the circumstances and action
taken. Such notification will be used as background information in the event
that formal conduct charges are initiated against the student.
(e)
The instructor
shall inform the student in writing of the right to appeal, and the procedure
to follow.
(f)
The instructor shall
keep the evidence of cheating or plagiarism in a secure place and provide it
upon request to any appeals officer or the conduct officer. The instructor
shall provide copies on request to the student at the student's expense.
(g)
The instructor
shall cooperate with academic and student conduct personnel in any appeal of
the decision, and/or in adjudication of any disciplinary proceedings.
F.
Dragan
Spring
2018