This page, http://www.cs.uiowa.edu/~hzhang/c145/, is always under construction.
Grades of C- or higher in 22C:019 and 22C:031.
|
Instructor:
Hantao Zhang
Office: 201B MLH, Email: hzhang@cs.uiowa.edu, Tel: 353 2545 Office hours: MWF, 1:30-2:30pm |
Teaching assistant:
Rajiv Raman
Office: 101K MLH, Email: rraman@cs.uiowa.edu, Tel: 353-2542 Office hours: T.Th. 1:30-3:00pm |
Attention The class on Friday, Dec. 8, is cancelled.
The deadline for submitting the web presentation of your final project is 4pm, December 14, 2006.
For a sample of the web presentation of your project, please see http://nest.cs.uiowa.edu/22C178f02/uploads/acct/tmorio/index.html
I need to hear from anyone who has a disability, which may require some
modification of seating, testing or other class requirements so that
appropriate arrangements may be made. Please contact me as soon as possible.
In addition, a number of class notes and handouts will be available through the course web site.
LATE-DUE HOMEWORK ARE NOT ACCEPTED.
For homeworks involving programming, please hand in a listing of your
code and a transcipt of a sample run. Please also send a copy of your
code by email to both TA and the instructor.
For Problem 6.1, add the following requirement. Implement the minimax method for playing Tic-Tac-Toe against a human. The human has the option of playing first or second. You are free to define your own utility or eval functions or you may use the one in Prob 6.1. Please use as much pruning techniques (alpha-beta and symmetry checking) as possible to reduce the search problem.
Ask a classmate in 22C:145 to play his/her program against your program (once your program goes first and once second).
Please submit (a) your code, (b) a transcript of a sample run of your code, and (c) the name of your classmate who played against your program and the result of the match between the two programs.
You are required to write a computer which reads a 9x9 matrix of integers (0 denotes unknown elements) and then generate a set of propositional clauses in DIMACS CNF format. You then use one of SAT solvers to find a model of the propositional clauses. You also need to write a small program which reads the model and displays the solution of the puzzle.
SAT solvers can be found at www.satlive.org. You may also use my SAT solver satbox which is required to be run on a 32-bit integer linux machine. CS linux machines support only 64-bit integers.
All of these solvers accept DIMACS CNF format and run on linux systems. Suppose satbox is the solver and puzzle_file is the problem file, a typical command would be
satbox puzzle_file
Bonus: Create a description of the puzzle in Problem 5.13 in propositional logic (DIMACS CNF format) and solve it using a SAT solver.
not_gate(0,1). not_gate(1,0). and_gate(0,_,0). and_gate(_,0,0). and_gate(1,1,1). nand_gate(A,B,C) :- and_gate(A,B,X), not_gate(X,C).
On CS linux machines, SWI-prolog is installed (the command is pl). Please see http://www.swi-prolog.org/ and SWI-Prolog Reference Manual. Your code should run in pl.
The remaining homework is a small programming project in Prolog: You are asked to implement Choose-Attribute in the function Decision-Tree-Learning in Figure 18.5 (page 658).
The examples will be the data from Figure 18.3, which can be specified in Prolog as follows:
atributs([alt([y,n]),
bar([y,n]),
fri([y,n]),
hun([y,n]),
pat([none,some,full]),
price([chea,medi,expe]),
rain([y,n]),
res([y,n]),
type([burger,french,italian,thai]),
est([w1,w2,w3,4])
]).
examples([x1([y,n,n,y,some,expe,n,y,french, w1], y),
x2([y,n,n,y,full,chea,n,n,thai, w3], n),
x3([n,y,n,n,some,chea,n,n,burger, w1], y),
x4([y,n,y,y,full,chea,y,n,thai, w2], y),
x5([y,n,y,n,full,expe,n,y,french, w4], n),
x6([n,y,n,y,some,medi,y,y,italian,w1], y),
x7([n,y,n,n,none,chea,y,n,burger, w1], n),
x8([n,n,n,y,some,medi,y,y,thai, w1], y),
x9([n,y,y,n,full,chea,y,n,burger, w4], n),
x10([y,y,y,y,full,expe,n,y,italian,w2], n),
x11([n,n,n,n,none,chea,n,n,thai, w1], n),
x12([y,y,y,y,full,chea,n,n,burger, w3], y)]).
You need to write a function to compute the information Gain
for all the atributes and then return one with the maximum gain.
There will be two midterm exams and no final exam. All midterms will be held during class time.
FOR THE POLICY ON CHEATING, SEE THE GRADUATE
HANDBOOK OF THE DEPARTMENT OF COMPUTER SCIENCE.
You are expected to study all the material in each chapter covered in the readings even if that material is not explicitly discussed in class or in the homework. You are also expected to study the extra material presented in class which is not in the textbook. Material presented in class, but not in the book may appear on tests.
The lecture notes are a supplement to the course textbook. They are supposed to help you understand the textbook material better, they are not a replacement for either the textbook or the lecture itself.