COSC574: Automated Reasoning
Fall 2017
Contents
Announcements
Where, When, Who
Class Time: 
TR 2:00 PM–3:15 PM 
Classroom: 
REI 284 


Instructor: 
Mark Maloof 
Office: 
325 St. Mary's Hall 
Office Hours: 
TR 12:00–1:30 PM (or by appointment).

Description
This graduate lecture surveys methods of automated deductive reasoning.
Through traditional lectures, programming projects, paper presentations,
and research projects, students learn
(1) to understand the foundations of logical and probabilistic methods of automated reasoning.
(2) to implement algorithms for logical and probabilistic reasoning,
(3) to comprehend, analyze, and critique papers from the primary literature,
(4) to replicate studies described in the primary literature,
and
(5) to design, conduct, and present their own studies.
Topics include
propositional logic,
predicate logic,
resolution proof,
production systems,
Prolog,
uncertain reasoning,
certainty factors,
Bayesian decision theory,
Bayesian networks,
exact inference,
approximate inference,
firstorder probabilistic models,
probabilistic programming languages,
and applications.
Students complete programming projects using Java.
Prerequisites:
Students should have taken undergraduate courses in computer
science through data structures;
at the very least, students must be able to implement trees and graphs in a
highlevel objectoriented programming language.
Students should have also taken undergraduate courses in mathematics,
such as probability, statistics, and perhaps propositional and
firstorder logic.
Recommended Text:
Additional Resources:
 Logical foundations of artificial intelligence,
by Genesereth and Nilsson.
[ Amazon  Lauinger ].
 Probabilistic graphical models: Principles and techniques,
by Koller and Friedman.
[ Amazon  Lauinger ].
 Pattern recognition and machine learning,
by Bishop.
[ Amazon  Lauinger ].
Learning Goals
By the end of the semester, students will be able to:
 explain the main foundations of automated reasoning
 understand and design objectoriented systems for automated reasoning
 analyze algorithms for automated reasoning in time and space
 implement methods of automated reasoning using a highlevel programming language
 comprehend, analyze, and critique scholarly papers from the primary literature
 replicate studies described in the primary literature
 design and conduct empirical studies
Policies
My course policies are designed to supplement the
CS
Department's Honor Policy.
Unless stated otherwise when I distribute an assignment, the
following is the default for all assignments for this course.
I've developed my policies from past teaching experiences and from
the
CS Department's Honor Code at George Mason University.
I am obligated to refer all suspected cases of academic dishonesty by
master's students to the Honor
Council.
I am obligated to refer all suspected cases of academic dishonesty by
doctoral students to the dean of the Graduate School.
If you have any questions about these policies or how they apply,
please discuss such concerns with me during class, during office hours,
or by email.
In my experience, students at Georgetown do honest work.
The small percentage of students who have submitted someone else's
work as their own did so because they did not manage their time wisely.
Students must follow proper scholarly practice for all submitted work,
whether graded or ungraded and whether a draft or final version of
a proposal, paper, or program.
We must acknowledge our reliance on the work of others through citation.
Students may be quite adept at and knowledgeable about citing and
quoting material from traditional sources, such as books and articles.
Typically, we do not have cite facts, common math formulae,
or expressions of our own ideas, observations, interpretations, and
analyses,
However, new graduate students in computer science may not realize that
formulae, theorems, proofs, algorithms, and programs can require the same
treatment as any other form of expression.
For convenience, you do not need to cite the course materials,
conversations with me or information you obtain from class lectures
and discussions.
If you are unsure about what requires citation or what constitutes
proper scholarly practice,
please ask me during class, during office hours, or by email.
I design my courses and assignments so students have what they need
to complete the assignments individually without consulting outside
resources.
I determine the size of and credit for assignments based on the
assumption that the work for them is the result of individual
effort using only the course resources and materials.
Students who use outside resources to complete assignments may not be
eligible for full credit.
Students who do not acknowledge their use of outside resources to
complete assignments may be in violation of my course policies
and the university's policies on academic integrity.
The following list details acceptable and unacceptable practices:
 You can:
 obtain assistance in understanding course materials (textbooks,
lecture notes, assignments);
 obtain assistance in learning to use the computing facilities;
 obtain assistance in learning to use special features of
