Spring 2020 -- Peter Brooks
The (ever-changing) Syllabus and readings
|Coding exercises using information theory. Due, Thurs, 5/28, midnight.||
Here are some coding
exercises using variable-length coding.
There is an algorithm called Huffman Coding that will, in fact, produce the most efficient coding for a situation like we covered in class. Namely, given a coin with a certain number N of faces, with each face F(i) having a certain probability P(i) of coming up, and given that you wnt to group together the results of G flips, what is the most effiicent coding?
Here's a tutorial on how the Huffman Coding works.
|deeplearning.ai||This is a newsletter/blog by Andrew Ng's group on AI news. Check out the A.I. Eurovision Song Contest, among other news|
|And now, for something completely different...||Of course, you don't have any time for this....but here's a remarkable feat of puzzle-solving: solving a Sudoku board (with some additional rules) knowing only 2 of the 81 values. Solving the “The Miracle Sudoku”|
|Information Theory||I've created a set of notes on the Shannon Theory of Information. We'll be going through these ideas.|
|Real-Machine Learning!||MENACE: A TicTacToe-playing machine, that learns to play TTT well, built out of matchboxes containing beads, invented by Donald Michie in 1961. Video.|
|Teachable Machine||Machine learning inside a browser.|
|The Traveling Salesman Problem (TSP) homework due Mon, May 11, midnight||
We'll be talking about Genetic Algorithms as applied to the TSP.
You're going to have a crack at the TSP -- here are the
Here's the Genetic Algorithm quick tutorial video.
For those of you who were wondering if a solution to TSP was really important: read this.
Monday, Apr. 27
MiniMax algorithm (and Alpha-Beta pruning)
The MiniMax Algorithm is really, down deep what you've been using
for your TicTacToe competitors. So here are two videos that
explain both the MiniMax Algorithm and also the Alpha-Beta Pruning
Technique (which you're not using using).
1. Sebastian Lague explaining MiniMax and Alpha-Beta (11 min). Good and clear in the general description, although the alpha-beta code is not easy to follow.
2. Patrick Winston -- MIT OpenCourseware (48 min)
Patrick Winston of MIT talks about chess, MiniMax, Alpha-Beta, progressive deepening, and some history. Winston is one of the old men of AI -- his AI book used to be the standard textbook in AI. His lecture here at MIT is from 2014, before AlphaGo. At about minute 12:00 he appears to copy my technique of estimating total number of computations for a combinatorially explosive problem (his lawyer will hear from me).
Thurs. Apr. 23
Final TTT competitor that can be played with the Netlogo-UI, due Monday, Apr. 27, midnight
Here are new (corrected - version 2) instructions for
completing the TicTacToe competitor and testing it. Download,
unzip and read the ReadMe and get started. (The code template
had a bug).
There's a talk, this Sat. afternoon at 4:00 by the head of AI at Uber, and the head of Applied AI at Google. You need to register to see this talk, by midnight tonight (4/23).
|Wed. -- I'm not "in class" today (minor family matter)..||We'll continue TicTacToe on Fri, with the Daily Digital tomorrow (Thurs).|
|TTT #2, due after Tues, Apr 21, midnight||Preparing for the TTT competitor... CreateAllBoards() is a function that will hold all of the relevant information about every TTT board in preparation for using that information in computing the best move given any valid middle-of-the-game board.|
|Essay on thinking and simulation. Officially due Wed night, with leniency to Sat. night.||Write an essay on the two questions posed here.|
|Tic-Tac-Toe, Due Mon 4/6/20||
Here's the first TTT assignment --
calculating how large the combinational space to explore is.
Upload code and also type results into Comments-to--Teacher
Here is some code to help your processing...
Zoom meetings all this week during period 3.
See below for the reading assignment, due by Monday. We'll talk about this.
|The reality of simulations, and about intelligence and consciousness and the Turing Test.||
Computing Machines and Intelligence by Alan Turing (read parts
1, 2, 6 and 7)
A Coffeehouse Conversation on the Turing Test, by Douglas Hofstadter (you needn't read the Post Scriptum section at the end)
The Seventh Sally by Stanislaw Lem (much shorter sci-fi short story)
Zoom Meetings will be at 9:30, except lab days which will be
announced here ahead of time.
Meeting ID/Pwd will be sent to you by email (keep that data for the future).
Smart Sudoku solver due Sun, 3/29, midnight
Zooming today at 9:30 as usual: Meeting ID:
Here are 8 Sudoku boards (the first 3 you already know). Test your smarter solutions on these boards. Once more to test your smart program (called, say: sudoku-smart.py) against board A4-1, you should be able to run the program with the following command-line arguments:
python3 sudoku-smart.py Sudoku-boards-Master-unsolved.txt answer.csv A4-1
...and get just the 9 lines of the solution in in CSV form written into answer.csv. You should also print out (to the console) the number of backtracks and the elapsed time.
Show your solver data: You should also fill the Google spreadsheet with your naive and smart data for boards A6-1, A7-1 and A8-1, which are in increasing difficulty order. BTW, you may have trouble waiting for your naive solver on A8-1 (long time).
Note: each cell of that spreadsheet should contain 3 numbers, and here's how to format them. Let's suppose your data for A6-1 was the following: naive backtracks = 450, smart backtracks = 105. Then, the cell entitled "A6 backtracks" should contain the following string: "450 / 105 / 4.29", with the 3rd number being the improvement ratio between the first two (just 2 or 3 significant digits, please). Do the same things for the naive and smart times and their ratio. If the number of backtracks for A6-1 is 0 (congrats), then the cell should read "450 / 0 / inf".
The Program Tester is up for this smart solver. The tester's command-line will look like the one above, except the last argument could be for any one of the 8 boards (A1-1 ... A8-1) from the Sudoku-boards-Master-unsolved.txt file. I have allowed up to 10 seconds of Program Tester CPU time for your solver (it should take much less than that).
|Wed, 3/25||Working on the smarter Sudoku version.|
|Tues, 3/24||Zoom at 9:30, as usual. Meeting ID: 805-292-466 (no password). We'll go over naive Sudoku backtracks and times. And then onward, into the smartlands!|
A day to finish your naive Sudoku solvers and post on the homework
Also: look at the office hours and checkin links above. I'm starting the office hours on Mon...
Zoom session starting our regular class time: 9:30am (sorry,
latebirds) -- I'll be going over the Naive Sudoku solver homework
due this Sunday.
This is your first non-trivial programming assignment, so start early, post questions on the Q&A forum.
Sudoku: the Naive solver
Due, Sunday, 3/22, midnight
Here are a number of Sudoku
we'll be working with.
Here's -- some info on the coding for this problem.
Here's the main loop for my naive (simplest) version
Here are my backtrack numbers for various boards (note that they're not strictly correlated with NYTimes's estimation of difficulty):
Here are the instructions for program-tester.
Your program will be given 3 command-line arguments:
1) name of input file (which will contain a subset of Sudoku boards)
2) name of the output file
3) name of the board to solve: that will be one of the following:
A2-1 or A3-1
The output file should be just the 9 lines of the solved board -- just like in the file Sudoku boards. Nothing else.
For the homework server submission:
The homework slot should contain more information, though. I'd like you to run your program on all 3 of the boards in the Sudoku-boards file (A1-1, A2-1, and A3-1), and put into the Comments-to-Teacher the number of backtracks you've had for each.
Tues, March 17
...we're moving online!
We're going to try out ZOOM!
You should all have received email from me about 2 sessions on Tues (12:00-noon, and if you can't make that one: 6:00pm), with instructions and meeting IDs and passwords to try out this free online video conferencing software. If you're going to be using your smartphone instead of a computer/tablet, download the Zoom app ahead of time.
Afterwards, fill out the survey form (even if you couldn't make a session):
Monday, March 16
Schools closed until April 20
|All right, we're going to move forward. I am working on the Sudoku program tester, which will be available shortly along with (perhaps different) test code. Stay tuned to this channel...|
|Parent-Teacher conference design, due tonight (Wed 3/11) or before class.||Give me your design thoughts, in whatever form to the homework server -- Google doc, MSWord, webpage, complete running system (auto 100 grade)|
|Moore's Law||Exponential growth: There's a wonderful series of charts by Ray Kurzweil on exponential growth of a lot of things including Moore's Law. This is a blow-your-mind site. Take a look at some of the other charts on this site, for instance charts 67, 20, 50, 70, 71 -- each displays exponential growth (key indication: an approximate straight line on a logarithmic chart).|
|AI history and present, due Wed 3/11 in class||
|Python test||Here are my answers (Jupyter Colab notebook)|
|Surveillance vs. Privacy: Thurs||Read the article "NYTimes report on surveillance in China" from the link on the Syllabus above. Also choose and read another article from the same "Security / Surveillance / Privacy" section or another article from elsewhere on the same topic. Be prepare to discuss and support your side of the argument|
|Sudoku warmup, due Sun, 3/1 midnight||
Sudoku swapped elements. Intstructions are here
Here's my answer code. Here's the program-tester input data. Here are the program-tester answers.
|AI topics/news||Here's a link to The Batch -- a very good newsletter on current AI topics. A lot of information digested by that organization headed by famed AI researcher Andrew Ng.|
|Presentations will start in 2 weeks (March 9)||Post your topic at least one week in advance of your presentation. Also, first poster on a topic gets it (but there are so many, don't worry).|
|Sudoku!||Here is the format we'll be using.|
|AI Summer camp||The following has come wizzing into my mailbox: announcement of an AI summer camp here in NYC.|
|Exercise in creating classes, due Sun, 2/16, midnight||
Create a program, called MakeFriends, that can be called from
the command-line as:
$ python MakeFriends.py input-filename output-filename
which will take commands in the inputfile and write its answers to the output file.
Here are the details, some of which have changed (2/14, 12:20AM)
|Sample of a class||
Here a Stack (last-in-first-out) class
in a notebook. Download and try it out and understand it.
Here is a much more complicated list -- a singly-linked ordered list -- to show a more involved use of classes with Nodes.
|Presentations||You (solo) or y'all (duo) will be giving a full-period 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.|
|Homework: reading and writing CSV files by Tues night (2/11)||
In a Jupyter notebook, create a function called DoIt(alist=None), that either takes a list as a parameter, or if no list is available, uses sys.argv as the list for incoming arguments (sys.argv will be used when you extract this code from the notebook and run it on the command-line). The incoming arguments are:
So, when you supply a list to DoIt(), it must contain 3 elements, above.
Create an input text file for testing. The file should have any number of lines. Each line will have a sequence of string elements separated by commas. Each line will have one or more positive integers and possibly other elements. For each input line, write a line out to the output file the number of positive integers and their sum, separated by a comma. If the input line contains nothing, no output line should be written.
So, if the input file contained:
Assuming that your program is called fred.py, you should be able to call it with the 2 arguments of input and output filenames from the command line.
Testing your program on the homework server...
1) Upload your program (.py file) to the homework server slot "CSV-test".
Reading files is simple in Python -- open with
f=open(filename,'r') -- provided you can access the directory
(requires authentication in Colab), and you can navigate to it.
Here's a notebook describing the file-reading procedures in Colab: File_Reading_2.ipynb. Here's a file called afile.csv. Download the notebook and the file, and upload them into Colab. Create a notebook that reads the file and print it out.
|Monkeys and Typewriters||The real experiment. With the published result. And, of course, there's a Wikipedia article.|
|Monday, Feb. 3: Learn about... 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).|
|First homework, due Mon, 2/3 midnight||Here's a notebook talking about an old math problem, and asking you how to solve it in a variety of ways, numerically. Fill in the notebook with your answers and submit it to the homework server.|
|Python review notebooks||
Download these 2 notebooks, and load them either into your own
laptop version of Jupyter or upload them to your Google drive, and
open them there with Colab. These are reviews and review
exercises. Do them. You'll need the ideas therein.
You might was to sneak a look at how these notebooks are written internally (JSON format). Of course, I don't think they're ever written directly by humans.
|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
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 Python.org'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
Excellent Python function/method guide (for v. 2.7 but almost everything is still true in 3.x)
|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).|
|First task: fill out your Profile on the Homework server.||
|Help from Mr. Brooks||Feel free to come and see me during periods 5, 6, or 7 in room 301 (just walk in) or by appointment beforehand just after school also in room 301.|
|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|