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: finite automata, which model computing machines with finite fixed memory, and the class of regular languages, which is used for pattern matching languages;
 pushdown automata and contextfree grammars that facilitate declarative specifications of language syntax;
 the universal computational model of Turing machines, and the inherent limits of what can be solved on a computer (undecidability); and, finally,
 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: Mon and Wed 10:3011:45, BYAC 150
 Instructor: Georgios Fainekos (fainekos at asu)
 Office
hours: Mon, Tue 16:0017:00 (Calendar)
 Office location: BYENG M112
 Electronic communication policy:
 If you have any question that is not related to personal issues, then first post it on the discussion board on Blackboard under the most relevant topic.
 We will 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/EmailaProfessor  Teaching Assistant: Bardh Hoxha
 Office hours & Office location: Please visit blackboard for uptodate information
 Recitations: There will be recitations on Fridays. Time: 9:3011:00, Room M109.
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 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 contextfree 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
 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
 Notes by Jean Gallier posted on Blackboard
Resources
 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
 File compression utilities for submitting your homework electronically:
Grading
Grades will be based on:
 Homework Assignments: 10%
 Online preclass quiz and weekly puzzle: 10%
 Inclass Quiz: 10%
 Two
Midterms: 35%
 Final Exam: 35%.
 If your final exam score is higher
than the midterm score, then the final exam score is going to replace
the midterm score.
 There will be one optional project. Those who choose to do the project will get from +2% to +6% on their final grade.
 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.
Algorithm for computing your final grade:
 HWS: Homework score
 HWS = Σ{ (HWi/THWi)  for i in {1,...,6} } / 6
 where Σ indicates summation and THWi is the total possible points for each HW i
 FES: Final exam score
 TFEP: the total possible points for the final exam
 MES: Midterm exam score
 MS1 = max{ ME1S/TME1P, FES/TFEP }, where ME1S is your actual score for midterm 1 and TME1P is total possible points for midterm 1
 MS2 = max{ ME2S/TME2P, FES/TFEP }, where ME2S is your actual score for midterm 2 and TME2P is total possible points for midterm 2
 MES = (MS1+MS2)/2
 QS: Quiz scores
 QS = Σ{ (Qi/TQi)  for i in {1,2,...,n} } / n
 where Qi is your score for quiz i, Σ indicates summation and TQi is the total possible points for each quiz i
 FG : Final Grade (updated on 2012.11.07)
 FG = (0.1*max{iQS,MES} + 0.1*oQS + 0.1*HWS + 0.35*MES + 0.35*FES)*PB
 where iQS are the inclassroom quizzes, oQS are the online quizzes, PB is the project bonus, i.e., PB = 1 if you did not do the project and ranges up to 1.xx as indicated in the project description.
Grading scale:
A+ 
>100% 
B 
[7580)% 
A 
[95100]% 
C+ 
[7075)% 
A 
[9095)% 
C 
[6570)% 
B+ 
[8590)% 
D 
[5565)% 
B 
[8085)% 
F 
<55% 
Homework Policy
There are going to be 6 homework assignments.
The homework must be turned in at the beginning of the class on the due day.
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:
 Individual homework exercises must be solved and submitted individually. Individual exercises are not challenging; therefore, no collaboration is allowed.
 You must form/join a group. Groups can have up to 36 members.
 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.
 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.
 Those who form their own group should email me
their group members and create a group on blackboard.
 If you want to join a group and you cannot find one, please use the respective discussion forum on blackboard.
 As the course progresses, the groups are going to be modified based on the performance of the students. The goal is to have balanced groups, where 12 leaders can help the rest of the group. The best understanding of the material is achieved when you try to explain the material to others. More on Peerled Team learning.
 If you submit a late homework, you need to send me and the TA an email.
 Bonus problems are not counted in late submissions.
Collaboration between individuals who are not in the same group or between groups is not permitted and will be treated as cheating! If such a case is detected 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 blackboard is highly encouraged and it actually 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.
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
If you prefer to submit the homework electronically,
then you may submit it in the Assignments section on Blackboard.
You may:
 type your answers in the native editor inside Blackboard under the current homework assignment or
 you may submit a file with your answers. You may type or scan your answers. The only acceptable format is PDF. You must use the file name convention: "last name"."first name"."HW#".pdf
If you are using MS Word to write up your answers, then
you can download and install the following addon:
http://www.microsoft.com/downloads/details.aspx?FamilyID=f1fc413c6d894f15991b63b07ba5f2e5&displaylang=en
Inclassroom Quiz Policy
There are going to be 3 inclass quiz. The examination time will be between 10 and 15 minutes. These are going to be multiplechoice, closed book, closed notes and no cheat sheet. The material covered will be from the previous examination until the previous class.Online Quiz Policy
The class follows the JustInTimeTeaching (JITT) philosophy. This means that you have to read the assigned material before coming to class and answer a brief quiz (on blackboard) before 11:59pm on the day before the class. This will help me identify potential weaknesses and revise that day's lecture based on your answers and feedback. The quizzes will contain 24 very simple questions which are graded and which simply test whether you read the assigned material or not. The quizzes will also contain 12 questions that test whether you have actually understood the material. The latter are bonus questions. However, the questions will not be identified as bonus or not on the quiz.Midterm Exam Policy
In class, 1hr long, a 2 page (1 piece of paper) cheat sheet is allowed. Nothing else must be on your desks besides your pen and/or pencil.Final Exam Policy
In class, closed book and closed notes. You may have a cheat sheet. The instructions will be included in the Final Exam Review Notes.Plagiarism Policy
Your work for this course must be the result of your
own
individual effort. 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 the latter copying is detected the
worst
credit will be split among the perpetrators, or worse! Also, if you can
find an
answer online, then so can I!
The best way to prepare for the midterms and the
exams is to
do the homework on your own!
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.