Artificial Intelligence

Spring 2021 -- Peter Brooks

The (ever-changing) Syllabus and readings

Final Project

Due Sat, June 12
I would like to dedicate the final AI project to finding ways that AI can reduce inequality.  That could be economic, racial, sexual, ethnic inequality.  We will start talking about this on Monday.  The project itself can be a paper, a powerpoint, a video, a song, a creation.  But it must imagine the harnessing of AI to a process whose prime intent is to reduce inequality.

Let's start by understanding at least the extent of one type of inequality: income.  Here's a way to do that.
Decision Trees Here are two simple loan-granting decision trees and one for taking a legal case.

Restaurant waiting decision-treeDecision-tree section of Russell & Norvig.

Homework, due Wed, 6/2 night.
Read this lipogram.
Letter frequency chart.

Read the Notes on Information Theory, and solve the report on your solutions for the exercises #1 and #2,  and give #3 a try.
Information Theory I'll be going over these Notes on Information Theory that I wrote about the topic.
Neural Net calculations, due Wed. May 5.

Here are 4 excellent(!) Youtube videos on how neural networks work from 3Blue1Brown (Grant Sanderson, is, in my opinion, the best explainer of difficult mathematical ideas on the net).

You'll need only the first video to do the homework calculations below....

Keep the following questions in mind:

  • How did he decide on the number of nodes in his network architecture: namely how many hidden layers and the number of nodes in each hidden layer?
  • How do you calculate the number of weights given the details (above) of the architecture?

  • Here are some terms I'll use below:
    • an Image-Cal is the computation process involved in showing the network a single image
    • a Cost-Calc is the process of showing the network every image from the entire set of training images: this process produces a single instance of the cost function's value(s)
    • Training-Calc is process of repeating CC many, many times to train the network and adjust its weights to an optimal value
  • Do the following calculation:
    • (Calc 1): if his network is presented with a single image, how many operations (each multiplication is an operation, as is an addition) does it take to calculate the single result (the list of 10 probabilities) from that image (the Image-Calc)?  Ignore the calculation of the sigmoid function, and we're only looking for approximate values (+- 10%).
    • (Calc 2): Having done that, now calculate that for a run 30,000 different images (the Cost-Calc). When finished, you've now calculated one data point measuring how well the network classifies (initially, it classifies very poorly). 
    • (Calc 3): Assume that it takes 100,000 data points (trials) to train the network.  If each operation takes a 10 nanoseconds (a single core processor), how long does does training take assuming you had only a single-core processor (the Training-Calc)?  Ignore the work of backpropagation, if you know about that.  Use the most reasonable humanly understandable time unit (secs or hours or days or fortnights or millenea...)
  • Put the answers into the Comments-to-Teacher

How economically/socially costly is it to do such calculations?  Read this article from MIT's Technology Review.  That article is 2 years old and is about GPT-2. GPT-3 is very much larger and more expensive to train, reputedly costing $12 million.

All right... on to perfection, at least for TicTacToe....

Create your perfect competitor.

by Mon, May 3.

We'll do this in 2 steps:

1. Create the CreateAllBoards(layout) function.  It will create the game tree of all moves starting from a particular board-layout.  Make sure that the statistics that you calculate from having run this function match the correct stats (here are mine) from the previous homework. 

2. Download the file and unpack.  It contains all the goodies to guide you in creating your competitor and also testing it interactively in NetLogo.

3. Create your perfect competitor, upload the program (that marries with the NetLogo UI) and also write your adventures in creating it in the Comments-to-Teacher.

Minimax Algorithm and Alpha-Beta Pruning explained.

The Matchbox (MENACE) version, by Donald Michie, and the video of it in action:
Starting on Tic-Tac-Toe

Due Wed night 4/21 (after class)
Here are some of the conventions we'll use in describing TTT boards: 

Here are the calculations I want you to make and post on the Comments-to-Teacher.
Here are my code answers for the calculations.
AI, Automation and Unemployment

Video needs to be watched and Economist piece read in time for our discussion of the issues on Fri 4/9

Essay due: Sat. 4/10
-- Create and submit an outline for the video and essay below. The outlines should be short restatements of the arguments presented in the video and in the essay. 
-- In the essay, which of the two points of view, argued for by the video and article below, convinces you more? 
-- Among your list of societal/political worries about the next 10 years, does this make the top 5? top 10?
-- Submit to the homework server in .pdf, .doc, .docx, or google-doc form.

