BIT 143:Programming - Data Structures (2009 Fall)

Lessons

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

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
    
    
17. Basic SmartArray Class (Hand-In)
     
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/3 

Individual Pre-Class Exercises:
< Due: Wednesday, Oct 7, by the start of class>

Feedback: Brief blurb explaining project layout?

1. 'Starter' project for the lesson 02 PCEs
   (Unless otherwise stated, put exercises into the PCE_Starter 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 and use the ErrorCode Enum (Hand-In)
   Feedback: Shouldn't mention lists/queues quite yet
    

5. Review: Big "Oh" Notation  (Hand-In)
   
   

6. Figure out what a stack is  (Hand-In)
    
7. Preview: Using the .Net FCL Stack (Hand-In)
   Feedback: Not really all that challenging
   Feedback: What should be done with the Peek method?
    
8. 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)
    
9. PCE Feedback (Hand-In)
   
    

In-Class Exercises:
<Class Date: Wednesday, Sep 30 >

(This class meets from 8:00pm -10:05pm every Wednesday, including this one)

Opt-out form

Pre-Course Survey

Videos:

1. Introduction
2. StudentTracker (how to create an account & brief overview)
3. What is a Visual Studio Project? (brief overview)
4. How to do the work for 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, Oct 7>
 

Videos:

1. Introduction
2. Stacks, Part 1
3. <Palindrome Exercise went here>
4. Stacks, Part 2
5. Queues
6. SmartArray Resize Tip
7. What is Unit Testing?

Preview:

NUnit!!

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: Oct 28)

