BIT 143:Programming - Data Structures (2007 Fall)

Lessons

Assignment 1 (DUE: Mon, Oct 8th)

Individual Pre-Class Exercises:
<Due:  Sept 29th   at noon PST
(FRIDAY of the FIRST week of class) >

1. Orient yourself to BIT 143
2. Get Visual Studio 2005
3. Join the class newsgroup ; (Required)
   Send the professor your email address
    
4. Create a simple console application    
                (Demo Video)
    
5. Single-file Demo for PCE's
6. Single-Solution Demo for PCE's
    
7. Console I/O, Operators (Chapter 3) (Hand-In)
   
   Semi-Optional Exercises:
8. Fahrenheit to Celsius
9. Nested Loops: Rectangles
10. Nested Loops: Hollow Rectangles
11. Fibonacci numbers in an array (Hand-In)
    
    OOP Basics:
    (Demo Video   Example Project)
    OOP Encapsulation:
    (Demo Video   Example Project)
     
12. Designing a class: Circle (Hand-In)
    (Ignore the stuff about the Point class)
     
13. 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.)
     
14. Circle class: Overlap method (Hand-In)
     
15. Email the instructor (MPanitz@cascadia.edu) with your Cascadia username, so that the instructor can create your Vault account.
     
16. Upload.php:  How to hand in pre-class exercises  and homework
     
17. PCE Feedback (Hand-In)
    (This will be graded)

Individual Pre-Class Exercises:
<Due: Oct 1 at noon PST (Monday) >

1. How to use a debugger: Intro
    