a programming language's implementation;
 obtain assistance in determining the syntactic correctness
of a particular programming language statement or construct;
 obtain an explanation of a particular syntactic error;
 obtain explanations of compilation or runtime error messages.
 You can obtain assistance only from me and the teaching assistants:
 in designing the data structures and algorithms used in your
solution;
 in modifying the design of an algorithm or data structure
determined to be faulty;
 in implementing your algorithm or data structure in a
programming language;
 in correcting a faulty implementation of your algorithm or
data structure;
 in determining the semantic correctness of your program;
 in designing an experimental study and interpreting its results.
 You can not:
 show or give a copy of your work in any amount or form to another student;
 see or receive a copy of someone else's work in any amount or form;
 attempt to gain access to files other than your own
or those that I designate and authorize;
 attempt to reverse engineer routines used for automatic grading;
 inspect or retain in your possession another student's
work, whether it was given to you by another student, it was found
after other student discarded his or her work, or it accidentally
came into your possession;
 collaborate in any way with someone else in the design,
implementation, or logical revision of an algorithm;
 use or present as your own any algorithm, data structure, or
implementation that is not of your own or of my design, or which
is not part of the course's required reading.
If you modify any procedure which is presented in the course's
texts that is not specifically mentioned in class or covered
in reading assignments, then a citation with page number must
be given;
 incorporate code written by others (such as can be found on the
Internet).
Policies dealing logistics:
 You have permission to occasionally take digital photos of the
material on the board for your personal use, but you can not post
these recordings on the Internet.
It is important to understand that all of the course material is
covered by copyright, either mine or someone else's.
 You should submit all assignments on time. For late projects,
there will be a 1% deduction for each minute after the deadline.
In the real world, it won't be your grade that decreases. It'll
be your stock price.
 I grant extensions only to students who have documentation for
a medical issue, a family emergency, or an accommodation from the
Academic Resource Center.
In the cases of a medical issue or a family emergency, it would be best
to coordinate with your advising dean since these situations often
affect your work in all of your classes.
 If you use your laptop for development, you should keep a backup
of your projects on a university or department machine (e.g., csclass)
so I can verify that you completed the work for an assignment before
the deadline.
 You must take the final exam with the section and during the
period designated by the Registrar.
 It is my job to maintain a constructive learning environment for
everyone. Please silence your cell phone and other electronic devices.
 If you must miss class, be sure to get the lecture notes from a
classmate.
 It is fine if you must leave class early, arrive late, or leave the
room to answer your phone, but you should do so in a manner
that does not disturb your fellow students.
 In the case of inclement weather that results in the
university's closure, we will meet virtually during normal class times
using Zoom.
Assignments and Grading
 Programming Projects, 50%
 Project 1, assigned M 9/4
R 8/31, due Su 10/15 Su 10/22 @ 5 PM, 20 points
 Project 2, assigned
T 10/17 W 10/22, due T 11/14 @ 5 PM, 20 points
 Project 3, assigned M
11/13 11/20, due R 12/7 @ 11:59 PM, 10 points
 Midterm Exam, T 10/17, 20%
 Final Exam, T 12/19 @ 4–6 PM in REI 284, 30%
String Grades::getLetterGrade()
{
if (grade >= 94)
return "A";
else if (grade >= 90)
return "A";
else if (grade >= 87)
return "B+";
else if (grade >= 84)
return "B";
else if (grade >= 80)
return "B";
else if (grade >= 67)
return "C";
else
return "F";
} // Grades::getLetterGrade
Materials: Readings, Videos, and Links
 Autolab, for submitting projects
 Piazza, for online discussions.
 Canvas, for document distribution and submitting projects if Autolab breaks
 Dynarski, S. M. (10 August 2017).
