Computer Software

  1. Alphanumeric Data
    • - refers to charachters that can be displayed or printed including numerals and symbols ( $, &, #....)
    • -excludes control characters ( tab, carriage return, form feed...)
    • - all symbolic data must be represented by binary code.
  2. Coding
    - Refers to the manner in which alphanumeric data and control characters are represented by a sequence of bits.
  3. ASCII
    • - American Standard Code for Information Interchange
    • - a seven-bit code permitting 128 ( 27) different combinations
    • - the use of the high order eighth bit is not commonly used in microcomputers.
    • - ASCII -coded magnetic tape and disk files are used to transfer data and documents between computers of all sizes that would not otherwise share data structures
    • - Extended Binary Coded Decimal Interchange Code
    • - is in widespread use in SuperComputers
    • - It uses eight bits ( a byte) for each charachter, allowing a max of 256 (28) different charachters.
  5. Hexadecimal
    • - or "packed" format is used to simplicity working with EBCDIC data since strings of binary digits (bits) are difficult to read.
    • - Each byte is converted into two strings are then converted to hexadecimal. Since (1111)2 = (15)10 = (F)16 the largest possible EBCDIC characters is coded FF in hexadecimal.
  6. What is 11110111 in EBCDIC?
    • 1111 = (15)10 or (F)16
    • 0111 = (7)10 or (7)16
  7. Program
    • - a sequence of computer instructions that performs some function
    • - a program is designed to implement an algorithm.
  8. Algorythm
    • - a procedure consisting of a finited set of well-defined steps
    • - each step in the algorithm usually is implemented by one or more instructions ( eg, Read, GOTO, OPEN ...) entered by the programmer.
    • - These original "human-readable" instructions are known as "source code statements".
  9. Source Code Statements
    • - Original "human-readable" insturctions
    • - Except in rare cases, a computer will not understand source code statements.
    • - Therefore, the source code is translated into machine-readable object code and absolute memory locations.
    • - Eventually, an executable program is produced.
  10. Software vs. Firmware vs, Hardware
    • Software - if the executable program is kept on disk or tape.
    • Firmware - if the program is placed in ROM or EPROM
    • Hardware - the computer mechanism itself.
  11. Internal Subprograms
    • - those subprograms written by the programmer.
    • - external subprograms are supplied in a library by another source.
  12. Structured Program II
    • - Ideally, the main line program will consist entirely of a series of calls ( references ) to these subprograms.
    • - Liberal use is made of FOR/NEXT, DO/WHILE, and DO/UNTIL. commands.
    • - Labels and GOTO commands are avoided as much as possible.
  13. Structured Program II
    • - Ideally, the main line program will consist entirely of a series of calls (references ) to these subprograms
    • -Liberal use is made of FOR/NEXT, DO/WHILE and DO/UNTIL commands.
    • - Labels and GOTO commands are avoided as much as possible.
  14. Recursive Calls
    • - Very efficient programs can be constructed in language that support recursive calls ( ie permit a subprogram to call itself )
    • - Some languages permit recursion, others do not.
  15. Local vs. Global Variables
    • - Variables whose values are accessible strictly within the subprogram are Local Variables.
    • - Global Variables can be refered to by the main program and all other subprograms.
  16. Loop
    • - If <conditions> THEN <action1> ELSE <action2>
    • - DO WHILE <condition> ...set of instructions ENDWHILE
    • -DO UNTIL <condition> ....set of instructions ... END UNTIL
    • - FOR <counter range> ...instructions NEXT <counter>
    • - GOTO operation avoided, fallen from favor
  17. Fields, Records, and File Types
    • - Record - a collection of Fields.
    • - Field - ie name, age and address
    • - File - group of records stored in
    • - Sequential File structures - magnetic tape
    • - Indexed Sequential Files - a separate index file is used to locate records
    • - Random (direct access) file structure
  18. File Indexing
    • - It is more efficient to keep the names in the order of entry than to sort the list each time names are added or deleted.
    • - An index ( key or keyword) file is analogous to the index at the end of a book.
    • - One field in the record is selected as the key filed ( record index )
    • - More than one field can be indexed, however, each field will required its onwn index file.
    • - The sorted keys are usually kept in a file separate from the data file.
  19. Successive Minima Sort
    • - a list is searched sequentially until the smallest element is fround and brought to the top of the list
    • - that element is then skipped and the remainig elements are searched for the smallest element which is placed after the previous minima
    • - comparisons required - n ( n-1 ) / 2
    • - comparisons required when n is large - n2 / 2
  20. Random Secondary Storage Devices
    • - Also known as mass storage devices
    • - Random access (direct access) storage devices
    • - Magnetic disk drives ( hard drives ) have several "platters" each with one or more read/write heads.
    • - "Tracks" are concentric storage areas
    • - "Sectors" are pie-shaped subdivisions of each track
    • -"cylinders" are the same numbered track on each platter
    • - some platters and "disk packs" are removable but most are not.
  21. Flow Chart
    - a step-by-step drawing representing a specific procedure or algorithm.
  22. Terminal - (flowchart
    • _________________
    • (_________________)
  23. Input/Output ( Flowchart )
    • _____________
    • / /
    • /____________/
  24. Processing ( Flowchart)
    • ____________
    • l........................1
    • 1___________1
    • refer to caluculations or data manipulation ( along with the predefined process symbol )
  25. Predefined Process (flowchart)
    • _______________
    • ll..........................ll
    • ll_____________ll
    • refer to calculations or data manipulation ( along with the processing symbol.
  26. Decision (flowchart)
    • ............./\
    • .........../...\
    • ..........\..../
    • ...........\./
    • - indicates a point where a decision must be made or where two items compared.
  27. Connector (flowchart)
  28. Connector (flowchart)
    • .........O
    • - indicates that the flowchart continues elsewere.
  29. Off- Page
    • ________
    • l..............l
    • l..............l
    • \............./
    • ..\........./
    • ....\..../
    • Indicates flowchart continues on another page.
  30. Annotation (flowchart)
    • ...................___________
    • _________l
    • ..................l___________
    • Note: Comments can be written in an annotation symbol
  31. Low-Level Languages
    • Two general types of specific languages
    • 1. Low- Level
    • 2. High -Level
    • Low-Level languages include:
    • 1. machine language
    • 2. assembly language
  32. Machine Language Instructions
    • - intrinsically compatable with and understood by the computers CPU
    • - they are the CPUs native language
    • - an insturction normally consists of two ports:
    • ...1.the operation to be performed (op-code)
    • ...2. the operand expressed as a storage location
    • - Each instruction ultimately must be expressed as a series of bits, a form known as intrinsic machine code.
    • - However, octal and hexidecimal coding are more convenient.
    • -In either case, coding a machine language program is tedious and seldom done by hand.
  33. Assembly Language
    • - more sophisticated ( ie is more symbolic)
    • than machine language
    • - Mneumonic codes are used to specify the operations.
    • - The operations are refered to by variable names rather than by the addresses.
  34. Macros ( macro instructions )
    • - Blocks of code that are to be repeated verbatim at multiple locations in the program.
    • - They are written once and refered to by a symbolic name in the source code.
  35. Assembly Language Code
    • - is translated into machine language code by an assembler (macro-assembler) if macros are supported
    • - after assembly, portions of other programs or function libraries may be combined by a linker.
    • In order to run, the program mjust be placed in the computers memory by a loader.
    • - Assembly language programs are preffered for highly efficient programs.
    • - However, the coding inconvenience outweighs the advantage for most applications.
  36. Language Type Examples
    • Language Instruction
    • Intrinsic Machine Code.....11110001
    • Machine Language.............1A
    • Assembly Language...........+
  37. High- Levle Languages
    • - easier to use than low-level languages because the instructions resemble english.
    • - High level statements are translated into machine language by either an interpreter or compiler.
  38. Compiler
    • - performs the checking and conversations on all instructions only when the compiler is invoked.
    • - Then a true stand-alone executable program is created.
  39. Interpreter
    - An interpreter differs from a compiler in that it checks the instructions and converts then line-by-line into machine code during execution but produces no stand-alone program capable of being used without the interpreter.
  40. Interpreters vs. Compilers Continued
    • - Some interpreters check syntax as the statement is entered by the programmer.
    • - some languages and implementations of other languages blur the distinction between interpreters and compilers.
    • - Terms such as pseudo-compiler and incremental compiler are used in these cases.
  41. Relative Computational Speed
    • 1. Assembly language programs._____Fastest v
    • 2. Compiled
    • 3. Pseudo-compiled
    • 4. Interpreted_______________Slowest v
    • Most Efficient Program Structures
    • 1. Simple equations - in repetitive opeartions__Fast v
    • 2. Stand - alone loop
    • 3. Loop withing a subroutine ________Slow v
    • Overhead: Incrementing the loop variables and managing the exit and entry points - these take time.
  42. Structured Language
    • - It is structured if subroutines and other procedures each have one specific entry point and one specific return point.
    • - Contrast this with BASIC with :
    • __1) GOSUB - to a specific subroutine with a return from anywhere in subroutine
    • __2) GOTO statements to anywhere in the main program.
  43. Strong Data Types
    - A languages has "Strong Data Types" if integer and real numbers cannot be combined in arithmentic statements.
  44. Portable Language
    • - A "Portable" Language can be implemented on different machines.
    • - Most portable languages are either (1) sufficiently rigidly defined ( as in "ADA" or "C" ) to eliminate variants and extensions or (2) (as in the case of "Pascal") are compiled into an intermediate machine independent form called pseudocode (p-code)
  45. Pseudocode (p-code)
    • - neither source nor object code
    • - The language is said to have been "ported" to a new machine when an interpreter is written that converts p-code to the appropriate machine code and supplies specific drivers for input, output, printers and disk use.
    • - Some companies have produced Pascal engines that run p-code directly.
  46. Structured Programming
    • - Also known as " top-down programming", "procedure-oriented programming", and "GOTO-less programming.
    • - Devides a procedure or algorithm into parts known as subprogramms, subroutines, modules, blocks or procedures.
    • - The format and readability of source code do not define structured programming.
  47. Bubble Sort
    • - In a bubble sort, each element in the list is compared with the element immediately following it.
    • - If the first element is larger, the positions of the two elements are reversed (swapped)
    • - The smaller element thus "bubbles" to the top
    • - If no swapps are made in a pass, list is sorted n2/2 comparisons are needed on average to sort list. Same as successive minima but more resources.
  48. Insertion Sort
    • - In an insertion sort, the elements are ordered by rewriting them in the proper sequence.
    • - After the proper position of an element is found, all elements below that position are bumped down one place in the sequence Vacancy filled by insertion.
    • - At worst n2/2 comparisons required
    • - On average, approximately n2/4 comparisons.
  49. Quicksort
    • - more complex but reduces the average number of comparisons to nx log(n) / log (2) which is much less than the other sorts on the order of n2 for succesive minima, bubble, and insertion (in order of n x log(n) )
    • - The quick sort falters in speed when the elements are in near perfect order.
  50. Heap Sort
    - The maximum number of comparisons for a heap sort is n x log(n)/log(2) but it is likely that even fewer comparisons will be needed.
  51. Searching (Probing)
    • - In a randomly organized group of records, a particular element in the list can be found only by a linear (sequential ) search.
    • - 1 comparison at best, n comparisons at worst, n/2 on average comparisons ( of order n )
    • - If the records are in ascending or decending order, the binary sort will be superior.
    • - The search begins by looking at the middle element in the list.
    • - If the middle element is the one sought-for the search is over.
    • - Otherwise, half of the list will be disregarded as too large or small.
    • - Then we look at the middle element of that list and so on.
    • - The number of required comparisons if in ascending or decending order is Log(n)/ Log(2) of order Log(n)
  52. Hashing
    • - An Index File is not needed if the record number (i.e. storage location for a read or write operation ) can be calculated directly from the key.
    • - This technique is called "hasing".
  53. Hashing function or algorithm
    • - The procedure by which a numeric or non-numeric key ( eg a last name ) is converted into a record number.
    • - Most hashing algorithms use a remaindering modululs (remainder after deviding the key by the number of records, n, in the list.
    • - Excellent results if n is a prime number and poor results occur if n is a power of 2.
    • - (finding a record in this manner requires it to have been written in a location determined by the same hashing routine.
    • - Not all hashed record numbers will be correct.
  54. a "Collision" ( in hashing )
    • - a collision occurs when an attempt is made to use a record number that is already in use.
    • - chaining, linear probing, and double hashing are techniques used to resolve such collisions.
  55. Database Structures
    • - Databases can be implemented as indexed files, linked lists, and tree structures.
    • - in all three cases, the records are written and remain in the order of entry.
  56. Flat File
    • - has only one key field by which records can be located.
    • - "searching " techniques are used to locate a particular record.
  57. Linked (Threaded ) List
    • - each record has an associated "pointer" (usually a record number or memory address) to the next record in key sequence.
    • - Only two pointers are changed when a record is added or deleted.
    • - Generally, a linear search following the links through the records are used.
    • Key and Data Files
    • Key File
    • Adams ......3
    • Jones.........2
    • Smith........1
    • Thomas....4
    • Data File
    • 1.....Smith .............John............27
    • 2.....Jones.............Wanda.........39
    • 3....Adams...........Henry..........58
    • 4....Thomas.........Susan...........18
  58. Tree Structures
    • - Pointers are also used Tree structures
    • - Each record has one or more pointers to other records that meet certain criteria.
    • - In a binary tree structure, each record has two pointers - usually to records that are lower and higher, respectively, in key sequence.
    • - In general, records are in a tree structure are refered to as nodes.
  59. Tree Structure ( How records are found )
    • - Records are found in a tree by starting at the root node and moving sequentially according to the tree structure.
    • - The number of comparisons required to find a particular element is 1+(log(n))/log(2)) which is on the order of log (n)
  60. Root Node ( in tree structures )
    • - The first record in a file is called the root node.
    • - A particular node will have one node above it ( the parent or ancestor ) and one or more nodes below it ( the daughters or )
    • .......................................[ Root Node ]
    • .................................................l.........................
    • ....._____James__.................................____Smith_____
    • Adams.........Kensington................Rogers.....................Thomas
  61. Hierarchical Database
    • - contains records in an organized, structured format.
    • - Records are organized according to one or more of the indexing schemes.
    • However, each field within a record is not normally accessible.
    • ......................................................................................
    • ..............l...................................l............................l
    • ..........Smith........................Jones.....................Thomas....
    • John................27.....Wanda.............39.....Susan................18
  62. Relational Database
    • - Stores all information in the equivalent of a matrix
    • - Nothing else ( no index files, pointers, etc,) is needed to find, read, edit, or select information.
    • - Any information can be accessed directly by refering to the field name or field value.
    • ...._________________________________________
    • ...l Rec. no ....l....Last......l....First....l....Age....l
    • ...l......1..........l....Smith...l....John....l....27.......l
  63. Artificial Inteligence (AI)
    • - in a machine, implies that the machine is capable of absorbing and organizing new data, learning new concepts, reasoning logically and responding to inquires.
    • - AI is implemented in a category of programs known as expert systems that "learn" rules from sets of events that are entered whenever they occur.
    • - Once the rules are learned, an expert system can participate in a dialogue to give advice, make predictions, and diagnoses or draw conclusions.
Card Set
Computer Software
FE Computers, Measurements and Controls - Software