Quiz#1 Topics and Promises COP3530, Fall 1999

Topics:

1. Abstract data type (ADT) consists of an encapsulated state and a set of behaviors.
An abstract implementation is a data model specifying some abstract organization of data (an ADT’s state), e.g., a list, a binary tree, a binary search tree, set, etc.
A data structure is the way we represent an abstract implementation. For example a list can be represented by an array of data items or by a linked list of data items.
In Java or C++, a behavior is invoked by a message. Methods are used to provide the behaviors associated with messages.

2. OOP concepts. Classes, encapsulation, hierarchies, polymorphism, static and dynamic binding.

3. Templates – class and method templates

4. Order analysis – Big-O, Omega, Theta, little-o; solving recurrence equations

5. Parallel Sorting – array architecture, even/odd exchange algorithm, analysis (cost vs work; cost/work efficiency).

6. Algorithm classifications (greedy, divide and conquer, dynamic programming)

use of amortization

7. List data model. Sublists versus subsequences. operations: insert, delete, lookup, sort, merge (two lists to one), split (one to two), concatenate, first, last, head, tail, retrieve ith, length, isEmpty, isNotEmpty

8. Abstract Data Types based on List data model
Stack – clear, isEmpty, isFull, push, pop
Queue– clear, isEmpty, isFull, enqueue, dequeue
Deque – clear, isEmpty, isFull, addLeft, addRight, removeLeft, removeRight
array and linked list implementations

9. Maximum sublist (consecutive subsequence) problem (greedy solution) and its variants (some greedy, some not)

10. Tree data model – terminology, various data structures, traversals, binary trees.
Tree data model use for abstract implementations of dictionaries. Binary Search Tree, AVL Trees and Trie abstract implementations.

11. Hashing. hash function; chaining; open addressing (linear, quadratic, double, random, virtual; extendible)

12. Priority queue ADT. priority ordered tree (POT) abstract implementation, balanced POT abstract implementation, and heap data structure. heapify, heapSort, bubbleUp and bubbleDown – code and analysis.
Expression trees – height, evaluation, code generation

13. Longest Common Subsequence (LCS) and Longest Increasing Subsequence (LIS) Problems– dynamic programming
Compare naive approach (exponential) versus dynamic programming (quadratic)

Promises:

1. I give you an ADT with description of semantics of each serviuce. I also give you some suggested abstract representations (data models) and, where appropriate, data structures for these representations. You must then fill in a table specifying the order of the best algorithms (assuming the most appropriate data structures, if I omit this) for each service when the specified abstract representation is used.

2. A recurrence equation to solve using inductive reasoning and then a short inductive proof to verify your assertion. I may be kind and give you the solution, in which case you must only verify this using an inductive proof.

3. A question regarding the Even-Odd Transposition parallel sorting algorithm.

4. A question about algorithms concerning subsequnces, e.g., max sum of contiguous subsequence or LCS or LIS.

5. An algorithmic and/or data structure question about lists, stacks, queues or deques.

6. An algorithmic and/or data structure question about trees, tries, BSTs or AVL trees.

7. A question about hash tables

8. A question about heaps

9. I will not have you write any long code sequences

10. The assignments, diagnostic test and sample questions are good models to use when you prepare for this quiz.