BIT 143:Programming - Data Structures (2008 Spring)

Lessons

(there are more dates listed in The Huge Due Date List, at the bottom of this page)

Assignment 1 (DUE: Weds, Apr 16)

Individual Pre-Class Exercises:
<Due: Apr 7, noon PST (MONDAY of the SECOND week of the class) >

Overall Feedback Idea: Move more material back into this week - specifically the SmartArray class?

1. Orient yourself to BIT 143
2.  
3. Get Visual Studio
    
4. Install the software for XNA
   (you will need XNA for Assignments 2 & 4;
   you can use the basic Visual Studio for the PCEs)
   (PCEs = Pre-Class Exercises)
    
5. Join the class newsgroup ; (Required)
   Send the professor your email address
    
6. Create a simple console application 
   (Ch 3.3 (walkthrough),
   3.2 (explanation of the program) )  
   There is a Demo Video that walks you through this, too
    
7. Downloading and using a simple console application
    
8. 'Starter' project for the lesson 01 PCEs (DOWNLOAD THIS!!)
    
9. Console I/O, Operators (Chapter 3) (Hand-In)
   
   Review Exercises:
10. Fahrenheit to Celsius
11. Nested Loops: Rectangles
12. Nested Loops: Hollow Rectangles
13. Fibonacci numbers in an array (Hand-In)
    
    OOP Basics:
    (Demo Video   Example Project)
    OOP Encapsulation:
    (Demo Video   Example Project)
     
14. Variable Scope (class, instance, local/param vars) (Hand-In)
     
