Summary Introduction to Theoretical Computer Science Syllabus – Fall 2021

Prerequisites Computer Systems Engineering BSE or Computer Science BS major; CSE 310 with C or better or CSE graduate student Major Topics Covered 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 context-free 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 Course Web Site All course documents, i.e. lecture slides, quiz solutions, etc., are available on Canvas at access the course material through this site. If you experience any difficulties, please let me know as soon as possible. It is your responsibility to check the latest announcement and print your assignments from the Canvas as soon as it is posted. Note: Announcements in the class take precedence over printed material. Grading & Exam Dates • Your grade will be based on the following schema. Item # of Items Point Value Percentage towards your Final Grade Exams 3 100 65% Assignments 6 100 25% Recitation 13 20 10% Quizzes/Attendance 7 10 5% Total 105% • Grading breakdown (+/- System) A+ A B+ B C+ C D E 3 3 of 6 70 60 Below 60 Exams, Assignments and Quizzes Policies • Exams: there will be three exams and the exam dates are fixed as below (please mark your calendar) Exam #1 – Wednesday, Sep. 29, 2021 Exam #2 – Wednesday, Nov. 3, 2021 Exam #3 – Wednesday, Dec. 1st, 2021 • Absolutely no make-up exam will be given unless you provide the supporting documents from an authorized third party in advance (i.e. before the exam’s date), such as from a doctor’s office, a police departments or the university, etc. An authorized make-up exam will only be given during the final week (Dec. 6 ~ Dec. 8) and the exam contents might cover all topics of the course contents! Your picture ID needs to be shown during the exams. Also for all exams, if you are late for more than 15 minutes, you will NOT be allowed to take it! • Assignments: Assignments must be solved and submitted individually, and they must be submitted electronically. Detailed instructions are provided with the homework instructions, you may type your answers or scan your handwritten answers, but in either case, the only acceptable format is PDF. • Recitation Sessions: CSE 310 students must also enroll in one recitation session. Recitations provide another opportunity for more exercises on problem solving in a smaller setting. • Missed/Late Assignments/Recitations: if you need to miss an assignment or a recitation, you must have a legitimate university approved excuse, such as a severe injury, or participation in a legal proceeding that require your presence, etc. You must contact the instructor and provide satisfactory evidence prior or within two days after the absence. A missed assignment/recitation without permission or supporting documents is a zero. Absolutely no late assignment or recitation will be accepted! We will NOT accept any submission through emails. Equipment defects and technical issues cannot become excuses for late submission. • Quizzes/Attendance: From time to time, just to enhance what you learned, I will distribute online quizzes and these quizzes will be graded. In total they are worth 5% towards your final grade. There will be absolutely no make-up for these quizzes. Note: these quizzes will NOT be announced in advance and will be used to check your class attendance. Attendance is important in this course, it allows you to be aware of what are going on in class, often during the class time, announcements will be made, or information will be discussed that is not available on the web site. • Misce./Exceptions: Accommodations will be made for religious observances provided that students notify the instructor at the beginning of the semester concerning those dates. Students who expect to miss class due to officially university-sanctioned activities should inform the instructor early in the semester. The preceding policies are based on ACD 304– 04, “Accommodation for Religious Practices” and ACD 304–02, “Missed Classes Due to University-Sanctioned Activities.” • Grading Appeals: Any questions, corrections, or appeals on grades of programs or tests must be done in writing within one week after it has returned to the class. State the problem and the rationale for any change in your grade in your appeal. For tests, bring the letter and test paper