CS1                                               
Linked Lists and Queues

( Catch A Falling Object (XNA) ; Helpdesk  (Console) )

 
Key Topics That Students Will Learn In This Assignment:

 

  • Linked Lists (adding to/removing from the ends)
  • Queue (implemented using a linked list)
Pre-requisite Knowledge That Students Must Know, Prior To Starting This Assignment:

(What students must know in order to able to complete this assignment)

  • Simple/Primitive Variables: int, double (etc)
  • Operators
  • Flow Control: conditional selection (if statements)
  • Flow Control: iteration (loops)
  • Object-Oriented Programming
    • Encapsulation
    • 'Basics' (data fields, methods)
    • Ability to define new classes
    • References to objects (including null)
    • This Assignment does NOT require inheritance, polymorphism, or generics/templates
  • OPTIONAL: Big 'Oh' Notation is used to describe required running time
    • This could be replaced with a longer, English description, if needed
  • OPTIONAL: Test Driven Development could be covered
    • The student starter solution, and the example solution, both include a full suite of tests for the class(es) that the students implement.  The instructor could remove these, or probably cover what the students need to know in about 10 minutes.
  • Console version: Basic Console Input/Output
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
(December 15, 2001)


written by
 

The Joint Task Force on Computing Curricula
IEEE Computer Society
Association for Computing Machinery

 

PF1. Fundamental programming constructs

  • Basic syntax and semantics of a higher-level language

  • Variables, types, expressions, and assignment

  • Simple I/O

  • Conditional and iterative control structures

  • Functions and parameter passing

  • Structured decomposition

PF3. Fundamental data structures

  • Primitive types
  • Records
  • Strings and string processing
  • Data representation in memory
  • Static, stack, and heap allocation
  • Runtime storage management
  • Pointers and references
  • Linked structures
  • Implementation strategies for stacks, queues, and hash tables
  • Strategies for choosing the right data structure

PL6. Object-oriented programming

  • Object-oriented design

  • Encapsulation and information-hiding

  • Separation of behavior and implementation

  • Classes and subclasses

AL1: Basic algorithmic analysis

  1. Big O, little o, omega, and theta notation
 
Technical Requirements:

(What the students will learn, and demonstrate, by doing this assignment)

 

From:
 

Computing Curricula 2001

Computer Science

Final Report
(December 15, 2001)


written by
 

The Joint Task Force on Computing Curricula
IEEE Computer Society
Association for Computing Machinery

 

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.

The primary goal of the assignment is to modify the code that's provided by the instructor
 

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.

It will be impossible to complete the assignment without the these items.

 

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.

 


This document and the related materials are developed with support from Microsoft Research Computer Gaming Initiative under the Computer Gaming Curriculum in Computer Science RFP, Award Number 15871.