1. "Humans Need Not Apply" video.
2. The Economist (magazine) has an excellent, though long, introduction to technological unemployment issues. I'd like you to read
a) the first 2 pages of the Introductory section (up to "Technology")
b) the section on The Impact on Jobs (pp. 5 - 8)
c) the Conclusion (pp 13-14)

Be ready to contrast the article with the video in class. 

The rest of this long Economist essay is also very good. I urge, though don't require, you to read the other sections.
Smarter Sudoku algorithms

Due: Wed. 4/7
Here is the file of boards again (slightly increased) with increasingly more difficult ones further down.  Sudoku-boards-Master-unsolved.txt

Record your results here (your backtrack numbers and execution times in seconds (not more than a couple of significant digits for sub-second times, please). For any change of algorithm that's reasonably smart, you should see a significant improvement in the stats.
Naive Sudoku solver.

Results (and code) due Wed, 3/24 8:00a
You'll be implementing a "naive" Sudoku solver -- namely a solver that works, but is quite simple.  I will describe the algorithm that you should implement.  For now, do not do anythings smarter -- this will be used to compare to your eventually much smarter version.

Here is the algorithm and a set of suggestions.

The backtrack measure: Compute the total number of incorrect-guesses for each of the 3 sample boards and put that into the Comments-to-Teacher for each of the boards you solve (put name-of-board and incorrect-measure for each board).  Defining the incorrect-measure more precisely: every time you backtrack to a cell that allows you to make another guess on that cell, increment the measure by one.  In particular, if you backtrack to a cell that has more no guesses available, and you have to backtrack again from that cell, do not increment -- wait until you reach a cell on your way back that allows another guess.

You can also try your solver on harder (and some much harder) boards from this file:  Sudoku-boards-Master-unsolved.txt

Here is my Sudoku-Naive-Solver and its .pynb file.

First Sudoku homework (swap-finder) due:
Sun night: 3/14
Basic Sudoku layout info.

The homework is to create a program that finds swapped entries in Sudoku boards:  Sudoku-swapped exercise.  You'll be submitting your program to the Program Tester for validation.

Here an answer for the Sudoku-swap problem.
Testing the Program Tester
Due: Wed 3/10, 8:00am
You will be creating a simple program that will be tested by the Homework server's Program Tester.

Here are the general Program Tester Docs on interacting with (care and feeding of) It.

Here are the instructions for creating this first program.  Upload the program to the homework server and test it. If it's failing or ailing, fix it and retest until fully baked.
Here's an answer to this exercise.
Constraint Satisfaction Problems

Look at this simple logic game.  Here is a way to start organizing its constraints into a data structure that is amenable to logic computation...

And here is a more complex puzzle that is solved in code (in .ipynb form)

Applied pessimism in algorithm design This is going out to HDubz and all you pessimistic coders out there:  Pessimal Algorithms
Definitions, foundations and history of A.I. There's no better introduction to what A.I. is than the first chapter of the major book in the field: Artificial Intelligence: A Modern Approach by Stuart Russell (Professor of Computer Science at the University of California, Berkeley and Adjunct Professor of Neurological Surgery at the University of California, San Francisco)  and Peter Norvig (Director of research at Google). The 3rd edtion was published in 2010 and the 4th in 2020.  The 3rd edition is available in PDF form (don't know about copyright violations) as well as inexpensive paper form.

If you want to understand the foundational definitions and the history, spend an hour or so with the 30 pages of absolutely clear writing of Chapter 1, Introduction: In which we try to explain why we consider artificial intelligence to be a subject most worthy of study, and in which we try to decide what exactly it is, this being a good thing to decide before embarking.

And if your bent is the philosophical foundations, including a discussion of the Chinese Room thought experiment, then flip to the last chapter: Philosophical Foundations: In which we consider what it means to think and whether artifacts could and should ever do so.

In between are more than 1,000 pages of the technology of A.I.
WordLadder Homework
Due: Sun night 2/28
My Jupyter version.
For Wednesday's (2/24) discussion: Can Machines Think?, read the following arguments...  Anti-Lovelace and the Chinese Room. 
Sign up for your Presentation Date-Time slot.

Signup due: Fri, 2/26 midnight. 

After that, I will sign up those who haven't.

Go to the Presentation Scheduler and you (or your partner) make a copy of name(s) in Column A and plant the copy in Column D for the date-time slot you've chosen.

