• Syllabus Project 0 and iClicker policy detailed here
• Scribbled notes: Course purpose and goals, how to make programs, how 310 should change your mind, Project 0: submit Hello World or equivalent program to Blackboard by Monday, Jan. 23, 12:00 Noon, Sketch of Project 1 due in 3 weeks began details demonstration of beginning Project 1
• At UAlbany, there will be an INSTANCE of the Jan 27-29 Global Game Jam. There will be MANY OTHER INSTANCES of the Game Jam at places all over the world.

• Info and access code for CodeMate: Get from Blackboard
• Misconceptions: Review to study for the readiness exam!

Get the java-sources for GE Data Structures, to replace your copy of book-classes from 201

Make sure you can run DrJava with the Data Structures version Picture class in Lab

Make sure you can copy, compile, and demontrate the OneCollageMaker program.

Begin to develop it into the TwoCollageMaker application; finish and submit on Blackboard by Sun. night.

• barbara.jpg
• caterpillar.jpg

Tip: Use tiny images like the above two so that your answer Picture is small enough to fit entirely in your computer screen.

• C02 Notes: From C01 with more added:
  • Understand what the problem is FIRST
  • Break big problems into steps..lecture shows several lists of steps.
  • Centered, bordered collage from 4 images project described briefly, number of Picture objects that must be made.
  • Two kinds of variables involved.
  • Breaking project problem into steps; simplifying some steps to begin.

• Info and access code for CodeMate: Get from Blackboard
• Misconceptions: Review to study for the readiness exam!

• Prerequisite preparation assessment quiz.
• Incremental development demonstrated resulting in OneCollageMaker.java
  • Code to declare 2 Picture REFERENCE variables
  • Why CamelCase is a word about camels (with one or two humps)
  • Code to instantiate (that is MAKE) 2 Picture objects.
  • Discussion of what the computer is doing at particular spots in the code; including
    • An inadvertant RACE condition, resulting in a messed-up image.
    • being BLOCKED (in the FileChooser.pickAFile methoc) waiting for the Prof. to click "OK"
• Lessons Learned(not shown in lecture)..
• Mad PhD video started when lecture ended.
• At UAlbany, there will be an INSTANCE of the Jan 27-29 Global Game Jam. There will be MANY OTHER INSTANCES of the Game Jam at places all over the world.

• Misconceptions: What various people missed demonstrating on the readiness exam!
• Version of OneCollageMaker.java existing at the time the lecture ended.
• Directory of lively coded lecture demos (Under Constr).
• Mad PhD video

• Demonstrate in lab code to (1) instantiate many House objects and (2) refer to same and different House objects with the same and different House REFERENCE or POINTER variables.
• Practice the principles communicated in the MadPhD video.
• After lab, find them on your S: drive or ssh access to itsunix.albany.edu and upload a complete Java program to Blackboard for grading and credit.

• Lab 02 Assignment
• Lab 02 In-Lab Grading sheet.

• Clicker quiz on how to put a class def. or blueprint into the computer.
• MadPhD makes objects video: Class definitions are expressed by .java files.
• Programming Project 1: FourCollageMaker w/ 2 horiz. flips and 1 vertical flip, centered nicely; FINAL SPEC DUE Feb 7 (8 days from Jan 31)
• Solved problem: calculating the TwoCollage
• Sample problem: How do you position two touching rectangular images so they form a nice looking left-to-right staircase? How do you do it by making the amount of overlap be 1/3 the width of one of them? Now, which one?

• One.jpg
• Two.jpg
• Three.jpg
• Four.jpg

• Lecture on linking Houses to Houses

• Lab 03 (Burglary Lab!) Assignment: Instructions in a new House.java file
• Data Structure Diagram
• Lab 03 attendance and process conformance report sheets.

• Project 2 and 3 and 4 will be assigned.
• Design & Data Structure Requirements
• Project 2 Data Structure & actions for setting up the data structure design (scanned sketch).