2. References  (Sample C# Project)
3. Arrays of Simple Types
    
4. SmartArray Overview
5. Basic SmartArray Class (Hand-In)
   (Starter Project)
    
6. Review: Big "Oh" Notation  (Hand-In)
    
7. Figure out what a stack is  (Hand-In)
8. Preview: Using the .Net FCL Stack (Hand-In)
    

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

10. Define the ErrorCode Enum (Hand-In)

11. Using the ErrorCode Enum (Hand-In)
    (Starter Project)
     

12. 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
     
13. PCE Feedback (Hand-In)
    (This will be graded)

Individual Pre-Class Exercises:
<Due: Oct 8th at noon PST (Monday) >

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

2. StackOfInts as specialized SmartArray
   (Starter Project)  (Hand-In)
    

3. QueueOfIntegers as specialized SmartArray
   (Starter Project)   (Hand-In)
    

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

5. SmartArray: Manually resizing
    

6. Figure out what Generics are

7. Basic, Generic class (Hand-In)
   Generics_Fillin.zip
    

8. PCE Feedback (Hand-In)
   (This will be graded)

Feedback: TDD tests are jumbled, and confusing to read.  Perhaps better to have 1 method per test, which sets up and tears down everything it needs?  It'll be easier to ID what has failed.

Feedback: Make use of NUnit?

In-Class Exercises:
<Class Date: Sept 24th  (Monday) >

(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 hand in pre-class exercises
   and homework
    
6. How to use a debugger
    
7. Basic class design

In-Class Exercises:
<Class Date: Oct 1 (Monday) >

Review:

1. Enums in detail
2. Bitwise enums

Preview:

1. Slideshow: Stack ADT
2. Using A Stack: Detecting Palindromes
    
3. Stacks: Running Time
    
4. Specifying the Queue ADT
    
5. Generics (quick overview)
    
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: Basics (Sect. 24.3, 24.4)
4. Linked List Of Ints: Add to the Front 
   (Sect. 24.4)
5. Linked List Of Ints: Traversing  (Sect. 24.4)
    
6. Preview: Interfaces, IEnumerable

Assignment 2 (Due: Mon, Oct 22)

1. SmartArray: Alloc on demand
    

2. Test-driven development: Implementing a stack of Circles                             (Hand-In)
   1. (It may be helpful to refer back to
      Stack of Simple Types vs. Reference Types)
       
3. Linked List Of Ints: Basics (Sect. 24.3, 24.4)
    
4. Linked List Of Ints: Add to Front   (Hand-In)
   (Sect. 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: Refactor into a Stack class
    
8. Additional StackLL Features
    
9. LL: Printing at a specific location
   (Try your best on this, but don't worry if you end up getting stuck)
    

10. Discovery of Interfaces: IEnumerable & Arrays        (Try your best on this,
    but don't worry if you end up getting stuck)
     

11. PCE Feedback (Hand-In)
    (This will be graded)

1. Objectifying the Linked List Code
   • Linked_List_Starter.zip -Starter Project for Add/Remove exercises
      
2. Generic Linked List (Hand-In)
    
3. IEnumerable & Linked Lists (Hand-In)
   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?
    
4. PCE Feedback (Hand-In)
   (This will be graded)

Individual Pre-Class Exercises:
<Due: Oct 29th  (Mon) before 8 pm  (PST)  >
 

1. Review for the exam
    

2. KeyedSmartArray (structs vs. classes)
    
3. Keyed Generic Linked List & default values of generic types (Hand-In)
   Feedback: Make it clear exactly what functions students need to implement for this exercise
    
4. PCE Feedback (Hand-In)
   (This will be graded)
   (Light green highlight means you don't have to do this 2007Fa)
    

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. Queue implemented via Linked List
    
3. Doubly-linked list
    

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

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

6. Recursion By hand: More Complicated
    
7. Recursively Printing Even Numbers
    
8. Print a singly linked list recursively
9. Add to a singly linked list, recursively
10. Remove from a singly linked list, recursively

<Midterm Exam>

1. A3 Skills pre-test
    
2. Study Opt-Out
    

Recursion: What does it print?

Recursion By hand: More Complicated

Assignment 3 (Due: Mon, Nov 5th)

Assignment 4 (Due Mon, Nov 19th)

1. Link to BIT 142's Recursion Material
    
2. Compare & Contrast Two Pow implementations (Hand-In)
   Feedback: didn’t understand what you wanted when you said “figure out how much space each implementation uses”.
    
3. LL/Re: Print a singly linked list recursively
   Feedback: maybe a video of a similar recursion print technique or more of a walk through?
4. LL/Stack:  Print a singly linked
   list iteratively, backwards (Hand-In)
   Feedback: specify that 'iteratively' means 'using a loop'
   Feedback: Maybe provide some starter files?  Troubles using/finding a prefab stack class?
   Feedback: more clear about what one time actions are in the public Print method.
    
5. Binary Search Tree preview (Required)
6. Binary Search Tree: Class Definitions
   (Hand-In)
   Feedback: didn't get much out of this - it should be all or nothing
   Feedback: Make it clear exactly what they're supposed to turn in - a complete BST, or just a framework? *** Several people implemented everything for this, rather than just doing the data definitions
    
7. Nested Classes
   Feedback: Move this so it' earlier in the term?
   Feedback: I think it was a little simpler than the explanation made it sound.
    
8. A3 Pre-test
   (+2 extra credit points for doing this (regardless of how you do on it); -10 for not doing it)(It must be done before you start A3)
    
9. Study Opt-Out
   (You need to read this; there is no 'work' for you to do here)
   (You should NOT inform the instructor if you choose to opt out!!!)
    
10. PCE Feedback (Hand-In)
    (This will be graded)

Individual Pre-Class Exercises:
<Due: Nov 12th  (Mon) before 8 pm  (PST)
VETERAN'S DAY - CASCADIA CLOSED

1. BST: Remove preview
    

2. Static constructors
3. Generics: Def of "constructed type"
4. Generic types & static variables (Hand-In)
   1. Review: Unique IDs from static vars
   Feedback: Be more clear about what needs to be done here This comment was made about 5-6 times - FIX THIS!!!
   Feedback: Add regular constructors in, too, and specify the order in which they're called
   
   
5. Explicit interface implementation (Hand-In)
   Feedback: explain what's important about this - why do we care?
   Feedback: point out syntactic differences, specifically not having the public/private thing for explicitly implemented interfaces
   Feedback: Clarify what I mean by the bool parameter to an internal method - perhaps even just add that to the starting template?  This caused a lot of questions...
    
6. A2 Skills post-test (Hand-In)
   A2 Attitude Survey (Required - this is an online survey, so you won't 'hand in' anything)
    
7. A4 Skills pre-test Hand-In)
    
8. PCE Feedback (Hand-In)
   (This will be graded)

1. BST: Remove (coded in C#) (Hand-In)
   Feedback: Provide more hints?
   Feedback: Video was really helpful for this
   Feedback: Starter code was too helpful, since a lot of it was already implemented?
    
2. Operator Overloading: BST Node (Hand-In)
   Feedback: Be more clear about whether students should build off of previous BSTs, or use the one in this document... x2
   Feedback: More examples?
   Feedback: It's a bit tricky to find online examples in C#
   Feedback: maybe more on the syntax of overloading operators
    
3. Sorting & Searching: setup for the in-class exercises  (Hand-In)
   Feedback: Be more clear about why we're doing this (prep for next lecture), and that Yes, this is intended to be really easy
    
4. Preview: MergeSort
    

5. Preview: QuickSort
    

6. PCE Feedback (Hand-In)
   (This will be graded)

In-Class Exercises:
<Class Date: Nov 5th (Monday) >

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
    
7. A2 Skills post-test
   A2 Attitude Survey
    
8. A4 Skills pre-test

STUDENT SOLUTIONS:

• Iterative Insert/Add
• Recursive Find

LECTURE RECORDINGS:

• Opening remarks / general info
• BST - Add

1. <Video: Due dates, etc, etc>
    
2. <Video: Explanation of BST-Remove>
    
3. BST: Remove By Hand
    
4. <Video: Explaining code details of BST-Remove>
   Demo: BST RemoveRootNode
    
5. BST: FindAndRemoveNextSmaller (in C#)
   <Starter Project> (same as previous demo)
    
6. BST: RemoveInternalNode (coded in C#)
    
7. Preview: MergeSort

1. A3 Skills post-test
   A3 Attitude Survey
    

2. SlideShow: QuickSort

3. QuickSort: By Hand

4. Implementing QuickSort
    

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

1. Implementing QuickSort (Hand-In)
   Feedback: All the code for this is in the slides from the previous lecture - either hide some code, and/or supplement these exercises?
    

2. Implementing MergeSort
    
3. A3 Skills post-test (Hand-In - email to your instructor no later than Friday, Dec 2nd at 5pm)
   A3 Attitude Survey (Required - this is an online survey, so you won't 'hand in' anything) (finish this by Friday, Dec 2nd, 5pm)
    
4. PCE Feedback (Hand-In)
   (This will be graded)

1. Review for the exam
    
2. Overall course feedback
    
3. Implementing MergeSort (Hand-In)
   
    
4. A4 Skills post-test (Hand-In - email to your instructor no later than Monday, Dec 3rd at 5pm)
   A4 Attitude Survey (Required - this is an online survey, so you won't 'hand in' anything) (finish this by Monday, Dec 3rd, at 5pm)

1. UWB-CSS presentation
    

2. CIEs!
    

3. A4 Skills post-test
   A4 Attitude Survey
    

4. Quizzes, then Final Exam: Q+A & Review
    

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>

Back to BIT 143's homepage

Unused Lecture Material

BIT 142's Lessons Page