Details of CS4102 (Autumn 2022)
| Level: 4 | Type: Theory | Credits: 4.0 |
| Course Code | Course Name | Instructor(s) |
|---|---|---|
| CS4102 | Artificial Intelligence: Search Methods For Problem solving | Dwaipayan Roy, Kripabandhu Ghosh |
| Preamble |
|---|
| This course is offered by NPTEL. The instructors listed here are the coordinators.
Enrolment: A student has to enrol themself in the course and should also opt for the course in the Welearn portal. Following are the dates for enrolling in the NPTEL portal. Course start date: 25 July, 2022 Course end date: 14 October, 2022 Exam date (on NPTEL): 29 October, 2022 Enrollment ends: ongoing, until 01 Aug 2022 Enrol here: https://onlinecourses.nptel.ac.in/noc22_cs67/preview Check here: https://nptel.ac.in/courses/106106226 Examination: The examination of the course will be conducted in-house by the Department of CDS. Specifically, there will be mid-semester and end-semester examinations. This in-house examination will be conducted for the course requirement of IISER Kolkata only and *will not* enable a student to get a certificate from NPTEL. If students want to get a course completion certificate from NPTEL, they need to register separately on NPTEL for the exam, pay a fee to NPTEL and write the proctored exam conducted by NPTEL in person at any of the designated exam centres. NPTEL will make the announcement regarding the commencement of registration for the examination. The online registration form must be filled and the candidate must pay the certification exam fee. More details will be made available by NPTEL when the exam registration form is published on the NPTEL course website. If there are any changes, they will be mentioned then. Please check the form for more details on the cities where the exams will be held, the conditions you agree to when you fill the form etc. (details available here: https://onlinecourses.nptel.ac.in/noc22_cs67/preview in the Course certificate section). Supplementary examination: In case a student fails in the course, there will be a provision for appearing for a supplementary exam which will be conducted by the department of CDS. There will be regular assignments from NPTEL that need to be submitted to NPTEL within the deadline. This is a requirement for getting a certificate from NPTEL together with seating for the exam. Although this is *not mandatory* for the purpose of course requirements at IISER Kolkata, it is encouraged as attending the assignments will help the students answer the questions in the in-house exams. |
| Syllabus |
|---|
| Week 0 : Introduction: History, Can Machines think? Turing Test, Winograd Schema Challenge, Language and Thought, Wheels & Gears
Week 1 : Introduction: Philosophy, Mind, Reasoning, Computation, Dartmouth Conference, The Chess Saga, Epiphenomena Week 2 : State Space Search: Depth First Search, Breadth First Search, Depth First Iterative Deepening Week 3 : Heuristic Search: Best First Search, Hill Climbing, Solution Space, TSP, Escaping Local Optima, Stochastic Local Search Week 4 : Population Based Methods: Genetic Algorithms, SAT, TSP, emergent Systems, Ant Colony Optimization Week 5 : Finding Optimal Paths: Branch & Bound, A*, Admissibility of A*, Informed Heuristic Functions Week 6 : Space Saving Versions of A*: Weighted A*, IDA*, RBFS, Monotone Condition, Sequence Alignment, DCFS, SMGS, Beam Stack Search Week 7 : Game Playing: Game Theory, Board Games and Game Trees, Algorithm Minimax, AlphaBeta and SSS* Week 8 : Automated Planning: Domain Independent Planning, Blocks World, Forward &Backward Search, Goal Stack Planning, Plan Space Planning Week 9 : Problem Decomposition: Means Ends Analysis, Algorithm Graphplan, Algorithm AO* Week 10 : Rule Based Expert Systems: Production Systems, Inference Engine, Match-Resolve-Execute, Rete Net Week 11 : Deduction as Search: Logic, Soundness, Completeness, First Order Logic, Forward Chaining, Backward Chaining Week 12 : Constraint Processing: CSPs, Consistency Based Diagnosis, Algorithm Backtracking, Arc Consistency, Algorithm Forward Checking |
| Prerequisite |
|---|
| This is a first course on Artificial Intelligence. While the intended audience is both UG and PG students studying Computer Science, in fact anyone comfortable with talking about algorithms should be able to do the course. |
| References |
|---|
| Text Book:
1. Deepak Khemani. A First Course in Artificial Intelligence, McGraw Hill Education (India), 2013. Reference Books: 1. Stefan Edelkamp and Stefan Schroedl. Heuristic Search: Theory and Applications, Morgan Kaufmann, 2011. 2. John Haugeland, Artificial Intelligence: The Very Idea, A Bradford Book, The MIT Press, 1985. 3. Pamela McCorduck, Machines Who Think: A Personal Inquiry into the History and Prospects of Artificial Intelligence, A K Peters/CRC Press; 2 edition, 2004. 4. Zbigniew Michalewicz and David B. Fogel. How to Solve It: Modern Heuristics. Springer; 2nd edition, 2004. 5. Judea Pearl. Heuristics: Intelligent Search Strategies for Computer Problem Solving, Addison-Wesley, 1984. 6. Elaine Rich and Kevin Knight. Artificial Intelligence, Tata McGraw Hill, 1991. 7. Stuart Russell and Peter Norvig. Artificial Intelligence: A Modern Approach, 3rd Edition, Prentice Hall, 2009. 8. Eugene Charniak, Drew McDermott. Introduction to Artificial Intelligence, Addison-Wesley, 1985. 9. Patrick Henry Winston. Artificial Intelligence, Addison-Wesley, 1992. |
Course Credit Options
| Sl. No. | Programme | Semester No | Course Choice |
|---|---|---|---|
| 1 | IP | 1 | Not Allowed |
| 2 | IP | 3 | Not Allowed |
| 3 | IP | 5 | Not Allowed |
| 4 | MP | 1 | Not Allowed |
| 5 | MP | 3 | Not Allowed |
| 6 | MR | 1 | Not Allowed |
| 7 | MR | 3 | Not Allowed |
| 8 | MS | 3 | Not Allowed |
| 9 | MS | 5 | Not Allowed |
| 10 | MS | 7 | Elective |
| 11 | MS | 9 | Elective |
| 12 | RS | 1 | Not Allowed |
| 13 | RS | 2 | Not Allowed |