Transforming Thoughts into Code

From BenningtonWiki

Bennington College
CS2220.01, Spring 2008
Joe Holt, Computing
M Th 4 - 6 p.m.

Contents 1 Description 2 Notes 2.1 Roster 2.2 Setup 3 Algorithmic Thinking 3.1 #1 Thursday, February 21st 3.2 #2 Monday, February 25th 3.3 #3 Thursday, February 28th 3.4 #4 Monday, March 3rd 3.5 Extra 4 Ruby Programming 4.1 #1 Thursday, March 6th 4.2 #2 Monday, March 10th 4.3 #3 Thursday, March 13th 4.4 #4 Monday, March 17th 4.5 #5 Thursday, March 20th 4.6 #6 Monday, March 24th 4.7 Extra 5 Chess 5.1 Thursday, March 27th 5.2 Monday, March 31st 5.3 #1 Thursday, April 3rd 5.4 #2 Monday, April 7th 5.5 Thursday, April 10th 5.6 #3 Monday, April 14th 5.7 #4 Thursday, April 17th 5.8 #5 Monday, April 21st 5.9 #6 Thursday, April 24th 5.10 #7 Monday, April 28th 5.11 #8 Thursday, May 1st 5.12 #9 Monday, May 5th 5.13 #10 Thursday, May 8th 5.14 #11 Monday, May 12th 6 Web Applications 6.1 #1 Thursday, May 15th 6.2 #2 Monday, May 19th 6.3 #3 Thursday, May 22th 6.4 #4 Monday, May 26th

[edit] Description

This course is about learning the programming language Ruby. In the first part of the course we’ll review algorithmic thinking and the process of defining and structuring data. We’ll follow that with an introduction to Ruby, focusing on how Ruby is a concise and elegant language for translating algorithmic thinking into machine code. We’ll study several classic programming problems and solve them in Ruby. Finally and to give the course real teeth we’ll build a dynamic and highly interactive web application using Ruby and JavaScript. There are no prerequisites for the course, but some understanding of computers and programming is expected. It is highly recommended that you also enroll in Code Critique (CS 4347.01).

[edit] Notes

[edit] Roster

Stefan M. Beeman
Zachary M. Franklin
Devin F. Gaffney
Jason A. Gallop
Reid R. Ginoza
Katherine M. Hayden
Glen Heinrich-Wallace
David P. Howard
Matthew S. Nunes
Ian B. Pearce
Emmet M. Penney
Marisa Prefer
Christopher A. Richardson
Megan E. Tong

[edit] Setup

• Laptops - ruby 1.8.6, irb prompt simplified
• text editor - Xcode
• Xcode and ruby on computer center machines?
• Account on cs0 with storage. Save work there (no svn).
• One account, folders for everyone.

• Ruby Programming Language on reserve

[edit] Algorithmic Thinking

Three or four classes spent exploring algorithmic thinking. Example algorithms from everyday life. Algorithm exercises. Using Ruby notation but not requiring accurate syntax. Ruby sketches.

Algorithm Exercises at the start of every 2nd half. Review programming assignments at the start of class.

[edit] #1 Thursday, February 21st

• First half: me, intro. Second half: student.
• Class intro, what, who, where, when.
• Dialogs. What. 14 students, 50 half-classes. Be prepared. Super-permission to ask questions, talk. Decide collectively how to pick students for dialogs. Quiz questions.
• Algorithm Exercise (at start of second half).
• "Inventing the Computer" book.
• What is an algorithm?
• Synonyms: strategy, game plan, policy, tactic, set of rules, laws, instructions, doctrine, method, formula, function, code (as in code of conduct), recipe, process, sequence, directions, procedure, description.
• Exercise: "This is how to..." A. Your choice. B. I give the process. C. Consider exceptions.
• Assignment: EW Dijkstra, A Short Introduction to the Art of Programming "Preface" and "Some Fundamental Notions" down to "The moral of this story is...". Discussion topics:
  • 1. Who was EW Dijkstra?
  • 2. What are the conceptual building blocks of an algorithm?
  • 3. Examples of algorithms drawn from everyday life.
  • 4. How do you prepare jugged hare?
  • 5. What is the difference between an eyewitness account and an algorithm?

