CAT: Memory Performace Application Cards

Title: Memory Performace Application Cards

Author: Kate

Date: April 19, 2004

Technique: Application Cards

Before Class Preparation Time: LOW

Class Completion Time: MEDIUM

In-Class Analysis Time: MEDIUM

Out-Of-Class Analysis Time: MEDIUM

Assessment Goals:

Develop ability to apply principles and generalizations already learned
Learn concepts and theories in the subject
Develop capacity to think for oneself
Develop ability to think creatively
Develop ability to draw reasonable inferences from observations

Topics:

Sorting
Real World Scenarios
Merge Sort
Memory
Efficiency
Cache

Purpose:

Instructors can find out how well students understand how to apply knowledge of how memory and caches work in order to explain unexpected performance results in algorithms.

Activity:

Read the following scenario and answer the question. Be certain to back up your decisions.

You are presented with two mergesort routines, MSORT1 and MSORT2. For small lists, both perform the same. For larger lists, however, MSORT2 significantly outperforms MSORT1. Comparing the code of the two routines, you find that both use roughly the same number of machine instructions.

What could possibly be the difference that makes MSORT2 perform better than MSORT1?

Solution:

Student answers will vary greatly. The most direct answer is to realize that the merge sort routine in MSORT1 is prone to thrashing the cache.

Instructor Responses:

Lecture
Next Day Summary
Class Discussion
Small Group Discussions
Homework

Response Analysis:

Read through the applications and sort or mark them as "Good," "Acceptable," "Marginal," or "Wrong." Read through the piles again to make sure that you have not accidently misclassified a response. You might also want to sort the responses by the type of explanation given.

Choose three or four of the best examples from the "Good" pile. Emphasize understandability, but try to have a diversity of example domains. Also consider a few acceptable and marginal responses that highlight points you wish to discuss.

If you use an application in class as a bad or poor example, change the application just enough to disguise the example from the original authors.

Variant Uses of Activity:

Have students write applications individually and submit these to the instructor anonymously. The instructor reads the applications and the class discusses the merits of these applications. The instructor might want to describe what the code would look like for some of the applications.
Each student writes an application and explains their application to the rest of the class.
Break students into small groups (2-4 people) and have each group find two or more applications. Have each group explain their applications to the rest of the class.

Device-Enabled: Difficult to Enable

Related Topics:

Algorithms
Data structures
Design
ADTs
Analysis