CSE303
INTRODUCTION TO THE THEORY OF COMPUTATION
  SPRING 2018


Course Information


News

POST FINAL OFFICE HOURS

Tuesday, May 22, 1:00pm - 4:00pm

HAVE A GREAT SUMMER!
Thank you for being such good students

FINAL is scheduled for Tuesday, MAY 8,  5:30 -8:00 pm,  in JAVITS 100

PRACTICE   FINAL SOLUTIONS  POSTED

 Q4 SOLUTIONS POSTED

PRACTICE FINAL POSTED
Practice Final is due  Wednesday, May 2, in class

Q3 SOLUTIONS POSTED
You can get your Q3 and Practice Midterm  from TA
Mohaddeseh Bastan  during her office hours


MIDTERM  Solutions POSTED
PRACTICE MIDTERM SOLUTIONS POSTED
Q2
 
SOLUTIONS   posted


 All GRADES are  listed on BLACKBOARD
Contact TAs if you need more information or need to talk about grading
 I  will list names  who is correcting which test when you take them
BLACKBOARD also has a DISCUSSION  section where you can post

CHECK  QUIZZES and TESTS Schedule Section  for NEW schedule


I WILL GIVE NEW QUIZZES and TESTS
PLEASE STUDY all material I made public. MINOR typos or mistakes; I leave them to make you STUDY and not only memorize the solutions
Lecture Notes,  Practice and Real Quizzes and Test Solutions contain solutions to ALL of your Homework Problems I have assigned.
Course Textbook contains a lot of solutions, but they are often in a form of ANSWERS, not proper solutions; use them a a hint and write your own, proper solutions

Prerequisites:

cse214, cse215

Time:

Monday, Wednesday:  2:30 pm - 3:50pm

Place:

ENGINEERING 143

Professor:

Anita Wasilewska

208  New CS Building;
phone: 632-8458
e-mail: anita@cs.stonybrook.edu

Office Hours:
  Wednesday  7pm  - 8pm,  Friday 2:30pm - 4:30pm,  and by appointment   

Teaching Assistants

Mohaddeseh Bastan
e-mail: mbastan@cs.stonybrook.edu
Office hours: Tuesday, Thursdays 4:30 - 6:00pm
Office Location: Room  2217  in Old CS Building
 
Hae-Na Lee
e-mail: haenalee@cs.stonybrook.edu
Office hours: Monday, Wednesday 10:00 am - 11:30 am
Office Location: Room  2217  in Old CS Building
 
Allen Kim
e-mail: allen.kim@stonybrook.edu
Office hours: Wednesday  4:00pm - 5:00 pm
Office Location: Room  2217  in Old CS Building
 
Rohit Chatterjee
e-mail: Rohit.Chatterjee@stonybrook.edu
Office hours: Monday 1:00pm � 2:00 pm
Office Location: Room  2217  in Old CS Building

TEXTBOOK

Elements of the Theory  of Computation} by Harry R. Lewis and
Christos H. Papadimitriou, Prentice Hall. (Second Edition, 1998)

COURSE OBJECTIVES

Introduce abstract models of computation such as finite and push-down automata, and analyze their relative expressive power. Explore the connection between abstract machine models and formal languages, as specified by grammars.
Enhance students awareness of both the power and inherent limitations of algorithmic computation via the study of Turing machines and/or other abstract computational models.

COURSE DESCRIPTION

The course is an introduction to the abstract notions encountered in machine computation. Topics include finite automata, regular expressions, and formal languages, with emphasis on regular and context-free grammars. Questions relating to what can and cannot be done by machines are covered by considering various models of computation, including Turing machines, recursive functions, and universal machines.

 

