CScD 300, Data Structures
This course covers fundamental abstract concepts of data
structures as well as their implementation in a programming
language. Topics include linked lists, stacks, queues, hashing,
recursion, complexity analysis of algorithms, binary search trees
and heaps. Programming projects with formal documentation are
Schaum's Outlines: Data Structures with Java, Second Edition,
by John R. Hubbard, ISBN 978-0-07-161161-9
The projected sequence of the topics that we will cover this
quarter, and their correspondence to the textbook, are listed
below. This will be subject to alteration as the quarter
| Book Chapter
Review of the simple singly-linked list.
Generation of an ordered linked list / sorting linked lists.
Circular and doubly linked lists. Linked lists with header nodes.
Definition of Big-O notation as a means of expressing time complexity.
Methods for determining time complexity of an algorithm. A walkthrough
of several sorts and searches including time complexity determination
for each algorithm. Introduction of Shell's Sort based on
insertion sort. See the following URL: http://www.cise.ufl.edu/~sahni/dsaaj/enrich/c2/shell.htm
Review of how recursion works including stack frame tracing.
Analysis techniques for recursive algorithms.
recursion, algorithm analysis
| Chapter 5
stack operations and linked list and array implementations.
| Chapter 5
Applications of stacks to conversion of infix to
postfix expressions and evaluation of postfix expressions.
| Chapter 6
Queue operations and linked list and array implementations.
| Chapter 9
The Merge Sort and Quick Sort algorithms and their analysis
| Chapter 8
Constant time data retrieval, hash function construction methods and
Binary trees: Binary Search
Tree. Binary Expression Tree. Huffman Tree
(not in text, supplemental material through Wikipedia)
||Stacks, Queues, Merge Sort,
Quick Sort, Hashing, Binary Trees
12-3 Monday December 9
|Cumulative and may include any material covered in
class not on the second exam. Also, you get three hours for
the final even though it is only written to take two (the final is
typically 1 3/4 the size of a regular exam)
Be sure and register ASAP!
|Saturday, October 26, 10:00am-1:00pm room TBA (probably 207 or 208) -- see http://ape.compsci.ewu.edu/phpAPE/
|Instructor 10am section
||TTh 9-9:50, MWF 1-1:50, or by appointment
— preferable contact method
Exams will count 50% of the final grade.
NUMERICAL GRADE CALCULATION:
2 IN QUARTER
EXAMS: 10% eachPROGRAMS: (including any written homework) will
count 50%. Expect at least 6 programming assignments.
FINAL EXAM: 30%
late assignments will be subject to a 20% penalty for one day late, after
that no points will be given
. See "Homework
" under "Policies
the following formula: ( 4.2
- (( 100 - Avg. Percentile Score) / 12)
instructor retains the right to
increase grades above this formula (which is to your benefit).
Basically, if you earn at least a 95%, you will get a 4.0.
For each percentage below 95, drop your grade point by 0.1.
The values shown in bold italics are guaranteed minimums - they may be
increased in the final formula but will NOT be less than these values.
Americans with Disabilities Act: If there is any student in this class
who has special needs for accommodation, please feel free to discuss
the matter with the instructor. Students requiring accommodations need
to contact Kevin Hills, Director of Disability Support Services
(DSS). He can be reached at (509) 359-6871. The
DSS Office is located in 124 TAW.
You are expected to attend every class session. Please do not use my
office hours as a substitute for attending lectures. In addition, you
are expected to read the appropriate sections of the text before each
class period. Classroom activities will complement, not necessarily
duplicate, the text. If you are unsure as to what will be covered next,
please ask at the end of the class period.
You are expected to read material from the
chapter in the book that is being discussed in class AHEAD of time (see
the syllabus for a list of topics and chapters). Examples
given in class and by the authors should be confirmed by the student at
home to guarantee complete understanding of the subject.
Homework assignments will be in the form of programming projects, each
worth 100 points unless otherwise noted. Homework is due by the date
and time posted on the assignment, unless specified differently in
class. Assignments will be accepted one day late, with a 20% penalty,
this no points will be given for that assignment.
assignments must be turned in (in working order as determined
the instructor) before quarter's end to be eligible to earn a passing
These will be based on (1) classroom lecture/activities, (2) homework -
(programming projects and anything else assigned), (3) material from
book. No makeup exams will be negotiated after an exam
begins. Make-ups may only be arranged in advance, in the most
and Attendance. You are not graded on participation
and attendance directly. However, at quarter's end these
items can positively influence your final grade.
Behavior. All students are expected to act in
accordance with the ACM Standards for Professional Behavior available through this link
. While I expect, and encourage, students to work together in an
appropriate manner, taking credit for someone else's work is forbidden
and is grounds for receiving a 0.0 in the class. Appropriate activities
include discussing program ideas, helping with code debugging, and
offering suggestions based on a running program. Inappropriate behavior
includes jointly developing a program and submitting it separately,
putting your name on a copy of someone else's code, and using an
algorithm or code copied from any source without crediting the source.
Should you have any questions about appropriate behavior, please talk
with me before submitting your work. Instances of cheating
will be dealt with SEVERELY. You may be expelled from the
university, expelled from the degree program, or given a 0.0 in the
Incompletes will NOT be granted except under extreme circumstances.
They will not be granted in cases where you were simply unable to keep
up with the workload. Requests for an incomplete must be submitted
prior to finals week and is subject to the following catalog
restriction: "PASSING work/progress (2.5 or above) must be demonstrated
through three weeks prior to the end of the term."
The instructor reserves the right to make changes to these policies as
necessary. You will ALWAYS be informed of these changes in