(Due during week #5)

Individual Pre-Class Exercises:
<Due:  Wednesday, Oct 14, by the start of class>

Familiarize yourself with NUnit-based 'autograded' exercises:
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

Graded exercises for this week:
Feedback:Generics stuff in the PCEs needs to be removed
Feedback Double check that resizeable array has no solution code (done)

1. 'Starter' project for the lesson 03 PCEs
   Hand in just Student_Answers.cs  (and the feedback file)
   
   

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

3. StackOfInts as specialized SmartArray (Hand-In)
   Feedback topOfStack's purpose was confusing
   Feedback Printable stack/queue worksheet (like recursion) might be good
    

4. QueueOfIntegers as specialized SmartArray    (Hand-In)
   Feedback parameter description for en/dequeue for top&backOfStack was confusing
    

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

6. SmartArray: Manually resizing (Hand-In)
    

7. PCE Feedback (Hand-In)

Feedback: Maybe have an 'add to end' routine?
Feedback: Like the quiz - exercise where code is given, and tell what it prints?

Feedback: Is it ok to modify the container/List class to add stuff like counters, etc?  More than first pointer?

1. 'Starter' project for the lesson 04 PCEs
   Hand in just Student_Answers.cs  (and the feedback file)
    

2. Reference Types vs. Value (Simple) Types
    

3. Nested Classes: Basics (Required)
   Feedback: copy-and-paste instructions don't work b/c of name changes: MyIntList and IntListNode and not LinkedList and LinkedListNode
   
4. Linked List Of Ints: Add to Front   (Hand-In)
   (Sect. 24.3, 24.4)
    
5. Linked List Of Ints: Traversing      (Hand-In)
   (Sect. 24.4 - 'Print' )
    
6. Linked List Of Ints: Remove From Front (Sect. 24.4) (Hand-In)
    
7. LL: Printing at a specific location (Hand-In)
   Feedback: Video for this would be great
   

    

8. SmartArray: Alloc on demand (Hand-In)
   Feedback: several people had a lot of trouble getting these tests to pass
   Feedback: feedback on rgnums == null test failures, more feedback in general
    

9. PCE Feedback (Hand-In)

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

Videos:

1. Intro
2. Nested Classes (Car/Engine demo of details)
3. Linked Lists: Introduction of the overall ideas
4. Linked Lists: Basic Code Definitions
5. Linked Lists: Basic Code Definitions, Part 2
6. Linked Lists: AddAtFront
7. Linked Lists: PrintAll
8. Linked Lists: RemoveFromFront

Videos:

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

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.

Assignment 3 (Due: Weds Nov 11)

(Due during week #7)

1. 'Starter' project for the lesson 05 PCEs
    
2. Strategies for LL: Traversing A Linked List (Print, Find, PrintAllMatching)
   
3. LL: Insert At Location (Hand-In)
    
4. LL: Remove At Location (Hand-In)
   
   
5. LL: Running time (Hand-In)
    
6. LL: Insert by value, in order

    

7. LL: Remove by value, in order
   
   
8. Strategies for LL: Clone
   (Read this over and think about it - we'll go through it in class together)
   Feedback: AddToList isn't defined, or defined up till now
   Feedback: What you're not supposed to do is too vague
    
9. PCE Feedback (Hand-In)
   

Individual Pre-Class Exercises:

<Due: Wednesday, Nov 4, by the start of class

no penalty until Nov 11 >
(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!)

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

   
   

2. 'Starter' project for the lesson 06 PCEs
   Feedback: contains excess start code, including 'crashing recursion' - remove all of these
   
   

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: Tracing through recursion
    
4. Recursion By hand: Warm-up #1
   
5. Recursion By hand: Warm-up #2
   
   
6. Recursively Printing Numbers 1 - 10
   Feedback: Clarify that a parameter is expected
   VIDEO: Writing recursive code: Basic approach
   VIDEO: Writing recursive code: PowR example
   
   
7. Recursively Printing Even Numbers (Hand-In)
   
   

8. This item is left here for future revision, but NOT due during 2009 Fall
   Recursively Printing Even Numbers, Verified
   Feedback: Remove this
   (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
   
   
10. Recursive Multiplication (Hand-In)
    Feedback: Need for two methods not apparent at start
    

     
    

11. Write Factorial
     
12. Fibonacci Numbers (And Arrays!)
    Feedback: NUnit tests appear to be passing in spite of code?  What does return value do?
    

    
    

13. Print a singly linked list recursively (Hand-In)
    Feedback: This was a 'very hard' exercise, x2
    Feedback: Make it clear that two methods MIGHT be useful, or they might not be

    
    

14. PCE Feedback (Hand-In)
    

Midterm Exam: Q+A & Review

Videos:

1. Class intro
2. Tracing through recursion
3. Writing recursive code: Basic approach
4. Writing recursive code: PowR example

Unused:

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. Compare & Contrast Two Pow implementations (Hand-In)
   Video: BigOh Applied To Space & Time
   Feedback: People found this confusing - what was the recursive running time?
   
   (Link to BIT 142's Recursion Material)
     
3. Binary Search Tree preview (Required)
          (Textbook: Chapter 24, Section 7)
   Video: BST Overview
    
4. 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)
    
5. BST: Find   (coded in C#) (Hand-In)
   Note: Where do the tests create the tree?  
   Video: BST.Find
   
   
   
6. PCE Feedback (Hand-In)

Individual Pre-Class Exercises:
<Due: Wednesday, Nov 18, by the start of class>
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?

Note: Please do copy code from your prior lessons and paste it into this lesson, whenever you can reuse useful code.

1. 'Starter' project for the lesson 08 PCEs
   
   
2. BST: Print  (coded in C#, using recursion) (Hand-In)
   Video: BST: Print
   Feedback: Broaden scope - try pre/in/post order traversal?
   Feedback: Clarify that this needs to print in-order
   
   
3. BST: Recursive Find (Hand-In)
   Video: BST: Patterns
   
   
4. BST: Recursive Add (Hand-In)
   Video: Recursive Add
   Feedback: Should duplicates cause problems, or not?
   
   
5. BST:Print Beneath Node
   
   
6. BST: Remove preview (remove - this is in the next PCE)
   Video: BST: Remove (Overview)
   
   
7. BST: Remove By Hand (remove - in next PCE)
   Video: Exercise Explanation
   
   
8. BST: PrintIterative (coded in C#, using iteration) (Very optional)
   Note: This is extremely-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, Nov 11 >

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
   

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>

2. Video: Remove From A BST (Concepts)
3. Video: Explaining code details of BST-Remove

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
   
   
2. BST: Remove preview
   Video: BST: Remove (Overview) (2009 Fa)
   Video: BST: Remove (Overview) (2008 Fa)
   
   
3. BST: Remove By Hand
   Video: Exercise Explanation
   
   
4. BST: FindAndRemoveNextSmaller (in C#) (Hand-In)
    
5. BST: Remove (coded in C#) (Hand-In)
   Feedback: Both people that failed this test failed all the tests starting with 100_
   

6. PCE Feedback (Hand-In)
   

1. 'Starter' project for the lesson 10 PCEs
   
   
2. Preview: QuickSort
   Video: QuickSort: The Algorithm
   

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

   
   
3. For a fun, visual demonstration of different sorting algorithms:
   http://www.sorting-algorithms.com/
   
   
4. QuickSort: Partition (Hand-In)
   
   
5. QuickSort: Implementing QuickSort (Hand-In)
   
   
6. PCE Feedback (Hand-In)

Instructor's Materials:
Notes
Slides   

Videos:

1. Intro  (Part 1)
2. QuickSort: The Algorithm

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?
   

   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.

MergeSort

1. MergeSort: Merging Arrays By Hand

2. Implementing MergeSort

1. Final Exam: Q+A & Review
   
   

2. Algorithms: Table of Time & Space
   
   (Solution)
   
   

3. Algorithms: Scenarios
   

1. Final Exam: Q+A & Review

1. POST-course survey goes here DON'T FORGET TO DO THIS FOR BOTH 142 AND 143!!!!
   
   
2. <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, Oct 5, by NOON	Email the professor, so that the professor has your email address
Monday, Oct 5, by NOON	PCE 01
Wednesday, Oct 7, by the start of class	Google Group: Sign yourself up, post a question, answer someone else's question:
Wednesday, Oct 7, by the start of class	PCE 02
Wednesday, Oct 14, by the start of class	A1 (initial version)
Wednesday, Oct 14, by the start of class	PCE 03
Wednesday, Oct 21, by the start of class	PCE 04
TBA	A1 (final, revised version)
Wednesday, Oct 28, by the start of class	A2 (initial version)
Wednesday, Oct 28, by the start of class	PCE 05
Wednesday, Nov 4	MIDTERM  EXAM
Wednesday, Nov 4, by the start of class (no penalty until Nov 11)	PCE 06
Wednesday, Nov 11, by the start of class	A3 (initial version)
Wednesday, Nov 11, by the start of class	PCE 07
TBA	A2 (final, revised version)
Wednesday, Nov 18, by the start of class	PCE 08
Wednesday, Nov 25, by the start of class	A4 (initial version)
TBA	A3 (final, revised version)
Wednesday, Nov 25, by the start of class	PCE 09
TBA	A4 (final, revised version)
Wednesday, Dec 2, by the start of class	PCE 10
Wednesday, Dec 2, by the start of class	Final Date To Hand In Any homeworks, revisions to homeworks, or PCEs (except PCE 11)
Wednesday, Dec 9, by the start of class	PCE 11
Wednesday, Dec 9	FINAL  EXAM

Back to BIT 143's homepage

Unused Lecture Material NUnit_ORIG Map

BIT 142's Lessons Page