For better learning in college lectures, lay down the laptop and pick up a pen.
Research Report, Brookings Institution, Washington, DC.
(Read if interested.)
 PerezHernandez, D. (28 March 2014).
Taking notes by hand benefits recall,
researchers find.
The Chronicle of Higher Education.
(Read if interested.)
 Mueller, P. A. and Oppenheimer, D. M. (2014).
The pen is mightier
than the keyboard: Advantages of longhand over laptop note taking.
Psychological Science, 25(6):1159–1168.
(Read if interested.)
 Russell and Norvig's algorithm for uniformcost search.
 Russell and Norvig's Unify algorithm.
 Slides: Genesereth and Nilsson's Sematics for FirstOrder Logic
 Robinson, J. A. (1965). A machineoriented logic based on the
resolution principle. Journal of the ACM 12.1:23–41.
 Kowalski, R. and Kuehner, D. (1971). Linear resolution with
a selection function. Artificial Intelligence 2:228–260.
 Russell and Norvig's forward and backward
chaining algorihtms.
 Slides: Bayesian Decision Theory.
 Bishop's Chapter 8: Graphical Models
 Barber, D. (2012). Bayesian Reasoning and Machine Learning. Cambridge University Press: Cambridge, UK.
 Russell and Norvig's variable elimination algorihtm.
 Russell and Norvig's Gibbs sampling algorithm.
 Slides: Algorithm for Probability Propagation in Trees.
 Tarjan, R. E. and Yannakakis, M. (1984).
Simple lineartime algorithms
to test chordality of graphs, test acyclicity of hypergraphs, and
selectively reduce acyclic hypergraphs. SIAM Journal on Computing
13.3:566579.
 Golumbic, M. C. (2004).
Algorithmic graph theory and perfect graphs
Elsevier: Amsterdam.
 Browne, C. et al. (2012).
A survey of Monte Carlo tree search methods.
IEEE Transactions on Computational Intelligence and AI in Games
4(1): 1–43.
 Slides: Monte Carlo Tree Search.

de Salvo Braz, R., Amir, E., and Roth, D. (2008).
A survey of firstorder probabilistic models.
In Innovations in Bayesian networks: Theory and applications,
289–317. Springer: BerlinHeidelberg.

Russell, S. (2015).
Unifying logic and probability.
Communications of the ACM 58.7:88–97.
 Nilsson, N. (1986).
Probabilistic
logic. Artificial Intelligence 28.1:71–87.
 Getoor, L. and Grant, J. (2006).
PRL:
A probabilistic relational language.
Machine Learning 61.1:7–31.
 Richardson, M. and Domingos, P. (2006).
Markov
logic networks.
Machine Learning 61.1:107–136.
 Gogate, V. and Domingos, P. (2011).
Probabilistic
theorem proving. In
Proceedings of the 27th Conference on Uncertainty in Artificial
Intelligence, 256–265. AUAI Press: Corvalis, OR.
 Domingos, P. and Web, W. A. (2012).
A tractable firstorder probabilistic logic. In
Proceedings of the 26th National Conference on Artificial
Intelligence, 1902–1909. AAAI Press: Menlo Park, CA.
Schedule
 Introduction: Definitions, Areas, History, Paradigms
 Propositional logic and resolution proof for the propositional case
 Predicate logic, Mostgeneral Unifiers
 Resolution proof for predicate logic
 Proof strategies, Prolog
 Post's Productions, Rulebased Systems, Rete Algorithm
 Midterm Exam
 Uncertainty, Probability Review, Certainty Factors
 Bayesian Decision Theory
 Bayesian Networks
 Exact Inference
 Approximate Inference
 Probabilistic Firstorder Logics
Other Interesting Links