CS 3240 DATA STRUCTURES AND ALGORITHMS: SYLLABUS (Winter 2006) Instructor: Ted Billard Email : ted.billard@csueastbay.edu Phone : 885-3437 Home Page : www.mcs.csueastbay.edu/~billard Class Time: TR 4-5:50pm Office Hrs: TR 9-9:30am, W 9-11am (Sc N216) Summary: This course focuses on abstract data structures, including lists, stacks, queues, trees, and hash tables. The fundamental sorting and searching algorithms are considered. Each of the structures is analyzed for its general performance. There is an emphasis on pointers and recursion with the topics listed below. The student is expected to implement various structures and algorithms in the context of given test programs and test cases. Prerequisite: CS 2360 Programming Methods Text: CS 3240 Instructor's Lecture Notes Data Structures & Algorithm Analysis in C, Mark Allen Weiss, Benjamin Cummings. Schedule: Date Topic Exercise DUE DATES 1 1/03 Introduction 2 1/05 Linked Lists 3 1/10 Binary Trees 4 1/12 QUIZ 1, Binary Search Trees 5 1/17 Tree Traversals 6 1/19 QUIZ 2, Array/Pointer Stacks ExIa: Lists 7 1/24 Array/Pointer Queues 8 1/26 Btree Insert ExIb: Lists 9 1/31 TEST 1 10 2/02 B-Tree, Binary Search 11 2/07 B-Tree 12 2/09 Heaps (Priority Queues) 13 2/14 QUIZ 3, Open (List) Hashing ExII: Binary Trees 14 2/16 Closed (Array) Hashing 15 2/21 Insertion, Selection, Bubble 16 2/23 TEST 2 17 2/28 Heapsort ExIII: B-Trees 18 3/02 Quicksort 19 3/07 Mergesort 20 3/09 TEST 3 21 3/16 FINAL EXAM ExIV: Hashing Preview of Exams: Practice 1: pointers in a linked list Quiz 1 : pointers in a linked list Practice 2: pointers in a linked list Quiz 2 : pointers in a linked list Test 1 : concepts: in-order, pre-order, post-order tree traversals, BST big-oh: array, list, stack, queue, BST coding: linked lists Practice 3: recursion in a binary tree Quiz 3 : recursion in a binary tree Test 2 : concepts: hash table, B-tree, priority queue (heap) big-oh: B+tree, priority queue (heap), hash table, binary search coding: binary trees Test 3 : concepts: quicksort, heapsort big-oh: sorting plus selection of previous functions coding: linked lists, binary trees Final Exam: coding: linked lists, binary trees All exams and quizzes will be held at the regularly scheduled time. No late exercises will be accepted. Grading: Quizzes : 3 * 2% = 6% Tests : 3 * 15% = 45% Exercises : 5 * 5% = 25% Final Exam: 24% Exercises: All test programs and test cases are available at: http://www.mcs.csueastbay.edu/~billard/cs3240.html ExIa: Lists A. Test Cases list list.dat B. Programming: list.c Ex1: create list Ex2: H(ead insert Ex3: d(isplay list Ex4: t(ail insert with iteration Ex5: T(ail insert directly Ex9: b(ackward display using prev pointers ExIb: Lists A. Test Cases list list1.dat B. Programming: list.c Ex6: o(rdered insert Ex8: I(ntersection of two sorted lists Ex12: s(how list using recursion Ex14: c(ount nodes using recursion ExII: Binary Trees A. Test Cases binary binary.dat B. Programming: binary.c Ex1: C(ount all nodes in a tree recursively Ex2: f(ind an element in a tree Ex3: F(ind parent of an element in a tree Ex4: s(imilar trees ExIII: B-Trees A. Test Cases btree btree.dat B. Programming: btree.c Ex1: A(scending recursive order traversal Ex2: D(escending recursive order traversal Ex10: C(ount all nodes (pages) ExIV: Hashing A. Test Cases ohash ohash.dat B. Programming: ohash.c Ex1: init_hash of array with no headers Ex2: find_hash in list with no headers Ex3: i(nsert into list with doubly-linked pointers Ex4: D(elete from list with doubly-linked pointers TURN-IN: All exercises are submitted for grading by floppy. The floppy label should have the student's name and NETID. The source file should also include this information along with a list of the problems solved. Be sure to run the program with the test case files. COLLABORATION/COPYING: Unless otherwise stated, do your own work in this class. Violations will be prosecuted to the full extent of the University rules.