  
Student Learning Outcomes 
 The successful student will be able to write and incorporate balanced trees, hash tables, directed graphs and priority queues in his or her software.
 The successful student will be able to analyze the time complexity of a variety of algorithms and data structure access techniques and choose the best algorithm and/or data structure for the project at hand.

Description  
 Systematic treatment of advanced data structures, algorithm analysis and abstract data types in the C++ programming language. Coding topics include the development of ADTs from scratch, building ADTs on top of the STL templates, vectors, lists, trees, maps, hashing functions and graphs. Concept topics include searching, bigO time complexity, analysis of all major sorting techniques, top down splaying, AVL tree balancing, shortest path algorithms, minimum spanning trees and maximum flow graphs.


Course Objectives  
 The student will be able to:
 Implement a userdefined vector abstract data type (ADT) and its associated iterator from scratch, and compare the performance to the builtin C++ standard template library (STL) vector.
 Implement a userdefined linkedlist ADT and its associated iterator from scratch, and compare the userdefined performance to the builtin C++ STL list.
 Build stack, queue and sparse matrix ADTs using C++ vectors and lists.
 Compute the bigO, littleo, omega and theta time complexity of search and sort algorithms.
 Define asymptotic behavior and perform empirical benchmarks to compare bruteforce techniques with divideandconquer strategies.
 Analyze the basic algorithms of a general tree ADT.
 Use objectoriented programming (OOP) to create alternative implementations of binary search trees in C++ and verify or compare the logN behavior of each.
 Describe the advantages of balanced trees and analyze the performance of AVL trees.
 Write code using the STL that realizes a Splay Tree using either topdown or bottomup splaying.
 Define linear probing, quadratic probing and open addressing as used in the hash tables ADT.
 Design a priority queue using heaps in C++.
 Analyze, classify and measure the main nonNlogN sorts and write a clear report of the results.
 Implement a C++ Quicksort and at least one other NlogN sort and compare the results as the number of data items approaches infinity.
 Define indirect sorting and explain why it is particularly important in C++.
 Create a graph data structure using OOP techniques and the STL container classes, and implement shortest path, minimum spanning tree and maximum flow problems.
 Describe common applications for each data structure studied in the course.
 Arrive at a strategy for selecting the right data structure for the job.

Special Facilities and/or Equipment  
  Access to a computer laboratory with C++ compilers.
 Website or course management system with an assignment posting component (through which all lab assignments are to be submitted) and a forum component (where students can discuss course material and receive help from the instructor). This applies to all sections, including oncampus (i.e., facetoface) offerings.
 When taught via Foothill Global Access on the Internet, the college will provide a fully functional and maintained course management system through which the instructor and students can interact.
 When taught via Foothill Global Access on the Internet, students must have currently existing email accounts and ongoing access to computers with internet capabilities.

Course Content (Body of knowledge)  
  The Vector ADT
 Implementing a vector from scratch
 Using STL
 Linked List ADT
 Implementing a linked list from scratch
 Using STL list and associated iterator
 Applications of Vectors and Lists
 Sparse Matrices
 Queues
 Stacks
 The "subset sum problem" and its solution using vectors and lists
 Time Complexity
 O(f) order of magnitude
 o(f) order of magnitude
 theta(f) order of magnitude
 omega(f) order of magnitude
 Constant, polynomial, logarithmic, and exponential time complexity
 NlogN time complexity
 Improper use of recursion leading to exponential time complexity
 Measuring Asymptotic Behavior
 Empirical methods of measurement (benchmarking)
 Brute force vs. strategies that use branching or divideandconquer algorithms
 Timing greedy and depthfirst algorithms in graphs
 General Trees
 Tree nodes, roots, leaves, children and siblings
 Binary node implementation of a general tree
 Insertion and deletion in general trees
 Traversal with recursion
 Cloning trees
 Searching and Binary Search Trees (BSTs)
 Ordering condition and structure condition
 OOP (objectorientedprogramming) Implementation
 Time complexity consequence of the divideandconquer algorithm in of BSTs
 The alternative "lazy deletion" implementation of tree nodes and its comparative performance to "hard deletion"
 Threaded trees
 Bin heaps
 Balanced BSTs 1: AVL Trees
 Tree height and rebalancing
 Single and double rotations as the fundamental rebalancing tools
 Implementing AVL trees by inheriting from a generic BST
 Balanced BSTs 2: Splay Trees
 Splaying
 Top down vs. bottomup splaying
 Implementing splay trees using STL classes
 Hashing
 Hashing functions
 Separate chaining
 Linear and quadratic probing
 Priority Queues
 The percolate down operation
 Bin heap implementation of priority queues
 Heap sort
 NonNlogN Sorts
 Insertion sort
 Shellsort
 Benchmarking nonNlogN sorts compared with the STL sort
 NlogN Sorts
 Merge sort
 Heapsort
 Quicksort
 Benchmarking NlogN sorts compared with the STL sort
 Indirect Sorting
 What it is
 Why it's needed in C++
 Graph Theory
 Structures of a graph
 Nodes, edges and adjacency tables
 Shortest path algorithms and Dijkstra
 Minimal spanning tree algorithms and Kruskal
 Maximum flow graphs and their algorithms
 The use of data structures in common applications areas
 Math
 Physics
 Chemistry
 Biology
 Astronomy
 Business and finance
 Internet
 Strategies for selecting the right data structure.
 Storage allocation and use memory for the data structure
 Deciding on a userdefined or builtin data structure
 How declaration models, binding and visibilty affect different ADT implementations.