Work Load

  • There will be 4 homework assignments, 4 quizzes covering respective homework assignments, a midterm and a final examination
  • There will be some extra credit problems as a part of quizzes and Tests
  • There will be a Practice Midterm and a  Practice Final ( both for extra credit)

  • Homework assignments

    There will be four (4) homework assignments
    Look in the SYLLABUS for the homework assignment and schedule
    None of  homework assignments will be collected or graded
    Students will be tested on their work on homework assignments by respective quizzes
     Quizzes problems will be taken from, or very close to Homework assignments and   posted  previous Quizzes
    Posted solutions of QUIZZES and TESTS contain solutions of majority of your Homework problems

    Final grade computation

  • You can earn up to 300 points + x  extra points = 300 +x  points during the semester.
  • The grade will be determined in the following way: number of earned points divided by 3 = % grade.
  •  The % grade is translated into a letter grade in a standard way as described in the course SYLLABUS

  • None of the grades will be curved

  • Records of students grades are being kept by the course TA. Contact the TA for information
  • Quizzes and Tests Schedule:

    All quizzes and tests are CLOSED book
     Quizzes will be given given at the end of class

    Here is a preliminary schedule
    Changes, if any will be advertised in NEWS section
     
    Q1 - February 12,  Monday
    Q2 March 19,  Monday
    PRACTICE MIDTERM - take home test published March 7  and due March 19
    SPRING BREAK  March 12 - 18

    MIDTERM  - Wednesday March 21
     Q3 April 11, Wednesday
    Q4 -   April 30, Monday
    PRACTICE FINAL -  
    take home test published April 30  and due May 2 (last day of classes}

    Last Day of Classes- May 2
     
    FINAL to be given during the University assigned place and time during the FINALS period May 8 - 16
    The exact date and place to be posted

    FINAL is scheduled for Tuesday, MAY 8,  5:30 -8:00 pm, place to be posted

    DOWNLOADS

    Syllabus
    Syllabus Slides

    Practice Midterm 
    Practice Midterm Solutions 
    Practice Final 
    Practice Final Solutions

    LECTURE NOTES

    Lecture 1 - Chapter 1
    Lecture 2 - Chapter 1
    Lecture 3 - Chapter 1
    Lecture 4 - Chapter 1
    Lecture 4a - REVIEW of Chapter 1
    Lecture 5 - Chapter 2
    Lecture 6 - Chapter 2
    Lecture 6a - REVIEW for Q2
    Lecture 7 - Chapter 2
    Lecture 8 - Chapter 2: Non-Regular Languages; Review for Q3
    Lecture 9 - Chapter 3
    Lecture 10 - Chapter 3
    Lecture 11 - Chapter 3 Problems
    Lecture 12 - Chapter 3 Short Review
    Lecture 13 - Chapter 4 Turing Machines
    Lecture 14 - Short REVIEW for Final

    SPRING 2018  QUIZZES and  TESTS SOLUTIONS

      Q1 Solutions 
    Q2 Solutions 
    PRACTICE MIDTERM Solutions 
    MIDTERM Solutions 
    Q3 Solutions 
    Q4 Solutions  
    PRACTICE FINAL Solutions -tba

    PAST QUIZZES SOLUTIONS

    Q1 Solutions
    Q2 Solutions
    Q3 Solutions
    Q4 Solutions

    PAST TESTS SOLUTIONS


    Practice Midterm Solutions
    Midterm Solutions

    MORE PAST QUIZZES SOLUTIONS

    Q1 Sample Solutions
    Q1 Practice Solutions to STUDY
    New Q1 Practice Solutions
    Q1 Solutions
    Q2 Sample Solutions
    Q2 Practice Solutions
    Q2 Solutions
    Past Q3 Practice Solutions

    Q3 Practice Solutions

    Q3 Solutions
    Past Q3 Solutions
    Past Q4 Practice Solutions
    Q4 Practice Solutions
    Past Q4 Solutions
    NEW Q4 Solutions

    MORE PAST TESTS and TESTS SOLUTIONS

    PRACTICE FINAL
    Practice Midterm Solutions
    Midterm Solutions
    NEW Midterm Solutions
    PAST PRACTICE FINAL
    PAST Practice Final Solutions

    Academic Integrity Statement

    Each student must pursue his or her academic goals honestly and be personally accountable for all submitted work. Representing another person's work as your own is always wrong. Any suspected instance of academic dishonesty will be reported to the Academic Judiciary. For more comprehensive information on academic integrity, including categories of academic dishonesty, please refer to the academic judiciary website at Academic Judiciary Website

    Stony Brook University Syllabus Statement

    If you have a physical, psychological, medical, or learning disability that may impact your course work, please contact Disability Support Services at (631) 632-6748 or Disability Support ServicesWebsite They will determine with you what accommodations are necessary and appropriate. All information and documentation is confidential. Students who require assistance during emergency evacuation are encouraged to discuss their needs with their professors and Disability Support Services. For procedures and information go to the following website: Disability Support Services Website