New York University Skopje

Faculty of Computer Science and Information Technology

COURSE SYLLABUS
Computational Modeling
Spring 2008 

Instructor(s):  Prof. Dr. Vladimir Radevski
Class Hours:  Wednesdays, 10:00h – 12:00h
Classroom:  Lab 2
Office Hours: Wednesday, Thursday, 13:00h – 15:00h
E-mail address: Prof. Dr. Vladimir Radevski (radevski@nyus.edu.mk)
Phone Number: +389 2 2034 632

Textbooks:

Introduction to the Theory of Computation, Michel Sipser, PWS Publishing, 1996.
Other resources:
     Introduction to Automata Theory, Languages, and Computation John E.
    Hopcroft, Rajeev Motwani, Jeffery D. Ullman Addison Wesley, 2nd ed
    Automata and Formal Languages, Dean Kelly, Prentice Hall ISBN 0-13-497777-7
    Models of Computation, John E. Savage, Addison Wesley, ISBN 0-201-89539-0
    Introduction to Languages and Theory of Computation, John C. Martin, McGraw Hill 1997

 Course Description
This course is meant to give the basis of the Formal Languages Theory, Automata, Computations Models and Computability.    

Course Objectives
After completing this course, students will be able to: 
Understand and apply the concepts of Regular Formal Languages
    Formal definition of computation
    Design of finite automata
    Formal definition of nondeterministic finite automata
    Equivalence NFAs DFAs
    Regular expressions
    Nonregular languages
Understand and apply the concepts of Context-Free Languages
    CF Grammars
    Pushdown automata
    Non-context-free languages
Describe the basis of the Computability theory
    The Church-Turing Thesis
    Turing Machines and variants
    The definition of algorithm
Determine the problem of Decidability
    Decidable languages
Understand the basis of the Complexity Theory
    Measuring Complexity
    The Class P
    The Class NP
    NP-Completeness

 Grading
The grade depends on the following:
    Class participation       5%
    Home work                  10%
    Quizzes                        10%   
    Midterm exam             30%
    Final exam                   40%

 THERE WILL BE NO MAKE UP EXAMS

*) H/E - refeers to the hardcopy / electronic version of the textbook;
HW - homework (dd/mm) to be submitted in a hardcopy on the specified day/month

Grading Scale