Computer Software

• - 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.

- Refers to the manner in which alphanumeric data and control characters are represented by a sequence of bits.

• - American Standard Code for Information Interchange
• - a seven-bit code permitting 128 ( 2⁷) 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 (2⁸) different charachters.

• - 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)₂ = (15)₁₀ = (F)₁₆ the largest possible EBCDIC characters is coded FF in hexadecimal.

• 1111 = (15)₁₀ or (F)₁₆
• 0111 = (7)₁₀ or (7)₁₆

• - a sequence of computer instructions that performs some function
• - a program is designed to implement an algorithm.

• - 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".

• - 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.

• 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.

• - those subprograms written by the programmer.
• - external subprograms are supplied in a library by another source.

• - 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.

• - 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.

• - 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.

• - 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.

• - 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

• - 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

• - 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.

• - 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 - n² / 2

• - 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.

- a step-by-step drawing representing a specific procedure or algorithm.

• _________________
• (_________________)

• _____________
• / /
• /____________/

• ____________
• l........................1
• 1___________1
• refer to caluculations or data manipulation ( along with the predefined process symbol )

• _______________
• ll..........................ll
• ll_____________ll
• refer to calculations or data manipulation ( along with the processing symbol.

• ............./\
• .........../...\
• ..........\..../
• ...........\./
• - indicates a point where a decision must be made or where two items compared.

• .........O
• - indicates that the flowchart continues elsewere.

• ________
• l..............l
• l..............l
• \............./
• ..\........./
• ....\..../
• Indicates flowchart continues on another page.

• ...................___________
• _________l
• ..................l___________
• Note: Comments can be written in an annotation symbol

• Two general types of specific languages
• 1. Low- Level
• 2. High -Level
• Low-Level languages include:
• 1. machine language
• 2. assembly language

• - 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.

• - 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.

• - 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.

• - 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.

• Language Instruction
• Intrinsic Machine Code.....11110001
• Machine Language.............1A
• Assembly Language...........+

• - 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.

• - performs the checking and conversations on all instructions only when the compiler is invoked.
• - Then a true stand-alone executable program is created.

- 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.

• - 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.

• 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.

• - 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.

- A languages has "Strong Data Types" if integer and real numbers cannot be combined in arithmentic statements.

• - 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)

• - 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.

• - 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.

• - 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 n²/2 comparisons are needed on average to sort list. Same as successive minima but more resources.

• - 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 n²/2 comparisons required
• - On average, approximately n^2/4 comparisons.

• - 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 n² 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.

- 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.

• - 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)

• - 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".

• - 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.

• - 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.

• - 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.

• - has only one key field by which records can be located.
• - "searching " techniques are used to locate a particular record.

• - 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

• - 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.

• - 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)

• - 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

• - 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

• - 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

• - 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.