PSU

From

---

Current revision as of 19:51, 29 October 2011

[PSU CS163] The goal of this class is to acquaint students with structures used in C++ for the storage and manipulation of data. The concept of data abstraction and the problem of building implementations of abstract data types are emphasized. Both static and dynamic implementations of major structures are presented and the advantages and disadvantages of each are discussed. Structures include lists of several types, stacks, queues, trees, binary trees, B-trees and graphs. Recursion and key transformation (hashing) are examined. Students are encouraged to examine algorithms and to make judgments about the practical and social application of these algorithm concepts to large scale programming projects; the course stresses the importance of quantitative methods in designing software.

Upon the successful completion of this course students will be able to:

• Apply data abstraction in a C++ programming problem.
• Become proficient at evaluating the benefits and drawbacks of their design in terms of memory and run time efficiency.
• Program using classes and linear linked lists, circular linked lists, doubly linked lists, binary search trees, arrays of linear linked lists.
• Select the proper sorting algorithm for a problem.
• Design solutions to problems requiring complex data structures (combinations of lists, stacks, queues, hash tables, and trees)
• Apply data abstraction.
• Apply both static and dynamic implementations of lists, stacks, queues, hash tables and trees.
• Evaluate the performance tradeoffs between binary search, 2-3, 2-3-4, red-black, B-trees, and AVL trees
• Build and traverse data structures to manage a simple graph.
• Apply recursion and key transformations.
• Make judgments about the practical and social application of algorithm concepts as they apply to large scale programming projects.