T R 03:45 pm - 05:00 pm
SMH - 111
|
Instructor Email |
Dr. Feodor Dragan |
Teaching Assistant Email |
TBA
|
This is a graduate level course. 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.
Introduction to Theory of Automata,
Formal Languages, Computation - CS 4/56201, Design & Analysis of Algorithms - CS 4/56101
"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 |
Tuesday |
March
?, 2015 |
03:45 - 05:00 p.m. |
30% |
|
Final
Exam |
Wednesday |
May
6, 2015 |
7:45
- 10:00 a.m. |
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
2015