COMPSCI 250: Introduction to Computation Summer 2024

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMPSCI 250: Introduction to Computation

Summer 2024

Course Goals

This is a list of specific tasks that students might be asked to perform on the final exam -- it is posted here as a study guide.

●  First Half of Course, Chapters 1, 2, 3,4:

○  Translate statements to and from propositional logic.

○  Prove statements of propositional logic using truth tables and/or propositional proof rules.

○  Translate statements to and from predicate logic.

○  Prove statements of predicate logic using the four quantifier proof rules.

○  Work with the definitions of types of relations (partial orders and

equivalence relations) and properties of functions (one-to-one, onto, bijections).

○  Be familiar with primality and modular arithmetic.

○  Know the statements (and something of the proofs) of the Inverse

Theorem, Fundamental Theorem of Arithmetic, and Chinese Remainder Theorem.

○  Prove statements about naturals by ordinary induction.

○  Prove statements about naturals by strong induction.

○  Prove statements about other data types (strings, trees, etc.) by induction on the definition of the type.

○  Work with a completely new inductive definition.

○  Prove correctness and termination of a recursive algorithm by induction.

○  Write a recursive algorithm to operate on an object of an inductively

defined class, such as boolean expression trees.

●  Second half the of Course, Chapters 9, 5, 14, and 15 :

○  Describe the behavior of general search, depth-first search,

breadth-first search, uniform-cost search, or A* search on an example.

○  Work with formal languages defined by regular expressions.

○  Prove a property of regular expressions by induction on the definition.

○  Determine the behavior of a DFA on a string or set of strings.

○  Use the Myhill-Nerode Theorem to argue about whether a given language has a DFA, or how many states its minimal DFA has.

○  Find the minimal DFA equivalent to a given DFA.

○  Understand the language of a given ordinary NFA or λ-NFA.

○  Convert a λ-NFA to an equivalent ordinary NFA.

○  Convert an ordinary NFA to an equivalent DFA.

○  Convert a regular expression to an equivalent λ-NFA.

○  Convert a DFA to an equivalent regular expression by working through r.e.-NFA's (called "GNFA's" in lecture).

○  Argue about the class of regular languages using the different equivalent definitions and various conversion algorithms.

○  Understand, informally, the behavior of a Turing machine.

○  Informally describe how a Turing machine might solve a given computational problem.

○  Know the definition of Turing Recognizable and Turing decidable languages.

Course Requirements and Grading

Your grade in COMPSCI 250 will be based on the following:

●  1 Midterm Exam (25%): There will be one midterm exam on Tuesday, June 27.

●  Final Exam (30%): This will be on July 21st and will be cumulative, with greater emphasis on the last half of the course.

●  Biweekly Homework (30%): There will be six Homework during the semester. Together they will count for 30% of your final grade. The lowest grade of your HW will be dropped.

You have the freedom to choose one HW and submit it one day late. The students with disabilities ( The ones for whom I received a letter from disability services) can submit all their HWs by the late due date (only one day).

--By giving you this opportunity, I don’t expect to get emails about extensions or missing deadlines unless you have severe health issues. If you have medical issues, contact me with related documents.

●  Discussions (9%): There will be seven discussions on Thursdays. Attendance at the discussion sections is required. You are allowed to miss one of the discussions with no penalty. This portion of the course grade will be based on your attendance and participation. Participation will be measured by group responses to in-class writing assignments, usually based on "Excursion" sections of the text. You will be divided randomly into groups of 3-5 people, and each group will hand in a response to the assignment. Your grade will be based on top 6 discussion grades.

●  Quizzes (6%): Every week, you need to complete two quizzes on the assessment package. We start it in the second week. Your grade will be based on your top 6 grades.

● In-class participation/activity (2%): I may ask you to do an activity in the class. The ones who are present and answer the questions will get 2 points (2 extra     credits).