Methods of Evaluation  
  Tests and quizzes
 Written laboratory assignments which include source code, sample runs and documentation.
 Final examination

Representative Text(s)  
 Weiss, Mark Allen. Data Structures and Algorithm Analysis in C++. Third Edition. Addison Wesley, 2006. This text is a classic text in the field and is used by many universities in both undergraduate and graduate classes on the subject of data structures.

Disciplines  
 Computer Science


Method of Instruction  
  Lectures which include motivation for syntax and use of the C++ language and OOP concepts, example programs, and analysis of these programs.
 Online labs (for all sections, including those meeting facetoface/on campus) consisting of
 A programming assignment webpage located on a collegehosted course management system or other departmentapproved Internet environment. Here, the students will review the specification of each programming assignment and submit their completed lab work.
 A discussion webpage located on a college hosted course management system or other departmentapproved Internet environment. Here, students can request assistance from the instructor and interact publically with other class members.
 Detailed review of programming assignments which includes model solutions and specific comments on the student submissions.
 In person or online discussion which engages students and instructor in an ongoing dialog pertaining to all aspects of designing, implementing and analyzing programs.
 When course is taught fully online:
 Instructorauthored lecture materials, handouts, syllabus, assignments, tests, and other relevant course material will be delivered through a college hosted course management system or other departmentapproved Internet environment.
 Additional instructional guidelines for this course are listed in the attached addendum of CS department online practices.


Lab Content  
  Implementation of timeintensive algorithms on various data types
 Design and implement an algorithm whose execution time and/or memory requirements grow significantly when data size increases.
 Use generics (A.K.A. templates), which are a universal tool in advanced data structures, in some aspect of the algorithm.
 Demonstrate that the algorithm adapts correctly when the generic that you use is applied to at least two distinct underlying data types.
 Document the results of the algorithm when the program is applied to different sized data and different underlying data types.
 Using linkedlist ADTs to optimize for sizevarying or spacesensitive data types
 Demonstrate the ability to use programming languagesupplied linkedlist structures in a problem that is not easily solved using fixedsize ADTs such as arrays.
 Incorporate generics so as to allow the algorithm to work on various underlying data types.
 Try different sized data for the linkedlist and demonstrate that it handles growth properly.
 Summarize the results along with sample program runs.
 Analyzing time complexity in the lab
 Implement an assigned algorithm after first predicting its time complexity (linear, quadratic, NlogN, etc.).
 Run the algorithm on various sized data sets, recording times.
 Describe the largest size data set that the computer can handle without running out of memory or taking an unreasonable amount of time.
 Compare the expected growth rate with the observed growth rate.
 Demonstrating competence with binary search trees
 Implement a binary search tree (BST) from scratch, or make significant assigned adjustments to an existing BST data structure supplied by your instructor.
 Use recursion as appropriate for some of the BST methods.
 Demonstrate that the class works on various underlying base type by use of generic specialization.
 Supply runs and report on expected vs. observed time complexity.
 Demonstrating competence with balanced trees
 Implement a some assigned balanced tree algorithm (such as AVL, splay or redblack) from scratch, or make significant adjustments to an existing balanced tree algorithm supplied by your instructor.
 Use recursion as appropriate for some of the balanced tree methods.
 Demonstrate that the class works on various underlying base type by use of generic specialization.
 Supply runs and report difference between balanced tree times and simple BST times.
 Incorporating hash tables into programs
 Produce a lab that creates or modifies a hash table and hashing function.
 Write a client that tests out the hash table on various data.
 Using a large data set, demonstrate that nearconstant time access is produced by the hashing function and hash table.
 Supply runs and report results with varying sized data sets.
 Analysis of a single sort algorithm
 Implement a single sort algorithm as directed by the instructor.
 Experiment with coding adjustments to try to improve the performance.
 Compare the known time complexity of that algorithm with what you observe using increasingly larger data sets.
 Attempt to explain any discrepancies in the expected vs. observed growth rate of the sort algorithm.
 Analysis of multiple sort algorithms
 Implement multiple sort algorithms, at least two of which involve Shell sort and quicksort.
 Experiment with coding adjustments to try to improve the performance on any one of them to see if you can beat the fastest of the algorithms.
 Time the algorithms on very small to very large data sets.
 Report on which algorithms work better on small sets, and which on large sets.
 Writing projects that use graph theory
 Implement a generic (a.k.a. template) that will realize/specialize a graph of any underlying data type, either from scratch or using code provided by your instructor .
 Write one of the common algorithms for graphs: shortest path, maximum flow or minimum spanning tree.
 Discuss the problems that arise when debugging labs which involve data structures as complex as graph theoretic algorithms
 Devise a reasonable output for displaying graphs and supply samples with your program runs.


Types and/or Examples of Required Reading, Writing and Outside of Class Assignments  
  Reading
 Textbook assigned reading averaging 30 pages per week.
 Reading the supplied handouts and modules averaging 10 pages per week.
 Reading online resources as directed by instructor though links pertinent to programming.
 Reading library and reference material directed by instructor through course handouts.
 Writing
 Writing technical prose documentation that supports and describes the programs that are submitted for grades.
 Writing specifications using prose to connect natural English language to the formulaic programming languages.
