BIT 143:Programming - Data Structures (2009 Spring)

Lessons

Individual Pre-Class Exercises:
<Due: April , noon PST (MONDAY of the SECOND week of the class) >
(Note that this is NOT the date listed in the pre-quarter email)

Feedback: DURING TERM, CLARIFY WHAT SPECIFIC NUNIT ERRORS MEAN (NullReferenceException in the linked lists chapter, etc, etc)

TODO: Do generics right, or else ditch them? (This note is for the prof, by the prof, which is why it's hard to read/hidden :)  )
IDEA: Have a 'video has been watched' worksheet that MUST be handed in at the start of class, in lieu of a quiz?
Feedback: Carve out more time for NUnit - combine BST stuff?

1. Orient yourself to BIT 143
    
2. Get Visual Studio
3. Install the software for XNA
   The XNA-based PCEs and assignments will be optional.
   You can install this software later, if you don't want to install it right now
    
4. Join the class newsgroup ; (Required)
   Send the professor your email address
    
5. 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
    
6. Downloading and using a simple console application
    
7. 'Starter' project for the lesson 01 PCEs (DOWNLOAD THIS!!)
   
   
8. How To Use Multi-Project Starter Solutions
   (related, optional reading: How to create your own multi-project solutions)
   
   
   Review Exercises:
9. Console I/O, Operators (Chapter 3) (Hand-In)
10. Fibonacci numbers in an array (Hand-In)
    
    OOP Basics:
    (Demo Video   Example Project)
    OOP Encapsulation:
    (Demo Video   Example Project)
     
11. Review: Variable Scope (class, instance, local/param vars) (Hand-In)
    Feedback: Explain when to use each
     
12. 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.)
     
13. Review: Class Composition: Circle Class (Hand-In)
     
14. Review:Circle class: Overlap method
     
15. Review: Arrays of Simple Types (Hand-In)
      
16. SmartArray Overview
    VIDEO: SmartArray overview
    
    
17. Basic SmartArray Class (Hand-In)
    Feedback: More detailed video on this, and onwards
     
18. Web Hand-In for pre-class exercises and homework:
    Go to the StudentTracker web app, and create an account for yourself, and then enroll in the course.
    Once you've created an account/enrolled, you can use this direct link to this, specific class: http://panitzco.com/CCC/StudentTracker/course_students/display/2 
    
    Feedback: More review on OOP stuff - inheritance, polymorphism?

Individual Pre-Class Exercises:
< Due: Friday, Apr 10, by noon>
Fair amount of confusion/lack of confidence around enums

1. 'Starter' project for the lesson 02 PCEs
   (Unless otherwise stated, put exercises into the PCE_Starter project)
   Array of Ints is still here, but has no directions - remove? Also enums in same project
    
2. How to use a debugger: Intro
    

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

4. Define the ErrorCode Enum (Hand-In)
   Make the distinction between constnats & enums more clear
    

5. Using the ErrorCode Enum (Hand-In)
    

6. Review: Big "Oh" Notation  (Hand-In)
   VIDEO: Big "Oh" notation review
   Feedback: Exercise: Give 5 different types of routines, match them to their O(N) notation time
   
   
   VIDEO: Abstract Data Types, Stack, Queue, Basic Generics
   (You should watch up to the part about Stacks, then stop)
   No one needs a 40 minute video about stacks :)
   
   

7. Figure out what a stack is  (Hand-In)
    
8. Preview: Using the .Net FCL Stack (Hand-In)
   Find a useful purpose for the stack?
    
9. 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
   (Not doing this will result in a point penalty)
   
   

