Fall 2004
Instructor: Derek Harter
Office: JOUR
208
Phone: 903-886-5402
Email:
Web Page: http://faculty.tamu-commerce.edu/dharter
Office Hrs: M-Th 10:00am – 11:00am
M,
W 1:30pm – 2:30pm
or by appointment
Course
Description:
This course continues with the concept of abstract
data structures and concentrates on building programming tools which can be
used to store and manipulate data.
Topics covered include stacks, queues, linked lists, trees, hash tables,
recursion, and analysis of algorithm efficiency.
Goals: After completion of this
course, you should be able to create and use classes to implement the basic
data structures (stacks, queues, linked lists, hash tables, and trees) and to
use classes from the Standard Template Library.
You should be able to design and code a program for application areas in
which these data structures would be useful.
Given multiple algorithms to solve the same problem, you should be able
to estimate which algorithm would be more efficient in terms of time and memory
required.
Prerequisite: CSci 152
Text: C++
An Introduction to Data Structures
by Larry Nyhoff (ISBN:
0-02-388725-7)
Source code for the example programs in the text is
available from the author’s web site: http://cs.calvin.edu/books/c++/ds/1e/SourcePrograms/
Any source code
from the text that is to be used in an assignment will also be available on my
web page.
Evaluation:
Your grade for the course will be based on the
following approximate percentages:
50% Exams (best 2 out of 3)
25% Final Exam
25% Programs (5 - 6)
Format
for the exams will typically be approximately half coding (usually
small sections of code such as functions, parts of functions, or calling
functions rather than entire programs) and half analyzing the effects of
executing code (describing output, completing diagrams to show values assigned,
short essay, etc). Four exams will be
given but only the 3 highest scores you achieve on the exams will be used.
A study
guide will be provided for each exam listing topics to be covered (or
omitted) and recommending selected problems from the text from which the
majority of exam questions will be derived.
Answers for these problems are available on my web page.
Letter grades will be assigned according to the
following scale:
A at least 90% of the total
points
B at least 80% but less than 90%
of the total points
C at least 70% but less than 80%
of the total points
D at least 60% but less than 70%
of the total points
F less than 60% of the total
points
You must earn an A on your own. Lower borderline grades may be affected by
your class attendance, participation, and behavior; the pattern of your grades;
and the class grade distribution.
For details of program requirements, see the
separate handout General Policy for
Programming Assignments.
Input data files, sample programs, and most
handouts can be downloaded from my web page:
http://faculty.tamu-commerce.edu/dharter
Makeups:
If you miss an exam, that will be the low grade (0 points) which will be
dropped. If there is a possibility you might
not be able to take the final exam at the scheduled time, please contact me as
soon as you recognize that you have a problem.
Attendance:
You are responsible for everything covered in all class meetings. Class attendance will be taken at the beginning
of each class.
Drops: If you find that you cannot complete the
course, please don't forget to drop. If
you're making an obvious effort in the course at the time you drop, you may
drop passing no matter what your actual grade might be. If you just disappear, your grade will be
whatever you have earned at the end of the semester.
|
Students
requesting accommodations for disabilities must go through the Academic
Support Committee. For more information, please contact the Director of
Disability Resources & Services, Halladay Student Services Bldg., Room
303D, (903) 886-5835. |
|
"All
students enrolled at the University shall follow the tenets of common decency
and acceptable behavior conducive to a positive learning
environment." (See
Student's Guide Handbook, Policies and Procedures, Conduct) |
|
All
students should be aware that plagiarism is a serious offense. This is true not only of written essays but
also of work written in artificial computer languages such as C++. Copying code for assignments from other
students or the internet is not allowed.
You may discuss general aspects and strategies of the coding
assignments with one another, but you must code the programming assignments
on your own. |
TENTATIVE SCHEDULE
|
Week |
Date |
# |
Topic / Activity |
|
|
1 |
30 Aug |
1 |
Introduction,
Preliminary Quiz , and review |
Ch 1 |
|
|
|
2 |
Review
of selected 152 topics |
Ch 2-3 |
|
2 |
6 Sep |
1 |
Stacks:
Introduction |
Ch
4:169-175 |
|
|
|
2 |
Stacks: Designing
and building stacks |
Ch
4:175-192 |
|
3 |
13 Sep |
1 |
Stacks:
Applications of stacks Programming Assignment
#1 Due |
Ch
4:192-204 |
|
|
|
2 |
Queues: Introduction |
Ch
5:211-220 |
|
4 |
20 Sep |
1 |
Queues: Array-based implementations |
Ch
5:220-228 |
|
|
|
2 |
Queues: Applications of queues |
Ch
5:228-239 |
|
5 |
27 Sep |
1 |
Exam 1 |
|
|
|
|
2 |
Templates
and Standard Containers: Introduction, Overloading and Templates |
Ch
6:243-268 |
|
6 |
4 Oct |
1 |
Templates
and Standard Containers: The vector
container Programming
Assignment #2 Due |
Ch
6:268-294 |
|
|
|
2 |
Templates
and Standard Containers: Other standard containers |
Ch
6:294-301 |
|
7 |
11 Oct |
1 |
Recursion:
Introduction & Examples |
Ch
7:320-336 |
|
|
|
2 |
Recursion:
More Examples and Implementation |
Ch
7:336-349 |
|
8 |
18 Oct |
1 |
Introduction
to Analysis of Algorithms |
Ch
7:349-364 |
|
|
|
2 |
Standard
Algorithms |
Ch
7:364-377 |
|
9 |
25 Oct |
1 |
Lists:
Introduction |
Ch
8:385-398 |
|
|
|
2 |
Lists:
Array-based implementations |
Ch
8:398-404 |
|
10 |
1 Nov |
1 |
Lists:
Pointer-based implementations of linked lists Programming Assignment
#3 Due |
Ch
8:404-450 |
|
|
|
2 |
Lists:
The standard list class template |
Ch
8:450-459 |
|
11 |
8 Nov |
1 |
Exam 2 |
|
|
|
|
2 |
Other
Linked Structures: variants including circular and doubly-linked lists |
Ch 9:
467-475,487-498 |
|
12 |
15 Nov |
1 |
Hash
Tables |
Ch 9:
482-486 |
|
|
|
2 |
Binary
Trees: Introduction and Review of Linear and Binary Search |
Ch 10:
513:525 |
|
13 |
22 Nov |
1 |
Binary
Search Trees |
Ch
10:525-536 |
|
|
|
2 |
Binary
Trees as Recursive Data Structures Programming Assignment
#4 Due |
Ch
10:536-554 |
|
14 |
29 Nov |
1 |
Applications
of Binary Trees |
Ch
10:554-567 |
|
|
|
2 |
Exam 3 |
|
|
15 |
6 Dec |
1 |
Programming Assignment
#5 Due |
|
|
|
|
2 |
Review
and Study for Final Exam |
|
|
16 |
13 Dec |
|
Final Exam |
|
270 Course Objectives
1. Be able to create and use
classes (review from 152).
2. Be able
to use the stack data structure.
3. Be able to use the queue data structure.
4. Be able to create and use templates.
5. Be able to design, code, and use recursive
functions.
6. Understand algorithm efficiency (Big-O
notation): what it means, how it is determined,
and why it should be considered in
effective programming.
7. Be able
to use address variables.
a.
Be able to declare a pointer variable, initialize
it, and dereference it.
b.
Be able to pass a variable by address using a
pointer parameter.
c.
Understand the relationship between pointers and
arrays.
d.
Be able to use pointer arithmetic to access
elements of an array.
e.
Be able to declare, initialize and use a reference
variable.
f.
Be able to use a reference variable as a function
parameter.
g.
Be able to use a reference variable as the return
data type of a function.
h.
Be able to pass an argument to a function that uses
a reference parameter to accept the argument’s address.
i.
Understand the differences between reference
variables and pointer variables.
8. Be able to use the linked list
data structure.
type
(ADT) class; be able to create and use destructor, copy constructor, and operator=
functions.
9. Understand what a hash table is
and what it is used for.
a.
Understand what a synonym is
and why collisions are a problem.
b.
Understand how collisions can
be handled.
10. Be able to understand and
use a tree data structure.
a.
Be able to implement a binary
search tree.
b.
Be able to use inorder,
preorder, and postorder traversals.
c.
Understand how trees can be
used as indexing systems for large collections of data.
d.
Understand how to implement a
dynamically allocated binary search tree as an abstract data type (ADT) class.
11. Be able to integrate the use
of container classes (user-created or STL) into a moderately
complex program solution.