1. You are to write a 2-3 page paper in the APA format about Abstract Data Types
ID: 3690270 • Letter: 1
Question
1. You are to write a 2-3 page paper in the APA format about Abstract Data Types. The paper should first introduce the concept of Abstract Data Types or ADT and then focus on one or more actual ADTs. You can select any one of the ADTs, like Stack, Queue, Lists, Trees, Graphs, etc. You need to explain what it is and what it can achieve or perform and some examples of the usage of it, like when you would use such an ADT. 2. Also included are a title page and a reference page. 3. The paper is to be typed, double-spaced, 12-pitch font, using Times New Roman font. 4. There will be 1” margins on all sides. 5. The paper is to be in the APA format and edited by the student for grammar, spelling, etc. 6. You must include at least one in-text citation and one reference (that is not our text), both of which must be in correct APA format. 7. You will be graded on the content of the paper, your language skills, and your writing skills. 8. You must turn in your paper on time, according to the Course Outline in this syllabus. Please i need this to be clear because it is for my final term paper.
Explanation / Answer
In computer science, an abstract data type (ADT) is a mathematical model for data types where a data type is defined by its behavior (semantics) from the point of view of auser of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations. This contrasts with data structures, which are concrete representations of data, and are the point of view of an implementer, not a user.
Formally, an ADT may be defined as a "class of objects whose logical behavior is defined by a set of values and a set of operations";[1] this is analogous to an algebraic structurein mathematics. What is meant by "behavior" varies by author, with the two main types of formal specifications for behavior being axiomatic (algebraic) specification and anabstract model; these correspond to axiomatic semantics and operational semantics of an abstract machine, respectively. Some authors also include the computational complexity ("cost"), both in terms of time (for computing operations) and space (for representing values).
In practice many common data types are not ADTs, as the abstraction is not perfect, and users must be aware of issues like arithmetic overflow that are due to the representation. For example, integers are often stored as fixed width values (32-bit or 64-bit binary numbers), and thus experience integer overflow if the maximum value is exceeded.
ADTs are a theoretical concept in computer science, used in the design and analysis of algorithms, data structures, and software systems, and do not correspond to specific features of computer languages—mainstream computer languages do not directly support formally specified ADTs. However, various language features correspond to certain aspects of ADTs, and are easily confused with ADTs proper; these include abstract types, opaque data types, protocols, and design by contract. ADTs were first proposed byBarbara Liskov and Stephen N. Zilles in 1974, as part of the development of the CLU language.
For example, integers are an ADT, defined as the values …, 2, 1, 0, 1, 2, …, and by the operations of addition, subtraction, multiplication, and division, together with greater than, less than, etc., which behave according to familiar mathematics (with care for integer division), independently of how the integers are represented by the computer.[a]Explicitly, "behavior" includes obeying various axioms (associativity and commutativity of addition etc.), and preconditions on operations (cannot divide by zero). Typically integers are represented in a data structure as binary numbers, most often as two's complement, but might be binary-coded decimal or in ones' complement, but the user is abstracted from the concrete choice of representation, and can simply use the data as integers.
An ADT consists not only of operations, but also of values of the underlying data and of constraints on the operations. An "interface" typically refers only to the operations, and perhaps some of the constraints on the operations, notably pre-conditions and post-conditions, but not other constraints, such as relations between the operations.
For example, an abstract stack, which is a last-in-first-out structure, could be defined by three operations: push, that inserts a data item onto the stack; pop, that removes a data item from it; and peek or top, that accesses a data item on top of the stack without removal. An abstract queue, which is a first-in-first-out structure, would also have three operations: enqueue, that inserts a data item into the queue; dequeue, that removes the first data item from it; and front, that accesses and serves the first data item in the queue. There would be no way of differentiating these two data types, unless a mathematical constraint is introduced that for a stack specifies that each pop always returns the most recently pushed item that has not been popped yet. When analyzing the efficiency of algorithms that use stacks, one may also specify that all operations take the same time no matter how many data items have been pushed into the stack, and that the stack uses a constant amount of storage for each element.
Abstract data types are purely theoretical entities, used (among other things) to simplify the description of abstract algorithms, to classify and evaluate data structures, and to formally describe the type systems of programming languages. However, an ADT may be implemented by specific data types or data structures, in many ways and in many programming languages; or described in a formal specification language. ADTs are often implemented as modules: the module's interface declares procedures that correspond to the ADT operations, sometimes with comments that describe the constraints. This information hiding strategy allows the implementation of the module to be changed without disturbing the client programs.
The term abstract data type can also be regarded as a generalised approach of a number of algebraic structures, such as lattices, groups, and rings.The notion of abstract data types is related to the concept of data abstraction, important in object-oriented programming and design by contract methodologies for software development.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.