10. Familiarize yourself with NUnit-based 'autograded' exercises:
    Note that NONE OF THESE WILL BE GRADED this week, but starting next week, you will be required to use these for your weekly exercises.
    Your Goal: Understand, and try out, enough of this so that you can ask good questions in class, and then use this in PCE03
    Slides (used in the following NUnit videos)

    Video: What is Unit Testing?
    (The bold-faced videos are expected to be especially helpful)
    
    Video: Overview of NUnit, Autograding in this class ; A couple of helpful tricks
    (These non-bold faced videos are good background)
    
    Video: Suggested Workflow ( "How you'll use NUnit, in this class" )

    Video: How the sample solution is set up
    Video: Details of using the GUI test runner program
    Video: Details of AutoGrader
    Video: Details of using the Debugger

    
    Starter project for the below videos and exercises (yes, this is separate from the above starter project.  You do NOT need to hand this one in)

    Video: Source Code Basics

    Exercise: Make failing tests pass

    Video: Basic Unit Tests

    Exercise: Making a basic unit test pass

    Video: I/O Redirection

    Exercise: Fixing broken output

    Video: Debugging Using 'Print' statements

    Exercise: Fahrenheit to Celsius

    
    Only watch these once you've run into a test that uses them:

    Video: [Values] Attribute

    Video: [TestCase] Attribute

    Video: [SetUp] Attribute & per-test setup

    
     
11. PCE Feedback (Hand-In)
    
     

In-Class Exercises:
<Class Date: Wednesday, April 1>

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

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

Videos:

1. First day's lecture: Overall orientation to BIT 142/143
2. StudentTracker (how to create an account & brief overview)
3. What is a Visual Studio Project? (brief overview)
4. How to work in this class
   (how to download, extract and open a project,
   make use of the exercise documents,
   prepare, .ZIP, and hand in your homework)
   
   
5. OOP review for 143
6. SmartArray overview
   
7. enums (overview)
8. Big "Oh" notation review

In-Class Exercises:
<Class Date: Wednesday, April 8>
 

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

Video:

• Intro, due dates, etc

Review:

1. Enums in detail
2. Bitwise enums
3. OOP review

Preview:

1. Slideshow: Stack ADT
2. Using A Stack: Detecting Palindromes
    
3. Preview: Using the .Net FCL Stack (running time)
    
4. Specifying the Queue ADT
    
5. Generics (quick overview)
   Example Code
    
6. Inheritance: Specializing a base class

Assignment 2 (Due: April 29)

