BIT 143:Programming - Data Structures (2007 Spring)

Lessons

Assignment 1 (DUE: Mon, April 9)

Individual Pre-Class Exercises:
<Due: Apr 2 - Monday , SECOND week of the class>

1. Get Visual Studio 2005
2. Orient yourself to BIT 143
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. Console I/O, Operators (Chapter 3) (Hand-In)
   
   Semi-Optional Exercises:
7. Fahrenheit to Celsius
8. Nested Loops: Rectangles
9. Nested Loops: Hollow Rectangles
10. Fibonacci numbers in an array (Hand-In)
    
    OOP Basics:
    (Demo Video   Example Project)
    OOP Encapsulation:
    (Demo Video   Example Project)
     
11. Designing a class: Circle (Hand-In)
    (Ignore the stuff about the Point class)
     
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. Circle class: Overlap method (Hand-In)
     
14. How to hand in pre-class exercises  and homework

Individual Pre-Class Exercises:
<Due: April 2 (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)

Individual Pre-Class Exercises:
<Due: April 9th (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

In-Class Exercises:
<Class Date: Mar 26th - MONDAY,
then again on Mar 28th - WEDNESDAY>

(This class meets TWICE during the first week ;
it meets ONCE A WEEK thereafter)

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

In-Class Exercises:
<Class Date: April 2 (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. Test-driven development:
   Implementing a stack of circles
    
2. Stack of Simple Types vs. Reference Types
    
3. Linked List Of Ints: Basics (Sect. 24.4)
4. Linked List Of Ints: Add to the Front
   (Sect. 24.4)
5. Linked List Of Ints: Traversing (Hand-In)
   (Sect. 24.4 - 'Print' )
    
6. Preview: Interfaces, IEnumerable

Assignment 2 (Due Weds, April 25th)

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
   TODO: Remove the 'class' part for VNext
    
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                                           (Hand-In)

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
    

Individual Pre-Class Exercises:
<Due: May 7th  (Monday)>
 

1. Review for the exam
    

2. Keyed Generic Linked List & default values of generic types (Hand-In)
    
3. KeyedSmartArray (structs vs. classes)
   Are these two out of order?

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. How to use a debugger
    
6. LL: Insert by value, in order
7. LL: Remove by value, in order
    

8. Generics for general-purpose ADTs
   Generic Linked List
    

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

1. Midterm Exam: Q+A & Review
    
2. Queue implemented via Linked List
    
3. Doubly-linked list
    

4. OOP 'Interface' idea - Dictionary type
   implemented by SmartArray, LinkedList
    

5. Polymorphism (for general-purpose ADTs)
    

6. Basic polymorphsim
   Polymorphism (for general-purpose ADTs)
   (move to later?)
    

7. Recursion: What does it print?

8. Recursion By hand: More Complicated
    
9. Review: Recursion By hand: Warm-up (Hand-In)
    
10. String & Object counting?
    Count up the allocated objects?
     

11. OOP Inheritance
    (Abstracting Commonalities)
    (Stack/Queue Commonalities?)
     

12. OOP 'Interface' idea - Dictionary type
    implemented by SmartArray, LinkedList

<Midterm Exam>

1. Recursion: What does it print?
2. Recursion By hand: More Complicated

Assignment 3 (Due: Weds, May 2nd)

Assignment 4 (Due Weds, May 16th)

1. Link to BIT 142's Recursion Material
    
2. Compare & Contrast Two Pow implementations (Hand-In)
    
3. LL/Re: Print a singly linked list recursively
4. LL/Stack:  Print a singly linked
   list iteratively, backwards (Hand-In)
    
5. Binary Search Tree preview (Required)
6. Binary Search Tree: Class Definitions (Hand-In)
    
7. Nested Classes

1. BST: Remove preview

2. BST: Remove By Hand
3. BST: Remove (coded in C#) (Hand-In)
    
4. Static constructors
5. Generics: Def of "constructed type"
6. Generic types & static variables (Hand-In)
   1. Review: Unique IDs from static vars
       
7. Explicit interface implementation (Hand-In)

1. Sorting & Searching: setup for the class
    

2. BST: Remove (coded in C#) (Hand-In)
    
3. Operator Overloading: BST Node (Hand-In)
    
4. Preview: MergeSort
    

5. Preview: QuickSort

In-Class Exercises:
<Class Date: May 7th (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

STUDENT SOLUTIONS:

• Iterative Insert/Add
• Recursive Find

1. BST: Remove By Hand
    
2. TODO: Present BST.Remove in pseudocode, with good modularization.  Perhaps have different students implement different parts & then plug it all together
    
3. BST: Find parent of next smaller (coded in C#)
   ( Starter Project )
    
4. BST: Find parent of next larger (coded in C#)
    
5. BST Remove (in lecture)
   Demo: BST Remove
    
6. Preview: MergeSort

1. Jeff & Joe's  Mergesort Slides
    

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

3. MergeSort: Western Kentuckey U Sample
    

4. <Break - panel discussion?>
    

5. SlideShow: QuickSort

6. QuickSort: By Hand

7. Implementing QuickSort
    

1. Implementing QuickSort (Hand-In)
    

2. Implementing MergeSort (Hand-In)

1. Review for the exam

1. NO CLASS ON THIS DAY!!

After some thought, I'd like to change the deadlines slightly:


What I'm thinking is that if you can hit the Wednesday deadline
for the original versions of the homework assignments, then I'll
definitely be able to get the homeworks graded by that weekend (or at  latest, on Saturday). I'd like for people to have a chance to do a  revision, which tends to be quicker to grade, so I'd be happy to  accept revisions of homework assignments (and only the revisions) up  till Wednesday, June 6th, at 5pm.
For the PCEs, getting them in to me by Friday (midnight) should
work, so that I can grade them over the weekend.


I think this should work for everyone - let me know ASAP if you have any questions / concerns!
 

1. <Final Exam>

Back to BIT 143's homepage

Unused Lecture Material

BIT 142's Lessons Page