CSI310 Data Structures, Computer Science Dept.

Simple Home Page for Spring 2007 session taught by Prof. S. Chaiken

Previous session web sites:  Spr. 2006 

What's New and Still Relevant

• The CS Teaching resources from Stanford include fine materials on linked lists and trees.
• Good free book by Ian Parberry on algorithms and data structures, for moving ahead to CSI403/CSI503. Select "Problems on Algorithms"

Handouts including Syllabus, Instructions and Assignments

• Course Syllabus with first reading and writing Homework assignments.(.pdf)
• Readiness Exam (.pdf)
• Lect 02 Reading Quiz
• Lecture 03 attendance and lab section report sheet...If you missed it you are marked absent.
• Project 1 Assignment(.pdf)
• Directory of C++ sources for Project 1 shown to the class.
• Instructions for turning in project work(.pdf)
• Process Requirements and Guidelines for CSI310 Programming(.pdf)
• Project 2 Assignment: DUE 2/14-16(.pdf) Extended to after the break.
• Copy of the chapter on strings from Stroustrup's "The C++ Programming Language" distributed. See me if you missed getting it.
• Project 3 Assignment(.pdf): Part 1 DUE 3/7-9, Part 2 DUE 3/7-14
• Topics for the Midterm Exam of March 15
• Lecture 16 Quiz (March 20)
• Project 4 Assignment on Merge Sorting: Due 3/26
• Readings, writings and Project 5 Assigned (Due April 10 and 16-18 (3/27)
• Using DDD to observe activations (Labs of Mar. 28 and 30)
• Project 6 assignment Due 4/24-26
• Project 7 Assignment due 5/1-3

Lectures

• Lecture 01 (1/18)
  • Readiness Exam (.pdf)
  • Course Syllabus with first reading and writing Homework assignments.(.pdf) The writing assignment is to write a 2 page plan for programming project 1; that project is briefly described in the Syllabus.
  • Administrivia: Meetings, Requirements, Grading, UA Lab facilities provide no excuse for missing or late requirements due to problems with student's equipment or software. The problems to solve in this course are problems solved by computer programs which you will learn to write.
  • Idea for project1: Simulate manipulations of 52 card pile. First get a full deck. Second, randomize it. Third, deal out 4 bridge hands of 13 cards each. Fourth, print each hand sorted and print its value in Bridge as described in Programming Project 4 of Ch. 1 in Carrano's book.
  • Idea for the reading assignment: Consider the array of 10 numbers on the readiness exam. Consider the C++ code to find the maximum number in it. The code is separate from the array but programmers have the burden of using this code only for this array.
    An OBJECT has two things: attributes and behaviors. Synonyms for attributes: characteristics, data values, data members, state. Synonyms for behaviors: function members, methods, operations. The behaviors are coded by executable code associated with the object.
    What is a class? "classes specify the attributes and operations for the objects" Some say a class is a set of object with common kinds of attributes and behaviors. I like to say a class is a template for object creation.
• Lecture 02 (1/23)(.pdf)
  Reading Quiz
  
  • Problem Analysis. Data abstraction means, concretely, that a programmer designs his/her OWN data types. Builtin types. A C++ class is a data type, programmer defined. Identifying and listing the properties and behavior of ONE Card needed for the project.
  • Verifying a full deck and dealing 4 hands from it demonstrated.
  • Following lecture slides, demonstrate logging into ITSUNIX and creating the Card class header (interface) file, Card class .cpp (implementation) file and a Card class tester.cpp program. Demonstrate compile and link commands from emacs. Demonstrate using emacs to quickly locate the line where an error occurs.
• Lecture 03 (1/25)(.pdf)
  Project 1 Assignment(.pdf)
  Attendance taken.
  
  • CSI310 process requirements. Going from analysis of class Card in project 1 to implementing and testing the Card class.
  • Use of arrays with fixed data to express application structure, such as the suits and ranks in Bridge and how they are printed and ordered.
  • An object is actually a variable. Arrays of objects.
• Lecture 04 (1/30)(.pdf)
  Attendance taken. Assistant consulting schedule distributed:
  Lab, Office Hour and Lecture Times
  Staff and Teaching Assistant Information
  Directory of C++ sources shown to the class.
  Instructions for turning in project work(.pdf)
  Process Requirements and Guidelines for CSI310 Programming(.pdf)
  • CSI310 process requirements. Going from analysis of class Card ..
• Lecture 05 (2/1)(.pdf)
  Directory of C++ sources shown to the class.
  Anybody working on Linux?? My suggested randomization code works on ITSUNIX but CRASHES on Linux. See the slides. I plan to present this as a case study.
  
  • C++ preprocessor operation, include guards and their use.
  • Project 1 main module software design
  • An INVARIANT expresses the thinking behind the main Card dealing loop.
  • A glimpse at how data in an object changes.
• Lecture 06 (2/6)(.pdf)
  Directory of C++ sources shown to the class.
  Anybody working on Linux?? My suggested randomization code works on ITSUNIX but CRASHES on Linux. See the slides. I plan to present this as a case study.
  
  • Solution to Quiz problem about the preprocessor. How rules about information technologies have to be understood and applied. (Jabberwocky, by Lewis Carroll)
  • Visualizing Program Exe. with ddd.
    1. start with "ddd PileSorter" command.
    2. break on main() first.
    3. run second.
    4. Highlight then display to display a variable.
    5. next makes next source line, with the green arrow, run
    6. step "steps INTO" a function call.
    7. Changes in the displayed variables are highlighted in yellow.
    8. finish to finish the current function call.
    9. undo and redo to look at past execution states.
    Important words and concepts:
    1. Within a member function, "this" holds a "pointer" to the object for which the function was called.
    2. Accessing the object pointed to by a pointer is called
    "dereferencing the pointer"
  • Key to success in beginning computer science: Be able to imagine and do on paper the actions of each line of program code on the data step by step. These step by step operations can be observed with a debugger.
  • (in the slides..) Ideas for sorting and for the 2nd part of project 1.
• Lecture 07 Outline (2/8)(.pdf)
  Previous lectures slides, consult skipped slides for needed details (.pdf)
  Project 2 Assignment: DUE 2/14-16(.pdf)
  Directory of Project 2 files to help you start.  These are also available in ITSUNIX under ~acsi310/pr2/Carrano.
  Copy of the chapter on strings from Stroustrup's "The C++ Programming Language" distributed. See me if you missed getting it.
  WARNING: TO USE Carrano's framework, write the line
  typedef std::string ListItemType;
  into ListA.h, and choose a class names like ListA and SListA to use consistantly for the array-based implementations.
  make sure there is the namespace qualifier "std::" in front of string in the header files.
  Anybody working on Linux?? My suggested randomization code works on ITSUNIX but CRASHES on Linux. See the slides. I plan to present this as a case study.
  
  • The "skeleton" to start developing Project 2 INCREMENTALLY, Visualized with ddd.
  • Exposure to the implementation of C++/STL string objects
  • (in the slides..) Ideas for sorting, moving data around in arrays, to finish project 1 and start project 2.
• Lecture 08 Outline (2/13)(.pdf)
  Directory of Files used in the DDD Demo of static versus dynamic arrays.  These are also available in ITSUNIX under ~acsi310/pr2/Carrano.dyn
• Lecture 09 (2/15)(.pdf)
  Directory of Files used in the DDD Demo of static versus dynamic arrays.  These are also available in ITSUNIX under ~acsi310/pr2/Carrano.dyn
  • Introduction to dynamic things.
• Lecture 10 (2/27)(.pdf)
  Project 3 Assignment(.pdf): Part 1 DUE 3/7-9, Part 2 DUE 3/7-14
  Directory of Files used in the DDD Demo of static versus dynamic arrays.  Directory of Files used in the DDD Demo of static versus dynamic arrays.  These are also available in ITSUNIX under ~acsi310/pr2/Carrano.dyn
  • QUIZ and wrapup: Object for which a method is called; care about understanding method calls.
  • Pointers and addresses.
  • Glimpse at a linked list.
  • Lab this week: reproduce Carrano's pointer diagrams with DDD
• Lecture 11 (3/1)(.pdf)
  • QUIZ about loops, ifs and variables. Need to understand: Sequential execution, meaning of braces, which variable is which, meanings of if(), while() and other statements.
  • Cursor logic: N lines, N+1 cursor positions.
  • Need to access the node before the target node.
  • Concrete classes: Complex and my TimingWatch
  • Steps to enlarge a dynamic array: QUIZ!
  • Data members of ListDynA; use of an assureEmptySpace method.
  • Questions raised about resizing strategies
  • Details for doing dynamic array allocation and using the array elements
• Lecture 12 (3/6)(.pdf)
  Reference versus value parameters in C++ (.pdf)
  • (making a web site with a public_html directory)
  • Idea of selection sort, refinement, variations.
  • class ListP for ADT with linked implementation, inner class ListNode, structure and where to code each.
  • Discussion: Both a node pointer and a line number integer are needed to implement the cursor in order to avoid inefficiencies from walking the list.
  • Need to access the ListNode before a target ListNode.
  • class vs. struct alluded to...
  • Dynamically Allocating and then accessing fields of class objects.
  • Linked list as treasure hunt.
  • Linked list end insert step by step details.
  • Advice for programming problem solving and coding with data structure diagrams.
  • Lab this week: Help and discussion of Proj 3
• Lecture 13 (3/8) Reference versus value parameters in C++ (.pdf)
  Recursion Intro, Studying function calling from Carrano(.pdf)
  • Details: Reference vs value parameters, and pointers.
  • Intro to recursion, importance of understanding function calling.
  • Lab this week: Help and discussion of Proj 3
• Lecture 14 (3/13)
  Topics for Next Lecture's Midterm Exam
  Analysis of Dynamic Array performance(.pdf)
  
  • More on recursion, importance of understanding function calling with activations.
  • "The Cat in the Hat Comes Back" by Dr. Suess introduces recursion. (Visit your local children's library or bookstore).
  • Lab this week: Observing and recording running times for Project 3 programs. Use this Lab Data Sheet
• Lecture 15 (3/15) - Midterm Exam
• Lecture 16 (3/20)
  Project 4 Assignment on Merge Sorting: Due 3/26
  
  • Review on function activation, return and local storage extant (automatic) variables.
  • Split and Merge pieces of Merge Sort
  • Merge Sort shown and dramatized.
  • Induction ("faith in recursive calls") and global structure introduced.
  • Lab this week: Observing and recording running times for Project 3 programs for SORTING. Use this Lab Data Sheet
• Lecture 17 (3/22) (old slides, new ones under construction)
  Cool animations of lots of sorting algorithms(Java)
  Updated Handout on Observing Activatations with DDD(.pdf)
  
  • Animations of selection sort and mergesort algorithms.
  • Divide and Conquer Pattern, Recursion review and Big Picture view of mergesort.
  • Running time analysis of mergesort by accounting for time used in terms of Big Picture View. Get O(N log N).
  • Running time analysis of "stupid" recursive insertion sort, get O(N^2) using triangle area formula.
  • Some recursion examples from Carrano. Start of seeing activations with DDD.
  • Lab this week: Observing and recording running times for Project 3 programs for SORTING. Use this Lab Data Sheet
• Lecture 18 (3/27)
  Readings, writings and Project 5 Assigned (Due April 10 and 16-18 (3/27)
  Old Slides to be encorporated (3/27)
  Using DDD to observe activations (Labs of Mar. 28 and 30)
• Lecture 19 (3/29)
  Readings, writings and Project 5 Assigned (Due April 10 and 16-18 (3/27)
  • html structure
  • Infix Expressions, Expression tree, Evaluation, Postfix Expressions, evaluation using stack
  • Basic Stack demos (Plates, Pez, reversing strings)
  • Stack used to (1) match parentheses (2) convert infix to postfix
• Spring Break 3/31-4/9
• Lecture 20 (4/10)
  
  • Expression wrapup and value
  • Infix-to-postfix algorithm
  • Some implementation details
• Lecture 21 (4/12)
  
  • Tree examples and applications, including National Inst. of Health's taxonomy tree of living organisms
  • Using an STL vector as a stack; iterators on STL containers.
  • Stacks of floats and expression tree node pointers
  • Expression tree built from linked nodes: class for ExpTreeNodes, building the tree by hand, recursive evaluation of the tree
  • Differences between chars and the operation they represent, differences between digit chars and the numbers they represent "subtract char code for 0 to convert"
  • Building the expression tree from the postfix expression is similar to evaluating the postfix expression using a stack.
• Lecture 22 (4/17)
  Project 6 assignment Due 4/24-26
  
  • Language and Trees--Pay a visit to Prof. Pinker's Harvard class(.pdf)
  • Using an STL vector as a stack; iterators on STL containers.
  • Stacks of floats and expression tree node pointers
  • Expression tree built from linked nodes: class for ExpTreeNodes, building the tree by hand, recursive evaluation of the tree
  • Differences between chars and the operation they represent, differences between digit chars and the numbers they represent "subtract char code for 0 to convert"
  • Building the expression tree from the postfix expression is similar to evaluating the postfix expression using a stack.
• Lecture 23 (4/19) under const..
  C-strings and their vulnerabilities
  
• Lecture 24 (4/24)
  Project 7 Assignment due 5/1-3
  
  • How shell scripts execute, pipeline shell commands, how a queue is used when a pipeline command is run.
  • Material for Project 7.
• Lecture 25 (4/26)
  Project 7 Assignment due 5/1-3
  
  • Material for Project 7.
• Lecture 26 (5/1)
  C-strings and their vulnerabilities
  Buffer Overflow, C++ strings use/pitfalls
  Review 1 (.pdf)


 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 Computing Help Desk, or call 442-3700, or visit LC-27, or email theshed@albany.edu

What Was New:

Miscellaneous Stuff:

• Midterm: Thursday Lecture, March 15; 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 2007 version.
• Writing Solid Code is in. 3 copies are available from the UAlbany Library. 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:
  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)