Syllabus

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.

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 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
conceptsBinary 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:
APEBe 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 | Tom Capaul |

Office | CEB 303 |

Office Hours | TTh 9-9:50, MWF 1-1:50, or by appointment |

tcapaul@ewu.edu — preferable contact method | |

Phone | 359-7092 |

Fax | 359-2215 |

Class home page | http://penguin.ewu.edu/cscd300/ |

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.

From the following formula: (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.- (( 100 - Avg. Percentile Score) /4.2)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.

*ADA***:**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.*Lectures*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.*Preparation.*. 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, after this no points will be given for that assignment. All assignments must be turned in (in working order as determined by the instructor) before quarter's end to be eligible to earn a passing grade (2.5).*Homework*. 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 extreme circumstances.*Exams*. You are not graded on participation and attendance directly. However, at quarter's end these items can positively influence your final grade.*Participation and Attendance*. All students are expected to act in accordance with the*Professional Behavior**ACM Standards for Professional Behavior**Incompletes**.*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 class.*Disclaimer.*