CS 440: Introduction to Artificial Intelligence (Fall 2024)

Lectures: Mon/Wed, 5:40 - 7:00 PM at Beck Hall - Room 100 (BE-100), Livingston Campus
Recitations: Sec 01: Tue 4:05 - 5:00 PM, Livingston TIL-246
Sec 02: Tue 2:15 - 3:10 PM, Livingston LSH-B269
Sec 03: Tue 12:25 - 1:20 PM, Livingston LSH-B115
Instructor: Xintong Wang (Email: xintong.wang[at]rutgers.edu; Please add CS440 in email subject, e.g., [CS440] + your subject)
TAs, Office Hours, Piazza: TAs: Yuhong Luo, Nikolaus Salvatore, Garrett Seo
Office hours: Announce every week in lectures
Piazza: https://piazza.com/rutgers/fall2024/cs440

Announcements

Welcome to CS440! You can find the course info, syllabus, and announcements here.
Sept 1: Please note that there will be no recitation this Tuesday, Sept 3.
Sept 3: We will be using Piazza for class discussion. The system is highly catered to getting you help fast and efficiently from classmates, the TA, and instructor. Rather than emailing questions to the teaching staff, I encourage you to post your questions on Piazza. Find our class signup link at: https://piazza.com/rutgers/fall2024/cs440.
Sept 16: Programming assignment 1 is out (due Mon 9/30, 5pm)! Please start early and first read through the project. If you have any question, please feel free to drop by office hours or ask on Piazza.
Sept 30: Programming assignment 2 on RL is out (due Mon 10/14, 5pm)! Please start early and first read through the project and submission instructions. If you have any question, please feel free to drop by office hours or ask on Piazza.

Course Overview

What do web search, AlphaGo, face recognition, machine translation, autonomous driving have in common? These are all complex real-world problems, and the goal of artificial intelligence (AI) is to tackle these with rigorous mathematical tools. This course will introduce the basic ideas, foundational principles, and techniques underlying the design of intelligent computer systems.
Specific topics include search, game playing, Markov decision processes, constraint satisfaction, graphical models, and machine learning. By the end of this course, you will have built autonomous agents that efficiently make decisions in fully informed, partially observable and adversarial settings. Your agents will draw inferences in uncertain environments and optimize actions for arbitrary reward structures. Your machine learning algorithms will classify handwritten digits and photographs. The techniques you learn in this course apply to a wide variety of artificial intelligence problems and will serve as the foundation for further study in any application area you choose to pursue.

Prerequisites: This course will assume prior computer programming experience and fundamental knowledge in algorithm design, discrete math, and probability. This course will involve substantial elements of both programming and mathematics, as these are central to modern AI. We will help with refreshing key concepts and techniques in recitations. However, you should be prepared to review basic probability on your own if it is not fresh in your head. Programming assignments will be in Python. We do not assume previous experience with the language, but we do expect you to learn the basics very rapidly. Project 0 is designed to walk you through the basics of Python, but if you want to get a head start here is a good tutorial.

Course Schedule (tentative)