Lect06 Live coding directory used in lecture.

Resources for Proj 2, 3 and 4
Arrays

• G&E Chap. 5
• Supplement Chapter for reviewing/properly understanding ARRAYS and introducing the ArrayList idea.

Programming Project 1 DUE Wed, Feb. 8

• Clicker Quiz: If you got A (the wrong asnwer), RUN THIS PROGRAM!!
• Tutoring available LI-84

  Weds 11:00AM-3:00PM

  Fri 10:30AM-1:30PM

  Tutor has a CodeMate account

  More coodination w/310 TBA.

• Continued talk through of Project 02 data structure plan and incremental coding. Images:
  • From previous lecture.
  • Today, showing proj 2 data structure with executed steps to build it.
  • (.pdf version)

• REQUIREMENTS CHANGE: MUST show the new collage after each change!!! Testability counts.
• Clicker warmup quiz.
• Projects 2, 3, 4 Programming Notes
• Array Collage: Finish Adding at End;

  Traverse: Simplistic picture placement solution,

• Linked-List Collage: Add at end;

  Traverse: Simlistic picture placement solution.

• Project 2 (Array)
  1. LineCollageMaker.java
  2. LinearCollage.java
  3. Version History
• Project 3 (Linked List)
  1. LinearCollage.java
  2. LineCollageMaker.java

• Lab 04: Circularly Linked List, TEAM-LAB Assignment
• cardGame.java file to start with

• Projects 2, 3, 4 Programming Notes

1. Scribbles about the array solution
   • Array1
   • Array2
   • Array3
2. Scribbles about the linked list solution
   • Linked List Walk (from G&E)
   • Linked List Node Removal (scribbled)
   • Walk up to preceeding node before removing the current node (from G&E)

1. Warmup Quiz
2. Prototype for Project 05--download and RUN from a command line: java -jar Proj5Proto.jar
3. Project 05 Assignment: Due March 3.
4. Making a cursor move back is easier with a Doubly linked list. with cursor.
5. Buggy list adding code quiz REDONE.
6. Walk up to preceeding node before removing the current node (from G&E not done)
7. Deleting a Node requires a finger to point to the Node before it (not shown)

Quiz:

1. Quiz-question
2. class Dnode definition needed for the quiz

• Buggy Linked List add-to-end code quiz
  • Answer Page 1
  • Answer Page 2
• Curse of the Cursor (for Project 5)
• Procrastinator's To-Do List, intro to stacks
  1. procrastinationProgram.java
  2. itemNode.java
  3. procrastinatorsToDoList.java
• Midterm Review
  1. DLL Plan Quiz.
  2. Midterm Sample Questions

Call tree scribbled for Cat in Hat Comes Back Part I.

code in ClickerSortingApplication.java and ClickerSortingEngine.java

• Examples of operations + and assign.
• Example of precedence rules re = versus ==
• The CALL operation introduced
• What CALL means.
• The RETURN operation and what it means.
• Questions answered about the return statement
• Example of early return, where writing return is necessary.

Calls and Returns in SortingApplication analyzed with a call tree, also expression tree example and exceptional control flow

Selection Sort needed for current Lab 08

Lab 08: Part Two of the Unix Lab: Replace Collections sort with your own Selection Sort code, and repeat timing.

Patches to make it work!!

Selection Sort explanation:

1. Javi API Comparable
2. First Swap
3. Second swap, subsequent no-swap.

   Selection Sort explantion and clicker questions

   ---

Activation History tree for the Procrastination Program, including the recursive palendrome printer:

1. procrastinationProgram.java
2. procrastinatorsToDoList.java
3. itemNode.java

Lecture notes.

Search for homo sapiens in NIH Taxonomy Tree Browser

The sorting project framework SW:

1. Engine
2. Program

Maybe ArrayList data structure (extensible array).

Official Java Language Spec on "access control"

