Studies commonly used data structures found in computing and the algorithms that manipulate them. Topics include lists, stacks, queues, trees, tables, priority queues, graphs, recursion, and sorting algorithms. Emphasizes the space and time efficiency of the various data structures and their associated algorithms. The course reviews and solidifies object oriented programming concepts learned in C.S. 2546. Prerequisite: C.S. 2546.  Co-requisite: C.S. 3166. (2nd)

Expectations:

E1.  Students know how to use simple module specification and design techniques and know how to implement such designs in a high-level programming language. (C.S. 2106)

E2.  Students know how to use advanced programming techniques, including recursion, file I/O, abstraction, multi-file programs, and using programming language libraries. (C.S. 2116)

E3. Students have a basic understanding of object-oriented programming and design, and can create programs using classes and objects. (C.S. 2546)

E4. Students are familiar with summation notation, union and intersection of sets, logarithms, exponential functions, and are able to work with abstractions and manipulate formulas. (Math 1530)

Course Outcomes:

R1. Students know the software development cycle and good OOP practices.  (CS/SE6, CS/SE15)

R2. Students understand Abstract Data Types (ADTs), how to specify ADTs with Unified Modeling Language (UML), how to implement ADTs with C++. (CS/SE11, CS/SE15)

R3. Students know how to use recursion and prove the correctness of a recurrence by mathematical induction. (CS/SE11, CS/SE14)

R4. Students understand basic data structures like lists, sorted lists, stacks, and queues and be able to evaluate the best data structure to implement them. (CS/SE3)

R5. Students understand space and time efficiency (Big O notation) of data structures and algorithms. (CS/SE3, CS/SE14)

R6. Students understand and use general trees, binary trees, binary search trees, and balanced search trees, tables, priority queues, and hash tables. (CS/SE15)

R7. Students can evaluate and select the appropriate data structure for a given problem (CS/SE3).

R8. Students know about intellectual property, including copyright and patent protection on data structures and algorithms. (CS/SE1)

R9. Students know how to program in C++ and have experience with file input and output, throwing and catching exceptions, dynamic memory allocation, pointers, strings, class templates and the Standard Template Library (STL), inheritance, virtual functions, polymorphism, and abstract base classes. (CS/SE15)