Spring 2013 (Section 1)

- Contact Information
- Catalog Description
- Prerequisites
- Texts
- Schedule

- Topics
- Homework and Tests
- Exams and Grading
- For Students with Disabilities
- Handouts (in pdf form)

- MacLennan’s home page
- Department of Electrical Engineering & Computer Science
- UTK Home Page

- ETS
Major Field Test in Computer Science content [pdf]

Bruce MacLennan, PhD

Phone: 974-0994

Office: Min Kao 550

Hours: WF 3:30–5:00 or make an appointment

Email:

Teaching Assistants:

Derek Rose

Office: Min Kao TBA

Hours: TBD or make
an appointment

Email: derek
at utk.edu

Yin Lei

Office: Min Kao TBA

Email: ylei6
at utk.edu

**
Classes:** MWF 12:20–1:10, Min Kao 404

**This page:** `http://web.eecs.utk.edu/~mclennan/Classes/312`

There are two required textbooks for COSC 312:

- Michael Sipser: Introduction to
the Theory of Computation, third edition, Course
Technology. $170 from Amazon.com.
A few paperback
copies seem to be available for about half this price. You
can probably get by with the second
edition, which is much cheaper ($30–60), but you will have
to be careful because some of the exercise numbers have changed!
[S]

- Clifford A. Shaffer, Data Structures and Algorithm Analysis Edition 3.2 (C++ Version). Free online. [Sh]

We will spend about two weeks on each of these topics:

- Finite Automata (S[ipser] 1.1–2)
- Regular Expressions and Languages (S 1.3–4)

- Context-free Grammars and Languages (S 2.1)

- Pushdown Automata (S 2.2–3)

- Turing Machines and Other Models of Computation (S 3.1–3)

- Uncomputable Problems (S 4.1–2; see also Shaffer §17.3.2)
- Complexity (S 7.1–4; see also Shaffer ch. 17)
- Algorithm Analysis (Shaffer
§2.4, chs. 3, 14)

*
Topics*: Most of the “basics of counting” are covered in COSC 311, and so COSC 312 will cover the
following:

- Solving recurrence relations [Sh 2.4, 14.2]
- The Master theorem [Sh 14.2.3]

Learning Outcomes

- Analyze a problem to create relevant recurrence equations or to identify important counting questions.

Topics

- Asymptotic analysis of upper and
average complexity bounds [S 7.1; Sh 3.4]

- Identifying differences among best, average, and worst case behaviors [Sh 3.2; S 7.1]
- Big Oh, little oh, omega, and theta notation [Sh 3.4]
- Standard complexity classes [Sh 3.1]
- Empirical measurements of
performance[Sh 3.11]

- Time and space tradeoffs in
algorithms [Sh 3.9]

- Using recurrence relations to analyze
recursive algorithms [Sh 2.4, 14.2]

Learning Outcomes

- Explain the use of Big Oh, omega, and theta notation to describe the amount of work done by an algorithm.
- Use Big Oh, omega, and theta notation to give asymptotic upper, lower, and tight bounds on time and space complexity of algorithms.
- Determine the time and space complexity of simple algorithms.
- Deduce recurrence relations that describe the time complexity of recursively defined algorithms.

*
Topics*:

- Finite-state machines (Sipser 1.1–2)
- Regular expressions and real-world applications (lexical analysis, scripting languages) (Sipser 1.3)
- Relationship between finite-state machines and regular expressions (Sipser 1.3)
- The pumping lemma for regular languages (Sipser 1.4)
- Context free grammars and real-world applications (parsing) (Sipser 2.1)
- Greibach and Chomsky Normal Forms (Sipser 2.1)
- Pushdown automata (Sipser 2.2)
- Relationship between PDAs and context free grammars (Sipser 2.2)
- The pumping lemma for context free languages (Sipser 2.3)

Learning Outcomes

- Design a finite state machine to accept a specified language
- Design a regular expression to formally specify a language
- Describe how finite state machines and regular expressions are related
- Design a pushdown automata to accept a specified language
- Design a context free grammar to formally specify a language
- Describe how pushdown automata and context free grammars are related
- Describe the difference between a finite state machine and a pushdown automata and describe why a pushdown automata can accept more languages than a finite state machine.

*
Topics*:

- Turing machines (Sipser 3.1)
- Church-Turing Thesis (Sipser 3.3)
- Uncomputable functions (informal definition: Sipser 4.2; Sh 17.3.2)
- The halting problem (Sipser 4.1–2)
- Implications of uncomputability

Learning Outcomes

- Describe a Turing machine and explain the significance of a Turing machine.
- Explain why a Turing machine is more powerful than a pushdown automata.
- Create simple programs using a Turing machine.
- Explain what it means for a function to be uncomputable.
- Describe the Church-Turing Thesis and explain its significance.
- Describe the halting problem and explain its significance.
- Provide a proof that the halting problem is undecidable.

- We will assign weekly homework, which will count a total of
15% of your Homework
+ Test average. In order to allow me to discuss
homework in class and to be fair to all students,
**late homework will not be accepted**. The individual homeworks are designed to be easily doable in the (approximate) week allocated to each. Also, if you get behind in the homework it will be difficult to catch up, since the material is cumulative. Turning homework in on time means at the beginning of class on the day it is due. Homework turned in after class begins will be considered late. (Of course I will consider extenuating circumstances.) - In addition, there will be three tests, each of which will count 25% of your Homework + Test average.
- Finally, there will be a quiz over algorithm analysis, counting 10% of your Homework + Test average.

- Feb 15: Test 1 (S1)
- Mar 15: Test 2 (S2–3)
- Apr 22: Test 3 (S4, 7)
- Apr 26: Quiz (Sh 3, 14)

**The Final Exam is 12:30–2:30, Tues. May 7.** The
cumulative Final Exam will be two hours worth of questions similar
in difficulty to those on the Tests.

Students who have a disability that require accommodation(s) should make an appointment with the Office of Disability Services (974-6087) to discuss their specific needs as well as schedule an appointment with me during my office hours.

- Problem solving steps from Polya’s How to Solve It [pdf]
- Summary of proof techniques from Solow [pdf]
- Context-free grammar for Algol 60 [pdf, rtf]

- Models of Computation,
Turing Machines, and the Limits of Turing Computation
slides [pdf]. For
an example of a physical TM, see A Turing Machine in the
Classic Style.

- HaltingProblem.cpp
(C++ program illustrating the undecidability of the Halting
Problem)

- RiceTheorem.cpp (C++
program illustrating Rice’s Theorem)

- Hierarchy of complexity classes [wikipedia] (principal classes discussed in this course)
- Map of complexity classes
- Complexity
Zoo (495 named and defined complexity classes (so far)!)

- Bachmann-Landau notation (big-Oh and its relatives):

Return to MacLennan’s home page

Send mail
to Bruce MacLennan / `MacLennan@eecs.utk.edu
`

Last updated: 2013-04-26.