CURRICULUM UNIT ON POINTERS AND LINKED LISTS |
Annamae Lang Nancy Yan Melissa Lam Ryan Johnston |
Students will develop an understanding of dynamic programming and communicate its advantages and disadvantages over static programming.
Students must come to an understanding that the world consists of an undefined number of items. Nothing is set at an exact value. The benefits of understanding a dynamic programming structure allows students to view the computer world more like the real world.
As many students in
the class see a future for themselves in a career in computers, they must
develop their programming skills to the status of those who are already in the
field. As computer programmers primarily use dynamic programming, students must
become familiar with this style in order to be beneficial to a business
community.
The following terms may be unfamiliar to students. They should be stressed and students will be expected to understand these terms and use them in discussions.
Dynamic data structure -- A data structure that has memory
that is readily available. The
programmer is not required to determine the required space to be allocated (or
set aside a maximum number of entries that are available).
Linked list -- A linked list uses pointers to
build a chain of data, which consists primarily of records of information.
Pointer -- A pointer is a dynamic data type. The data held by
pointers are memory addresses where other data can be found.
Record -- The record is a structured data type in that the
variables of a record type can hold different amounts of data.
Static data structure -- A data structure that has memory
that does not change. The programmer must determine the maximum space to be
allocated before the program is compiled. No more entries than that number will
be inserted into the data structure.
The following objectives and performance criteria are things that teachers should have their students attain. Students should be competent in all these topics.
Objective #1(a): Students will be able to communicate
the difference between dynamic and static data structures, specifically between
linked lists and arrays. (Knowledge, Critical)
Performance Criteria: Given a written question, students
will describe the benefits of a dynamic data structure over a static data
structure.
Objective #1(b): Students will communicate the
advantages and disadvantages of dynamic structures over static structures.
(Knowledge, Critical)
Performance Criteria: Given a programming situation,
students will be able to state and give reason for the structure that best
suits the structure.
Objective #2: Students will be able to maintain a
linked list of records through insertion, deletion, sorting and searching.
(Skill, Critical)
Performance Criteria: Students will design a computer
program in Pascal to allow insertion into a list and deletion from a list. It
will enter the items into a sorted order and allow the user to search for a
specific item.
Objective #3: Students will be able to understand
the enhancements to linked lists including other types besides the singly
linked list: doubly-linked and circular. (Knowledge, desirable)
Performance Criteria: Given a diagram, students will be
able to label the various types and give one example of when the style of
linked list would be beneficial to a program.
Objective #4: Students will participate in class
discussion and activities to enhance their knowledge of the topic. (Skill and
Knowledge, Critical)
Performance Criteria: Given a topic to discuss, or a
question to consider, students will work alone or in groups to come up with a
design or an answer to discuss the question.
The type of grading will be numerical grading. The numbers will come from the various quizzes, tests and assignments and will be determined upon creation of the assessment tools. Students will be expected to participate and hand in all testable materials, and to participate in class to obtain the grade for the unit.
The grading will be
determined in the following manner:
|
Class Participation |
25% |
|
Assignments (In and Outside Class) |
20% |
|
Quizes |
15% |
|
Tests |
25% |
|
Group Work / Projects |
15% |
This course is a Grade 12 programming class. Most students will be Grade 12 students with some exceptions of younger students taking the course. All of the students will have successfully taken the grade 11 programming class. As well as having the knowledge of basic programming from the grade 11 class, the students must have an in-depth understanding of records and arrays, and an understanding of searching, and sorting.
At the start of the
grade 12 programming course, it will be easy to spot students who should not be
in the class. At the beginning of the term, students with no background or
limited background with programming should be switched to the grade 11
programming class. Another case of students not having the required
capabilities would be if a student has a programming background, but does not
understand a concept from this course that is essential. An example of this
would be a student who does not understand records, or arrays. In this case, the
student would be encouraged to seek extra help, during, and after class. The
student would be told that if they do not grasp linked lists and pointers that
they will have problems with the next units. It is important that the students
do not fall behind.
This will be the
second course in programming that the students are taking. Either the students
enjoy the challenge of programming and the students have strong programming
skills. Students may also have a desire to pursue a career in computer
programming.
This section will discuss the ways in which the unit will be presented, including an outline of each lesson and some instructional strategies to teach that lesson.
7.1 Instructional Schedule
Order of topics:
This topic naturally follows the unit
on records and arrays. This is essential in moving into this unit. Students
should be competent in both records and arrays and with arrays of records.
Lesson #1: Introduction to Pointers
This lesson will introduce the concept
of pointers and dynamic memory. It will give them a hands-on experience to view
the pointer data type. Assessment:
In-class handouts with activities.
Lesson #2: Comparison to Arrays
This lesson will have students
comparing the advantages and disadvantages of pointers and arrays and which
will be better under certain circumstances. Assessment: Completion of chart with advantages and
disadvantages (in-class), and summary sheet (handed in).
Lesson #3: Intro to Singly Linked Lists
This lesson will allow the students to use pointers to create a singly linked list holding single items of data. Assessment: Short fill-in-the-blanks assignment, with pictures as aids. Quiz.
Lesson #4: Searching
This lesson will broaden on students
knowledge and understanding on using records inside a linked list. Students
will expand their knowledge of searching to include linked lists. There is
strong focus on "next" and "nil" pointers in this
lesson. Assessment: Short assignment where students find output
based on commands given for a piece of code.
Lesson #5: Insertion and deletion of
Linked Lists
Students will learn how to insert and
delete in linked lists. This will require students to formally perform these
operations as a class on a blackboard situation with pictures and then to
actually code this themselves. Assessment: Short programming assignment. Quiz.
Lesson #6: Sorting with Linked Lists
Students will learn how to sort the
items as they are inserted into the list. This is an expansion of their
knowledge of sorting from using arrays.
Assessment: Test. Major project (idea should be class
constructed).
7.2 Instructional Strategies
1.
Role Playing
·
Students act
out the basic functions (insert, delete, add, remove etc.) using their bodies
to represent each record and their arms as pointers (Lessons 3, 4, 5)
2.
Drawing
Pictures
·
Given code,
students draw diagrams of the linked list(s) as they trace the code. (Lessons
1, 3, 4, 5, 6)
3.
Writing Code
·
Given diagrams
of linked lists and pointers, students write code that will give the depicted
output. (Lessons 1 6)
4.
Fill in the
Blank
·
Given code
with chunks of words/lines missing, students fill in the blanks (also show
pictures). (Lessons 1 6)
5.
Scavenger Hunt
·
Given clues,
students identify different records and pieces of data. They may also write
clues and exchange them with their peers to determine the specific record. (Lessons 1, 3)
6.
Concrete
Representation
·
Use cut-outs
of records so that students can manipulate (move around) them.
·
Have the
cut-outs displayed on the blackboard or stuck with tacks on a corkboard. (Lessons 1 6, strongly recommended for
Lessons 4 6)
7.
Choosing/Designing
Data Structures
·
Given specs,
students choose an appropriate data structure (arrays vs. linked lists) and
declare it. (Lessons 2 4)
8.
Pseudocode to
Code
·
Given several
small bits of pseudocode, students write actual code (handwritten). (Lessons 3 6)
9.
Debugging
·
Given medium
size programs on the computer, students (in small groups) run the code and
debug it. (Lessons 4 6)
10.
Debugging
Log/Journal
·
Every time
students get an error in their programs, they record it and describe the
problem and solution in their journals. Later on, they can refer to their
journals if they encounter a similar type of problem. (Lessons 4 6)
7.3 Assessment
The following rubric demonstrates how
assessment of the students throughout the unit and at the conclusion of the
unit is possible. It incorporates the Ministry standards and the
"4-ICE" ideology.
Notice that assessment strategies should include those listed in the instructional strategies. The majority of the instructional strategies are usable on a formal test (paper) as well as other methods including group work and classroom participation. (See Appendix.)
The following section will discuss various student differences that a teacher may face in his or her classroom. It will also attempt to describe the many ways in which a teacher can adapt his or her teaching techniques to include these exceptional students.
8.1
Students with
Exceptional Needs
Students with exceptional needs are those students who have impaired vision, hearing or mobility. Students with impaired vision will probably need instructions and explanations in large print. They may require lesson materials in Braille. In addition, it will be necessary for the teacher to speak loudly and clearly as they may highly depend on their sense of hearing for instruction. It would be difficult for students who are blind to work on the computers to program code, so the teacher may have to make adaptations in assessing these students' knowledge and skills. The teacher may allow these students to orally code programs or to write their programs. If available, students may use a Braille computer that gives them oral feedback. Teachers need to give continual feedback and aid to these students to help them monitor their own progress.
Teachers who have students with hearing
disabilities will need to speak loudly and clearly. It is important for them to
write vital instructions and explanations on the board. It would also be
helpful to the student if the teacher gave a summary sheet at the end of the
unit with the basic concepts and ideas presented during the course of the unit.
Students with mobility difficulties
will probably need extra time in completing their programming assignments. If
these students have problems with typing code, the teacher may adapt
assignments to consist of writing or talking out their code.
8.2
Students with
Low Motivation or Aptitude
Students with low motivation or aptitude need to feel that they have some ownership in their work. Therefore, the teacher should include these students in the planning process. Perhaps, they could take part in the design of specific assignments or rubrics. In addition, these students may work more effectively in group settings. Thus, the teacher may create some activities that require students to work in groups. Again, teachers need to continually provide feedback to these students.
8.3
Faster
Learners
Faster learners are those students who learn the new material relatively quickly and get bored quite easily. For these students, the teacher should have special enrichment activities. Teachers should not give busywork but rather activities that faster learners will be able to glean new information and learning from them. In this unit plan of pointers and linked lists, teachers could have the students code a more difficult situation or an enhancement (such as a graphics bonus assignment) requiring pointers and linked lists.
The following section will discuss the various resources needed during the course of this unit plan: materials, equipment, facilities and human resources.
9.1
Materials
The software used in this unit would all be found in a typical networked high school computer lab. This unit plan on pointers and linked lists is based on Pascal software.
9.2
Equipment
This curriculum requires an overhead projector and screen. No other additional equipment is needed for this unit other than that normally found in a secondary school computer lab.
9.3
Facilities
The facilities that are required for this unit would be a typical networked high school computer lab.
During the process of creating the unit
document, our group worked together and came up with the ideas so fast that it
was difficult to write down how they came to us.
Initially, the beginning ideas were
generated by our experiences in our first year computer science course at
University of Waterloo, CS 130. We all recalled the ideas that were used and
how it was presented, so as to make the concepts simple for us. Most of these
are reflected in the instructional strategies, including the "Human
Pointers" skit.
We examined the Internet to see if we
could find information, but we chose to consult our old course notes for the course
to give ideas for the actual instructional strategies.
On that note, we broke up the
in-between tasks of completing the Sections beyond section 7. Hence, the ideas
for each section came from the person who wrote it, generally in the order they
are presented.
We all went over the final copy of each section to make sure that it flowed together and that the ideas made logical sense. By splitting up the tasks, it made the work go faster for us (as we were all going to be away for the weekend anyway), and then we were able to come together with a finished product. As we do not have a "idea-log" in the sense that you might have been looking for, we still had ideas generated as a group. As we recall, it fell in this order:
·
Instructional
strategies (all -- our days at UW)
·
Definitions
(all -- from Internet resources)
·
Sections 1-9
(each of our own)
·
Section 7.1
(together)
·
Section 7.2
(Melissa, Nancy, and Annamae)
·
Acknowledgements
(Annamae and Nancy)
·
Idea Log
(Annamae and Nancy)
·
Rubrics
(Annamae and Nancy)
Annamae Lang: Sections 1-5 inclusive,
7, Rubrics
Nancy Yan: Sections 7-9.3, Rubrics
Melissa Lam: Sections 7, 9.4-9.6
Ryan Johnston: Sections 6,7
Rubric For Downloading (Word 97 File)