KUTZTOWN UNIVERSITY

Department of Computer Science

Course Title: CSC 325 – Introduction to Computer Science Theory (Spring 2012)

Instructor: Dr. Charlie Y. Shim

E-Mail Address:

Home Page: http://faculty.kutztown.edu/shim

Office: OM 245

Phone: 610-683-4414

Office Hours: M, W 3:00 – 4:00PM,

T, Th 1:30 – 3:00PM, or by appointment

Meeting Time & Place: T, Th 12:00 – 1:20PM, OM 123

Course Description: This course covers computer science skills required to understand, model, and devise efficient solutions for problems. These skills include techniques for modeling problems, determining inherent complexity of problems, devising appropriate solutions for problems, and analyzing the efficiency of problem solutions. Topics include problem solving, automata theory, computability theory, algorithm design strategies, and algorithm anlaysis.

Prerequisite: CSC 225 and CSC 237

Course Objectives: Upon satisfactory completion of the course the student will be able to:

A.  Discuss the scientific method and how it applies to computational problem solving.

B.  List the steps in the problem solving process and the considerations made during each step.

C.  Demonstrate the use of modeling and abstraction in problem solving.

D.  Describe the distinguishing characteristics of algorithms and heuristics.

E.  Use big O, omega, and theta notation to give asymptotic upper, lower, and tight bounds on time and space complexity of algorithms.

F.  Discuss factors other than computational efficiency that influence the choice of algorithms, such as programming time, maintainability, and the use of application-specific patterns in the input data.

G.  Demonstrate the following capabilities: to evaluate algorithms, to select from a range of possible options, to provide justification for that selection, and to implement the algorithm in programming context.

H.  Describe the shortcoming of brute-force algorithms.

I.  For each of several kinds of algorithm (brute force, greedy, divide-and-conquer, backtracking, branch-and-bound, and heuristic), identify an example of everyday human behavior that exemplifies the basic concept.

J.  Implement a greedy algorithm to solve problems such as minimum spanning trees, single-source shortest path, activity selection, or Huffman coding.

K.  Implement a backtracking algorithm to solve a problem such as navigating a maze or coloring a graph.

L.  Describe various heuristic problem-solving methods.

M.  Implement a pattern matching algorithm to analyze substrings.

N.  Implement a numerical approximation heuristic to solve a mathematical problem, such as finding the roots of a polynomial or computing the square root of a number.

O.  Implement an algorithm requiring the use of graphs.

P.  Perform an empirical analysis of the run-time performance of an algorithm.

Q.  Describe the characteristics and features of finite state machines including DFA, NFA, PDA, and Turing machines.

R.  Define a regular expression for generating a specified language.

S.  Define a context-free grammar for generated a specified language.

T.  Design a deterministic finite-state machine to accept a regular language.

U.  Design a pushdown automata to accept a context-free language

V.  Design a Turing machine that computes a function such as adding two non-negative numbers.

W.  Prove that some problems (such as the halting problem) have no algorithmic solution.

X.  Provide examples that illustrate the concept of uncomputability.

Y.  Define the classes P and NP.

Z.  Explain the significance of NP-completeness.

AA.  Determine a language’s location in the Chomsky hierarchy (regular sets, context-free, context-sensitive, and recursively enumerable languages).

BB. Explain the Church-Turing thesis and its significance.

Text Book: Discrete Structures, Logic, and Computability

By James L. Hein (Publisher: Jones and Bartlett)

Grading: Exam I 20 %

Exam II 20%

Final 30 %

HW Quiz 30 %

------

Total Points 100 %

Your final grade in the course will be given according to the following scale:

A ≥ 90%, B ≥ 80%, C ≥ 70%, D ≥ 60%, F < 60%

Attendance: Lecture attendance is strongly encouraged. You are responsible for all material covered during lectures whether you are present or not. You are also expected to have read the appropriate sections of the text prior to the lecture. Unannounced quizzes will be given frequently throughout the semester. Makeup quizzes will not be given.

Exams: There will be two 100-point midterm exams and a 100-point comprehensive final exam. All exams must be

taken at the scheduled time unless I have approved an alternative time PRIOR to the scheduled time. Make up

exams will be given to those students, who have official University functions or other well-documented circumstances,

such as hospital confinement. Please inform instructor well in advance of such circumstances. Makeup should be

completed within one week of the exam date or you will receive a grade of zero.

Homework: Start on homework as soon as it is assigned. Homework must be handed in at the beginning of class on the due date. Late assignments will have a reduction in points of 10% per day and absolutely no late homework assignment will be accepted if they are more than two days late. It is important to complete the reading assignment before the next class.

Accreditation: Assignments, exams, and quizzes may be photo-copied and retained for program accreditation.

E-Mail Correspondence: Students are REQUIRED to use their Kutztown University e-mail account for all e-mail correspondence with the course instructor. Please indicate the course number (enclosed in square brackets) in the subject line.

Course Etiquette and Behavior: Students will demonstrate respect for the instructor and other students in the classroom and lab. This includes unacceptable language usage in the classroom and laboratory. The course instructor will report behavior that is disruptive to the positive learning environment. A warning will be issued on the first instance and will be reported to the department chairperson. On a second instance, the student will be referred to the Provost’s Office.

Academic Dishonesty: Plagiarism and cheating are serious offences and may be punished by failure on exam, paper or project; failure in the course; and/or expulsion from the University. Academic dishonesty includes the following actions, as well as other similar conduct aimed at making false representation with respect to the student’s academic performance:

(1)  Cheating on an exam or quiz,

(2)  Collaborating with other students on work to be presented, if contrary to the stated rules of the course,

(3)  Submitting, if contrary to the rules of the course, work previously submitted in another course,

(4)  Copying or changing programs done by other students and submitting it as their own,

(5)  Plagiarism.

For more information, visit the Computer Science department’s academic integrity policy, located at:

http://cs.kutztown.edu/pdf/AcademicIntegrityPolicy.pdf

Students with Special Needs: If you have already disclosed a disability to the Disability Services Office (215 Stratton Administration Building) and are seeking accommodations, please feel free to speak with me privately so that I may assist you. If you have an injury sustained during military service including PTSD or TBI, you are also eligible for accommodations under the ADA and should contact the Disability Services Office.

Web reference: http://www.kutztown.edu/admin/humandiversity/disabilityservices/