Code of the methods whose calls/returns were diagrammed.

Recursive view of palendrome making

How MERGESORT works: Steps 1 and 2

Step 3: non-recursive MERGE (different from MERGESORT)

Next class: The whole activation history for using MERGESORT to sort 8 numbers.

Ways to trace and understand recursion:

1. Activation (call/return) history tree

   Tree for MERGESORTing 8 items.

2. Stack of activation records (you have to erase or redraw after some return operations) WILL DO.
3. Mathematical induction or "faith" (you have to obtain solutions to the recursively solved subproblems some other way, but it's good for design and for proving correctness. (EXPLAINED ORALLY--will provide notes)
   • MERGESORT method sketch
   • MERGESORT on an odd number of items (3)
   • index wrangling to implement MERGE
   • THE MERGE STEP--you MUST merge into a scratch array and then copy the sorted list back to the original.
   • Merging within the one, single original array doesn't work; here is an example of the trouble with that idea.

Prepared slides on recursion, MERGESORT, Trees, etc.

Situation of the length 1 subarray

Ways 1 and 2 of indexing subarrays

• Way1
• Way2

SearchEngine.java (Binary Search case study)

• Java Program
• Solutions 123
• Solution 4

MERGESORT method, make it return immediately after the three steps.

The Cat in the Hat Comes Back recursively.

Recursive code for printing a palendrome analyzed 3 ways: History tree, activation record stack, induction based on the recursive structure of a palendrome.

Binary search tree intro.

Prepared slides on recursion, MERGESORT, Trees, etc.

introducing the expression tree and use of stack in evaluating an expression.

The Java ArrayList and its generic partially-filled dynamically-extendable array.

Intro to readings 10.3-10.4

Paper by Chomsky

Search for homo sapiens in NIH Taxonomy Tree Browser

Binary Search Tree definition

How the stack tracks evaluating an expression recursively.

• Evaluation Algorithm
• Animation (multipage .pdf document)
• Movie (.wmv)(no sound yet!)
• NEW! Movie with sound(low resolution)!
• NEW! Movie with sound(High Resolution)!

• Java Program
• Solutions 123
• Solution 4
• Images

Matcher.java download

• Project 07 clue
• Use of memory by setup()

iClicker survey and Kinds of Tree Traversal

Post-Order traversal corresponds to evaluating an expression expressed by an expression tree with using a stack for storing intermediate results

Inorder drawn vertically.

Prefix and Postfix notation.

Evaluation of postfix expression using a stack.

Making a compiler One.

Towers of Hanoii.

• Java Program
• Solutions 123
• Solution 4
• Images

Pattern Matching Lab tips

ArrayList

Why mergesort is fast (again?).

Postscript Language Specification

Last Project Assigned Due May 5

• Exploring a cave with (1) safety line and (2) candle to mark where you've been.
• Links to safety in a linked list.

Maze Lectures

• Beginning to trace the printSolution recursive activations.

1. Kitware Flyer 1    Kitware Flyer 2      Wed., May 2 CCI-Women In Tech Meeting 4:00PM
2. Doubly-Linked Lists and Extendable Partially Filled Arrays COMPARED
   1. Doubly-Linked Lists in Linux Kernel (struct list_head)

      Actual kernel code defining the list_head type

   2. Sketch of how list_heads are used.
   3. Table
   4. Algorithm for adding an item to an extendable array: the code under if is executed ONLY when there is no more room.
   5. Analysis of total time to add N items when the array is extended by one element each time (get O(N^2))
   6. The doubling strategy
   7. Analysis of total time to add N items when the array is extended by being doubled in size when it must be extended (get O(N), just like linked list).
   8. Table (now note information in the lower left corner.)

Arrays vs ArrayLists (or extendable-partially-filled arrays)

Copying of old items is done sometimes (not always)

Tracing maze search with activation record stack.

Please use the Blackboard discussion board for questions and answers of review, and email sdc to alert me to respond.