15. Using The Distance Formula (Demo Video   Word Document Used in the Video)
    (There is nothing to hand in for this PCE.  Personally, I'd recommend doing a couple of examples by hand in order to make sure that you understand the formula.  You will be using the formula on homework assignment 2, et al.)
     
16. Class Composition: Circle Class (Hand-In)
    Feedback: Most people did this via inheritance - clarify why composition means, and why it's a better fit than inheritance
    
17. Circle class: Overlap method (Hand-In)
     
18. Web Hand-In for pre-class exercises and homework
    (Using the StudentTracker thingee)
    (Direct link to this, specific class: http://panitzco.com/CCC/StudentTracker/Pages/course.php?courseId=2 )

Individual Pre-Class Exercises:
< Due: Apr 9 (Wednesday), before the start of class >

Overall Feedback Idea: Make it clear that some exercises are meant as 'level 1'/background exercises, and others are meant as more open-ended problem solving/application?

1. How To Use Multi-Project Starter Solutions
   
   (related, optional reading: How to create your own multi-project solutions)
    
2. 'Starter' project for the lesson 02 PCEs
   (Unless otherwise stated, put exercises into the PCE_Starter project)
    
3. How to use a debugger: Intro
    
4. Reference Types vs. Value (Simple) Types
   Feedback: How to make this more clear?
    
5. Arrays of Simple Types
    
6. SmartArray Overview
7. Basic SmartArray Class (Hand-In)
    
8. Review: Big "Oh" Notation  (Hand-In)
   Feedback: Exercise: Give 5 different types of routines, match them to their O(N) notation time
    
9. Figure out what a stack is  (Hand-In)
10. Preview: Using the .Net FCL Stack (Hand-In)
    Feedback: Confused about how to start - quick starter code? Clarify that this is 'discovery'?
    Feedback: What exactly to include in the code?
     

11. Figure out what an enum is  
    (Demo Video   VS Project Used in the Video)
     

12. Define the ErrorCode Enum (Hand-In)
     

13. Using the ErrorCode Enum (Hand-In)
    Feedback: Consolidate these two?
    IDEA: Maybe do these before the SA?
    Feedback: Put the enum stuff right next to SA
     

14. PCE Feedback (Hand-In)
     
15. Post at least 1 question in the Google Group for this class.
    
    Answer at least 1 question
    (that someone else has posted)
    in the Google Group for this class
     

Individual Pre-Class Exercises:
<Due:  Apr 16  (Wednesday), before the start of class>

1. 'Starter' project for the lesson 03 PCEs
   (Unless otherwise stated, put exercises into the PCE_Starter project)
   IDEA: move the stack/queue classes to the TOP of their respective .CS files
   CHANGE: Just ErrorCode enums into the project - make sure that exercise language still agrees with this.
   Feedback: Move all tests to bottom, and/or put them into a separate file? <<Clutter>>
   
   

2. OOP Inheritance (Specialization):
   (Demo Video   Example Project)
    

3. StackOfInts as specialized SmartArray
   (Hand-In)
    

4. QueueOfIntegers as specialized SmartArray    (Hand-In)
   Feedback: Clarify: Peek looks @ FRONT, not last in
   Feedback: Clarify w/ diagram? Clarify, please!
    

5. Stack / Queue: Annotate with Running Time (Hand-In)
   Feedback: Remove reference to resizing array
   
   

6. Figure out what Generics are
   
   There's a very (very very) thorough explanation at http://msdn2.microsoft.com/en-us/library/ms379564(VS.80).aspx.  If you read the first couple of sections (up to Applying Generics), that should be enough background for you.
   
   

7. Basic, Generic class (Hand-In)
   Feedback: Clarify: provide example output?
   Feedback: Clarify: exactly what needs to be done
   Feedback: Why are these useful?  Programmer should have control over what objects are being passed in, right?
    

8. PCE Feedback (Hand-In)

 Move the SmartArrayAOD back to here?

In-Class Exercises:
<Class Date: Apr 2  (Wednesday) >

(This class meets from 5:45-10:05pm this first week ;

it meets from 8:00pm -10:05pm thereafter)

1. Create a simple console application
2. Basic Console I/O
3. Single-file Demo for PCE's  
4. Single-Solution Demo for PCE's
   (You need use this (or something similar) as the 'template' for the other PCEs)
    
5. How to use a debugger
    
6. Basic class design

In-Class Exercises:
<Class Date: Apr 9  (Wednesday) >
 

(This class meets from 8:00pm -10:05pm starting this week)

Review:

1. Enums in detail
2. Bitwise enums
3. IS-A vs. HAS-A & PCE01 Ex 15

Preview:

1. Slideshow: Stack ADT
2. Using A Stack: Detecting Palindromes
    
3. Stacks: Running Time
    
4. Specifying the Queue ADT
    
5. Generics (quick overview)
   Example Code
    
6. Inheritance: Specializing a base class

1. Stack of Simple Types vs. Reference Types
    
2. Test-driven development:
   Implementing a stack of circles
    
3. Linked List Of Ints: Add to the Front 
   (Sect. 24.4)
   
4. Linked List Of Ints: Traversing  (Sect. 24.4)
    
5. Preview: Interfaces, IEnumerable

Assignment 2 (Due: Weds, Apr 30)

Due This Week:

• Due on Monday, Apr 28, before midnight:
  A2 Skills pre-test
  Hand this in by emailing it to the instructor (MPanitz@cascadia.edu) -
  Do NOT include this in this week's PCE's.
  

Feedback: Requirement to add in running time confusing?--

1. 'Starter' project for the lesson 04 PCEs
   
   

2. SmartArray: Alloc on demand (Hand-In)
   IDEA: Move this back to the Lesson 03 PCEs
   Feedback: This is out of order w/ respect to next one?
   Feedback: Remove the Resize method
   Feedback: Clarify that this one does the allocation only once, but not until it's needed.
    

3. SmartArray: Manually resizing
   Feedback: This is out of order with respect to the AllocOnDemand assignment?
   Feedback: Clarify that this one will reallocate the array as needed.
   Feedback: Make these two substantially different, in a way that's easy for students to notice
   
   
4. Test-driven development: Implementing a stack of Circles                            
   Feedback: If this is going to be required, then be specific about how many tests for students to do (2 for isEmpty, etc, etc)
   Feedback: If this is going to be required, then mark it as 'hand-in'
   Feedback: Make it clear that the tests should work, but don't spend too much time on these
   1. (It may be helpful to refer back to
      Stack of Simple Types vs. Reference Types)
      
       
5. Linked List Of Ints: Add to Front   (Hand-In)
   (Sect. 24.3, 24.4)
   Feedback: Writing this into main, then moving into classes was specifically called out by 1 person as being good
   Feedback: What should be implemented in main? x2                                 
    
6. Linked List Of Ints: Traversing      (Hand-In)
   (Sect. 24.4 - 'Print' )
    
7. Linked List Of Ints: Remove From Front (Sect. 24.4)                                   (Hand-In)
    
8. LL: Refactor into a Stack class
   Feedback: Specify that the 'limited size' tests should be changed so that the test will now test for UNlimited size of the linked list based implementation
    
9. Additional StackLL Features
    
10. LL: Printing at a specific location
    (Try your best on this, but don't worry if you end up getting stuck)
     

11. Discovery of Interfaces: IEnumerable & Arrays        (Try your best on this,
    but don't worry if you end up getting stuck)
    Feedback: Explain what a 'helper class' is
     

12. PCE Feedback (Hand-In)

Feedback: Seemed to be a particularly frustrating lesson, instructions-wise

Feedback: At some point, the O() notation should stop :)

1. 'Starter' project for the lesson 05 PCEs
   
   
2. SmartArray: Auto-Resizable
   Feedback: Provide a solid starting base for this?
   Feedback: Mark this as required, sinc the next one depends on this one?
   
   
3. KeyedSmartArray (structs vs. classes) (Hand-In)
   Feedback: Scrub this for references to the Resizable version
   Feedback: Remove the test code, or else update it
   Feedback: Overall, 'struct' coverage is still pretty light.
   Feedback: Clarify instructions?
   
   
4. Objectifying the Linked List Code
   Feedback: Update starter so that students don't accidentally do all exercises 'up front'?  There's something that says "implement all methods on the class" x2
5. LL: Insert by location/index (Hand-In)
6. LL: Remove by location/index (Hand-In)
   Feedback: What's in PCEs didn't seem to match up with starter project?
    
7. LL: Insert by value, in order
8. LL: Remove by value, in order
   Feedback: This needs to be updated - uses term 'value', where code/prior exercisees uses 'index'
   Feedback: This wrongly recommends the same tests as for the previous exercises?
   
   
9. Generic Linked List (Hand-In)
    
10. IEnumerable & Linked Lists
    This could use some work - it needs substantially more guidance (other doc?)
    Also - specify that this should be done on the non-generic LL
    ALSO - throw in the yield keyword?  Start there, then go to std/java iterators?
    
11. Recursion By hand: Warm-up #1
    
12. Recursion By hand: Warm-up #2
    
13. PCE Feedback (Hand-In)

Individual Pre-Class Exercises:

<Due: May 7 (Wednesday) before the start of class;

no penalty until May 14 >
Feedback: Exercise ideas for recursion: Conway's Game Of Life, 'Ant Walk', making a Mandelbrot set, etc.

1. Review for the exam!!! 
   
   

2. 'Starter' project for the lesson 06 PCEs
   
   

3. Keyed Generic Linked List & default values of generic types (Hand-In)
   Feedback: Didn't really achieve goal of expanding knowledge of linked lists
   Feedback: Insist on InsertAt, and RemoveAt, instead of just dealing with the front of the list?
   ADD: How to compare generic objects? (From GoogleGroup)
   Feedback: Generics with two types was confusing?
    
   Recursion
   IDEA: Emphasize that recursion will be used in BSTs, and that these are just warm-ups?
   
   (Note that this was formerly in Lesson 09 in BIT 142, so if you've taken 142, then this will be review)
   
4. Recursively Printing Even Numbers
   
   
5. Recursive Power Function
   
6. Recursive Multiplication (Hand-In)
   Feedback: More info on base case / coding recursively?
   
   
7. Write Factorial
8. Fibonacci Numbers (And Arrays!)
   
   
9. Print a singly linked list recursively (Hand-In)
   Feedback: Be clear that printing backwards should also use the 1 public, 1 private approach
   Feedback: Be clear that in addition to the boolean argument, students can add anything else they want
   Feedback: More guidance would be good, but it's not a crisis
   Feedback: maybe a video of a similar recursion print technique or more of a walk through?
   
   
10. PCE Feedback (Hand-In)
    

Review:

1. Interfaces, IEnumerable
    
2. Linked List stuff

Preview:

1. Objectifying the Linked List Code
   • Linked_List_Starter.zip -Starter Project for Add/Remove exercises
      
2. LL: Insert by location/index
3. LL: Remove by location/index
    
4. LL: Running time
    
5. LL: Insert by value, in order
6. LL: Remove by value, in order
    

7. Generics for general-purpose ADTs
   Generic Linked List
    

8. Memory Management:
   KeyedSmartArray (structs vs. classes)

1. Midterm Exam: Q+A & Review
    
2. Recursion By hand: Warm-up #1
3. Recursion By hand: Warm-up #2
   

4. Recursion By hand: Warm-up (#3)

5. Recursion by Hand: Warm-up (#4)

6. Recursion By hand: More Complicated
    
7. Recursive Multiplication
   
   
   
8. Print a singly linked list recursively
9. Add to a singly linked list, recursively
10. Remove from a singly linked list, recursively
    
    
11. Queue implemented via Linked List
     
12. Doubly-linked list
    

Midterm Exam: Q+A & Review

<Midterm Exam>

Assignment 3 (Due: Weds May 14)

Assignment 4 (Due Weds, May 28)

Due This Week:

• Due on Friday, May 23, before noon:
  A2 Skills post-test
  Hand this in by emailing it to the instructor (MPanitz@cascadia.edu) -
  Do NOT include this in this week's PCE's.
  
  
• Due on Friday, May 23, before noon:
  A2 Opinion Survey  
  Hand this in by going to the website, entering your 'Rock Star Alias', and then filling out the online form.  When you click 'Submit', your survey form will be stored in a database where Prof. Rosenberg can get them.
  Do NOT include this in this week's PCE's.

Due This Week:

• Due on Monday, May 19, before midnight: A4 Skills pre-test  
  Hand this in by emailing it to the instructor (MPanitz@cascadia.edu) -
  Do NOT include this in this week's PCE's.

1. 'Starter' project for the lesson 07 PCEs
   
   
2. Link to BIT 142's Recursion Material
    
3. Compare & Contrast Two Pow implementations (Hand-In)
   Feedback: More scaffolding for using O() to describe space
     
4. Binary Search Tree preview (Required)
   Feedback: There's a section in the book on this - find those sections & list them here.
   
5. Binary Search Tree: Class Definitions
   

6. Lecture Recordings From Previous Terms:

   • BST - Add
     Feedback: Demonstrate both iterative, and recursive solutions for this - especially since most online examples will be recursive?
     Feedback: Be clear about what to do for duplicates?
     IDEA: What about having forced discussions about things like 'what to do about duplicates?"  THis might help them be more independent, but in a way that it's clear they're supposed to be independent.
     Feedback: Audio quality - wrong version of Flash player - NEED BACKUP PLAN!!!
     
     
7. BST: Add   (coded in C#) (Hand-In)
   Feedback: Make sure that there is a video lecture of code, before asking them to write code
   Feedback: .DOC mentions Add, project has Insert
   
   
8. Nested Classes: Basics
   
9. PCE Feedback (Hand-In)
   (For this PCE, please focus your comments on the online video, and whether it's helpful for the 'Add' exercise, and how to improve it)

Individual Pre-Class Exercises:
<Due: May 21 (Wednesday)  before the start of class>
Feedback: Was a pretty easy lesson - pretty much just static vars
Feedback: Video of static vars?
IDEA: Provide code to hard-wire a BST, then make them do the searching routine?  Video with iterative & recursive approach?  Variation: Hardcode a bunch of duplicates, make them modify search to find dups?

1. 'Starter' project for the lesson 08 PCEs
   
   
2. Static Instance Variables: Just the trick for assigning unique IDs (Hand-In)
   
3. Initializing static variables
   Feedback: This was really confusing! x2
    http://www.csharphelp.com/archives3/archive565.html
   Feedback: Make it clear that unique ids need to be addressed
   
   
4. Generics: Def of "constructed type"
   
5. Generic types & static variables (Hand-In)
   Feedback: Carbon copy of previous exercise?
    
Feedback: Add regular constructors in, too, and specify the order in which they're called



6. BST: Remove preview
    

7. <Video: Explanation of BST-Remove (Concepts)>
   
8. BST: Remove By Hand
   (The lecture 8 quiz will be similar to one of these exercises)
   Feedback: Shorter, cut out the pauses because of waiting for the audience to ask a question?
   
   
9. PCE Feedback (Hand-In)

OBSERVATION: A lot of people got the search loop wrong.  This indicates that they didn't get it earlier.  Also, A4 was really really rough - the BST material isn't getting through.
IDEA: merge the 'findandremovenextsmaller' back into the mainline method, maybe?

1. 'Starter' project for the lesson 09 PCEs
   
   
2. BST: Remove (coded in C#) (Hand-In)
   Video: Explaining code details of BST-Remove
   Feedback: Too much scaffolding with the code?
    
3. Operator Overloading: BST Node
   Feedback: More detail; example code?
   Feedback: More examples?
   Feedback: It's a bit tricky to find online examples in C#
   Feedback: maybe more on the syntax of overloading operators
    
4. Sorting & Searching: setup for the class (Hand-In)
   Feedback: Way too easy
   IDEA: Maybe make them redo BubbleSort as a review?
   IDEA: BinarySearch & LinearSearch as review?
   IDEA: Also have them do the version that measures the number of comparisons, and then graph those in Excel?
    
5. Preview: MergeSort
    

6. Preview: QuickSort
    

7. PCE Feedback (Hand-In)

In-Class Exercises:
<Class Date: May 14 (Wednesday) >

1. Discuss the Pow implementations
2. BST: Find, Add by hand
3. BST: Add   (coded in C#)
4. BST: Find   (coded in C#)
5. BST: Print  (coded in C#)
6. BST: Remove preview
   

STUDENT SOLUTIONS:

• Iterative Insert/Add
• Recursive Find

1. Demo: BST RemoveRootNode
    
2. BST: FindAndRemoveNextSmaller (in C#)
   <Starter Project> (same as previous demo)
    
3. BST: RemoveInternalNode (coded in C#)
   

1. SlideShow: QuickSort

2. QuickSort: By Hand

3. Implementing QuickSort
   

4. Preview: MergeSort 

1. Due dates, etc
2. QuickSort

Older Videos:

1. Due dates, etc
2. QuickSort
3. <MergeSort has been delayed till next week>

• Due on Friday, Jun 6, before noon:
  A4 Skills post-test
  Hand this in by emailing it to the instructor (MPanitz@cascadia.edu) -
  Do NOT include this in this week's PCE's.
  
  
• Due on Friday, Jun 6, before noon:
  A4 Opinion Survey  
  Hand this in by going to the website, entering your 'Rock Star Alias', and then filling out the online form.  When you click 'Submit', your survey form will be stored in a database where Prof. Rosenberg can get them.
  Do NOT include this in this week's PCE's.

Feedback: Covered thoroughly in recorded lecture, with code in Ppt slides, so students breezed through it. 
OBSER: Very few people caught/fixed the error with left starting 1 too high.
IDEA: Find a couple different implementations, inject errors & get them to find the errors?

1. 'Starter' project for the lesson 10 PCEs
   
   

2. Implementing QuickSort (Hand-In)
   Feedback: Wikipedia entry has a nice animation (June 6, 2008)
   IDEA: Also have them do the version that measures the number of comparisons, and then graph those in Excel?
    

3. PCE Feedback (Hand-In)

1. Review for the exam
    
2. Implementing MergeSort (Optional)
    
3. Final Exam: Q+A & Review

1. CIEs!
   
   

2. Quiz
   
   

3. Final Exam: Q+A & Review
    

4. MergeSort: PseudoCode  (the Print-Out Version)
    

5. Jeff & Joe's  Mergesort Slides
    

6. MergeSort: By Hand (Time Diagram)
         Time Diagram Example (Excel)
    

7. MergeSort: Western Kentuckey U Sample

1. <Final Exam>
   
2. Post-Course Evaluation

   (Required - this is an online survey, so you won't 'hand in' anything) (You will do this BEFORE you start the final)

The Huge Due Date List

Note: This list is an attempt to collect up in a single spot all the due dates for the term.  These dates may change.  There may be more items added.  It is your responsibility to make sure that you know what's due when, to make sure that you don't miss anything.

In particular, the homework revisions may be moved to a week earlier, if the instructor can return the initial version within 24 hours of the due date.

Due on: (For items due on a Wednesday, the time which they are due by is the start of class, unless otherwise stated)	Activity
Wednesday, Apr 2 (This will be done in-class on the first day)	Fill out the 'pre-course' survey: (NOTE: You will need your 'rock star' pseudonym before you're able to do this. This will be assigned to you on the first day of class)
Wednesday, Apr 2 (No later than midnight)	Email the professor, so that the professor has your email address
Monday, Apr 7, by NOON	PCE 01
Wednesday, Apr 9	Google Group: Sign yourself up, post a question, answer someone else's question:
Wednesday, Apr 9	PCE 02
Wednesday, Apr 16	A1 (initial version)
Wednesday, Apr 16	PCE 03
Wednesday, Apr 23	PCE 04
Monday, Apr 28, by MIDNIGHT	Skills pre-test for A2
Wednesday, Apr 30	A2 (initial version)
Wednesday, Apr 30	PCE 05
Wednesday, Apr 30	A1 (final, revised version)
Wednesday, May 7 (no penalty until May 14)	PCE 06
Wednesday, May 7	MIDTERM  EXAM
Wednesday, May 14	A3 (initial version)
Wednesday, May 14	PCE 07
Wednesday, May 14	A2 (final, revised version)
Wednesday, May 21	PCE 08
Friday, May 23, by MIDNIGHT	Skills Post-test for A2
Friday, May 23, by MIDNIGHT	Opinion survey for A2
Monday, May 26, by MIDNIGHT	Skills pre-test for A4
Wednesday, May 28	A4 (initial version)
Wednesday, May 28	A3 (final, revised version)
Wednesday, May 28	PCE 09
Wednesday, Jun 4	PCE 10
Wednesday, Jun 4	A4 (final, revised version)
Friday, Jun 6, by NOON	Skills Post-test for A4
Friday, Jun 6, by NOON	Opinion survey for A4
Wednesday, Jun 11	PCE 11
Wednesday, Jun 11	FINAL  EXAM
Wednesday, Jun 11	'Post-Course' opinion survey

Back to BIT 143's homepage

Unused Lecture Material

BIT 142's Lessons Page