CSE 30331

J. Izaguirre (J. Stewman (06) / P. Brenner (07))

Course Goals:  Fundamental techniques in the design and analysis of non-numerical algorithms and associated data structures; Template class design and operator overloading; Detailed introduction to the C++ STL (class API?s and methods of implementation), including sequence containers (vectors, deques, lists), container adapters (stack, queue, priority queue) and associative containers (sets, maps); Dynamic memory management, pointers and linked structures (lists, trees, graphs). Sorting and searching algorithms; File compression using Huffman codes; Divide and conquer approaches; recursion and dynamic programming; heaps.

At the end of the course, students will be able to:
1.     Apply object oriented design methods to software design, including choice of appropriate data structures and algorithms.

Measures: graded programming assignments

2.     Create simple UML Use Case & Class diagrams

Measures: graded group programming project

3.     Correctly use C++ STL containers (vector, list, deque, queue, stack, priority_queue, set & map)

Measures: graded programming assignments & exam questions

4.     Compute the big-O time complexity of simple algorithms and demonstrate knowledge of the complexity of standard algorithms for searching and sorting

Measures: graded homework problems & exam questions

5.     Create recursive functions & apply simple dynamic programming techniques

Measures: graded programming assignment

6.     Create template classes and functions with overloaded operators

Measures: graded programming assignment

7.     Create and use pointers, destructors and copy constructors to properly manage dynamically allocated memory

Measures: graded programming assignment

8.     Demonstrate understanding of how heaps and binary search trees are used as effective implementation techniques for various containers

Measures: exam questions

9.     Explain hashing and collision resolution techniques

Measures: exam questions

10.  Construct binary search trees and balanced 2-3-4 & Red-Black trees

Measures: graded programming assignment & exam questions

11.  Generate Huffman codes using priority queue & binary tree

Measures: exam questions

12. Implement graphs, use and analyze their search & traversal algorithms, and create spanning trees

Measures: exam questions