Here are the requirements for the Presentation:

  • It must be about an AI topic.  It can be technical (e.g. what are CNNs and what are they good for), about capabilities (e.g. demo a good text-generator and show its limits), about industrial or military applications (e.g. AI in drone tech, AI in agriculture), social issues (e.g. AI in criminal justice, AI biases), philosophy (e.g. AI rights) or other topics you can find.  If you're not sure about a topic, run it by me.  There is a lot of material in the Syllabus and Readings above, but there's of course a vast amount out there.
  • You (person or pair) will have 15 minutes to present, with about 5 minutes for questions afterwards.  Each member of a pair must present about equally.  There will be 2 topic presentations during the class period, and we will have presentations about every other class period.
  • Declare your topic at least one week before your presentation, on the Presentation Scheduler above.  All topics must be different.
  • Add your presentation documents to the following Google Doc
    -- add your at the top, pushing the older ones down.  This should include links to videos, Google presentations, and other documents (or a synopsis of your talk).
  • Uninformed (like breadth-first)
  • Greedy (somewhat like depth-first)
  • A*

Searching:  Here's an explanation, in excruciating detail, of those searches applied to a simple example.

Here is a webpage showing the results of different search techniques.

Essay bargain: read 3, write 1.

Homework Due Thurs (2/11) midnight, with no-penalty grace period until 2/14 midnight

Homework: read 3 essays and write a short essay (at least one side, double-spaced) to answer a couple of simple questions (that have been debated for at least 60 years).


Finish signing up by the time we return from break.  All non-duos will be then designated solos.
You (solo) or y'all (duo) will be giving a 15-20 minute presentation later in this semester.  Here is a signup sheet.  Next to your name, indicate with "y" or  "n" whether you'll be presenting with a partner, and if so, who.
First Homework: write a linked-list class:
Due on the homework server Wed 2/10 morning 8:00a
Here's the template of code for the linked-list.  Write the code that's missing and test it (there's a test routine at the bottom.
If you have problems, write about them on the Comments-to-Teacher on the homework server slot for this homework.

My answers: in .IPYNB form:   and in ordinary .PY form (will be downloaded as .txt file and then change the file suffix to ".py")
Python Classes Yes, you can program classes and instances in Python, except it's a lot less bossy than Java.  Here's my quick intro to Classes.ipynb (download).
More Python Review Here's a second Jupyter Notebook Python-Review-2.  Download and study, along with its links.
Python review Here's a Jupyter notebook (right-click to download).  Load it into a working Jupyter server (at school, or at home, or Google's Colab) and:
- read all of my Python review docs (#2 and #3) in the first cell
- in your browser, bookmark the PQR reference
- I have left a cell below each review topic in the notebook for you to play in.  Play in them.
Python!  Jupyter Notebooks! We'll be using Python in this class.  Feel free to forget the arcane details of Java, but retain at least some knowledge of classes.

Learn about Jupyter Notebooks using Google's free Colab environment here.  And/or you can use Jupyter notebooks by downloading and installing the huge Anaconda distribution from here.

If you've never been introduced to Python or are pretty rusty, take a look at's suggestions for learning.  If you're willing to read, I recommend Head First Python.  Also CodingBat for quickie exercises.

Learning Python resources:
My Python cribsheet
Python topic explanations from Intro-2
Richard Gruet's Python page This is my standard quick-reference for Python.  It's the first place I go to for a quick look at the operators and methods of built-in datatypes.  I often have this up in a different browser tab with programming.   Although it's only really accurate for v. 2.7.x, there is very little difference between this and 3.6.x (and anyway, the 3.6.x+ compiler will warn you if you have sinned).
Help from Mr. Brooks Feel free to come to the class channel: #office-hours during office hours or make an appointment with me by email.

Office Hours Zoom (sometimes) -- preferably, send me email beforehand if you will want to Zoom-talk...  I will also be on the channel: office-hours 
Meeting ID: 811 5113 1539
Passcode: 235232
First task: fill out your Profile on the Homework server.
  1. Go to the main class link page (
  2. Click on the Homework/Grade server link
  3. Choose the Profile menu item
  4. Choose your period and name
  5. Log in with your OSIS number as your password
  6. Fill out your email address and preferred first name only, DO NOT CHANGE YOUR PASSWORD YET.
  7. Save: (Change Profile button)...
  8. (optional, but recommended): now you can change your password for this Homework server, if you want.
  9. REMEMBER this password!
Sending email to Mr. Brooks:
Send mail to:

You MUST include your name in the subject line or body of the message, otherwise I won't know who it's from.
Stuyvesant bell schedule  
Homework/grade server  
Support Wikipedia