Course Description: The first half of the course studies the theory of computing. Topics include finite automata, context free grammars and parsing, regular languages, pushdown automata, Turing machines, decidability, computablity, and complexity.
What does all this mean? These should become familiar terms as the course progresses. Overall, the course is fairly mathematical and relies upon logic, algebra, and discrete math. Some students find the abstract concepts difficult to grasp, particularly the proofs, so be prepared to put in some extra reading if this is the case! In general terms, at first we will study abstract computing devices starting from very simple devices (deterministic finite automata) and moving to complex abstract computing devices (turing machines). Along the way we'll see other computing devices and ways to describe what can be computed through grammars, languages, and answer basic questions of computability and tractability. Through the concept of a turing machine we will describe algorithms and the complexity bounds of what can be computed. Some problems we will see are undecidable (they can't be solved by any computer!) while others may be intractable (they can be solved by a computer, but take a ridiculously long time to do so).
The second half of the course studies techniques for the design and analysis of algorithms. This includes problem solving and the study of common problems such as sorting, searching, graph algorithms, string matching. We will study the techniques used to solve these problems, including brute force, divide and conquer, decrease and conquer, transform and conquer, dynamic programming and greedy algorithms. Students should learn to develop a group of useful algorithms that can be used to solve common problems along with methods to analyze the correctness, time, and space used by these algorithms.
Instructor Goals: The instructor will:
Student Outcomes: Upon completion of the course the student will be able to:
Homework Assignments : Due on Blackboard by the posted date/time, or by the beginning of class if you are turning anything in on paper. Approximately seven homework assignments will be given, some of which may include programming in the language of your choice. Late homeworks will be penalized 10% per day late up until the date solutions are posted. Unless otherwise indicated, programming assignments and written assignments must represent your own work. It is permissible to discuss the assignments with other students, but do not discuss the solution.
Small Group Problem Discussion: Every Thursday except for the first, last, spring break, and midterm weeks we will save the last 30 minutes of class for random groups of 3 (or 2) students to present solutions to problems given earlier that week. Each student should come prepared with a solution to all of the problems (usually 3) and will be responsible for presenting his or her solution to at least one of the problems to the small group. Your group can discuss the presented solution. I will post my own solutions to the problems after class. These are graded as done/not-done and two not-done will be dropped to allow for sick or unplanned events.
Questions: If you have any questions, feel free to come in to my office. In general, I have an open door policy -- if I am available in my office, you are welcome to come by. An even better way to reach me is through email. I check my email frequently and you should receive a response quickly. Email is preferred over telephone and you will probably receive a faster response since I don't check voicemail very frequently.
Grading: Letter grade. There will be two exams, a midterm and a final exam. The midterm will cover the Automata material and the final will cover the Algorithms material. Unless prior arrangements are made no make-up exams will be given. Since you will be tested upon your critical thinking and problem solving skills and not your ability to memorize formula, the exams will be open book. Any written material and a computer is acceptable to bring to the test.
Grading breakdown:
Midterm: 25%
Final:
25%
Homeworks: 40% (Each
homeworks worth an equal amount)
Small Group Discussion Problems: 10% (Approx 11, each
an equal amount, allowance to drop two absent/not prepared grades)
The grade scale is a traditional 90-100 for A, 80-89 for B, 70-79 for C,
60-69 for D, and anything else an F. The grading curve may be
lowered if necessary but it will not be raised. This means that if
you received an 89% then you will at least get a B, but may receive a
higher grade based on the curve.
An incomplete grade will only be given for a valid excuse (e.g. medical, death in the family). An incomplete grade does not let you take the class over again, your final grade will be assigned based on work submitted in class and work that remains to be submitted.
Cheating: Students are expected to uphold the UAA standard of conduct relating to academic dishonesty outlined in the UAA catalog and student handbook. Cheating is not tolerated and constitutes grounds for dismissal. For this class, it is permissible and encouraged to assist classmates in general discussions of how to attack the homework problems. It is not permissible to copy another's work (or portions of it) and represent it as your own.