Course Profile Computer and Information Science, Grade 11,
University/College Preparation, Catholic and Public
Unit
5: Using Data Structures
Time: 18 hours
Activity 1 | Activity 2
| Activity 3 | Activity 4
| Activity 5 | Activity 6
This unit
focuses on the programming techniques required to store and manipulate data and
to solve problems through the development of a database. Each activity develops
knowledge and skills that students apply in the culminating challenge of this
unit, to develop a database for a school team (e.g., the hockey team or similar
organization, consisting of personal data such as player name, position played,
jersey number, phone number, goals, and assists). Students examine the
structuring of one- and two-dimensional arrays and how data is represented and
stored in these structures. They write programs that create lists and tables of
data, manipulate the data, and output the result. Sorting and searching
techniques are also applied.
|
Activity |
Time |
Expectations |
Assessment |
Task/Strategy |
|
1: Examining Data Structures |
1 hour |
TFV.03, TF2.05 CGE4f |
Communication Knowledge/Understanding |
Class discussion Group problem solving |
|
2: Data in Lists |
3.75 hours |
SP1.03, SP2.02, SP2.10, SP2.14, SP2.15, SP2.16 CGE7h |
Knowledge/Understanding Application |
Lab exercises |
|
3: Relating Lists |
2 hours |
SP1.03, SP2.02, SP2.03, SP2.10, SP2.14, SP2.15 CGE5a |
Knowledge/Understanding Application |
Lab exercises Quiz |
|
4: Data in Tables |
3.75 hours |
TFV.03, TF2.05, SP1.03, SP2.02, SP2.10, SP2.14, SP2.15 CGE5e |
Knowledge/Understanding Application |
Lab exercises |
|
5: Sorting Data |
3.75 hours |
SP1.07, SP2.02, SP2.10, SP2.14, SP2.15, SP2.16 CGE3c |
Application |
Lab exercises |
|
6: Searching Lists and Tables |
3.75 hours |
SP2.02, SP2.10, SP2.14, SP2.15, SP2.16 CGE7h |
Application |
Lab exercises Assignment Unit test |
Time: 60 minutes
Students
identify the programming techniques (i.e., storage of data in lists and tables,
sorting and searching data) that are necessary to program a database. This
allows students to write programs that efficiently store and manipulate larger
amounts of data than the programs developed in previous units. Array concepts,
including element value, index, and bounds, are explored using models. They
examine written examples of programs illustrating basic application of a
variable array. Students develop thinking skills through analysing programs
using variable arrays to input, process, and output data (e.g., class set of
marks).
CGE4f -
applies effective communication, decision-making, problem-solving, time, and
resource management skills.
Overall
Expectations
TFV.03 -
explain standard control and data structures used in computer programs.
Specific
Expectations
TF2.05 -
define the structure of one- and two-dimensional arrays and associated concepts
(e.g., subscripts, elements, bounds).
Students:
·
understand
how data is stored in string and numeric variables (Unit 2);
·
can
use an operating system to perform tasks such as managing files;
·
can
use built-in networking functions such as shared files and input/output
devices;
·
are
able to implement a comprehensive backup strategy for files.
·
Review
basic syntax of one-dimensional array structures for specific language used
(Appendix 5.1.1).
·
Prepare
notes to illustrate basic structures of declaring arrays, totalling array
elements, inputting data from the keyboard or data file, and outputting results
to the screen.
·
Prepare
demonstrations using models (e.g., on chalkboard, paper and pencil, deck of
cards), giving students visual representations of data storage and manipulation
in arrays.
The
teacher:
·
presents
visual representations of array structures using models such as a set of
numbered envelopes, each containing a word or number;
·
assists
students in identifying examples of data that can be represented using an array
(e.g., names of motel room occupants or post office box holders);
·
defines
basic structure of a one-dimensional array;
·
clarifies
differences between the index (1, 2,…10) and the value of an array element;
·
demonstrates,
through the development of the code for a simple program, the control
structures necessary to store data in an array.
Students:
·
in
groups of four, brainstorm a description of the data that would be part of a
database of a sports team in the school and the programming techniques required
(e.g., representing a table of data, sorting data, and searching for matching
data), which forms the culminating challenge for this unit;
·
manipulate
visual models, illustrating storage of data in one-dimensional arrays;
·
in
pairs, summarize concepts of arrays in their own words and apply the concepts
by identifying additional examples of data that can be represented using an
array;
·
develop,
using pencil and paper, the code for a simple program (e.g., storing and
displaying the list of classes that they are currently taking).
Evidence
of student achievement of the concepts of one-dimensional variable array
structures is assessed at the completion of Activity 2. At that time, students
have applied the concepts in the development of programs requiring the use of
one-dimensional arrays.
The
following are ways in which the activity can be adapted to accommodate the
student’s needs:
·
teachers
should consult the OSR, IEP, Guidance, and Special Education staff with respect
to student exceptionalities;
·
provide
print copies of on-line and print resources to individual students as
appropriate;
·
provide
support through one-to-one teacher-directed conferencing to ensure
understanding.
Hume,
J.N.P. Problem Solving and Programming in
Turbo Pascal.
Hume,
J.N.P. Problem Solving and Programming in
Turing.
Wright,
Peter. Peter Wright’s Beginning Visual
Basic 6.0.
ISBN 1-861001-05-3
Time: 225 minutes
Students
write programs to store, process, and output lists of string or numeric data,
using a one-dimensional array to solve problems, such as managing a class set
of marks, the names of the elements, or members of a school team, and applying
the concepts examined in Activity 1. They move data between an array and a
sequential file and use a linear search to locate matching information in the
array. They also apply tracing techniques to error-check and debug programs.
CGE7h -
exercises the rights and responsibilities of Canadian citizenship.
Specific
Expectations
SP1.03 -
select suitable data structures to represent information;
SP2.02 -
incorporate one-dimensional and two-dimensional arrays into computer programs;
SP2.10 -
incorporate and maintain internal documentation to a specific set of standards,
including author, date, file name, purpose, and explanatory comments of major
statement groups;
SP2.14 -
trace program execution using manual methods and software debugging tools;
SP2.15 -
identify and correct logic, runtime and syntax errors in programs;
SP2.16 -
use linear searches and simple sort routines in programs.
Students:
·
have
stored and manipulated data in sequential files;
·
can
apply repetition structures (loops);
·
can
apply selection structures (if-then);
·
are
able to incorporate subroutines, functions, and menus;
·
have
used tracing and debugging techniques.
·
Review
sequential file structure and manipulation.
·
Choose
appropriate examples and models illustrating the use of arrays and files.
·
Review
data types.
·
Prepare
sample data files for use with the exercise problems.
The
teacher:
·
facilitates
a discussion on the steps for using one-dimensional arrays in creating and
storing lists of information;
·
illustrates,
using a program example, the step-by-step logical process for reading a list of
information into an array and determining the number of elements in the list;
·
solicits
responses from students to develop pseudocode for a program using a list (e.g.,
a list of integers), including array declaration;
·
assists
students in applying developed tracing and debugging techniques to array
problems;
·
assigns
programming exercises requiring use of arrays.
Students:
·
work
in pairs to enter and debug program code developed in Activity 1;
·
working
in pairs, develop code based on the pseudocode developed by the group
discussion;
·
individually
solve problems (Appendix 5.2.1) requiring:
a. creating
a variable array to store a list of a specific data type;
b. determining
the number of elements in an array;
c. displaying
information contained in an array;
d. reading
data from a sequential file into an array;
e. writing
data stored in an array to a sequential file;
f. manipulating
and analysing the data contained in an array (e.g., finding total, mean,
smallest, and largest values in an array.);
g. searching
for specific elements in an array.
Students
complete and submit their solution to a selected problem from the exercises.
Evidence of students’ achievement of the application of one-dimensional
variable array structures in the solution of the problem is assessed using a
rubric (Appendix 5.2.3). The rubric is distributed to students at the outset of
the activity.
The following are ways in which the activity
can be adapted to accommodate exceptional students’ needs:
·
provide
print copies of subroutines and vocabulary new to students;
·
selectively
pair students to assist with developing and debugging code;
·
provide
a “scaffolded” program, with subroutine heading, etc. included, to help
struggling students.
Stephenson,
Chris. Turing Stuff: A Collection of
Teacher-Created Exercises, Projects & Quizzes.
Introduction
to Visual Basic – Project 12 (Variable Arrays) –
http://www.moorpark.cc.ca.us/~gcampbell/begVB12.htm
Arrays
in C++ - http://www.cee.hw.ac.uk/~pjbk/pathways/cpp1/node176.html
Pascal
Tutorial 5C One-dimensional Arrays –
http://www.taoyue.com/tutorials/pascal/pas5c.html
Time: 120 minutes
Students
write programs that store, retrieve, and process related lists of information
(e.g., a class set of student surnames, first names, and marks) using multiple
one-dimensional arrays similar to those used in Activity 2. This expands the
scope of problems that students can solve to include problems such as
displaying the atomic number, name, and atomic mass of an element when the
atomic number is specified. Data is transferred from sequential access data
files to the arrays and back to the files.
CGE5a -
works effectively as an interdependent team member.
Specific
Expectations
SP1.03 -
select suitable data structures to represent information;
SP2.02 -
incorporate one-dimensional and two-dimensional arrays into computer programs;
SP2.03 -
write programs that use related arrays to store and extract data;
SP2.10 -
incorporate and maintain internal documentation to a specific set of standards,
including author, date, file name, purpose, and explanatory comments of major
statement groups;
SP2.14 -
trace program execution using manual methods and software debugging tools;
SP2.15 -
identify and correct logic, runtime, and syntax errors in programs.
Students:
·
store
and manipulate data in sequential files;
·
use
repetition structures (loops);
·
use
selection structures (if-then);
·
use
subroutines, functions, and menus.
·
Select
examples of data that are presented in related arrays (e.g., list names of
players found on baseball cards, the team they play for, and the value of their
card).
·
Prepare
models illustrating the use of related arrays (e.g., rows of disposable cups,
each row labelled with a name, and each cup in the row with a sequential
index).
·
Prepare
presentation materials illustrating the declaration and use of related arrays
in sample programs.
·
Prepare
sample data files for use with the exercise problems.
·
Prepare
a quiz (Appendix 5.3.2).
The
teacher:
·
introduces
the rationale for and structure of related arrays;
·
leads
discussion with students to develop the steps for creating and storing lists of
information in related arrays;
·
demonstrates
writing of code based on an example of pseudocode developed by students;
·
assigns
programming exercises requiring the application of related arrays.
Students:
·
brainstorm
examples of applications for related arrays;
·
in
small groups, develop criteria for determining when to use related arrays;
·
working
collaboratively in groups, develop pseudocode for a program that requires use
of related arrays (e.g., lists of student names and ages), including array
declaration;
·
individually
complete exercises (Appendix 5.3.1), including:
a) creating
parallel arrays to store lists of related data of similar or mixed data types;
b) determining
the number of elements in each array;
c) displaying
tables showing the information contained in the arrays;
d) generating
and storing data in related arrays;
e) reading
data from a sequential file into parallel arrays;
f) manipulating
and analysing the data contained in the arrays (e.g., finding the name of the
youngest or oldest person in the class);
g) searching
for specific information in the arrays (e.g., finding the names of all students
of a specific age or finding the age of a specific student).
Students
complete a programming and theory quiz (Appendix 5.3.2). Programming solutions
are evaluated for application of related arrays, solution of the program,
programming style, and internal documentation.
The
following are ways in which the activity can be adapted to accommodate
exceptional students’ needs:
·
selectively
pair students to assist with developing and debugging code;
·
provide
print copies of code for programs similar to those in the exercises;
·
provide
partially developed programs requiring completion.
Kaufman. Problem Solving and Structured Programming
Pascal. Don Mills: Addison-Wesley Publishing Co. Inc., 1995. ISBN
0-201-11736-3
Time:
225
minutes
Students
write programs to store, process, and output tables of string or numeric data
using a two-dimensional array. This permits more efficient handling of data
than the use of related arrays for tables of consistent data type. They apply
the techniques to problems selected from a variety of contexts (e.g., a salary
grid or table of measured precipitation).
CGE5e -
respects the rights, responsibilities, and contributions of self and others.
Overall
Expectations
TFV.03 -
explain standard control and data structures used in computer programs.
Specific
Expectations
TF2.05 -
define the structure of one- and two-dimensional arrays and associated concepts
(e.g., subscripts, elements, bounds);
SP1.03 -
select suitable data structures to represent information;
SP2.02 -
incorporate one-dimensional and two-dimensional arrays into computer programs;
SP2.10 -
incorporate and maintain internal documentation to a specific set of standards,
including author, date, file name, purpose, and explanatory comments of major
statement groups;
SP2.14 -
trace program execution using manual methods and software debugging tools;
SP2.15 -
identify and correct logic, runtime, and syntax errors in programs.
Students:
·
have
used repetition structures (loops);
·
know
how to store and retrieve data stored in sequential files;
·
are
able to use one-dimensional arrays in solving problems.
·
Review
basic syntax of two-dimensional arrays for the specific language.
·
Prepare
notes to give students basic structures of declaring two-dimensional arrays,
moving across individual rows and columns, as well as reading from a file and
outputting results.
·
Choose
examples of problems that require use of two-dimensional arrays in solution.
·
Prepare
demonstrations through use of models (e.g., on chalkboard, paper and pencil,
deck of cards) to give students visual representations of two-dimensional
arrays.
·
Prepare
exercises manipulating two-dimensional arrays.
The
teacher:
·
introduces
the components of a two-dimensional array;
·
assists
students in identifying the data structures that are appropriately managed with
two-dimensional arrays;
·
clarifies
the use of row and column labels to assist students’ understanding of the role
of each index in a two-dimensional array;
·
emphasizes
restrictions on data types when using a two-dimensional array;
·
demonstrates
development of pseudocode for a program requiring use of two-dimensional arrays
(e.g., tables of wind-chill values or stock inventory items including item
number, description, quantity in stock, and retail price), including array
declaration and the use of nested loop structures;
·
provides
examples of programs to illustrate use of tracing and debugging techniques in
identifying and correcting program code errors (e.g., incorrect index
labelling, subscript out-of-range errors);
·
assigns
exercises.
Students:
·
work
in groups to describe how array concepts can be applied to examples such as
battleship; chess;
·
in
groups, manually trace the execution of a simple program that uses a
two-dimensional array;
·
in
pairs, develop and debug code based on the pseudocode developed as a group;
·
complete
exercises (Appendix 5.4.1), including:
a) creating
two-dimensional arrays;
b) determining
number of rows and columns required by the array;
c) declaring
array appropriately;
d) displaying
tables showing the information contained in the array;
e) reading
data from and to a sequential file using a two-dimensional array;
f) manipulating
and analysing data contained in arrays (e.g., summing or averaging data
contained in rows and columns of numeric two-dimensional array);
g) searching
for specific information in arrays (e.g., listing first names of all students,
given a specified surname).
Students,
working in pairs, assess each other’s solution to a selected problem from the
exercises using a checklist (Appendix 5.4.2).
The
following are ways in which the activity can be adapted to accommodate the
student’s needs:
·
provide
print copies of additional example programs illustrating the use of
two-dimensional arrays;
·
use
mapping and/or flowcharts to assist students in understanding manipulation of
data in two-dimensional arrays;
·
selectively
pair students to assist with developing programming solutions;
·
challenge
students to attempt problems requiring multi-dimensional arrays such as
recording individual player statistics for multiple teams in a hockey league.
Arrays
in C – http://www-ee.eng.hawaii.edu/Courses/EE150/Book/chap7/chap7.html
Arrays
in C++ – http://www.cee.hw.ac.uk/~pjbk/pathways/cpp1/node176.html
Pascal
Tutorial 5D –multi-dimensional arrays -
http://www.taoyue.com/tutorials/pascal/pas5d.html
Time: 225 minutes
Students
develop algorithms for sorting data using a model. They develop pseudocode and
write programs, which use simple sorting algorithms to organize string and
numeric data in one- and two-dimensional arrays, using the array manipulation
techniques developed in Activity 4 (e.g., calculating the median of a set of
data using a bubble sort).
CGE3c -
thinks reflectively and creatively to evaluate situations and solve problems.
Specific
Expectations
SP1.07 -
solve the same problem using various tools (e.g., a calculator and a computer
program, a sort program and a spreadsheet/database/word processor sort
function);
SP2.02 -
incorporate one-dimensional and two-dimensional arrays into computer programs;
SP2.10 -
incorporate and maintain internal documentation to a specific set of standards,
including author, date, file name, purpose, and explanatory comments of major
statement groups;
SP2.14 -
trace program execution using manual methods and software debugging tools;
SP2.15 -
identify and correct logic, runtime, and syntax errors in programs;
SP2.16 -
use linear searches and simple sort routines in programs.
Students:
·
use
loop structures to manipulate data in one-dimensional arrays;
·
use
a random number generator;
·
manipulate
data using one-dimensional arrays;
·
structure
programs using procedures/sub programs.
·
Review
the basic algorithms for sorting data using a computer (Appendix 5.5.1).
·
Review
the ASCII chart to identify problems students may have when dealing with string
variables.
·
Assemble
materials to be used by students in developing sorting algorithms.
·
Prepare
exercises requiring the development of programs to apply and compare at least
two different sorting methods.
The
teacher:
·
introduces
the use of a model for the development of sorting algorithms (Appendix 5.5.2);
·
facilitates
a discussion how to evaluate the sorting algorithms they have developed;
·
presents
at least two basic, standard algorithms for sorting data using a computer,
(Appendix 5.5.1), for student comparison;
·
assigns
exercises.
Students:
·
work
in groups to use a model to develop algorithms for sorting data stored in an
array
(Appendix 5.5.2);
·
develop
pseudocode for the sorting algorithms they have developed;
·
examine
Internet-based simulations of sorting algorithms;
·
develop
program code for a standard sorting algorithm;
·
completes
exercises, including:
a) creating
one-dimensional arrays to store lists of data;
b) sorting
the data in ascending or descending order using at least two algorithms;
c) displaying
results of the sort;
d) comparing
the results of a program incorporating a sorting algorithm to that of a
spreadsheet.
Students
assess their solution to a selected programming problem using a checklist.
The following are ways in which the activity
can be adapted to accommodate exceptional students’ needs:
·
provide
examples at levels of programming skills and experience;
·
students
requiring a challenge and/or enhancement of their program can attempt extension
activities involving additional sorting algorithms;
·
provide
extra time and one-to-one teacher support;
·
select
problems to allow for both remediation and enrichment.
Carter,
John. Problem Solving in Pascal.
Toronto: Addison-Wesley Publishers Limited, 1989,
pp. 343, 350. ISBN 0-201-11215-9
Sorting
Algorithms – http://www-lsi.upc.es/~rbaeza/handbook/sort_a.html
Animation
of Sort Algorithms –
http://blackcat.brynmawr.edu/~spoonen/JavaProject/sorter.html
Bubble
Sort –
http://www-ee.eng.hawaii.edu/Courses/EE150/Book/chap10/subsection2.1.2.2.html
Bubble
Sort – http://www.cs.princeton.edu/~ah/alg_anim/gawain-4.0/BubbleSort.html
Insertion
Sort Demonstration –
http://www.cs.orst.edu/~minoura/cs162/javaProgs/sort/InsertSort.html
Time: 225 minutes
Students develop algorithms for simple
searching routines and apply them to problems (e.g., locating the name of a
group in a database of albums and artists). They also complete exercises and
write programs applying at least two search algorithms. They complete the
culminating challenge presented in Activity 1 – programming a database for a
sports team in the school. The database requires the application of techniques
for manipulating and sorting data learned in the previous activities.
Ontario
Catholic School Graduate Expectations
CGE7h - exercises the rights and
responsibilities of Canadian citizenship.
Strand(s): Skills and Processes
Specific
Expectations
SP2.02 -
incorporate one-dimensional and two-dimensional arrays into computer programs;
SP2.10 -
incorporate and maintain internal documentation to a specific set of standards,
including author, date, file name, purpose, and explanatory comments of major
statement groups;
SP2.14 -
trace program execution using manual methods and software debugging tools;
SP2.15 -
identify and correct logic, runtime, and syntax errors in programs;
SP2.16 -
use linear searches and simple sort routines in programs.
Students:
·
use
loop structures to manipulate data in one-dimensional arrays;
·
describe
basic structure for one-dimensional arrays;
·
structure
programs using procedures/sub-programs.
·
Prepare
exercises for students to compare, program, and analyse at least two searching
methods;
·
Prepare
the unit test.
The
teacher:
·
directs
students to Internet resources illustrating the algorithms for searching arrays
for matching data;
·
assigns
exercises requiring searching lists and tables of data.
Students:
·
working
in groups, use a model to create at least two algorithms for searching an array
for matching data;
·
examine
Internet-based simulations of searching algorithms;
·
create
pseudocode for a searching algorithm;
·
write
and debug code for a searching algorithm;
·
complete
exercise problems (Appendix 5.6.2) which require:
a) creating
arrays to store data of the same type;
b) searching
matching data using at least two algorithms;
c) displaying
results of search;
d) comparing
efficiency of searching algorithms.
·
complete
a summative programming assignment (Appendix 5.6.3).
·
Students
submit their solution to the summative assignment to be assessed using a rubric
(Appendix 5.6.4).
·
Students
complete a unit test (Appendix 5.6.5).
The
following are ways in which the activity can be adapted to accommodate
exceptional students’ needs:
·
provide
parts of subroutines or parts of code to aid struggling students;
·
provide
print copies of pseudocode for searching routines;
·
challenge
students to investigate additional searching algorithms.
Carter,
John. Problem Solving in Pascal.
Toronto: Addison-Wesley Publishers Limited, 1989,
pp. 334-337. ISBN 0-201-11215-9
Searching
Algorithms – http://www-lsi.upc.es/~rbaeza/handbook/search_a.html
|
Arrays : |
A table of values of the same type and a fixed size. The table may have one or more dimensions. |
|
|||||
|
Components : |
The data within the array. |
|
|||||
|
Index : |
The position of a component in an array. The index must be of an ordinal type. |
|
|||||
|
Example: |
Given the array
declaration in Pascal |
OR Basic |
||||
|
|
MARKS : ARRAY[ 1..10 ] OF INTEGER; |
DIM MARKS(1 TO 10) AS INTEGER |
||||
If
we were to read into the array the following data
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
72 |
44 |
66 |
87 |
54 |
85 |
92 |
65 |
71 |
63 |
The
components are the marks themselves.
The
components can be accessed with MARKS[1]
or MARKS[5]. In Pascal
OR MARKS(1)
or MARKS(5) in Basic
The
indices are 1,2,3...10
Therefore,
MARKS[3] or MARKS(3) has a value of 66
MARKS[7] or MARKS(7) has a value of
92
Manipulating
Values in Arrays
Assuming
the following declaration:
|
In Pascal |
In Basic |
|
VAR MARKS : ARRAY [1..10] OF INTEGER; I, J : INTEGER; TOTAL : INTEGER; AVERAGE : REAL; |
DIM MARKS(1 to 10) as INTEGER DIM I, J as INTEGER DIM TOTAL as INTEGER DIM AVERAGE as REAL |
Suppose a
file contained ten records, we could read each value into the arrays MARKS, and
NAMES with the following:
|
In Pascal |
In Basic |
|
FOR I := 1 TO 10 DO READLN(INFILE,MARKS[I]); |
FOR I = 1 TO 10 INPUT #1, MARKS(I) NEXT I |
We could
find the average with the statement:
|
In Pascal |
In Basic |
|
TOTAL := 0; FOR J := 1 TO 10 DO TOTAL := TOTAL + MARKS[J]; AVERAGE := TOTAL/ I; |
TOTAL = 0 FOR I = 1 TO 10 TOTAL := TOTAL + MARKS(J); NEXT I AVERAGE = TOTAL / I |
We could
print out the records with the statement:
|
In Pascal |
In Basic |
|
FOR I := 1 TO 10 DO WRITELN(MARKS[I]:8); WRITELN('Average = ',AVERAGE:5:2); |
FOR I = 1 TO 10 PRINT#1, MARKS(I) NEXT I PRINT #1, AVERAGE |
1. To use the “speed dial” feature of your home
phone you must first store each of the phone numbers that you wish to use. Each
phone number is accessed by entering the speed-dial number, from 0 to 9, used
for storing the number. Write a program that will help you remember who’s phone
number you have stored with each speed dial number. Your program must use an
array to store the list of names. The user enters a number from 0 to 9 and is
shown the name of the person that would be called if you entered that speed
dial code into the phone. Store the data from the array in a sequential file.
2. Write a program that allows the user to enter
up to 20 numbers to be stored in an array. When the user has finished entering
numbers, calculate and display the sum of the numbers, the mean (arithmetic
average) of the numbers, and the largest and smallest values entered.
3. Create a program that reads a list of no more
than 100 names from a sequential file into an array. The names are stored in
the file in the form “last_name, first_name.” Allow the user to display the
list; add, modify, and delete names; and save the modified list in a sequential
file with the same name.
4. Write a program to simulate rolling two dice
together 100 times. Count the number of times each result (i.e., total of the
two dice) occurs and print out the results. Note that rolling two dice together
is not the same as picking a number from 2 to 12!! (If you really turn on your
problem-solving skills, this program can be most easily done WITHOUT AN IF
STRUCTURE!!)
|
Achievement Category |
Level 1 (50 – 59%) |
Level 2 (60 – 60%) |
Level 3 (70 – 79%) |
Level 4 (80 – 100%) |
|
Understanding of array concepts (K/U) |
- provides limited differentiation between indexed and non-indexed variables |
- sometimes differentiates between indexed and non-indexed variables |
- usually differentiates between indexed and non-indexed variables |
- demonstrates an understanding of efficiency of data representation in lists |
|
Identification of data (K/U) |
- rarely identifies characteristics of data best represented as lists |
- identifies some data best represented as lists |
- usually identifies data best represented as lists |
- clearly differentiates data best represented as lists |
|
Problem Solving (A) |
- approaches problems in a trial and error manner |
- develops incomplete and/or insufficiently detailed plan |
- properly plans and details solution in a stepwise manner |
- properly plans highly efficient solution to problem |
|
Documentation (C) |
- documentation communicates appropriate information in a limited manner |
- documentation provides some description and identification of programming logic |
- correctly and appropriately comments on code and variables |
- provides complete documentation (help screens and/or external documentation) |
|
Programming Style (C) |
- rarely uses proper style (indentation, separation of program structures) |
- usually uses proper style |
- consistently uses proper style |
- consistently uses proper conventions and style |
|
Declaration of array variables (A) |
- improperly declares arrays in a limited manner |
- declares arrays and uses some appropriate variable types |
- declares arrays using appropriate data types and index values |
- code reflects efficient use of arrays |
|
Use of indices (A) |
- rarely uses indices |
- partially implements use of indices in programming structures |
- consistently uses indices correctly in programming structures |
- uses indices correctly with a high degree of programming structures |
|
Solution of problem (A) |
- program rarely solves problem |
- program is functional but fails limit testing |
- program adequately solves problem |
- program provides exemplary solution |
|
User Interface (A) |
- user interface rarely communicates with user |
- confusing and/or incomplete user interface |
- user interface is intuitive and user-friendly |
- user interface consistent with industry standards |
Note: A student whose achievement is below level 1
(50%) has not met the expectations for this assignment or activity.
1. Create a program that reads a list of names
from a sequential file into an array, storing the name, and another array
corresponding to their age. The arrays must be organized so that there is a
1-to-1 correspondence between the indices of the name and age. When the user enters
an age, the names of all the people of that age should be displayed. The user
should also be able to add, delete, and modify the names and ages entered.
2. Create a program that creates and administers
a true/false quiz. Questions are read from a data file into one array and a
related array is used to store the answers, either T or F, for each question.
When the user takes the test, questions are presented in random order, without
repetition. Keep track of the number of questions answered and the number of
correct answers. When the user has finished the quiz, display the mark as a
percentage.
Part 1 –
Answer the following questions on a separate piece of paper.
1. Explain the difference between the index and
the element of an array.
2. Describe how data is linked in related
arrays.
3. Give an example of a set of data that is best
represented by related arrays.
Part
2 – Create a program to solve the following problem. Make sure your code is
properly documented and structured. Print one copy of your code to hand in.
The
sample data file “quiz1.dat” contains a list of students in a class and their
marks for the class.
Read
the marks into two related arrays.
Using
the values stored in the arrays, determine and display the class average and
the name of the student with the highest mark.
1. This table contains the average weekly
precipitation for four Ontario Cities.
|
|
Precipitation (cm) |
|||
|
Month |
London |
Kingston |
North Bay |
Dryden |
|
January |
12.4 |
13.5 |
12.1 |
12.6 |
|
February |
8.2 |
9.5 |
8.0 |
7.5 |
|
March |
14.9 |
13.5 |
12.9 |
15.3 |
|
April |
30.0 |
35.5 |
40.2 |
37.7 |
|
May |
24.5 |
26.1 |
23.4 |
24.0 |
|
June |
30.3 |
4.6 |
11.4 |
21.6 |
a) Create
a data file, containing the above data, using a spreadsheet and saving the data
as a comma delimited file.
b) Declare
the two-dimensional array for the above data called PRECIPITATION.
c) Read
the data from the data file into the array PRECIPITATION.
d) Print
out the precipitation data in a neat table with headers and row titles.
e) Calculate
and display:
a. the
average weekly precipitation for North Bay;
b. the
average precipitation for April;
c. the
total precipitation for all areas for the first six months of the year;
d. the
city with the largest precipitation for June;
e. the
month with the smallest precipitation in London.
2. Write a program that reads the police salary
grid into a two-dimensional array from a data file you have prepared.
Negotiators have asked you to project new pay grids based on various increases.
Use 1.5%, 2.5%, and 4% increases in pay as your test data. Calculate the new pay
increases across the pay grid. Output the original grid and the new grids with
pay increases. The grid below is used to pay police officers:
|
Police Pay Schedule |
||||
|
|
|
Rank |
||
|
|
|
Lieutenant |
Sergeant |
Constable |
|
|
0 |
30000 |
28750 |
26500 |
|
Y |
1 |
32000 |
30540 |
28750 |
|
E |
2 |
34000 |
32400 |
29900 |
|
A |
3 |
37300 |
34100 |
31200 |
|
R |
4 |
39100 |
36200 |
33300 |
|
S |
5+ |
40000 |
38000 |
35000 |
The
police Commission is also concerned with the cost of the raise in pay. The
following is a table indicating how many employees are in each category.
|
Number of Employees in Each Category |
||||
|
|
|
Constable |
Sergeant |
Lieutenant |
|
|
0 |
89 |
90 |
55 |
|
Y |
1 |
90 |
36 |
47 |
|
E |
2 |
45 |
23 |
20 |
|
A |
3 |
73 |
41 |
42 |
|
R |
4 |
91 |
62 |
33 |
|
S |
5+ |
12 |
80 |
52 |
Find the
total cost to the Police Commission if any of the above pay increases was
granted. Display your results in an appropriate format.
Program
Title: ________________________ Programmer:
________________________________
Assessed
by: ________________________________
|
User Interface |
(circle choice) |
|
|
1. |
Program is able to read data from a file. |
Y / N |
|
2. |
Data is aligned in columns. |
Y / N |
|
3. |
User can easily input percentage increase. |
Y / N |
|
4. |
Input is checked for acceptable value. |
Y / N |
|
5. |
Appropriate on-screen prompting is displayed. |
Y / N |
|
Problem Solution |
|
|
|
5. |
Pay increases have been correctly calculated. |
Y / N |
|
6. |
Total cost of pay increase is correctly calculated. |
Y / N |
|
Program Structure |
|
|
|
7. |
Program is appropriately divided into subroutines. |
Y / N |
|
8. |
Program header contains required information. |
Y / N |
|
9. |
Internal documentation is complete. |
Y / N |
|
10. |
Program uses a two dimensional array. |
Y / N |
|
11. |
Variable names are appropriate. |
Y / N |
There are
many different types of sorting routines. Below is the pseudocode for two
different sorts.
Selection
Sort
In
a selection sort, we start at one end of the array looking for the largest or
smallest depending on whether the sort is in ascending or descending order.
Once found, we can place it in it’s proper spot and continue searching through
the remaining elements in the array. Once an element has been swapped, it is
never moved again. One disadvantage to this type of sort is that it must
perform N2 passes through the array regardless of the original order.
for i =
the beginning of the array to the end
‘Look for the smallest (or largest) element and
put it in the ith element
for
j = the ith element to the last element
if
the jth element is smaller than the ith element
smallest
= j
swap the jth element with the ith
element after going through the array
Bubble
Sort
In
a bubble sort, adjacent values are compared and exchanged if they are not in
order. It uses a boolean variable “SORTED” which determines if the list is
sorted and stops execution if found to be in order. Although many more swaps
are performed in this sort, it is especially efficient if only a few elements
have been added to the array, since the sort is a “smart” sort and stops when
the boolean flag becomes true.
procedure
sort
set
sorted to false
set max to
top
while not
sorted and top > 1
set sorted to true
for passes = 1 to top –1
if element at i >
list at i + 1
exchange the
ith element with the ith + 1 element
set top to top -1
Purpose
To use a
model to develop an algorithm for sorting data stored in a one-dimensional
array.
Description
A series
of labelled disposable cups represent the elements of an array. A small, folded
piece of paper is placed in each cup. Each piece of paper has a number, letter,
or word written on it. Students, working in small groups, sort the data (pieces
of paper) using methods that are available within a computer program. A
description of the algorithm developed, pseudocode for the algorithm, and code
are developed.
Method
1. Label each of eight disposable cups with a
name and a number similar to the labelling of elements in an array (e.g.,
cup(1), cup(2), cup(3), etc.). Place the cups in a line in order.
2. Cut a piece of paper into eight pieces,
approximately 3 cm x 6 cm. Write the numbers from 1 to 8 on the pieces of paper
and fold each in half so that the number is hidden.
3. Mix up the pieces of paper and place one
piece in each cup.
4. Using the following rules, develop a method
for sorting the numbers on the paper in order so that the smallest number is
found in cup(1) and the largest is in cup(8) and all others are in sequence.
Use brainstorming techniques with your group.
a. Only
two numbers may be removed from the cups at any one time.
b. A
number being viewed may be placed only in the cup from which it was removed or
a cup that does not contain a number currently being viewed.
c. Papers
must remain folded so that the number is hidden when the paper is in the cup.
d. Additional
cups may be used, but they must be labelled.
e. The
cups must remain in order at all times.
5. Experiment with different suggested methods
until you have found a simple method to sort the data that can be described in
a few, repeatable steps.
6. Record the steps in the sorting method you
have developed (the algorithm). If additional cups are used, their use must be
described.
7. Test the steps by having one person read the
steps one at a time and another person follow the instructions. Don’t make
things up – follow the instructions exactly!
8. Test your algorithm with different data
(e.g., when one number is repeated).
9. Modify your algorithm based on what you
discover during testing.
10. Individually, write pseudocode for the
algorithm.
11. Compare your pseudocode with that of your
group members.
12. Write code for the algorithm. Don’t forget to
include variable declarations and variable initialization.
13. Test your code using various data sets,
including data in which numbers are repeated and string data (words).
Teacher’s Note: Students may create a variety of algorithms.
Ask each group to demonstrate their algorithm. As a group, evaluate each
algorithm for efficiency (sorting in the fewest steps) and ease of programming.
You may wish to describe the algorithm for the Two-Buffer sort and Bubble sort
and allow students to experiment with them using the cups.
1. Write a program that finds the median of a
set of numbers input by the user. In order to find the median you must first
sort the numbers in ascending or descending order. If there are an odd number
of numbers then the median is the middle number in the list. If there is an
even number of numbers, then the median is found by averaging the two middle
values.
2. Using the data file “PRECIP.DAT” from problem
1 of Appendix 5.4.1, read the data into a two-dimensional array of 6 rows and 6
columns. Calculate the average precipitation for each month (rounded to 1
decimal place) and store the average in the 6th column. Sort the rows in
ascending order by average rainfall and display the resulting table.
3. Repeat problems 1 and 2 using a spreadsheet
to store and sort the data. Write a brief report comparing the results achieved
by your program and the spreadsheet. Describe how the sort function is used in
the spreadsheet and any limitations to its use that you found.
Program
Title: ________________________ Programmer:
________________________________
Assessed
by: ________________________________
|
User Interface |
(circle choice) |
|
|
1. |
Data is easily entered. |
Y / N |
|
2. |
Appropriate prompting is present. |
Y / N |
|
3. |
Input is screened for acceptable values. |
Y / N |
|
Problem Solution |
|
|
|
5. |
Median is correctly calculated for odd data numbers. |
Y / N |
|
6. |
Median is correctly calculated for even data numbers. |
Y / N |
|
Program Structure |
|
|
|
7. |
Program is appropriately divided into subroutines. |
Y / N |
|
8. |
Program header contains required information. |
Y / N |
|
9. |
Internal documentation is complete. |
Y / N |
|
10. |
Program uses a sorting algorithm. |
Y / N |
|
11. |
Variable names are appropriate to the problem. |
Y / N |
Sequential
Search
In
a sequential search, we start at the beginning of the array and search one
element at a time until the element is found. A Boolean variable “found” is
used to allow the search to stop if the element has been located. This search
can be inefficient and time consuming, since it must go through the array one
element at a time.
Pseudo
Code for sequential search
Set found = false
Set Index to 1
Input search item
While not found and not at the end of the array
If
list at index = search item
Found
= true
Location
= index
Endif
End while loop
If found
= false, output that item was not found
If found
= true, output location item was found at.
Binary
Search
If
your array is in order, then a binary search can be performed and is far more
efficient than a sequential search. The basic premise is to divide the array in
half and look to see if the item we are searching for is in the top half or the
bottom half. We continue cutting the remaining array in half, looking to see
which half to search through until the element is found or when the top
overlaps the bottom meaning that the item is not found.
Pseudo
Code for binary search
Set bottom to 1 and top to MAX elements
Set Found to false
Input item searching for
While bottom <= top and not found
Middle = (bottom + top)
/2
If
list at middle = item
Found = true
Location =
middle
Else
If list at
middle < item ‘ discard the bottom
half
bottom
= middle + 1
else
top
= middle –1 ‘ discard the top half
endif
endif
end while loop
If found
= false, output that item was not found
If found
= true, output location item was found at location middle
Written
Answer
the following questions:
1. When would the sequential search be more
efficient?
2. Why does the binary search require that the
array be sorted?
3. Assume that an array contains the following
data:
23 34 43 45 52 59 70 75 77 86
Trace
the binary search for the following items
89 59 40 75
6. What changes would you need to make to the
sequential search if the array is to be sorted in descending order?
7. What changes would you need to make to the
binary search if the array is to be in descending order?
8. What is the maximum number of passes
necessary to perform a binary search on an array of 100 elements?
Programming
Problems
1. Store 20 random numbers in the range 1 to 100
in an array. Display the numbers in the array. Sort the list using the bubble sort
and write a function “BINSEARCH” to perform a binary search for a requested
value.
2. Create a data file containing a list of at
least fifty albums and the artist or group that recorded it. Write a program
that allows the user to find the name of the album when they enter the name of
the artist or group. Your program must use a binary search.
You are
to create a database for a school team including appropriate player and
statistical information. For example, if you choose the hockey team, your data
should include each player’s first name, surname, position played, height,
weight, shoots left/right, plus/minus record, games played, goals, and assists.
The
application should allow the user to:
a) display the team data in alphabetical order
by last name;
b) add new players;
c) edit the information for a player;
d) delete players;
e) find and display an entry based on a search
by any field.
|
Achievement Category |
Level 1 (50 – 59%) |
Level 2 (60 – 60%) |
Level 3 (70 – 79%) |
Level 4 (80 – 100%) |
|
Solution of Problem (K/U) |
- program rarely solves problem |
- inefficient algorithm and/or program structure |
- program fully solves problem |
- program includes additional functionality |
|
Documentation (C) |
- documentation rarely communicates appropriate information |
- documentation lacks sufficient description and identification of programming logic |
- correctly and appropriately uses program headers and comments |
- provides additional documentation (help screens and/or external documentation) |
|
Programming Style (A) |
- rarely uses proper style (indentation, separation of program structures) |
- usually uses proper style |
- consistently uses proper conventions and style |
- always uses proper conventions and style |
|
Application of sorting algorithm (A) |
- program rarely sorts data |
- program uses two arrays for sorting |
- program uses bubble sort |
- more efficient sorting algorithm used |
|
Application of search algorithm (A) |
- program rarely locates matching values |
- program uses linear search |
- program uses binary search |
- program uses more efficient search |
|
User Interface (A) |
- user interface rarely communicates with user |
- confusing and/or incomplete user interface |
- user interface is intuitive and user-friendly |
- user interface consistent with industry standards |
Note: A student whose achievement is below level 1
(50%) has not met the expectations for this assignment or activity.
Unit
Test
Part 1 - Answer the following questions on the
paper provided: (13 marks)
1. (4) Give
an example of a set of data that is most appropriately presented using related
arrays and best represented by a two-dimensional array. Explain characteristics
of the data that affected your choice.
2. (4) Write
the pseudocode for a two-buffer sort to sort a list of fifteen numbers.
3. (2) Explain
why you might choose to use a bubble sort in your program rather than a
two-buffer sort.
4. (3) Describe
the algorithm for a binary search.
Part 2 –
Programming (15 marks)
Save your
program in your own directory on the fileserver as “test1”. Be sure to save
your program frequently. Proper programming techniques and documentation must
be used.
The
samples directory contains a file that contains a list of items in stock at the
local hardware store, consisting of the item number and description (e.g., A-90321,
Screwdriver). Write a program that reads the data into a two-dimensional array
and allows the user to display the data sorted in ascending order by item
number or name. Also, allow the user to enter the item number and display the
matching description.
Course Overview | Unit 3 | Course Profiles Main
Menu