A2 COMPS

• Abstraction


  The process of modeling a complex system in an easy to understand way by only including essential details
• Abstraction techniques


  • Functions and procedures with suitable parameters (Imperative Programming)
  • Classes (Object Orientated Programming)
  • Facts and rules (Declarative programming)
  • ADTs (Abstract Data Types)
• Serial/Sequential/Linear Search


  All the values are considered in sequence, even if an item is not found, all the values will have been considered
• Serial/Sequential/Linear Search


  • Best-case scenario: item to be found is at the start of the list → O(1)
  • Worst-case scenario → max number of comparisons, when item to be found is at the end of the list → O(N) where N is the number of elements in the list
  • Average number of comparisons → N/2

  
• Binary Search


  Used to search an ordered array, much faster than a linear search for arrays of more than a few items
• Binary Search


  1. Ordered array divided into 3 parts: middle, lower and upper

  2. Middle item is examined to see if it is equal to the sought item

  3. If not, and the middle value is greater than the sought item, the upper part of the array is disregarded

  4. The process is repeated for the bottom part
• Binary Search


  • Worst-case → log2 N + 1 → O(log2 N)
  • When compared to linear search, whose worst-case behaviour is N iterations, we see that binary search is substantially faster as N grows large. For example, to search a list of one million items takes as many as one million iterations with linear search, but never more than twenty iterations with binary search
• Insertion Sort


  Items from the input array are copied one at a time to the output array, each new item is inserted into the right place so that the output array is always in order

  
• Bubble Sort


  The list is divided into two sublists: sorted and unsorted, the largest element is bubbled from the unsorted list and moved to the sorted sublist, after that, the wall moves one element back, increasing the number of sorted elements and decreasing the number of unsorted ones
• User-defined data types


  When object-oriented programming is not being used, a programmer may choose not to use any user-defined data types. However, for a large program, their use will make a program less error-prone and more understandable. It also has less restriction and allows for inevitable user definition.
• The performance of either sort routine is the best when the data is already in order and there are a small number of data items
• Linked Lists

  Can be represented as two 1-D arrays -string array for data values and integer array for pointer values

  
• Creating a Linked list


  Setting values of pointers in free list and empty data linked list

  
• Stacks


  An ADT where items can be popped or pushed from the top of the stack only, LIFO - Last In First Out data structure
• The use of built in data types are the same for any program. However, there can't be a built-in record type because each different problem will need an individual definition of a record.
• Composite data types


  have a definition with a reference to at least one other type.
• Record Data type


  A data type that contains a fixed number of components that can be of different types. It allows the programmer to collect together values with different data types when these form a coherent whole. It could be used for the implementation of a data structure where one or more of the variables defined are pointer variables.
• Record Data type definition

  TYPE <main identifier> DECLARE <subidentifier1> : <built in data type> DECLARE <subidentifier2> : <built in data type> ENDTYPE <main identifier>.<sub identifier(x)> ← <value>
• Set Data type


  Allows a program to create sets and to apply the mathematical operations defined in set theory. Operations like: Union, Difference, Intersection, Include an element in the set, Exclude an element from the set, Check whether an element is in a set
• Objects and Classes


  In object-oriented programming, a program defines the classes to be used-they're all user-defined data types. Then for each class, the objects must be defined.
• Non-Composite data types


  Non-composite user-defined data types don't involve a reference to another type. When a programmer uses a simple built-in type the only requirement is for an identifier to be named with a defined type. They have to be explicitly defined before an identifier can be created-unlike built-in data types which include string, integer, real...
• Enumerated Data type


  A list of possible data values. The values defined here have an implied order of values to allow comparisons to be made. Therefore value2 is greater than value1(they're not string values and can't be quoted). This allows for comparisons to be made. It is also countable thus finite values.
• User-defined data types


  When object-oriented programming is not being used, a programmer may choose not to use any user-defined data types. However, for a large program, their use will make a program less error-prone and more understandable. It also has less restriction and allows for inevitable user definition.
• The use of built in data types are the same for any program. However, there can't be a built-in record type because each different problem will need an individual definition of a record.
• Composite data types


  Composite user-defined data types have a definition with a reference to at least one other type.
• Record Data type


  A data type that contains a fixed number of components that can be of different types. It allows the programmer to collect together values with different data types when these form a coherent whole. It could be used for the implementation of a data structure where one or more of the variables defined are pointer variables.
• Record Data type definition

  TYPE <main identifier> DECLARE <subidentifier1> : <built in data type> DECLARE <subidentifier2> : <built in data type> ENDTYPE <main identifier>.<sub identifier(x)> ← <value>
• Set Data type


  Allows a program to create sets and to apply the mathematical operations defined in set theory. Operations like: Union, Difference, Intersection, Include an element in the set, Exclude an element from the set, Check whether an element is in a set
• Objects and Classes


  In object-oriented programming, a program defines the classes to be used-they're all user-defined data types. Then for each class, the objects must be defined.
• Non-Composite data types


  Non-composite user-defined data types don't involve a reference to another type. When a programmer uses a simple built-in type the only requirement is for an identifier to be named with a defined type. They have to be explicitly defined before an identifier can be created-unlike built-in data types which include string, integer, real...
• Enumerated Data type


  A list of possible data values. The values defined here have an implied order of values to allow comparisons to be made. Therefore value2 is greater than value1(they're not string values and can't be quoted). This allows for comparisons to be made. It is also countable thus finite values.

  
• Enumerated Data type definition

  TYPE <Datatype> = (<value1>,<value2>,<value3> ENDTYPE DECLARE <identifier> : <datatype>
• Pointer Data type

  Used to reframe a memory location. It may be used to construct dynamically varying data structures. The pointer definition has to relate to the type of the variable that is being pointed to(doesn't hold a value but a reference/address to data).
• Pointer Data type definition

  TYPE <Datatype> = ^<type name> ENDTYPE DECLARE <identifier> : <datatype> <assignment value> ← <identifier>^
• Special use of a pointer variable is to access the value stored at the address pointed to. The pointer variable is said to be dereferenced.
• Text file

  Contains data stored according to a defined character code defined by ASCII or Unicode. A text file can be created using a text editor.
• Binary file


  A file designed for storing data to be used by a computer program(0's and 1's). It stores data in its internal representation(an integer value might be stored in 2 bytes in 2's complement representation to represent a negative number) and this file is created using a specific program. Its organization is based on records (a collection of fields containing data values).
• Serial files


  Contains records that have no defined order. A text file may be a serial file where the file has repeating lines which are defined by an end of line character(s). There's no end of record character. A record in a serial file must have a defined format to allow data to be input and output correctly. To access a specific record, it has to go through every record until found.
• Serial file access


  • Successively read record by record until the data required is found thus very slow. Uses: Batch processing, Backing up data on magnetic tape, Banks record transactions involving customer accounts every time there is a transaction
• Sequential files


  Has records that are ordered and is suited for long term storage of data and thus is considered an alternative to a database. A key field is required for a sequential file to be ordered for which the values are unique and sequential. This way it can be easily accessed. A sequential database file is more efficient than a text file due to data integrity, privacy and less data redundancy. A change in one file would update any other files affected. Primary keys from the DBMS(database management system) need to be unique but not ordered unlike the key field from the sequential files which need to be ordered and unique.