COMP 590 – Advanced Topics in Comp Sci – Spring 2018

Course Syllabus

  • Course URL: http://soltys.cs.csuci.edu/blog/?page_id=3183
  • CI Catalogue URL
  • Instructor: Michael Soltys <michael.soltys@csuci.edu>
  • Twitter: @MichaelMSoltys
  • Course Outline: This course presents the foundations of computation. We define the basic elements of computation: alphabets, words and languages. We then study languages through the lens of standard models of computation: Finite Automata (as DFAs, NFAs and Regular Expressions), Context Free Grammars (as grammars and as PDAs), and finally Turing machines. We will look at issues of decidability, and at impossibility results (e.g., Pumping Lemmas, undecidability, the Post Correspondence problem, etc.). At the end of the course the student will have a firm grasp of the foundations of computer science and the limits of computability, as well as deciding what model of computation is suitable for a given problem.
  • Lectures: Tuesdays, 4-5pm, Location Bell Tower 2372.
  • Textbook: Chapter 8 in An Introduction to the Analysis of Algorithms, by Michael Soltys.
  • Grading: One long assignment, to be completed throughout the course, and handed in at the end.
  • How to avoid plagiarism: The assignment will be worked on individually; verbal discussions of problems among individuals are allowed, but you should not show written notes, and you should not leave such discussions with written notes.
  • Attendance: Attendance is required.
  • Students with disabilities: Cal State Channel Islands is committed to equal educational opportunities for qualified students with disabilities in compliance with Section 504 of the Federal Rehabilitation Act of 1973 and the Americans with Disabilities Act (ADA) of 1990. The mission of Disability Accommodation Services is to assist students with disabilities to realize their academic and personal potential. Students with physical, learning, or other disabilities are encouraged to contact the Disability Accommodation Services office at (805) 437-8510 for personal assistance and accommodations. Please discuss your arrangements with the instructor as soon as possible.
  • Check this web page regularly for announcements.

Announcements and class diary

  • Feb 13, 2018: We discussed Regular Expressions, and the fact that DFAs, NFAs and REs recognize the same class of languages: regular languages. Also, the limitations of these models: if counting is necessary, they cannot do it. 
  • Feb 6, 2018: Definition of a regular language; all finite languages are regular. Extended transition function (\hat\delta) and Non-deterministic finite automata (NFA).
  • Jan 31, 2018: This course has a Canvas page: https://csuci.instructure.com/courses/4098 but we will use it minimally.
  • Jan 30, 2018: We introduced finite automata and saw some examples of languages recognized by them. We posed the following exercise: find a DFA for: \{0,1\}^*001^*00.
  • Jan 25, 2018: Please pick up your course materials (at cost of printing) from the Copy Center at the UGlen Town Center (email: copycenter@coast-repro.com) .
  • Jan 23, 2018: First lecture, alphabets, words and languages; Kleene’s star and concatenationWe discussed the philosophical underpinnings of representing information with strings.

Assignment Problems

  1. Give a DFA for \{0,1\}^*001^*00 and prove that it is correct.
  2. Let L_n=\{(f_i)_u:i\le n\}, that is, L_n is the language of unary encodings of the first n Fibonacci numbers. Design A_n with as small a number of states as possible.
  3. Consider the family of languages L_p=\{w\in\{0,1\}^*:\#(w)_0=p\}, that is, L_p is the languages of binary strings where the number of 0s is p, where p is a prime. Give the Regular Expression for L_p.