CIS 351 - Data Structures

Course Objectives

Upon successful completion of the course, a student should be able to: 1. Describe the basic knowledge to edit, compile, test run a computer program written by an imperative language.
2. Apply the basic programming constructs: branching, looping, recursion and Boolean functions to compose a computer program written by an imperative language.
3. Describe the procedures required to compose computer programs with IO operations and arrays written by an imperative language.
4. Identify the techniques of (1) parameter passing, (2) aliasing for the manipulation of arrays, and (3) exception handling in a given computer program.
5. Describe the rationale of exception handling and demonstrate its usage with code snippets.
6. Explain the following basic object-oriented programming concepts: class variables, class methods, instance variables, instance methods and identify their usage in a given Java class.
7. Define the key features of the stack data structure, explain a possible array-based implementation (ArrayStack) and discuss how to use an array in a backtracking scenario.
8. State the definitions of (big-O, big-Omega and big-Theta), discuss its use in analyzing the complexity of basic sorting and searching algorithms and apply the techniques (big-O, big-Omega and big- Theta) to analyze the complexity of the algorithms discussed.
9. Apply the analysis techniques (big-O, big-Omega and big-Theta) to determine the complexity of basic operations of the stack data structure.
10. Apply the techniques (big-O, big-Omega and big-Theta) to analyze the complexity of the usual queue operations data structure and evaluate the overall complexity of using the queue data structure in a typical application.
11. Explain what a Java reference is and explain the relations to the concept of pointers.
12. Illustrate, with the help of diagrams, how to use Java reference concept to build a node and to implement a linked-list based stack and/or a queue.
13. Explain the need to employ generic programming techniques, and explain its use to build the stacks and queue data structures via code examples.
14. Compose the key procedures regarding the implementation(s) of a stack and/or queue data structures using generic programming techniques.
15. Describe an implementation(s) of a stack and/or queue based on double linked lists.
16. Compare and contrast an implementation of either a stack or a queue via a singly linked list versus an implementation which uses a doubly linked list. Give a critique using the big-O, big-Omega and big-Theta analysis techniques.
17. Present the concept of hashing as an alternate search technique, state the basic features to perform hashing (hash functions and tables) and discuss the criteria to evaluate it effectiveness.
18. Show, with the aid of diagrams, two different ways open addressing to implement a hash.
19. Define trees and its basic parameters (paths, heights etc.); Discuss the use of each type of trees as a data structures and identify the key supporting operations.
20. State at least four possible ways to order the nodes of a binary tree; analyze, compare and contrast the implementations of the ordering algorithms associated to each of the methods stated.
21. Illustrate, with the aid of diagrams, a tree implementation of the dictionary data type.
22. State the definition of a binary search tree.
23. Describe, compare, contrast and analyze the implementations of the dictionary operations (insert, delete and find) of a binary search tree.
24. Present the main features of a priority queue, discuss an implementation that uses a binary search tree as the underlying data structure and analyze the running times of each of the operations for its maintenance.
25. Define the binary max-heap property as the defining property for a binary max-heap.
26. Explain, with the aid of diagrams and pseudocode, the key operations (1) heapify, and d(2) make-heap for the maintenance of the binary heap data structure. In addition, be able to analyze the worse running time of these operations.
27. Discuss heap sort as an application of using a binary max-heap data structure for sorting and its running time.
28. Discuss an implementation of the priority queue ADT by using a binary heap, and describe an implementation of each of the priority operations and discuss their worse running time.
29. Present the key features (depth of a node, depth of the tree) of a random binary tree.
30. Define the treap data structure and discuss its connections to the binary tree and heap.
31. State the definitions for undirected graphs and directed graphs, present their basic features and describe implementations that are (1) based on a two dimensional array, and (2) one that are based on array of linked lists.
32. Discuss, compare and contrast (1) the adjacent matrix representation, versus (2) the adjacency list representation as the underlying data structure for the graph data type.
33. Describe, with the aid of diagrams and pseudocode, two graph traversal method (1) breadth first search (BFS), and (2) depth first search (DFS).
34. Give an outline to solving each of the problems such as: detecting cycles, computing shortest paths, existence of a path between two given vertices, using either DFS and BFS.