Simple Home Page for Spring 2006 session taught by Prof. S.
Chaiken
What's New and Still Relevant
- The CS Teaching
resources from Stanford include fine materials on linked
lists and trees.
- Advice on Proj4 in response to
some student questions.
- Project 4: Revised Due Dates. Responding to requests from several students, and
my realization that the non-break period originally allotted for project 4 is a bit too
short, here is the new policy for Project 4:
- Early-bird bonus period: Submissions received between 11:59PM Apr 19 and
11:59 Apr 21 will receive a 10% "early bird bonus". So the deadline for
at least full credit is the end of Friday, Apr 21.
- Late turnin period: Submissions received between 11:59AM Apr 21 and 11:59 Apr
26 will be have their score reduced by 10% per 24 hour day, calculated almost
continuously.
My expectations are that students will get the Albany (parenthesis matching)
version of the 2-stacks algorithm as outlined in the textbook working before
Spring break begins. Then, enough time is available after the break to
complete and debug the feature that tracks index ranges of subexpressions;
and to complete part2 which builds and traverses the expression tree.
The topics of various kinds of search, additional applications of trees, and
queue based simulations will begin right after the break.
The final deadline of Apr. 26 is designed to leave enough time for the
project 5 which is on maze searching.
Handouts including Syllabus, Instructions and Assignments
Lectures
-
Lecture
01 (1/24)(.pdf)
Reading: Chapters 1, 2 and 3; especially details in 3 for the first
project.
Themes:
- Detailed understanding of a first example program:
- #include <iostream> means during compiling, copy the file named iostream from a
a system wide master copy into a temporary file in place of the #include statement, append
the rest of the original program file, and compile the whole thing.
- You will write your own header files and "#include" them throughout this course.
- Remark about what "virtual" (as in virtual memory) means: An entity that
is usable in the same way as a "real"
entity, with the same behavior and capabilities, but which is implemented in a different
way. The C++ standard allows included files to be precompiled AS LONG AS the effect
is identical to copying the file whenever the #include statement is processed.
- using namespace std; Namespaces were added to C++ to solve the crisis of conflicting
names in large or legacy software. This statement makes the compiler look for the
fully qualified name std::abc when it finds an unrecognized name like abc.
- int main( ) { ... } is ONE WHOLE STATEMENT
- it defines main as the name of a function and makes that name designate the
body of code in the sub-statement after the ().
- main is a special purpose function name for the function at which C/C++ program execution
begins (except for global constructors). There is a similar reserved method name in Java.
- const int Asize = 10; makes Asize be an abbreviation for the integer 10. The const means
the program will not change the value signified by Asize from the original value of 10.
- int ninput = 0; causes a variable named ninput to be declared and defined. A data storage box
with name ninput will be allocated and the data value in it will be initialized to 0
- while( ninput < Asize && cin >> A[ninput] ) { ninput++; } was reviewed.
Details of short circuit evaluation of logic expressions were explained..Flowchart TBA
- Single
variables and arrays are our first two data structures. Obvious
advantages of an array over separately named variables.
- Key subject ideas: Pointers (i.e., Java references) and Recursion
- Pointer/reference data is data that refers to OTHER DATA, not data like
a birthday or count that pertains to the application.
- Very complicated structures of data records pointing to other data records
occur in computers...this subject is about them!
- What is a recursive function? A function whose body either directly or
indirectly calls the function with same name.
- Recursive definition to a tree. Nodes could be hosts or switches on a network
and arcs would be the CAT 5 cables joining pairs of nodes.
- The 30 year lesson of Object Oriented Programming: Data is more
important than executable code.
- The concept of a variable, virtually the same as an object, is crucial
Lecture
02 (1/26)(.pdf)
Reading: Chapters 1, 2 and 3; especially details in 3 for the first
project.
Themes:
- Introduction to Invariants, pre- and post- conditions...required style for
CSI310 program documentation.
- Detailed Flowcharting of a for() statement and short-circuited evaluation
of a boolean expression.
- What assert() is for.
- Variables, difference between the variable itself and its value
- Copying of data from one variable to another; assignment statements; an assignment
statement is different from a mathematics equation.
- Objects are basically the same as variables, but...
- Object Oriented Programming BASIC IDEA: An objects have BOTH state (i.e., value as
a variable) and Behavior
- Definition and use of the Point class illustrated.
- Defining and invoking METHODS
- Each object has a unique identity
Lecture
03 (1/31)(.pdf)
Reading: Chapters 1, 2 and 3; especially details in 3 for the first
project.
Themes:
- Arrays: variable composed of subvariables called elements.
- Critical issues: Use of an index that may vary; need to know where the
ends of the array are.
- All elements in one array have a common type.
- Contiguous locations.
- Selection for access by index value
- Elements can have struct/class type.
- Some applications: Multiple instances of application concept objects like
piles of coins, fixed application data like denomination for each pile of
coin, mathematical vectors, statistics or price tables, character strings.
- Project 1 will be about managing
and disbursing money of US coin denominations.
- Writing pseudocode to defer some coding work: Various reasons including the
fact that you cannot test data-gathering code unless code to reliably print
the gathered data is available.
- Arrays of characters
- Always fully used compared to partially filled arrays. For partially
filled arrays, one must be able to determine where the end is.
- Use of end marker like the NULL char compared to a count of used elements.
- C-strings: what they are, use of cstring library functions.
- Character constants: Letter in single quotes 'A' or '\0' for NULL.
- Command recognizer pattern for CSI310 projects, cin.getline().
- Vulnerability caused by C-strings, tradeoffs in the choice of C-strings.
- Selection sort manipulates and compares chars as numbers.
Lecture
04 UNDER CONSTR.. (2/2)(.pdf)
Reading: Chapters 1, 2 and 3; especially details in 3 for the first
project.
Themes:
Lecture
05 (2/7)(.pdf)
Reading: Project 1/Lab 3 Assignment
Chapters 1, 2 and 3; especially details in 3 for the first
project.
Themes:
- What's an Abstract Data Type? Separation of Concerns (in SW Engineering)
- Combine different ADTs with different implementation data structures
- A container class that USES a concrete class
- Header files and their inclusion with #include
- Representation invariants
- Getting an algorithm correct with invariants.
- Differences between 2 parts of Proj. 1: Building a class vs. Building an application
- Reference (vs value) parameters (in C++)
- Const parameters (in C++)
Lecture
06 (2/11)(.pdf)
Reading: Project 1/Lab 3 Assignment
Chapters 1, 2 and 3; especially details in 3 for the first
project.
Homework due 2/14..code tracing(.pdf)
Themes:
- Project management.
- Data referring to data instead of real things, URL and end-index examples.
- Arrays, permutations, and cycle computation.
- Permutations as (1) binary relations and (2) functions on ints 1..n; viewing
these as graphs, viewing cycles in a graph.
- Instance function/methods always called ON or FOR an object (instance or varible)
- Distinctions among variables, values, and variable names.
- Glimpse at memories, addresses, address refers to a variable, and another
variable contains an memory address.
Lecture
07 (2/14)(.pdf)
Reading: Chapter 4.
Piles Uninitialized(.pdf)
Piles Initialized(.pdf)
Themes:
Lecture
08 (2/16)(.pdf)
Reading: Chapter 4.
Piles Uninitialized(.pdf)
Piles Initialized(.pdf)
Themes:
- Preview of Project 2 (.pdf) Due March 13-15
- Overloading of operators: What are the arguments and their types.
What happens when overloaded << for output is invoked.
Reference parameters, arguments and return value.
- Objects (variables), values, name, storing names in variables.
- Assignment changes values.
- Pointer value is a memory address of a varible.
- Multibyte sizes of variables.
- Memory Pictures.
- Binary number system, Hex system and notation
- Reason for digital electronics today: Logic Restoration.
- Glimpse at virtual addresses, memory managment, paging/page faults,
and caches.
- DDD visualizations of one Coin, array of Coins, Pile containing
an array of Coins, the array of 6 Piles used in teller.
- Limitations of static sized data strutures.
- A dynamic sized Pile class.
Lecture
09 (2/28)(.pdf)
Reading: Chapter 4 and 5,
Project 2 Finalized(.pdf) Due March 13-15,
Sample program to support command line processing for Proj 2:
command_study.cxx.txt
Training exercise 2.
Themes:
- Dynamic versus static.
- Linked Data Structures.
- Data Structure variants and their diagrams surveyed.
- Limitations of static size.
- Dynamic Partially Filled array---separate structure for
pointer and sizes from the dynamically allocated array.
- (1)Getting pointer values, (2) Declaring pointer variables,
(3) Dereferencing pointer variables.
- Simple code examples involving pointers and the corresponding
data structure diagrams and values of printed under C++
Lecture
10 (3/2)(.pdf)
Reading: Chapter 4 and 5,
Project 2 Finalized(.pdf) Due March 13-15,
Sample program to support command line processing for Proj 2:
command_study.cxx.txt
Training exercise 2.
Themes:
- Project 2 support details..also see
planning, problems, pseudo-code...See last 4 slides.
- C-strings are not "First Class Objects". Java and C++ STL
strings, and the dynamic string class of DSO Ch.4 do provide
first class string objects (with proper copying, resizing or
bounds checking, etc.)
- Accessing C-strings with char pointer variables.
- Structures that contain pointers
- Dynamic C-strings, allocation, copying from a fixed buffer.
- Dynamic node allocation and making the node point to a C-string
- C++ pointer usage and its pecularities
- (1)Getting pointer values, (2) Declaring pointer variables,
(3) Dereferencing pointer variables.
- Simple code examples involving pointers and the corresponding
data structure diagrams and values of printed under C++
- Failures: (1) Dereferencing the NULL pointer value (2) Coding
& of a non-lvalue, i.e, expression that does not denote a variable
The slides for the next lecture or 2 are useful for project 2:
Lecture
11 (3/7)(.pdf)
Reading: Chapter 4 and 5,
Project 2 Finalized(.pdf) Due March 13-15,
SURPRISE QUIZ--Due in next lecture, March 9(.pdf)
Training Exercise 3---Using emacs features to support
Building and Debugging(.pdf)
Themes:
- Project 2 Planning
- Some details about command and line input compared
- Objects and pointer in C++ and Java compared.
- Linked List Programming Details (begun)...how to solve problems in
such programming
Lecture
12 (3/9)(.pdf)
Reading: Chapter 4 and 5,
Project 2 Finalized(.pdf) Due March 13-15,
SURPRISE QUIZ--Due in next lecture, March 9(.pdf)
Training Exercise 3---Using emacs features to support
Building and Debugging(.pdf)
Themes:
- Dynamic objects reviewed.
- Array and linked list COMPARED; both are data structures that implement
a sequence. What operations are slower for arrays than for linked lists, and
what operations are faster for arrays than for linked lists. Introduction
to "asymptotic comparisons" Time equal to constant compare to time equal to
the number of elements copied times a constant.
- Local extent (automatic) variables/objects introducted and
compared with dynamic variables/objects. When local extent variables
are allocated and when they are deallocated (entry and exit from function
activations or blocks of statements.) Non-reference function parameters
and (non-static) variables declared inside a function body or block are
local extent. Discussion of variable declared within for( ... ).
- OOP and Classical C style compared..Advantages and disadvantages of
constructors and access functions compared with using direct access to
public data members
- A case for using a dynamically allocated thing without the pointer variable:
(new Thing)->doIt(); (This is a pattern for some Java library objects but probably
won't be used in CSI310. One would code the constructor or Thing::doIt() to
save the pointer value by copying it from the "this" variable.
-
Suggested simplified structure for the editorCore class, so it
USES a completely public struct/class for nodes. Programming the
insert-at-the-front method for this.
- Please study programming examples by dissecting or reverse engineering
them...don't just read or copy. Tried to diagram the action of each
statement on a dirty white board.
Lecture 13 (3/14)
Reading: Finish Ch. 4 and 5;
Midterm March 16 syllabus, Review lecture slides.
Themes:
- Linked structure visualization, studying and programming
- Character and C-string data..details and summary
- Details and summary about programming with classes
- Details and summary about reference and value parameters
Lecture 14 (3/16)--Midterm Exam
NEXT TOPIC: RECURSION and other approaches to SORTING
Reading: Begin with Ch. 9. Then read a little in Ch. 13 about
mergesort and selection sort. (The project will include mergesort of
a linked list.) Finally, jump back and read a little about stacks in Ch. 7 and
about trees in Ch. 10.
Miscellaneous Ch.3,4,5 Topics:
Lecture 15 (3/21)
Reading: Begin with Ch. 9. Then read a little in Ch. 13 about
mergesort and selection sort. (The project will include mergesort of
a linked list.) Finally, jump back and read a little about stacks in Ch. 7 and
about trees in Ch. 10.
Themes:
- Making Hard Things Easy: variables and values. functions and activations.
- Recursion: Introduced, explained in terms of non-recursive functions and Cats in Hats
(of Dr. Seuss).
Lecture 15 (3/21)
Reading: Sect. 9.1, Chapter 4, Sect 13.1 and 13.2 (up to mergesort).
Themes:
- Sorting
- Divide and Conquer applied to Sorting gives Mergesort
- Project 3 management, control flow diagram, and data structure diagram
Lecture 17 (3/28)
Ackermann's Function(.pdf)
Reading: Sect. 9.1, Chapter 4, Sect 13.1 and 13.2 (up to mergesort).
Themes:
- Sorting
- Divide and Conquer applied to Sorting gives Mergesort
- Recursion: (1) Activation tree (2) Recursive calls do what they do.
- Project 3 management, control flow diagram, and data structure diagram
Lecture 18 (3/30)
Ackermann's Function(.pdf)
Reading: Chapters on Stacks, Trees, finish Recursion.
Themes:
- Recursion: (1) By induction (2) By activation tree structure
- Expression Tree
- Activations and other uses of Stacks
- Intro to Parsing.
Lecture 19 (4/4)
Albany 2-Stacks Algorithm for Proj 4, part 1(.pdf)
Project 4 assignment--Due 4/19-4/21
Postscript Technology/Graphics Training Exercise(.pdf)
Reading: Chapters on Stacks, Trees, finish Recursion.
Themes:
- Stacks: string reversal, checking balanced parentheses.
- Activations compared to explicit stack for string reversal.
- The two-stacks algorithm for expression evaluation--Project 4!
- Expression Tree
- Intro to Parsing.
Lecture 20 (4/6)
Albany 2-Stacks Algorithm for Proj 4, part 1(.pdf)
Project 4 assignment--Due 4/19-4/21
Postscript Technology/Graphics Training Exercise(.pdf)
Reading: Chapters on Stacks, Trees, finish Recursion.
Themes:
- The two-stacks algorithm for expression evaluation: continued
and refined with data to track the subexpression which each number-stack
entry correspoinds to.
- Various details for Project 4, including stacks whose
elements are structured data records (like Coins).
- Part 2 of Project 4: How to build the expression tree
by storing in the number stack pointers to previously build subtrees.
- Quick Intros to Postfix expressions, how they express
calculations of expressions, how a stack maintains intermediate numeric
results.
-
Quick intro Recursive Tree Traversal.
Lecture 21 (4/18)
Postscript Technology/Graphics Training Exercise(.pdf)
Reading: Chapters on Stacks, Trees, finish Recursion.
Themes:
-
Taxonomy Tree of Organisms (Biology)
search for "human" and "root"
Select "Primates" from lineage, set levels to 7, and
look for "human"
-
Why the 2-stacks algorithm works.
- Linked structures used to implement binary trees; building
a tree from the bottom up.
-
Building a tree with the 2-stacks algorithm
-
Recursive Tree Traversals; the 3 kinds and their uses.
Lecture 22 (4/20)
Maze Proj Intro (4/20)
The 8-queens problem and a
Backtracking Search solution (Prof. Main's slides)
Project 5 Assignment
Postscript Technology/Graphics Training Exercise(.pdf)
Reading: Chapters and section cited in the Project 5 Assignment.
Themes:
- Maze search problem introduced.
- Maze search problem related to the N-Queens Problem.
Lecture 23 (4/25)
(Generalities about trees will be resumed later, after Proj 5 is underway)
More of Maze Proj Intro
Maze Proj Continued (4/25)
The 8-queens problem and a
Backtracking Search solution (Prof. Main's slides)
Project 5 Assignment
Reading: Sections cited in Project 5 assignment.
Themes:
- Graph abstraction of the maze.
-
Top-down problem analysis, design and project details.
-
Introduction to labelling search and traversal.
Lecture 24 (4/27)
Themes:
- Labelling and Backtracking Graph Search and Traversal
- Some Connections/tips for Project 5, part 1
- Depth-first Traversal for Project 5, part 2
- Glimpse at Breadth-First Traversal, for Project 5, part 3
Lecture 25 (5/2)
Finishing graph traversals
(4/29)
Reading: Section on iterators, finish reading Sec. 15.3.
Themes:
- Glimpse at templates.
- Complete Breadth-First Traversal.
- Glimpse at iterators.
Lecture 26 (5/4)
Go back into trees.
Reading: Chapter on trees, section TBA on function parameters,
graph chapter section on game trees, sections on binary search
trees and on heaps.
Themes:
- Glimpse at function parameters and function pointers
- Summarize Depth and Breadth First Traversal Codes.
- Traversal trees obtained for Depth-first and Breadth-first traversals
-
Special Properties of Breadth-First, and of Depth-First traversal;
some problems each solves.
- Some tree lore (leaf, child, binary, complete binary)
- Tree examples covering both explicit and implicit trees.
Lecture 27 (5/9)
Last Lectur of course
Reading: Chapter on trees, section TBA on function parameters,
graph chapter section on game trees, sections on binary search
trees and on heaps.
Themes:
- Glimpse at inheritance: Inheritance first distinguished from containment ("is-a" distinguished
from "has-a"), inheritance examples (clocks, organisms, computer games),
virtual functions as a case of polymorphism
- Where to go from here
- Outline of Topics for Final Exam study with textbook section..see slides
- Some tree lore (leaf, child, binary, complete binary)
- What is a search tree? What is a binary search tree? What is binary search?
- What is a heap-ordered tree? Glimpse at using heap-ordered trees for sorting
- The three tree traversals reviewed; pre-order is the same as depth-first traversal the
tree. We described breadth-first traversal of a tree.
- How the recursive definition of trees is analogous to the recursive definition
of expressions. (Remember expression trees express the structure of expressions.)
- Tree examples covering both explicit and implicit trees.
Lab, Office Hour and Lecture
Times
TA/Staff Information
Link to latest lecture postings
Telnet access link to
the U. Albany Unix cluster
U. Albany ITS Help
Desk, or visit LC-27.
What Was New:
- Extra help on Recursion re. Project 3! Anton Beza has volunteered to hold extra
evening office hours in HU-25 at 7:15PM-9:00PM Wednesday.
Also, be sure to attend this Tues. lecture. Two easy ways to think about how the
kind of recursion that mergesort does will be presented.
- Following a request, a Project 3 reference implementation is now
available. Use it observe how your program should work, and what the
formats of the messages should be.
Remember that when you run sorterbench, you must:
- Not seeing any prompts, type in a few data lines.
- Type Control-d (one keystroke) on a line by itself to terminate terminal input
- To see the input data, request one or more of the sorting algorithms be run,
and see the results, you must type the relevant command line arguments on the
same line as the sorterbench command
The sorterbench executable is available in the ITSUNIX directory with pathname
~acsi310/Proj3/
At present, mergesort is unimplemented..
- Some Project 3 DETAILS to help people NOT GET STUCK:
- To declare the data member pdata so it is a pointer to an array of C-pointers:
class SorterBench {
...
char * * pdata; //note the TWO stars!
// pdata holds a pointer
// (so it is declared ???? ??? ( * pdata );
// which is the address of the first element
// of an array. The array elements are pointers:
// (so the declaration is char * ( ???? ); )
// (Yes, C/C++ declaration syntax is messy.)
...
};
- To invoke new to obtain an array of pointers to char:
(Within a member function of the SorterBench class...)
pdata = new char * [ /*put updated value for capacity here*/ ]
//The description of the type of each array element is (char *)
//so that is what you write between new and [ numb. of elements ]
- Edited, corrected, improved Project 3/Recitation
instructions (on recursion visualization) (.pdf)
- The Permutation Cycle finding program trace homework
is due in next lecture, 2/14, NOT 2/12.
- Slightly corrected Project 1 Assignment(.pdf)
The difficult
parts are more accurately identified, the sample menu for test_Pile is corrected (It is a
copy of the sample program output.), and references to Bills are replaced by Coins.
Miscellaneous Stuff:
- Midterm: Thursday Lecture, March 16; 11:45-1:05. Closed Everything: no books, papers, PDA, etc.
Last Year's Topic outline/study guide and sample exam...Stay tuned for
Spring 2006 version.
- Writing Solid Code is in. 3 copies are available from the
UAlbany Library Reserve Room (basement of main library). You can now also
buy a used copy at the UAlbany bookstore. This book is recommended for
detailed motivation and instructions for programming with assertions
as well as other practical debugging and bug avoiding practices.
- Writing Solid Code, by Steve Maguire, is an excellent
book covering the use of assertions, pre and post-conditions. It includes many other tips and ideas
for avoiding or rapidly finding bugs when you write code. Check out this WIKI review.The book is in the
UAlbany Library and often in Barnes & Noble or Borders bookstores.
- TAs will explain basic UNIX commands and usage in the Lab/office hour sessions, but you
must ask. Basics: Directory concept, navigation, home and working directory reference using pwd and cd.
Listing directory contents using ls -l (hyphen-lower-case-el). Making fresh directories with
mkdir. Copying files. Running and observing results of compile and link commands. Using
separate editor and shell windows concurrently. Observing and changing file modes to make a
build script executable.
Similarly you can ask for general advice for getting started only after reading the previous
and current project assignments and labs.
- Cool Recreation of the Apollo Moon Mission Computer
- Bug Bounty Policy...Occasionally, my published reference programs will have bugs. The first
student who reports each bug that I can confirm will get a bounty of 10 (10%) on the corresponding
project. Of course, we will use test cases that reveal such bugs on grading the programs too, but
we will announce them.
-
Saunders, D., & Thagard, P. (forthcoming).
Creativity in computer science. In J. C. Kaufman & J. Baer (Eds.),
Creativity across domains: Faces of the muse. Mahwah, NJ: Lawrence Erlbaum Associates. PDF
From the Computational Epistemology Laboratory at Univ. at
Waterloo (//cogsci.uwaterloo.ca/)
- Albany Lab Tips Collected
- Instructions for ECL Login
- Final Exam: AS SCHEDULED IN OFFICIAL UALBANY SCHEDULE: May 15, LC-19
The final exam will be taken with no information carrying or receiving
materials (books, computers, PDA's, cell phones in use, data watches, etc)
OTHER THAN one 8.5x11inch paper sheet of notes (printing/writing on both
sides OK).
- Final exam Q/A Review Session: will be scheduled..
-
Exhaustive list from last year's of question types for exam review(.txt). Additional
questions might be added, but most of the exam will be a short selection
of particular cases of these questions. Stay tuned for this list updated for
this year.
- Excerpts from a previous final(.pdf)
-
Prof. Main's exam questions