|
CS1 ( Catch A Falling Object (XNA) ; Helpdesk (Console) ) |
Key Topics That Students Will
Learn In This Assignment:
|
|
Pre-requisite Knowledge
That Students Must Know, Prior To Starting This Assignment: (What students must know in order to able to complete this assignment) |
|
Summary |
The students will create a Linked List class that they will use as a
Queue (meaning that they don't need to manipulate any linked list
nodes other than the first & last). For the Console version, the students are given a partially completed Helpdesk program, wherein the user is allowed to enter new tickets into a Queue of helpdesk jobs. The oldest helpdesk job is resolved next ; upon resolution, the ticket is discarded (i.e., it's not archived anywhere). The twist is that tickets may be 'low' priority, or 'high' priority. All the tickets in a given priority are (effectively) stored in their own queue, so that the oldest high priority ticket is resolved before any low priority tickets are resolved. The example solution contains examples of two common styles of solution (1) a single list of Ticket objects that's divided into 'high priority' and 'low priority' regions (2) and a class that uses two linked list helper objects, one for each priority. IMPORTANT INSTRUCTOR NOTE: the first style (a single list) isn't really a pure Queue (which normally allows for insertions only at one end, and deletions at the other end). If you're ok with this, then you should make sure to update the rubric that you hand out to students accordingly. For the XNA version, the students are given a mostly game, wherein the user is allowed to create new Toys in a Queue, where a Toy is either a high-priority Animal, or a low-priority Tool. The Queue is displayed across the top of the screen, and the player controls a box that can slide from side to side at the bottom of the screen in an attempt to catch the Toys, as they fall from the top of the screen. When the currently Toy leaves the screen (either by being caught by the player, or by moving past the bottom of the screen), the oldest Toy in the queue is activated, by dropping it from the top of the screen.. The twist is that Toys may be 'low' speed (the Tools), or 'high' speed (the Animals). All the Toys of a given speed are (effectively) stored in their own queue, so that the oldest high speed Toy (an Animal) is activated before any low speed Toys (a Tool) are activated. |
Instructor F.A.Q. | |
Pre-Test | Post-Test |
Lecture Hours Prior To Assignment Due Date: | 10-20 |
ACM Classification (Topics Covered): (What the students will learn, and demonstrate, by doing this assignment)
From: Computing Curricula 2001 Computer Science — Final Report —
The Joint Task Force on Computing Curricula
|
PF1. Fundamental programming constructs
PF3. Fundamental data structures
PL6. Object-oriented programming
AL1: Basic algorithmic analysis
|
Technical Requirements:
(What the students will learn, and demonstrate, by doing this assignment)
From: Computing Curricula 2001 Computer Science — Final Report —
The Joint Task Force on Computing Curricula
It is hoped that providing this information may help instructors with the accreditation process, as calling this information out will help clarify how this assignment (and from here, the overall course) meets the learning outcomes for the overall program/department, and institution. |
Programming Fundamentals: Fundamental programming constructs PF1.1 - Analyze and explain the behavior of simple programs involving the fundamental programming constructs covered by this unit. Since the students are given the existing code, but aren't given a detailed explanation for how it works, they will have to demonstrate that they have developed an understanding of the program by extending it
PF1.2 - Modify and expand short programs that
use standard conditional and iterative control structures and
functions. PF1.3 - Design, implement, test, and debug a
program that uses each of the following fundamental programming constructs: basic
computation, simple I/O, standard conditional and iterative
structures, and the definition of functions.
PF1.4 - Choose appropriate conditional and iteration constructs for a given programming task. It will be impossible to complete the assignment without this.
PF1.5 - Apply the techniques of structured (functional) decomposition to break a program into smaller pieces. This is largely provided to the students, in the sense that there isn't a lot of extra functions needed. However, they do need to be able comprehend the existing structure of the provided code, including the functional decomposition inherent in that design.
Programming Fundamentals:: Fundamental data structures PF3.2 - Describe how the data structures in the topic list are allocated and used in memory. This is largely provided to the students, in the sense that there isn't a lot of extra functions needed. However, they do need to be able comprehend the existing structure of the provided code, including the functional decomposition inherent in that design.
PF3.4 - Implement the user-defined data structures in a high-level language. The focus of the assignment is to implement a queue, in C#, using a (student-created) linked list as the underlying implementation.
PF3.6 - Write programs that use each of the following data structures: arrays, records, strings, linked lists, stacks, queues, and hash tables. The focus of the assignment is to implement a queue, in C#, using a (student-created) linked list as the underlying implementation.
PF3.8 - Choose the appropriate data structure for modeling a given problem. The assignment is structured so that the word 'Queue' isn't used in the assignment, so that the students are forced to choose the appropriate data structure / Abstract Data Type for modeling the given problem.
Programming Languages: Object-Oriented Programming PL6.2 - Design, implement, test, and debug simple programs in an object-oriented programming language. This assignment requires the
students to understand and utilize encapsulation. PL6.3 - Describe how the class mechanism supports encapsulation and information hiding. The students are not directly
asked to describe this, but they are required to mark their data
fields / methods with the appropriate access restriction. Algorithms and Complexity: Basic algorithmic analysis AL1.3 - Determine the time and space complexity of simple algorithms. The students are (optionally) told to implement constant-time insert/delete operations on their queue (implemented as a linked list) using the Big 'Oh' notation, so they must be able to determine the time & space complexity of their implementation, in order to know if the implementation is in compliance with the constraints set forth in the homework assignment.
|