(Due during week #5)

Individual Pre-Class Exercises:
<Due:  Friday, Apr 17, by noon>

VIDEO: Abstract Data Types, Stack, Queue, Basic Generics

1. 'Starter' project for the lesson 03 PCEs
   Don't forget to delete bin/obj/DELETETHIS..
   before handing this in!!!
   
   TODO: No tests for isFull
   
   

2. OOP Inheritance (Specialization):
   (Demo Video   Example Project)
   Feedback: Emphasize ': base()' syntax for constructors
    

3. StackOfInts as specialized SmartArray (Hand-In)
   Feedback: SmartArray.Print needs to be changed, in order to pass NUnit?
   Feedback: Clarify that you should inherit from SmartArray, NOT re-implement methods
    

4. QueueOfIntegers as specialized SmartArray    (Hand-In)
   ERROR: SOLUTOIN LEFT IN STARTER PROJECT
   Feedback: More details on how to implement the circular queue?
    

5. Stack / Queue: Annotate with Running Time (Hand-In)
   
   

6. SmartArray: Manually resizing (Hand-In)
   TODO: Left solution in starter project?
   Feedback: Quick note about errors non-protectedrgNums will cause?
   
   

7. 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.
   
   

8. Basic, Generic class (Hand-In)
   Feedback: Explain why we'd use this.  1-line summary: for collections
   IDEA: Have them re-do the SmartArray with generics?  Then roll into a generic LL in PCE 04
    

9. PCE Feedback (Hand-In)

Feedback: Maybe have an 'add to end' routine?
IDEA:  cover nested classes here, or in PCE 02, so we can use them here?
Feedback: Minimum of 5 elements caused problems - emphasize and/or remove?

Feedback: Motivation for why we're learning what we're learning?
Feedback: Like the quiz - exercise where code is given, and tell what it prints?

1. 'Starter' project for the lesson 04 PCEs
   Don't forget to delete bin/obj/DELETETHIS... before handing this in!!!
    

2. Reference Types vs. Value (Simple) Types
    

3. Linked List Of Ints: Add to Front   (Hand-In)
   VIDEO: TDD, Linked List basics, Add To Front
   (Sect. 24.3, 24.4)
    
4. Linked List Of Ints: Traversing      (Hand-In)
   VIDEO: Linked List: Print All (Traverse ALL)
   (Sect. 24.4 - 'Print' )
    
5. Linked List Of Ints: Remove From Front (Sect. 24.4) (Hand-In)
   VIDEO: RemoveFromFront

   Feedback: Clarify: Null reference should be checked for

    
6. LL: Printing at a specific location (Hand-In)
   VIDEO: Linked Lists: InsertAt
   

   Feedback: Test specifies PrintAll instead of PrintAt?
   Feedback: Video is about InsertAt, not PrintAt - PrintAt video?
   

7. SmartArray: Alloc on demand (Hand-In)
   Feedback: Clarify: Inherit from prior one, or re-implement?

    

8. PCE Feedback (Hand-In)

Videos:

1. Intro & Overhead: Due dates, new assignments, etc, etc

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: Print At Index

Extra-Challenging Questions/Exercises:

• Reverse a linked list
• Examine what a 'skip list' is:
  Research online what a 'skip list' is, including what operations it supports (like add, remove, find, etc).  For each operation, find what the expected running time is.  Also find the expected running time for a comparable operation on a normal linked list.  Be ready to explain all of this, and also be to be ready to explain (intuitively) how skip lists are implemented.

Videos:

1. Intro ("What's due when")
2. Nested Classes
3. Linked Lists: InsertAt
4. Linked Lists: RemoveAt
5. Linked List Schema: Traversal

Review:

1. Interfaces, IEnumerable
    
2. Linked List stuff

Preview:

1. LL: Insert by location/index
2. LL: Remove by location/index
    
3. LL: Running time
    
4. LL: Insert by value, in order
5. LL: Remove by value, in order
    
6. Strategies for LL: Clone
    

1. Generics for general-purpose ADTs
   Generic Linked List
    

2. Objectifying the Linked List Code
   • Linked_List_Starter.zip -Starter Project for Add/Remove exercises

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

No more generics

Assignment 3 (Due: Weds May 13)

(Due during week #7)

Individual Pre-Class Exercises:

<Due: Friday, May 8, by noon

no penalty until May 15 >
(There is no penalty for handing this lesson's PCEs in until Nov 5- you are still responsible for knowing the material on the midterm exam!)

Feedback: Exercise ideas for recursion: Conway's Game Of Life, 'Ant Walk', making a Mandelbrot set, etc.

Feedback: More on the running time of recursive methods?
Feedback: Helper functions: be clear about when this is spelled out, vs. when students need to make this decision on their own.

Feedback: Exercises to ID / select base case?
Feedback: Recursion with multiple parameters? With odd (array) parameters?
Feedback: Challenging recursive fucntions?

1. Review for the exam!!! 
   Midterm Exam Topics

   
   

2. 'Starter' project for the lesson 06 PCEs
   
   

3. Recursion
   (Note that this was formerly in Lesson 09 in BIT 142, so if you've taken 142, then this will be review)
   VIDEO: Recursion Mechanics (Review from 142)
    
4. Recursion By hand: Warm-up #1
   
5. Recursion By hand: Warm-up #2
   TODO: Repackage the printable recursion docs
   
   
6. Recursively Printing Numbers 1 - 10
   VIDEO: Recursion Coding Strategies
   
   
7. Recursively Printing Even Numbers (Hand-In)
   Feedback: Emphasize the nit-picky output checking ("Argument: 0" vs. "0")
   
   

8. Recursively Printing Even Numbers, Verified
   (This is a new type of test that I'm trying out - if it's confusing or you're having problems, please look for help ASAP - on the Google Group, from the instructor, etc, etc!!)
   TODO: Fix this!!  Need to check that the values seen correspond to some subset of those specified
   Feedback: Quick video/doc explaining what this is, and how 'virtual' works?

   
   

9. Recursive Power Function
   Video: Recursion (Basic Coding Strategies)
   
   
10. Recursive Multiplication (Hand-In)
    Video: Recursion Coding Strategies
    Feedback: Video is 53 seconds long - error?
    

     
    

11. Write Factorial
     
12. Fibonacci Numbers (And Arrays!)
    Feedback: A little bit strange - not a lot of material online
    

    
    

13. Print a singly linked list recursively (Hand-In)

    Feedback: if the test fails you give no information!!!!
    
    

14. PCE Feedback (Hand-In)
    

Midterm Exam: Q+A & Review

1. Print a singly linked list recursively
2. Add to a singly linked list, recursively
3. Remove from a singly linked list, recursively
   
   
4. Queue implemented via Linked List
    
5. Doubly-linked list
   

Midterm Exam: Q+A & Review

< MIDTERM EXAM>

1. 'Starter' project for the lesson 07 PCEs
   
   
2. Link to BIT 142's Recursion Material
   Feedback: Dup from a couple of lessons back?
    
3. Compare & Contrast Two Pow implementations (Hand-In)
   Video: BigOh Applied To Space & Time
     
4. Binary Search Tree preview (Required)
          (Textbook: Chapter 24, Section 7)
   Feedback: Wrong textbook section?
   Video: BST Overview
    
5. BST: Add   (coded in C#) (Hand-In)
   Note: How do the NUnit tests verify that your BST is working?
   Video: BST Basic Class Definitions
   Video: BST.Add
   (You will probably need to watch the video for the 'Find' method (below) first)
    
6. BST: Find   (coded in C#) (Hand-In)
   Note: Where do the tests create the tree?  
   Video: BST.Find
   BUG: This really should be covered before Add - maybe hard-code a tree into the starter, to bootstrap Find?
   Feedback: Find vs. FindR wasn't clear - emphasize that this is the 'iterative' lesson
   
   
7. PCE Feedback (Hand-In)

Individual Pre-Class Exercises:
<Due: Friday, May 22, by noon>
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?
Feedback: Make it clear what individual tests require from previous lessons; make it clear that the best way to go is to copy over the stuff from the prior lesson & add onto it.

1. 'Starter' project for the lesson 08 PCEs
   
   
2. BST: Print  (coded in C#, using recursion) (Hand-In)
   Video: BST: Print
   Feedback: Make it clear what the pre-reqs are - these tests required that Add already works (?)
   Feedback: Broaden scope - try pre/in/post order traversal?
   
   
3. BST: Recursive Find (Hand-In)
   Video: BST: Patterns
   Feedback: NOTE that this requires the Find (not FindR) method to be working!!
   Feedback: Find vs. FindR wasn't clear - emphasize that this is the 'recursive' lesson
   
   
4. BST: Recursive Add (Hand-In)
   Feedback: This mentions a video, but there isn't one here
   Feedback: Video leaves out the 'if(top == null)' logic?
   
   
5. BST:Print Beneath Node
   
   
6. BST: Remove preview
   Video: BST: Remove (Overview)
   
   
7. BST: Remove By Hand
   Feedback: More detail on what needs to be done - maybe a quick demo of a similar exercise?
   Feedback: Because trees will vary based on removal of predecessor/successor.  Maybe pick one?
   
   
8. BST: PrintIterative (coded in C#, using iteration) (Very optional)
   Note: This is extra-challenging.  Try it briefly, give it some thought, but don't spend more than 20-30 minutes thinking about this.  If we have time, we'll look at this in more detail in class.
   
   
9. PCE Feedback (Hand-In)

In-Class Exercises:
<Class Date: Wednesday, May 13 >

Exercises:

1. Discuss the Pow implementations
2. BST: Find, Add by hand
   
3. BST: Add   (coded in C#)
   

In-Class Activities:

1. Quiz
   
2. JigSaw: 
   Break into groups of four.  Pair up within the group, and have 1 pair solve each of:
   PrintIterative
   PrintBeneathNode
   When you're done, share your answer with the other pair.
   
3. BST: ReverseTree
   
4. Extra Super Challenge:
   Flattening A BST

Notes: PrintBeneath was fairly easy, but has a nice 'compose it out of Find+Print' thing going on.  Perhaps do NOT put these into the PCEs?
PrintIterative was WAAAAAAY too difficult.  It also unbalanced the jigsaw.
What about something like "CopyToLinkedList" - all the data from nodes that meet a certain criteria are copied into a LL?

1. NUnit 'Starter' project for the lesson 09 PCEs
   Feedback:
   
   
2. Video: Remove From A BST (Concepts)
   
   
3. Video: Explaining code details of BST-Remove
   
   
4. BST: FindAndRemoveNextSmaller (in C#) (Hand-In)
    
5. BST: Remove (coded in C#) (Hand-In)
   Feedback: RemoveRoot, NonRoot are too similar to really need both
    
6. Preview: QuickSort
   Video: QuickSort (2008 Spring)

   QuickSort SlideShow (this are the same slides used in the above video)

   Feedback: 'preview' link is dead?
   
   
7. For a fun, visual demonstration of different sorting algorithms:
   http://www.sorting-algorithms.com/
   
8. QuickSort: Partition (Hand-In)
   Feedback: Several people commented on how tricky this was.
   
   
9. QuickSort: Implementing QuickSort (Hand-In)
   Feedback: More feedback from NUnit
   

10. PCE Feedback (Hand-In)
    

1. Final Exam: Q+A & Review
   

2. 'Starter' project for the lesson 10 PCEs
   
   

3. Preview: MergeSort
   Feedback: pros/cons of MergeSort vs. other sorts?
   
   

4. Implementing Merge (Hand-In)
   Video: Merge Intuition
   Video: Merge (as typically used in MergeSort)    
   
   

5. Implementing MergeSort (Hand-In)
   Video: MergeSort page link broken
   Feedback: TEST_ isn't clear - does it also use Merge or not?
   
   

6. PCE Feedback (Hand-In)

CIEs:
1.      Go to: http://assessment.cascadia.edu or http://assessment.cascadia.edu/cie/default.aspx

2.      *Enter your SID and Pin #

3.      Select the class from the drop down menu

4.      Click on the Start Evaluation button

5.      Fill out and submit the survey

Q+A: BST.Remove (also A4)

1. <No exercises for this section>

QuickSort

1. Partition: By Hand

2. QuickSort: By Hand

3. QuickSort: Running Times

4. QuickSort variation: Random pivot
   IDEA: QS by hand: do partition, then circle the side you're working with, then only copy that side into the next row down?
   

MergeSort

1. MergeSort: Merging Arrays By Hand

2. Implementing MergeSort

Videos:

1. Intro / Overheat (Part 1)
2. Intro / Overheat (Part 2)

QS IDEA: Find a couple different implementations, inject errors & get them to find the errors?

OBSER: Very few people caught/fixed the error with left starting 1 too high.

1. Quiz
   

2. Final Exam: Q+A & Review
   

3. Algorithms: Table of Time & Space
   
   (Solution) - link will be made live later
   

4. Algorithms: Scenarios
   

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

2. Jeff & Joe's  Mergesort Slides
    

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

4. MergeSort: Western Kentuckey U Sample

1. Final Exam: Q+A & Review

1. <Final Exam>

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
Monday, April 6, by NOON	Email the professor, so that the professor has your email address
Monday, April 6, by NOON	PCE 01
Friday, Apr 10, by noon	Google Group: Sign yourself up, post a question, answer someone else's question:
Friday, Apr 10, by noon	PCE 02
Wednesday, April 15, by the start of class	A1 (initial version)
Friday, Apr 17, by noon	PCE 03
Friday, Apr 24, by noon	PCE 04
TBA	A1 (final, revised version)
Wednesday, April 29, by the start of class	A2 (initial version)
Friday, May 1, by noon	PCE 05
Wednesday, May 6	MIDTERM  EXAM
Friday, May 8, by noon (no penalty until May 15)	PCE 06
Wednesday, May 13, by the start of class	A3 (initial version)
Friday, May 15, by noon	PCE 07
TBA	A2 (final, revised version)
Friday, May 22, by noon	PCE 08
Wednesday, May 27, by the start of class	A4 (initial version)
TBA	A3 (final, revised version)
Friday, May 29, by noon	PCE 09
TBA	A4 (final, revised version)
Friday, June 5, by noon	PCE 10
Wednesday, June 3, by the start of class	Final Date To Hand In Any homeworks, revisions to homeworks, or PCEs (except PCE 11)
Friday, June 12, by noon	PCE 11
Wednesday, June 10	FINAL  EXAM

Back to BIT 143's homepage

Unused Lecture Material NUnit_ORIG Map

BIT 142's Lessons Page