[edit] #2 Monday, February 25th

• Discussion of assignment.
• ABCD.
• Exercise: Identify ABCD of example algorithms from everyday life.
• Algorithm Exercise.
• Data modeling. What's the data in a recipe? (Recipe with data blacked out?) Games.
• Assignment: Why's Try Ruby!, Ruby-lang's Quickstart. Do the Quickstart in Why's online Ruby window or in Terminal. Once the quickstart gets to running from a file, just read. Discussion topics:
  • 1. Ruby's versions of ABCD.
• Assignment: Sketch of an algorithm using Ruby-like syntax. Example: Bennington registration.

[edit] #3 Thursday, February 28th

• Business: laptops.
• Discussion: tag, data modeling, spending big % planning data.
• Practice identifying ABCD is various algorithms.
• Algorithm Exercise.
• Discussion of assignment. Go through tutorials?
  • Ruby's Actions.
  • Branches (this one's slightly tricky).
  • Conditionals.
  • Data. Especially the built-in ways that Ruby structures data.
• Assignment: Identify three processes from your FWT and express them as algorithms using Ruby-like syntax. Zoom in enough so that there are conditionals and loops. That is, no jugged hare algorithms.

[edit] #4 Monday, March 3rd

• Discussion of assignment: Look at several FWT algorithms closely.
• Ruby data representations. Object. "Bowl of objects".
• Simple variable: name -> object.
• Simple types: numeric, string. Methods on them.
• Assignment: Study the Ruby class library for Numeric, Integer, Float, String, Array. Discussion topics: 1. Impressions. 2. Do the actions for the classes make sense? 3. Confusion? Elation?

Things we didn't get to

• Discussion of assignment: Bennington Registration on board.
• Collections: class, array, hash.

[edit] Extra

Criticizing algorithms: Correctness, Size, Speed. Example on the board.

[edit] Ruby Programming

An exercise, time to code, checking results. Pairing up as well as individually.

Once programming level becomes sufficient, the assignments become programming exercises. Continuations of algorithm exercises or programming new topics.

Code reviews. Each is assigned another's work to review between classes. Look at code on the server, make comments in the code and save.

• ruby-debug.

[edit] #1 Thursday, March 6th

• Introduction to cs0. Accessing the file server. Logging in via ssh.
• irb. Ruby#Some_Basic_Ruby.
• Discussion of assignment. Trying them out in irb.
  • http://www.rubycentral.com/pickaxe/ref_c_numeric.html
  • http://www.rubycentral.com/pickaxe/ref_c_fixnum.html
  • http://www.rubycentral.com/pickaxe/ref_c_integer.html
  • http://www.rubycentral.com/pickaxe/ref_c_float.html
  • http://www.rubycentral.com/pickaxe/ref_c_string.html
• Algorithm Exercise.
• Arrays.
• Assignment 1: Read and do this: Command Line. Do the examples on your own Mac or log in to cs0 from a Mac or PC. There are no great surprises here, just a simple introduction to command lines. It will be useful when we begin storing and running ruby programs on cs0. Be prepared to discuss what you've learned.
• Assignment 2: Read and do this: Why's Poignant Guide. It'll make you laugh, it'll make you cry. Work through as much as you like. I tend to get bored once the elves start putting stars on the monkey faces.
• Assignment 3: The challenge. Come up with an interesting Ruby one-liner in irb. Be prepared to share it.
• Also: Programming Ruby (including class reference).

[edit] #2 Monday, March 10th

• Prep: Ruby Cheatsheet, laptops in Dickinson.
• Discussion of assignment. One-liners. [took 90 min]
• Discussion: Command lines.
• No assignment.

[edit] #3 Thursday, March 13th

• Review.
  • What is an algorithm? What is a programming language? What does that make a computer?
  • Matz quote.
  • Ruby actions, branches, conditionals, data.
  • Reference materials. Class references.
• Windows putty problems?
• Biz: registration algorithms.
• Using cs0 as a file server.
• Running Ruby programs from the command line.
• Programming exercises. Computing Interview Questions.
• Algorithm Exercise. Have everyone spend some time looking over the list, and then pick one as a class to discuss.
• Assignment: Eight Ruby programs, saved to server. Reviewed by another student.

[edit] #4 Monday, March 17th

• Discussion of assignment.
• More programming exercises.
• Algorithm Exercise.
• Assignment: Five Ruby programs, saved to server. Reviewed by another student.

[edit] #5 Thursday, March 20th

• Biz: no class on the 27th.
• Discussion of assignment. This time, break the class into six 20 min segments.
• In-class programming exercises.
• Algorithm Exercise.
• Assignment: Two Ruby programs, saved to server. Reviewed by another student (pick new pairs).

[edit] #6 Monday, March 24th

• Biz: no class on the 27th.
• http://letsmakerobots.com/node/112
• Chess: Who plays it?
  • Pres on the history of chess. - Chris Richardson
  • Pres on the machine and computer chess. - Reid
  • Pres on chess rules and strategies. - Glen
  • 8 chess boards. - Marisa
• http://projecteuler.net/index.php?section=about
• Discussion of assignment.
• In-class programming exercises.
• Algorithm Exercise.
• Assignment: Presentations.

[edit] Extra

• Encoding exercise. The medium and the message. Two decks of cards, one with a medium and one with a message. For example, the medium might be a piece of string. The message might be a song. The more oblique the better. Other media: a wheel, a bird, water, a dead phone, a 1mm square piece of paper, a quartz crystal, a single number, a deck of playing cards. More message types: text, audio, a quantity, a binary state (up/down, etc.). Messages: a love letter, a famous speech, a year, a price, music transcription, an rsvp.

[edit] Chess

Object-oriented programming through the implementation of a chess-playing program.

• Piece moves. Generating array.
• Representing the board. Chessboard class; initializing it; displaying it.
• Evaluator.

• Artificial Intelligence and Game Playing
• Minimax
• Media:First Steps in Computer Chess Programing.pdf
• Programming a Computer for Playing Chess, Claude Shannon, 1950

[edit] Thursday, March 27th

No class.

[edit] Monday, March 31st

No class.

[edit] #1 Thursday, April 3rd

• Presentations.
• Playing rounds of chess.
• Algorithm Exercise.
• Sketches of modeling chess, chess algorithms.
• Assignment: 1 queen problem. Program asks for queen's location as x, y. Program then asks for a location and tells you whether the queen is occupying that spot. Program then prints out the queen's location.
• Assignment: Sargon article. Discussion topics: 1. Representing pieces. 2. Representing the board. 3. Representing game state. 4. Generating legal moves.

[edit] #2 Monday, April 7th

• Review assignment: 1 queen problem.
• Review: Sargon article.
• Reid presentation.
• Algorithm Exercise.
• Representing pieces. Attributes. Subclassing. The "class" class. Ruby Objects
• Reading assignment: Chap 21.

[edit] Thursday, April 10th

No class, long weekend.

[edit] #3 Monday, April 14th

• SEPC meeting.
• Review: cs0 from terminal, web, file sharing.
• Review: Assignments due to date. 8 + 5 + 2. Should be *.rb, runnable from Terminal on cs0.
• Review reading: Chap 21.
• Representation of the board. Just putting strings in there for now. But eventually Piece objects.
• Algorithm Exercise.
• Assignment: http://www.computerhistory.org/chess/
• Assignment: Create a board. Print it out. Input a piece. Print out the board again. Repeat.

          ......      ......      ......      ......      
8     Rb  ..Nb..  Bb  ..Qb..  Kb  ..Bb..  Nb  ..Rb..      
          ......      ......      ......      ......      
    ......      ......      ......      ......      
7   ..Pb..  Pb  ..Pb..  Pb  ..Pb..  Pb  ..Pb..  Pb  
    ......      ......      ......      ......      
          ......      ......      ......      ......      
6         ......      ......      ......      ......      
          ......      ......      ......      ......      
    ......      ......      ......      ......      
5   ......      ......      ......      ......      
    ......      ......      ......      ......      
          ......      ......      ......      ......      
4         ......      ......      ......      ......      
          ......      ......      ......      ......      
    ......      ......      ......      ......      
3   ......      ......      ......      ......      
    ......      ......      ......      ......      
          ......      ......      ......      ......      
2     Pw  ..Pw..  Pw  ..Pw..  Pw  ..Pw..  Pw  ..Pw..      
          ......      ......      ......      ......      
    ......      ......      ......      ......      
1   ..Rw..  Nw  ..Bw..  Qw  ..Kw..  Bw  ..Nw..  Rw  
    ......      ......      ......      ......      

      A     B     C     D     E     F     G     H

[edit] #4 Thursday, April 17th

• Review computerhistory.org.
• Review chessboard.rb. Questions first.
• Review chap 21.
• Algorithm Exercise.
• Assignment: Add pieces to the chessboard. Just use strings for now ("Pb", etc.).
• Assignment: Generating moves. Print a list of all the possible moves of a queen placed anywhere on the board.

[edit] #5 Monday, April 21st

• MVC talk.
• Review assignment: pieces on the board.
• Review assignment: queen moves.
• Algorithm Exercise.
• Review Ruby objects: attributes and behavior. Variables and Methods.
• More "class" stuff. Instance variables.
• Algorithm Exercise.
• Representation of pieces.
• Piece variables and methods. :symbol, :value, :board, :color, :file, :rank. all_moves()
• Assignment: Material advantage. Total all the pieces on the board, print out the total for each side.

[edit] #6 Thursday, April 24th

• Algorithm Exercise.

[edit] #7 Monday, April 28th

• Algorithm Exercise.

[edit] #8 Thursday, May 1st

• Review game, board, pieces.
• Algorithm Exercise.
• Assignment: continue working on game, board, pieces.

[edit] #9 Monday, May 5th

Pieces

1. Can you create one of every kind of piece?
2. Can you create more than one of each?
3. Can you set a piece’s position? Determine its position?
4. Can a piece tell you its value?
5. Can a piece tell you its color?
6. Can a piece tell what board it’s on?
7. Can a piece generate its legal moves? Including captures?
8. Can the King determine if it’s in check?

Board

1. Can you create a board?
2. Can the board display itself?
3. Can you place pieces on the board?
4. Can you total the material value of each side?
5. Can you move a piece?
6. Can you remove a piece?
7. Can the board determine which piece is at a square?
8. Can the board determine if a square is being attacked?

Game

1. Can you create a game?
2. Can the game display a board with pieces in their starting positions?
3. Can the game generate all the legal moves for a side?
4. Can the game rate the moves?
5. Can the game pick the best move for a side?
6. Can the game ask you for move input?
7. Can the game alternate turns?
8. Can the game tell if the game is over?

[edit] #10 Thursday, May 8th

• Continue work on game, board, pieces.
• "UI"
  • ruby chess.rb, on cs0
  • player is always white
  • display board
  • "Your move?" ex. d2-d4
  • loop until game over

[edit] #11 Monday, May 12th

• Chess games.

[edit] Web Applications

Transforming the command-line chess program into a web application. Simple cgi interface. POST with game number, command.

Chess tournaments, debugging, optimization, individual improvements, review.

• Set up Apache to serve out of user directories in class directory.

"Hello Bennington" from a server-side ruby app. Seattle, Rvík?

[edit] #1 Thursday, May 15th

• Algorithm Exercise.

[edit] #2 Monday, May 19th

• Algorithm Exercise.

[edit] #3 Thursday, May 22th

• Algorithm Exercise.

[edit] #4 Monday, May 26th

• Algorithm Exercise.