Objectives

• To develop algorithm animations using Python and browser technologies. The point is to look over some algorithms and to implement them in Python. The implementation is mostly about developing a visual expression that helps to understand the algorithm.
• To learn the fundamental mathematical techniques of algorithm analysis. These include the big-Oh notation, recursion equations, and inductive analysis of programs.
• Course curriculum will also include:
  • Python
  • Google App Engine
  • Javascript, AJAX and Prototype
  • DHTML and CSS

Announcements

• The textbook will be draft version of Vazirani's Algorithms book.
• For Pyton, refer to the official Python reference, including the Tutorial.
• For Prototype, refer to the official Prototype reference.
• For Google App Engine, refoer to the tutorial and the API documentation accessed by the left sidebarlinks.
• This course will bring together the algorithms curriculum of CSC 517 with the web app development curriculum of CSC 598.073. See those sites for additional background and resources.

Algorithm animations

I have done some algorithm animation using Javascript for my CSC 517 algorithms course. For example:

• Cheaper by halves
• Loop invariants for findmin
• Partition
• Counting sort
• Hashing, linear probing

For additional inspiration, see the fantastic example of Doug Ierardi's tree algorithm animations.

I am happy with the use of Javascript and DHTML to achieve these animations. For the purposes of this course, however, we will try to implement animations using a web-app architecture, using Python of Google App Engine as the backend, and some minimal Javascript glue on the front end (the browser). I am looking at Raphael as the graphics package for Javascript.

Class notes

• Overview
• Python and Big-Oh
• Scheme lists, scheme-like programming
• divide and conquer and recursion equations

Assignments

• Week 1
  • Math assignments
    1. Read the prologue of Vazirani's book.
    2. Read my notes on big Oh notation.
    3. Do all exercises in Vazirani's prologue. (some answers)
  • Python Assignments
    1. Read the Python tutorial chapters 1 through 6 for now.
    2. Setup IDLE (python -m idlelib.idle)
    3. Write the fibonacci function in Python. Try a few different ways:
       • with an exponential run-time;
       • with a polynomial run-time;
       • using generators.
       • (some answers)
    4. In python, experiment with the binomial coefficients.
       • Use list comprehensions to create row i of pascal's triangle from row i-1.
       • Make an ascii art mod 2 pascal's triangle.
    5. Read lectures 1 through 4 from Spike's notes.
  • Visualization/GAE Assignments
    1. Prepare to use Google App Engine by setting up an account and downloading the SDK.
    2. Follow the app engine tutorial.
• Week 2
  • Math assignments
    1. Read chapter two of Vazirani's book, about Divide and Conquer algorithms (not FFT)
    2. Do problems 2.1 through 2.5.
    3. Look over problems 2.12 through 2.24.
  • Python Assignments
    1. From the Python Language Reference read Chapter 3, Data Model and Chapter 4, Execution Model.
    2. Read lectures 5 through 7 from Spike's notes.
    3. Implement Randomized Selection in Python using Spike's SchemeLists and the map and/or fold functions. (randsel-answer.py)
  • Visualization/GAE Assignments
    1. Have a look at some javascript code.
• Week 3
  • Math assignments
    1. Review the proofs of big-Oh problems.
    2. Look at the proofs of some 2.5 exercises
    3. Do problems 2.14 through 2.17.
  • Python Assignments
    1. Reimplement our selection algorithm, using the "in-place" technique you discovered for problem 2.15.
    2. Implement hashing, with chaining, and with linear probing.
  • Visualization/GAE Assignments
    1. Add numbers GAE application.
    2. Hit counter GAE application.
• Week 4
  • Math assignments
    1. TBA
  • Python Assignments
    1. Finish selection and quicksort using cons lists (answers)
  • Visualization/GAE Assignments
    1. TBA

References

• HTML 4.01 Specification
• CSS 2.1 Specification
• PHP Tutorial and Reference Manual
• Python documentation, including a tutorial.
• MySQL Reference Manual
• JavaScript reference
• Standrd ECMA-262: ECMAScript Language Specification 3ird edition.
• Document Object Model in Mozilla
• AJAX documentation.
• RFC 2616: Hypertext Transfer Protocol -- HTTP/1.1
• RFC 2396: Uniform Resource Identifiers (URI): Generic Syntax
• RFC 2109: HTTP State management. I.e. Cookies! (See also RFC 2965.)
• RFC 1034: DNS.
• Jemima Pereira's 4096 Color Wheel
• More Crayon's color cube, based on the RGB square.
• The 216 web colors arranged by VisiBone.
• Signal vs. Noise
• John Maeda
• Position is Everything: Modern browser bugs explained.
• A List Apart: the art and industry of web sites.
• REST: Representational State Transfer.
• A relation model of data for large shared data banks, E. F. Codd. Comm ACM 13(6) June 1970. pp 377-387.
• The Third Manifesto by Darwen and Date. About relational databases.
• Introduction to Data Modeling with the relational model explained.
• Dos and Don'ts of Client Authentication on the Web by K. Fu, E. Sit, K. Smith and N. Feamster.
• The Failure of Client Authentication the Web by Kevin Fu.
• Defeating Script Injection Attacks with Bowser-Enforced Embedded Policies, T. Jim, N. Swamy and M. Hicks, WWW 2007, 2007.
• CAS: the central authentication system.
• A Guide to Web Authentication Alternatives, Jan Wolter
• Introducing SSL and Certificates using SSLeay by Frederick Hirsch.
• OpenSSL Command-Line HOWTO
• PCI Security Standards Council
• Rules for Visa Merchants
• Dojo: JavaScript Toolkit
• Prototype: a JavaScript Framework
• Entity relationships in GAE