Date	Lectures	Readings	Recitations (Tues)	Dues
Wed 9/4	Introduction [slides]	Chap. 1 & 2	No recitation
Mon 9/9	*[Search]: Problem solving as path finding...* Uninformed Search [slides] (Tree search, BFS, DFS, uniform cost search)	Chap. 3.1-3.4	Review: Probability & discrete math	Class survey
Wed 9/11	Informed Search [slides] (A* search and heuristics)	Chap. 3.5-3.6		Last day to add/drop (Thu 9/12)
Mon 9/16	Informed Search (cont.) [slides] (designing heuristics) [Markov Decision Processes]: Decision making in a stochastic environment... Utility, MDP I [slides] (MDP, utility, policy evaluation)	Chap. 17.1-17.3; RL Chap. 3 & 4	P0: Python tutorial Recitation 2: Search [solution]
Wed 9/18	MDP II [slides] (policy evaluation, value iteration, policy iteration)	Chap. 17.1-17.3; RL Chap. 3 & 4
Mon 9/23	Reinforcement Learning I [slides] (Framework, model-based vs. model-free, TD learning, Q-learning)	Chap. 21.1-21.3; RL Chap. 5 & 6	Recitation 3: MDPs [solution]
Wed 9/25	Reinforcement Learning II [slides] (Q-learning (cont.), exploration vs. exploitation, approximate-Q)	Chap. 21.4-21.6; RL Chap. 9
Mon 9/30	Reinforcement Learning II (cont.) [slides] (approximate-Q) [Game Playing]: Decision making in a multi-agent environment... Adversarial Games I [slides] (Adversarial search, Minimax)	Chap. 5.1-5.3	Recitation 4: RL [solution]	PA1: search (Mon 9/30 5pm on Canvas)[pseudocode]
Wed 10/2	Adversarial Games II [slides] (Minimax, expectimax, Alpha-beta pruning)	Chap. 5.1-5.3
Mon 10/7	Adversarial Games II (cont.) [slides] (expectimax) Game Theory I [slides] (simultaneous-move game, normal-form representations, solution concepts)	Chap. 17.5	Recitation 5: Adversarial Search [solution]
Wed 10/9	Game Theory II [slides] (DSNE, PSNE, MSNE, equilibrium computation)	Chap. 17.5-17.6
Mon 10/14	*[Constraint satisfaction problem]: Problem solving as assigning variables under constraints...* CSP I [slides] (Definition, types of CSP, backtracking, filtering)	Chap. 6.1	Recitation 6: Game Theory [solution]	PA2: RL (Mon 10/14 5pm on Canvas)
Wed 10/16	CSP II [slides] (backtracking search, arc consistency, (nearly) tree structure)	Chap. 6.2-5
Mon 10/21	CSP II (cont.) [slides] (local search) *[Bayesian networks]: Quantifying uncertainty and probabilistic reasoning...* Probability [slides] (Notations, joint, marginal, and conditional probability distribution, probabilistic inference)	Chap. 13.1-13.3	Recitation 7: CSPs [solution]
Wed 10/23	Midterm Review [slides]			Homework 1 (Wed 10/23 5pm on Gradescope)[solution]
Mon 10/28	In-class Midterm
Wed 10/30	Bayesian networks I [slides] (Bayes rule, conditional independence, representations)	Chap. 13.4-13.5 & 14.1-14.3
Mon 11/4	Bayesian networks II [slides] (Query independence)	Chap. 14	Recitation 8: Probability & Bayesian Network Representation [solution]
Wed 11/6	Bayesian networks II [slides] (Query independence cont'd) Bayesian networks III [slides] (Inference)	Chap. 14.3-14.4
Mon 11/11	Bayesian networks III [slides] (Inference cont'd) Bayesian networks IV [slides] (Approximate inference with sampling)	Chap. 14.5	Recitation 9: Bayesian Network Inference [solution]	PA3: Adversarial Games (Mon 11/11 5pm on Canvas)
Wed 11/13	Bayesian networks IV [slides] (Sampling, cont'd) *[Machine Learning]: Learning from examples...* Naive Bayes, supervised learning setup [slides] (Classification, train/test, overfitting)	Chap. 13.5 & 18.2
Mon 11/18	Linear models [slides] (Perceptrons, SVM, train/test, overfitting)	Chap. 18.6 & 18.9	Recitation 10: Sampling & Naive Bayes [solution]
Wed 11/20	Linear models [slides] (Improving perceptrons, cont'd) Logistic regression & Gradient Descent [slides]	Chap. 18.6 & 18.7		Homework 2 (Wed 11/20 5pm on Gradescope)[solution]
Mon 11/25	Generalization, overfitting & model selection [slides]
Wed 11/27	Thanksgiving break, no class
Mon 12/2	Neural Networks I [slides] (Representationability, forward pass)	Chap. 18.7
Wed 12/4	Neural Networks II [slides] (Backpropagation)	Chap. 18.7
Mon 12/9	*Unsupervised learning, Advanced topics and applications, Future of AI [slides]			Homework 3 (Mon 12/9 5pm on Gradescope)[solution]
Wed 12/11	Final Exam Review [slides]			PA4: ML (Wed 12/11 5pm on Canvas)

Textbooks (for reference not required)

There is no required textbook for this class, and you should be able to learn from the lecture notes and homeworks. Slides will be posted after lectures. We will draw on the following books for some of the lectures:

(Default) Russell and Norvig. Artificial Intelligence: A Modern Approach. A comprehensive reference for all the AI topics that we will cover.
(RL) Sutton and Barto. Reinforcement Learning: An Introduction. Covers Markov decision processes and reinforcement learning. Available free online.
(LFD) Yaser S. Abu-Mostafa, Malik Magdon-Ismail, Hsuan-Tien Lin. Learning From Data. Covers the basic theory, algorithms, and applications of machine learning.

Coursework and Policy

Grading

The course will involve 4-5 (paired) programming assignments, 2-3 (individual) written homeworks, a midterm, and a final. Typically, each assignment/exam will include opportunities for extra credit. We will follow the grading scheme below:

Programming assignments (30%): The programming assignments will ask you to implement key components of an algorithm, for example, in search, adversarial games, reinforcement learning, machine learning, etc. You can work in pairs, if you wish. More details on submission instructions to follow.
Written homeworks (20%): There will be 2-3 problem sets, to complement the programming assignments and cover theoretical concepts discussed in lectures. The written assignments are individual. Homeworks should be written up clearly and succinctly. You are encouraged to use LaTeX to writeup your homeworks, but this is not a requirement. You will receive one (1) bonus point for submitting a typed written assignment (e.g., LaTeX, Microsoft Word). We will accept scanned handwritten assignments but they will not receive the bonus point.
Midterm (20%): We will have one in-class midterm that will test your knowledge and problem-solving skills on preceding lectures. You cannot use any external aids except one double-sided page of notes. The tentative date is 10/28. If you have a major conflict (e.g., an academic conference), submit a request to take it at another time.
Final (30%): The exam is during the final period and will test your knowledge and problem-solving skills on preceding lectures, projects, and homeworks. You cannot use any external aids except one double-sided page of notes. If you have a major conflict (e.g., an academic conference), submit a request to take it at another time once we confirm the final date and time.
Participation (bonus 3%): Positive participation bonus will be given to students who actively participate in lectures and recitations and/or answer other students' questions on Piazza in a substantial and helpful way.

As a rough guide, the following may be used for final grades, A: > 89; B+: 80-89; B: 70-79; C+: 60-69; C: 50-59; D: 40-49; F: less than 40.

Late, regrade, makeup policy

The following policy applies except for institute-established illness or emergency, in that case please kindly provide any official approval.

Grace period: You have seven late days in total that can be distributed among the written/programming assignments without penalty. For each written/programming assignment, we will allow a max of two late days (48 hours). In case that two members in a group have different numbers of days remaining in grace periods, we can only apply the lesser of the two.
Late discount: After the grace period, you can choose to receive a 25%, 50%, or 75% reduction in your grade for 1, 2, or 3 late days. No assignment will be accepted after that.
Regrade: You may submit a regrade request within one week after the grades are released. This applies to all written/programming assignments and exams (except the final, for which we will need to meet Rutger's grading deadline). After that, all grades are final.
Makeup exam: We will ensure the dates for exams are posted well in advance. To request a makeup exam due to a major conflict, you must email the course staff at least ten days before the exam. Please note that due to the large size of the class, we cannot ensure accommodation for alternate exams. If you miss an exam due to a documented extenuating circumstance, we may consider increasing the weight of the other exam or finding another solution at the instructor's discretion.

Collaboration policy and honor code

You are free to form study groups and discuss homeworks and programming assignments, without sharing code or answers. You should write up homeworks and code independently, and you must acknowledge in your submission all the students (from other groups for coding assignments) you discussed with.
You are responsible for the content of your writing, including its correctness and that it does not plagiarize other sources. If absolutely necessary to use other sources, cite any tools, web sources, papers, textbooks that you consulted. GenAI is not allowed.
If you choose to work with another student on the programming assignment, you two should discuss and work on all the problems together.
Please read this document for more information on academic integrity and student support.

Acknowledgments

This course is designed with generous help and inspiration from Profs. Pieter Abbeel (UC Berkeley), Lirong Xia (Rutgers), Abdeslam Boularias (Rutgers), Percy Liang (Stanford), and Dorsa Sadigh (Stanford). Specifically, we want to acknowledge the following courses: