CScD 300, Data Structures
Syllabus

Catalog Description

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 required.


Required Text

Schaum's Outlines: Data Structures with Java, Second Edition, by John R. Hubbard, ISBN 978-0-07-161161-9


Topic Coverage

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 progresses.

 Book Chapter Topics.
Chapter 3
Chapter 1
Linked Lists: 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.
Inheritance and Interfaces: Review
Class notes
PowerPoint slides
Algorithm Analysis: 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
Chapter 9 Recursion: Review of how recursion works including stack frame tracing.  Analysis techniques for recursive algorithms.
EXAM 1 Linked lists, recursion, algorithm analysis
   
 Chapter 5 Stacks: Basic stack operations and linked list and array implementations.
 Chapter 5 Infix Expressions: Applications of stacks to conversion of infix to postfix expressions and evaluation of postfix expressions.
 Chapter 6 Queues: Basic Queue operations and linked list and array implementations.
 Chapter 9 Advanced Sorting:  The Merge Sort and Quick Sort algorithms and their analysis
 Chapter 8 Hashing: Constant time data retrieval, hash function construction methods and overflow handling.
Chapter 10
Chapter 11
Trees: Basic concepts
Binary trees:  Binary Search Tree.  Binary Expression Tree.   Huffman Tree (not in text, supplemental material through Wikipedia)
EXAM 2:  Stacks, Queues, Merge Sort, Quick Sort, Hashing,  Binary Trees
FINAL EXAM
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)
FYI: APE
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 Information

Instructor 10am section Tom Capaul
Office CEB 303
Office Hours TTh 9-9:50, MWF 1-1:50, or by appointment
Email tcapaul@ewu.edu  — preferable contact method
Phone 359-7092
Fax 359-2215
Class home page http://penguin.ewu.edu/cscd300/



Grading

WEIGHTS:
EXAMS: Exams will count 50% of the final grade.
2 IN QUARTER EXAMS: 10% each
FINAL EXAM: 30%

PROGRAMS: (including any written homework) will count 50%.  Expect at least 6 programming assignments.
Note:  late assignments will be subject to a 20% penalty for one day late, after that no points will be given.  See "Homework" under "Policies" below.
FINAL NUMERICAL GRADE CALCULATION:
From the following formula:  ( 4.2 - (( 100 - Avg. Percentile Score) / 12)
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.
NOTE: The 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.

Policies