CSE303
INTRODUCTION TO THE THEORY OF COMPUTATION
  SPRING 2019


Course Information


News

Q2 SOLUTIONS POSTED

PRACTICE MIDTERM POSTED
PRACTICE MIDTERM
  is due any day BEFORE or ON Monday, March 25 via BLACKBOARD

MIDTERM is  as scheduled Thursday, March 28
Midterm covers material from Lectures 1- 6a

Q1 SOLUTIONS POSTED
Q1 corrected copies
are in my office to pick up during my office hours

We will finished   Lectures 1 - 6a

Office Hours POSTED
TESTS and QUIZZES SCHEDULE IS UPDATED


Cardinalitie of Sets Alive on YOUTUBE

TESTS and Quizzes POLICY
We do not give make-ups  except of documented cases of illnes or documented emergencies

 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  SOME of  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:

Tuesday,  Thursday:  1:00 pm - 2:20pm

Place:

FREY HALL 104

Professor:

Anita Wasilewska

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

Office Hours:
 Tuesday, Thursday  5:40 pm  -7:00 pm,   and by appointment

 Graduate Teaching Assistants

Thu Nguyen
e-mail:  ttnnguyen@cs.stonybrook.edu
Office hours:  Wednesday, 12:00 pm - 2:30 pm
Office Location: Room  2217  in Old CS Building
 
Rebecca Drucker  
e-mail: rebecca.drucker@stonybrook.edu
Office hours: Wednesday, 10 am to 12 pm
Office Location: Room  2217  in Old CS Building
 
 Javad Nejati
e-mail: jnejati@cs.stonybrook.edu
Office hours:  
Office Location: Room  2217  in Old CS Building
 
Sauradeep Paul  
e-mail: saupaul@cs.stonybrook.edu
Office hours:  Monday, 2:25 pm - 3:25 pm
Office Location: Room  2217  in Old CS Building
 
Sriram Gattu  
e-mail: sgattu@cs.stonybrook.edu
Office hours: 
Office Location: Room  2217  in Old CS Building
 
Adarsh Alangar  
e-mail: aalangar@cs.stonybrook.edu
Office hours: 
Office Location: Room  2217  in Old CS Building
 
Jahnavi Tharigopula 
e-mail: jtharigopula@cs.stonybrook.edu
Office hours: 
Office Location: Room  2217  in Old CS Building

  Undergraduate Teaching Assistants

Xiangying Liu 
e-mail: xiangying.liu@stonybrook.edu
Office hours: Tuesday, 12:00 pm - 1:00 pm
Office Location: Room  2217  in Old CS Building
 
Yihan Wang  
e-mail: yihan.wang@stonybrook.edu
Office hours:  Monday, 2:00 - 3:00 pm
Office Location: Room  2217  in Old CS Building

Xinrui Lyu (Sherry)  
e-mail: xinrui.lyu@stonybrook.edu
Office hours: Tuesday 5:30 pm - 6:30pm
Office Location: Room  2217  in Old CS Building
 
Zhongkai Ye  
e-mail: zhongkai.ye@stonybrook.edu
Office hours: Wednesday, 4:00 pm to 5:00 pm
Office Location: Room  2217  in Old CS Building
 
Qien Jiang  
e-mail: qien.jiang@stonybrook.edu
Office hours: Wednesday, 1:00 pm - 2:00 pm
Office Location: Room  2217  in Old CS Building
 
Shengzhi Zhou
shengzhi.zhou@stonybrook.edu
Office hours: Wednesday, 2:30 pm -3:30 pm
Office Location: Room  2217  in Old CS Building
 
Hangchao Chen
hangchao.chen@stonybrook.edu
Office hours: Tuesday, 10 am - 11 am
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

    ATTENTION
    Tests and Quizzes cover homeworks assignments for the PORTION of material covered in class

    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 on BLACKBOARD
  •  Contact  TAs when you have questions about grading and your grades
  • 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 21,  Thursday
    Q2 March 14,  Thursday
     Practice Midterm- take home test published March 14  and due March 26  via BLACKBOARD
    SPRING BREAK  March 18 - 24
    MIDTERM  - Thursday,  March 28
    Q3 April 18, Thursday
    Q4 -   May 2,  Thursday
     
    Practice Final -
    take home test published April 30  and due May 9  via BLACKBOARD

    Last Day of Classes- May 11
     
    FINAL to be given during the University assigned place and time during the FINALS period May 14 - 22
    The exact date and place to be posted

    DOWNLOADS

     
    PRACTICE MIDTERM
     
    Syllabus

    Syllabus Slides

    LECTURES
     
    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 2019  QUIZZES and  TESTS SOLUTIONS

    Q1 Solutions
    Q2 Solutions  
    PRACTICE MIDTERM Solutions  tbp
    MIDTERM Solutions  tbp
    Q3 Solutions  tbp
    Q4 Solutions tbp
    PRACTICE FINAL Solutions tbp

    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