CSE355: Introduction to Theoretical Computer Science (Section 11833)

[https://sites.google.com/a/asu.edu/cse355-spring-2015-fainekos/]

Last update: 2015.04.15 
Revisions after hard-copy syllabus distributed in class: 

  1. Added "Attendance Policy" and "Table of contents"
  2. Added "Title IX"
  3. Updated instructions on on-line quizzes

Introduction

This course provides a first introduction to the theoretical concepts of Computer Science. The focus of the course is the study of abstract computing devices without targeting a specific programming language and/or computing platform. In particular, we will study:
  1. finite automata, which model computing machines with finite fixed memory, and the class of regular languages, which is used for pattern matching languages;
  2. pushdown automata and context-free grammars that facilitate declarative specifications of language syntax;
  3. the universal computational model of Turing machines, and the inherent limits of what can be solved on a computer (undecidability); and, finally,
  4. time complexity theory, which helps us measure the time used to solve a problem.

The course also emphasizes rigorous thinking and mathematical proofs.

Logistics

  • Class: Monday and Wednesday 3-4:15PM, COOR 174
  • Instructor: Georgios Fainekos (email: fainekos at asu)
    • Office hours: Monday 5-6 PM & Wednesday 1-2 PM (Calendar)
    • Office location: Centerpoint 203-17
    • Electronic communication policy:
      • I do not respond to emails or to on-line discussions over the weekend.
      • If you have any question that is not related to personal issues, then you MUST first post it on the discussion board on Piazza under the most relevant topic.
        • Piazza enrollment instructions and the access code are provided on Blackboard > Course Information.
        • If you would like to participate to on-line discussions, on-line polls etc you must enroll to Piazza.
      • We will be responding to any questions after 1 business day. This will let your classmates enough time to attempt to answer your question for class participation credit.
      • If you think you must send me an email due to the personal nature of your question or you think that your question might not be interesting to the rest of the class, then email both me (and the TA for faster response).
      • Before sending an email please follow the excellent advice here:
        http://www.wikihow.com/Email-a-Professor

  • Teaching Assistants: 
    • Adel Dokhanchi (office hours and recitations)
    • Office hours & Office location: Please visit Blackboard for up-to-date information
    • Recitations: Please visit Blackboard for up-to-date information

Prerequisites


CSE 310
Data Structures and Algorithms

Textbooks

  • Required: Introduction to the theory of computation, Michael Sipser, Thomson Course Technology, 3rd Edition, 2013
    • Note: The publisher also provides an electronic version of the book through CourseSmart (http://www.coursesmart.com/). They also provide Apps for all platforms.
    • Note: The 2nd Edition can still be used. However, you might have to consult with your classmates regarding the mapping of homework problems and pages between the two editions. Also, time permitting, we will be having one lecture on deterministic context-free languages. This section is only included in the 3rd edition, but we will provide lecture notes on the topic.
    • Note: The 1st Edition is still acceptable. However, the 1st edition does not include any problem answers and it does not have as many examples and explanations as the 2nd and above editions. Also, you will have to consult with your classmates regarding the mapping of homework problems and pages between the 2 editions.
    • Note: The international editions of the textbook have different numbering in the exercises. If you are using the international edition, you will have to consult with your classmates regarding the mapping of homework problems and pages between the 2 editions.
    • Errata
  • Supplementary reading:
    • Ganesh Gopalakrishnan and Tyler Sorensen, Modeling and Reasoning about Computation, February 25, 2013 [On-line & Also on Blackboard: Content > Other readings]
    • John E. Savage, Models of Computation: Exploring the Power of Computing [On-line & Also on Blackboard: Content > Other readings]
  • Additional References (These are recommended readings for those who want to gain a deeper understanding of the subject or prefer a more formal approach):
    • Introduction to Automata Theory, Languages and Computation, J.E. Hopcroft, R. Motwani, and J.D. Ullman, Addison Wesley, Third edition, 2006
    • Lecture notes by Jean Gallier posted on Blackboard

Resources

  • Youtube videos: On Blackboard you will find links to videos from:
    1. Past lectures (and or possible lectures from this year), and
    2. Videos explaining problems related to homework assignments. 
  • On-line discussions and polls: Piazza
    • Piazza enrollment instructions and the access code are provided on Blackboard > Course Information.
  • Warm-up quizzes on Blackboard to test your knowledge before the class or after on-line lecture videos
  • The software JFLAP can help you better understand the material in this course.
    • Note: some of the homework problems must be submitted as JFLAP files.
  • Automata Tutor
  • Finite automata tool (FAT) implements algorithms for determinization, minimization, intersection, union, and complement.
  • File compression utilities for submitting your homework electronically:

Grading

The grading philosophy is based on the principle of constant improvement. In other words, you will be given the opportunity to demonstrate your knowledge of the material multiple times. As long as your new grade is improved, the old grade will be overwritten. In order for this grading philosophy to work, a minimal effort is enforced. That is, you will be required to demonstrate a minimum level of performance throughout the term.


Grades will be based on:

  • Homework Assignments: 20%
  • Quizzes: 10%
    • If your final exam score is higher than the average quiz score and your average quiz score is at least 25%, then the final exam score is going to replace the average quiz score.
    • Take these seriously. Quiz grades can make the difference between D and C or B- and B. 
  • Two to Three Midterms: 35% 
    • If your final exam score is higher than the midterm score and your midterm score is at least 25%, then the final exam score is going to replace the midterm score.
  • Final Exam: 35%
    • If your final exam score is below 45%, then you automatically fail the class unless you do the optional class project.

  • Class Participation
    • Bonus points: up to +2%
    • Class participation involves the following:
      • Contributing to both on-line and in-class discussions. This should be an activity throughout the semester.
      • Correcting your instructor and/or TA in class!
      • Helping others figure out fallacies in their line of thought when attempting to solve a problem.
      • Giving hints to your classmates, but not the complete answer.
      • Getting positive feedback from your group members and peers on the homework forms.
  • Optional project
    • Bonus points: +2% to +6% depending on the milestones completed.
    • Important: Only fully working programs take the extra credit. No partial credit is given for good intentions or effort.
    • If you are somewhere in the middle of the letter range, then this means that you might increase your final grade by one letter point.
    • The project will be announced after the completion of Chapter 1.
    • Any programming language is allowed. However, C/C++ is recommended.
    • This is an individual project. The code will be compared among all those who have ever submitted the programming project plus internet sources. The nature of the project makes easy the detection of copied or isomorphic code in an automatic way.
    • If cheating is detected, expect to get at least -10% on your final grade. Read also the plagiarism section below.
I do not normalize the final grades! I put a lot of effort in making sure that the exams are of reasonable difficulty. I reserve the right to adjust the final grades downward, e.g., in the case cheating is detected, or upward, e.g., in the case of noticeable and meaningful class participation or exceptional project work.

Algorithm for computing your final grade (Σ indicates summation):
  • HWS: Homework score
    • HWS = Σ{ (HWi/THWi) | for i in {0,1,...,m1} } / m1
      • where:
        • THWi is the total possible points for each HWi, and 
        • m1 is the total number of homework assignments
  • FES: Final exam score
    • TFEP: the total possible points for the final exam
  • MES: Midterm exam score
    • If MESi/TMEPi>25, then MSi = max{ MESi/TMEPi, FES/TFEP } 
    • If MESi/TMEPi<=25, then MSi = MESi/TMEPi
      • where 
        • MESi is your actual score for midterm i, and 
        • TMEPi is total possible points for midterm i
    • MES = Σ{MSi | for i = 1, 2, ..., m2) / m2
      • where
        • m2 is the total number of midterm exams
  • QS: Quiz score
    • AQ = Σ{ (Qi/TQi) | for i in {1,2,...,m3} } / m3
      • where
        • m3 is the total number of Quizzes
        • Qi is your score for quiz i, and 
        • TQi is the total possible points for each quiz i
    • If AQ>25%, then QS = max{ AQ, FES/TFEP }
    • If AQ<=25, then QS = AQ
  • FG : Final Grade
    • FG = min((0.1*QS + 0.2*HWS + 0.35*MES + 0.35*FES)+PB+CP, 100) + APB
      • where 
        • QS are the in-classroom quizzes, 
        • PB is the project bonus, 
        • CP is the class participation bonus, and
        • APB is the bonus for receiving A+ in the class. For APB to apply, one of the following two conditions must be met:
          • Case 1
            • (0.1*QS + 0.2*HWS + 0.35*MES + 0.35*FES)+PB+CP>=100, and
            • Special designated bonus questions must be answered in exams with score more than 50%, and 
            • All the optional project milestones must be successfully completed (or) an extra project as indicated under Honors Contracts must be successfully completed.
          • Case 2
            • (0.1*QS + 0.2*HWS + 0.35*MES + 0.35*FES)+PB+CP>=100, and
            • Special designated bonus questions must be answered in exams with score more than 90%

Grading scale:

 A+ >100%  B- [75-80)%
 A [95-100]%  C+ [70-75)%
 A- [90-95)%  C [65-70)%
 B+ [85-90)%  D [55-65)%
 B [80-85)%  F <55%

Homework Policy

The homework must be turned in at the beginning of the class on the due day as a hardcopy as well as electronically on Blackboard.

Homework problem solutions are going to be discussed in the first recitation after the homework due date.

If the homework is turned in late, the maximum grade you can expect is 50% of the total grade.


The homework will have an individual part and a group part [YOU MUST ANSWER BOTH PARTS, i.e., if you are submitting on your own the whole homework, you still need to submit the group part]:

  1. Individual homework exercises must be solved and submitted individually. Individual exercises are not challenging; therefore, collaborative work is not allowed. However, if you are stuck or you do not understand something, you are allowed to post a question on Piazza. If you are still not making progress you may use internet sources.
    [See word of caution below]
  2. It is highly recommended that you form/join a group. Groups can have up to 3 members. 
    • The best way to understand a new topic is when you try to explain it to someone else.
  3. A person from the group must submit the group homework exercises with his/her individual homework exercises. That is, each group submits only one solution. The names of all the group members should be displayed on the submitted group part.
  4. The grade of the group homework is the same for all group members. However, the grade will be modified upward or downward based on feedback received through peer assessment among the members of the group.
  5. Those who form their own group should email me and the TA their group members.
  6. If you want to join a group and you cannot find one, please use the respective discussion forum on Piazza.
  7. As the course progresses, the groups can be modified.
  8. Again: The best understanding of the material is achieved when you try to explain the material to others. More on Peer-led Team learning (http://en.wikipedia.org/wiki/Peer-led_Team_Learning).
  9. Collaboration between individuals who are not in the same group or between groups is not permitted and will be treated as cheating! However, if your group is facing a challenging problem and you are not making progress, then you are allowed to post questions on Piazza. If you are still not making progress you may use internet sources. [See word of caution below]
Other:
  1. If you submit a late homework, you need to send me and the TA an email.
  2. Bonus problems are not counted in late submissions.
  3. If cheating is detected, then the homework score will be zero and the final score will be lowered by an additional 5%.

Remark: Answering questions, explaining concepts and pointing out mistakes to other students at the discussion forums on Piazza s highly encouraged and it counts towards class participation. Please use your judgement on what constitutes an intellectual and intelligent discussion about the HW assignments VS solving someone else's HW assignment. 


A word of caution regarding internet sources:
  • We collect solutions posted on the internet and we constantly check for plagiarism. Copied solutions from the internet and between students are detected and plagiarizing students always have been reported.
  • Recommended approach to learn and succeed in the class:
    1. Read examples from the notes and textbooks.
    2. Attempt to solve the problems.
    3. If stuck, post question on Piazza or visit instructor, TA or tutors.
    4. If still stuck, use internet to get a hint to move forward from the point you are stuck. Do not copy!

The homework policy will be strictly enforced since it is already very permissive. The 50% policy is intended to minimize the consequences to those who for any reason cannot turn in the homework on time.


NO excuses will be accepted, so plan ahead!

Rules for electronic submission of homework

The homework must be submitted electronically and as a hard copy. Detailed instructions will be provided on the homework instructions.


Some general guidelines:

  1. If you are asked to submit other files, e.g., JFLAP files, besides your answer sheet, then you must compress all the files into a ZIP file.
  2. You may type or scan your answers. 
  3. In either case, the only acceptable format is PDF.

If you are using an old version of MS Word to write up your answers, then you can download and install the following add-on:
http://www.microsoft.com/downloads/details.aspx?FamilyID=f1fc413c-6d89-4f15-991b-63b07ba5f2e5&displaylang=en

On-line Quiz Policy (Automatically graded)

The class follows the Just-In-Time-Teaching (JITT) philosophy. This means that you have to read the assigned material before coming to class and answer a brief on-line quiz. This will help me identify potential weaknesses and revise that day's lecture based on your answers and feedback. The quizzes will contain 2-4 very simple questions which are graded and which simply test whether you read the assigned material or not. 

If you prefer, you are allowed to meet with your group to discuss the quiz questions. Note that some questions on the quiz may not be the same for all group members since the quizzes are randomized. The self-assessment quizzes are not timed and can be taken an unlimited number of times. However, the self-assessment quizzes count towards your grade. The only due date for the on-line quizzes is the final exam date/time.

Midterm Exam Policy

In class, 1hr 15 min long exams. A cheat sheet will be allowed which must be hand written. Nothing else must be on your desks besides your pen and/or pencil. Not even scrap paper. For scrap paper you can use space on the exam booklet. The exact material for each midterm exam will be announced in class. Practice tests from previous years will be distributed.

Final Exam Policy

In class, closed book and closed notes. A cheat sheet will be allowed which must be hand written. Nothing else must be on your desks besides your pen and/or pencil. Not even scrap paper. For scrap paper you can use space on the exam booklet. Detailed instructions will be included in the Final Exam Review Notes. The final exam is cumulative. Practice tests from previous years will be distributed.

Makeup Exam Policy

Makeup exams will be given only for medical reasons or other personal emergency. You must submit verifiable documentation with your petition for a makeup exam.

Plagiarism Policy

Your work for this course must be the result of your own individual effort or - when permitted - the result of your group. Having said that, you are allowed to discuss problems with your classmates or me, but you must not blatantly copy others' solutions. 


Copying (or slightly changing) solutions from online sources, other books or your friends is easily detectable. 


If such copying is detected, then a zero grade is applied to the respective assignment, -5% to the final grade and a formal report will be filed! 


Do not forget that if you can find an answer online, then so can we! Actually, if there is an answer on-line, then we download 10 versions and we check your answers for copying.

The best way to prepare for the midterms and the exams is to do the homework according to the rules above!

Class evaluations and feedback

I take very seriously class evaluations and feedback. During the semester, I will be posting surveys on Blackboard for feedback on both the course organization and the course content. I will appreciate it if you respond to these surveys. Ideally, the changes I implement will help you better succeed in the course.

As an example, in 2012, there were on-line quizzes before each class according to the JITT teaching philosophy which were required to be taken before the class starts. Student feedback stated that the idea of pre-class quizzes was great, but too stressful. Thus, this year we keep the on-line quizzes, but you are allowed to take them at any point in time and for an unlimited time of attempts. 

Finally, it is extremely important that you respond in the final anonymous survey solicited by the university at the end of the school year. The overall feedback helps me make changes for the next year.

Honors Contract

Options for honor's contract:

  1. 8-10 page survey paper with basic theory and 1-2 applications on any topic from the following list:
    1. probabilistic automata
    2. omega automata
    3. timed or hybrid automata
    4. advanced topics in complexity theory
    5. complexity classes beyond NP
    6. automata learning
    7. current problems in automata theory
  2. Work on a small theoretical research problem from automata theory 
  3. Build software tools to support learning outcomes for the course

Attendance Policy

I do not have an attendance policy. Come to class only if you like. Most of the material are available (or will be available) on-line. In theory, we only have to see each other during the exams.

However, if you skip classes, you do miss the chance for class-participation bonus through Piazza.

If you cannot come to an exam, then I will need some back-up documentation from a third party, e.g., a doctor, to schedule a make-up exam.

Special Needs

If you are entitled to extra accommodation for any reason (such as a disability), I will make every reasonable attempt to accommodate you. However, it is your responsibility to discuss this with the instructor at the beginning of the course. For further information, please visit the website of the ASU Disability Resource Center at

https://eoss.asu.edu/drc/

Title IX

Title IX is a federal law that provides that no person be excluded on the basis of sex from participation in, be denied benefits of, or be subjected to discrimination under any education program or activity.  Both Title IX and university policy make clear that sexual violence and harassment based on sex is prohibited.  An individual who believes they have been subjected to sexual violence or harassed on the basis of sex can seek support, including counseling and academic support, from the university.  If you or someone you know has been harassed on the basis of sex or sexually assaulted, you can find information and resources at 

http://sexualviolenceprevention.asu.edu/faqs/students.