A Graduate Course at The University of Texas at Austin
Website: | cs.utexas.edu/users/hunt/class/2015-fall/cs395t/index.html |
Location: | GDC 6.516 |
Time: | Tuesdays and Thursdays, from 3:30pm to 5:00pm |
Unique Number: | 51086 |
Google Group: | |
Instructors: | Marijn J.H. Heule and Warren A. Hunt, Jr. |
Offices: | GDC 7.714 (Heule) GDC 7.818 (Hunt), GDC South building |
Office Hours: | TBA |
Email: | {marijn, hunt} at cs dot utexas dot edu |
Teaching Assistant: | TBD |
TA Office: | TBD |
TA Hours: | TBA Also available by request. |
TA Email: | CSuserid at cs dot utexas dot edu |
Reserved study room: | |
Reserved room times: |
Our course will investigate the use satisfiability and theorem-proving techniques to analyze formal models of computing systems. We will use mathematical methods to determine whether hardware circuits and software programs conform to their specifications. We will learn how to write formal specifications, how to capture mathematical models of hardware and software, and how to use decision procedures and theorem provers to verify that hardware and software models meet their specifications. Our course will convey many practical and research problems to the interested students. Our course assumes no particular background, but does expect students to understand propositional logic, recursion, induction, and some mathematical analysis.
This course will help participating students to analyze models of their designs and programs. The techniques presented will provide participants the ability to make automated determinations of reachability and termination; these determinations may demonstrate program properties (e.g., that no dead-end state can be reached or whether a program will terminate). There are many industrial uses for these techniques and tools. For example, these tools are used for commercial hardware and software verification; AMD, Centaur Technology, IBM, Intel, Oracle, and many other companies use these techniques. Academia is making use of the techniques; for example, various open combinatorial problems have been solved using the techniques we will be presented.
The mathematics presented in this course will be useful to students for the foreseeable future. The mathematical foundations presented we be useful in most, if not all, other computing-science courses. The successful student will be better able to tackle material problems where modeling is needed and where validation is required.
A series of increasingly difficult problems will be assigned. Some of these problems will be discussed in class. Class participation is expected, and student grades will, in part, reflect each student's contributions. Not showing up for class is a sure way to have a student's class-participation grade lowered. There will be a final exam (given in November) and several in-class quizzes. Each student will work on a project proposed by the student. Students will present their projects in class at the end of the semester.
Each student will propose a project topic on which to work prior to October 9. In the later part of the course, the demands from homework assignements will be reduced with students spending more of their time on their projects.
There will be two exams given. Homework will (generally) be assigned each week, and due nine days later (with some exceptions). The weighting of the grades for the various aspects of the course are: in-class exams - 30% (15% for the first exam and 15% for the last exam), homework - 30%, class project - 30%, and class participation 10%. The lowest homework grade will be dropped in the computation of the final homework grade. Homework will not be accepted late. Projects must be submitted by the last day of our class (May 8th). The examinations must be taken at the scheduled time.
Date | Topic | Reading | Homework | Slides |
---|---|---|---|---|
August 27 Thursday |
Introduction to Satisfiability | Homework 1 assigned | Slides (tentative) | |
September 1 Tuesday |
Applications of Satisfiability | Homework 2 assigned | Slides (tentative) | |
September 3 Thursday |
Encoding Problems into SAT | Homework 1 due | Slides (tentative) | |
September 8 Tuesday |
Local Search Techniques | Homework 3 assigned | Slides (tentative) | |
September 10 Thursday |
Lookahead Techniques | Slides (tentative) | ||
September 15 Tuesday |
Conflict-Driven Clause Learning 1 | Homework 2 due | Slides (tentative) | |
September 17 Thursday |
Conflict-Driven Clause Learning 2 | Homework 4 assigned | Slides (tentative) | |
September 22 Tuesday |
Preprocessing Techniques 1 | Slides (tentative) | ||
September 24 Thursday |
No class | Homework 3 due | ||
September 29 Tuesday |
Preprocessing Techniques 2 | Homework 5 assigned | Slides (tentative) | |
October 1 Thursday |
Quantified Boolean Formulas | Homework 4 due | Slides (tentative) | |
October 6 Tuesday |
Proof Logging for SAT and QBF 1 | Slides (tentative) | ||
October 8 Thursday |
Proof Logging for SAT and QBF 2 | Homework 5 due | Slides (tentative) | |
October 13 Tuesday |
Exam | |||
October 15 Thursday |
Project Proposals | Homework 6 assigned | ||
October 20 Tuesday |
||||
October 22 Thursday |
||||
October 27 Tuesday |
||||
October 29 Thursday |
Project Proposal Summaries | Homework 6 due Homework 7 assigned |
||
November 3 Tuesday |
||||
November 5 Thursday |
Homework 7 due | |||
November 10 Tuesday |
Project Reports and Questions | |||
November 12 Thursday |
No class, available for questions | |||
November 17 Tuesday |
Project Reports and Questions | |||
November 19 Thursday |
No class, available for questions | |||
November 24 Tuesday |
Project Reports and Questions | |||
November 26 Thursday |
No class, Thanksgiving Holiday | |||
December 1 Tuesday |
Student Presentations | |||
December 3 Thursday |
No class, available for questions |
There are no specific prerequisites for this class. Students are expected to have graduate standing of have received the instructor's permission to take this class.
In general, the information found in Code of Conduct is a good guide on how to conduct yourself in this class. Additional general information about College of Natural Sciences (CNS) class coursework and procedures can be found in Vice Provost Laude's memorandum to the CNS faculty.
This course should comply with the requirements of the University and the State of Texas. Texas House Bill 2504 specifies a number of items regarding course materials and instructor qualifications: Hunt. In addition, the material contained in the class webpages are designed to be compliant with Gretchen Ritter's (Vice Provost for Undergraduate Education and Faculty Governance) August 3, 2012, memorandum. Ritter's memorandum also addresses issues concerning campus safety and security. Please familiarize yourself with this information, and let us know if you believe the class Website does not comply with these requirements.
Any scholastic dishonesty will be referred to the Dean of Students Office. The following passage is taken from the University of Texas at Austin Information Handbook for Faculty.
As a reminder, the "UT Code of Conduct" is included below, and additional information on-line where one may find additional information (through additional links) about what constitutes plagiarism, cheating, etc. Specifically, the Academic Policies and Procedures of UT Austin may be consulted if you have any questions.
We fully support the University's scholastic honesty policies, and we will follow the University's policies in the event of any scholastic dishonesty. If you are ever unsure whether some act would be considered in violation of the University's policies, do not hesitate to ask your instructors or other University academic representatives.
Students with disabilities may request appropriate academic accommodations from the Division of Diversity and Community Engagement, Services for Students with Disabilities, 512-471-6259, or follow this link.
A notice regarding accommodations for religious holidays. By UT Austin policy, you must notify us of your pending absence at least fourteen days prior to the date of observance of a religious holy day. If you must miss a class, an examination, a work assignment, or a project in order to observe a religious holy day, you will be given an opportunity to complete the missed work within a reasonable time after the absence.
The following recommendations regarding emergency evacuation from the Office of Campus Safety and Security, 512-471-5767, or see the safety office website.
Occupants of buildings on The University of Texas at Austin campus are required to evacuate buildings when a fire alarm is activated. Alarm activation or announcement requires exiting and assembling outside. Familiarize yourself with all exit doors of each classroom and building you may occupy. Remember that the nearest exit door may not be the one you used when entering the building. Students requiring assistance in evacuation shall inform their instructor in writing during the first week of class. In the event of an evacuation, follow the instruction of faculty or class instructors. Do not re-enter a building unless given instructions by the following: Austin Fire Department, The University of Texas at Austin Police Department, or Fire Prevention Services office.
Information about emergency evacuation routes and emergency procedures is available.