Programming & Problem Solving II
Programming & Problem Solving II CECS 274
Popular in Course
Popular in Computer Science and Engineering
This 29 page Class Notes was uploaded by Zackary Cronin on Monday October 5, 2015. The Class Notes belongs to CECS 274 at California State University - Long Beach taught by Donna Pompei in Fall. Since its upload, it has received 50 views. For similar materials see /class/218751/cecs-274-california-state-university-long-beach in Computer Science and Engineering at California State University - Long Beach.
Reviews for Programming & Problem Solving II
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/05/15
UNIX Introduction The UNIX File System Defn A UNIX le is a collection of characters stored together Defn A UNIX directory is a collection of UNIX les Defn Your home directory is the directory you are in when you rst log into your UNIX account Note You can move from one directory to another within the UNIX le system Defn Your current directory or working directory is the UNIX directory you are working in at a particular time Example When you rst log into your account your working directory is your home directory Defn A UNIX le system is the organization of the UNIX les on a UNIX computer system UNIX le systems are organized into a tree structure of les and directories Terms root leaf parent child root bin dev etc home tmp usr Var 7M z lh Users39 home directories The root is referred to in writing commands as not root Every le and directory has a name Your home directory has the same name as your account username Naming convention 0 File and directory names may be up to 14 characters long 0 File names are case sensitive o The following may be used 0 Uppercase letters AZ 0 Lowercase letters az ltgt Numerals 09 0 Period underscore comma Examples Legal lenames Illegal lenames Elvis Elvis EPresley E Presley HelloWorld HelloEverybody NolFile NolFile Defn A pathname is an address that uniquely speci es a le s location in the UNIX le structure Defn An absolute pathname gives the position of a le from the root directory Absolute pathnames always begin with 1 I jack 2 Continents Oceans Bats Marsupials possum l bandicoot kangaroo wombat Examples Filename Absolute pathname jack home j ack jill homejill possum homejillpossum kangaroo homejilllVlarsupialskangaroo Your home directory has the pathname Jack s home directory has the pathname jack Defn A relative pathname is a pathname that begins at the working directory dot the current working directory dotdot the parent of the current working directory ruat b139n dev etc home tmp usr var Continents Oceans Bats Marsupia39ls possum bandimot kangaroo wombat Examples Suppose your current working directory is jill Filename Relative pathname possum possum kangaroo Marsupialskangaroo jill home jack jack ls UNIX File Commands list the contents of a directory unixgt ls ltretgt unixgt ls ltdirectorynamegt ltretgt Files are hidden from the simple 1s command when their name begins with a period To display hidden les the a option is used with IS To display les in quotlongquot format ie with detailed information about the le the 1 op onisrmed unixgt ls a ltretgt unixgt ls a ltdirectorynamegt ltretgt unixgt ls al ltretgt unixgt ls al ltdirectorynamegt ltretgt move a le from pathnamel to pathname2 rename a le unixgt mv pathnamel pathnameZ ltretgt Example With current working directory jill unixgt mv possum Marsupialsopossum moves the le possum to Marsupials opossum see gure on next page 6 root U jack ji Continents Oceans Bats Marsupiak A x bandicoot kangaroo opossum wombat cp copy a le from pathnamel t0 pathnameZ unixgt cp pathnamel pathnameZ ltretgt Example With current working directory jill unixgt cp possum Marsupialsopossum gt redirect the output from a command to a le unixgt ltCommandgt gt ltfilenamegt ltretgt Example unixgt ls gt listing gtgt stores the output of ls into the file listing append add at the end the output to a le unixgt ltCommandgt gtgt ltfilenamegt ltretgt Example unixgt pwd gtgt listing cat unixgt unixgt Example unixgt unixgt unixgt appends the output of pwd onto the file listihg View the contents of a le concatenate cat ltfilenamegt ltretgt cat ltfilenamelgt ltfilename2gt ltfilename3gt ltretgt ls gt Ll creates Ll cat Ll displays Ll cat Fl F2 displays the files Fl followed by F2 more View the contents of a le one page at a time unixgt more ltfilenamegt ltretgt ltspacegt will display the next page ltretgt will display one line at a time q will quit more Example unixgt ls gt Ll redirects the output of ls into file Ll unixgt more Ll displays Ll less quotless is morequot less is like more except less will let you page backwards through a le unixgt less ltfilenamegt ltretgt ltspacegt will display the next page b will display the previous page ltretgt will display one line at a time q will quit less Example unixgt ls gt L1 redirects the output of ls into file Ll unixgt less Ll displays Ll 10 mkdir create a new directory gt mkdir ltnewdirectorynamegt ltretgt Example If the current working directory is jill gt mkdir cec3274 root jack Bats Marsupials Continents Oceans r i wombat bandicoot kangaroo opossum wombat cd change your working directory gt Cd ltretgt returns to home directory gt Cd ltdirectorypathnamegt ltretgt Example If the current working directory is jill gt Cd jackContinents will move the working directory to home j acldContinents 11 pwd show the name of your working directory gt pwd ltretgt gives your present working directory Example If the current working directory is jill gt pwd will show that the present working directory is homejill man access the help manual and display information on any command gt man ltcommanolgt ltretgt displays information about the ltcommandgt Example gt man Cp will display information about the op command You can page through the information using the same options available with quotlessquot rmdir remove a directory gt rmdir ltdirectorynamegt ltretgt rmdir will remove a directory if it is empty If it still has les inside of it it will give an error message Example If the current working directory is jill gt rmdir jackOceans will remove the directory Oceans rm remove a le gt rm ltfilenamegt ltretgt Example If the current working directory is Marsupials gt rm wombat will remove homejillMarsupialswombat The r option will remove a directory and all of the les and subdirectories contained in the directory Your working directory must be an ancestor directory of the directory to be removed when you enter the command gt rm r ltdirectorynamegt ltretgt Example If the current working directory is jill gt rm r Marsupial s will remove homejilllIarsupials and all its subdirectories and les APPENDIX A Arrays memory and Allocation Basics Carrano Helman Veroff pp A26A32 A Arrays Defn Arrays are indexed collections of components all of the same type When using an array in C the dimensions and type of elements stored in the array must be declared The dimensions of the array will always begin with 0 Example const int CALENDAR 12 double Income CALENDAR This declaration will create an array called Income made up of twelve variables of type double The indices of the array will be Oto 11 B Memory and Allocation Basics Typical storage types for computers 1 Random Access Memory RAM fast and volatile 2 Disk slow relatively speaking and permanent Typical Memory Organization 0 Bytes are groups of 8 bits 0 A Byte can store 28 256 different values 0 Bytes are indexed by address Storage of Values A11 program variables are stored in Bytes of RAM They may occupy one or more Bytes Usually Characters 1 Byte Integers 2 Bytes Now typically 4 bytes Floats 4 Bytes This can vary depending on the machine being used Larger quantities eg arrays strings etc are made up of combinations of these Byte allotments It is the compiler that decides computes the actual locations where variables will be stored Storage Allocation Consequences The size of the storage space limits the quantities that can be stored Example For INTEGERS o 1 Byte 128127 since 28256 o 2 Bytes 3276832767 since 21665536 o 4 Bytes 2147483648 2147483637 since 2324294967296 For FLOATS The more Bytes available the more digits that can be stored after the decimal point Storing and Accessing an Array typedef int studentScores4 studentScores X X0 X1 X2 X3 424 425 426 427 428 429 430 431 To compute the location of Xi 424 j 0 2 In general the formula for an array A is ampAi Starting Address j lSt Index Component Size The compiler calculates this arithmetic formula so that the elements of the array can be easily accessed Arrays of Larger Components typedef int studentScores4 typedef studentScores classScoreslOO classScores mathClass The component size of studentScores is 8 4 integers at 2 bytes nteger To nd ampmathClass i ampmathClassi Starting Address j O 4 2 Accessing Nested Components of Arrays typedef int studentScores4 typedef studentScores classScoreslOO classScores mathClass If integers are each 2 Bytes then the size of each component of mathClass is 4 2 8 the full size of studentScores To nd mathClassj ampmathClass i Starting Address j 1st Index of classScores 8 To nd ampmathClass i k ampmathClassik ampmathC1assj k 1st Index of studentScores Component size of studentScores Starting address j O 8 k O 2 Arrays with Multiple Dimensions In storing a 2dimensional array matrix either the rows or columns can be grouped together For simplicity we will assume the rows are grouped together in rowmaj or order Example typedef float Matrix43 Matrix Z In rowmajor order the rows are stored together The elements are grouped by the 1St index Z0 Z1 Z21H Z31H 100 111 112 123 124 135 136 147 Formulas for 2Dimensi0nal Arrays Rowmajor Order ampZjk Starting address j 1st index of dimension 1 row size k 1st index of dimension 2 component size where the row size last index of dimension 2 1st index of dimension 2 1 component size C Adding Flexibility t0 Arrays in C Defn An unconstrained array is an array in which the bounds of the array and the indices of the array are not speci ed when the type is declared Unlike Ada the C language does not have builtin unconstrained arrays In C the indices of arrays must be declared and all arrays begin with index 0 However a programmer can create an array class that permits the equivalent of Ada39s unconstrained arrays and beginning index value Example A vector class for onedimensional integer arrays class vector public vector constructor lastindex firstindex vectorsize l space is allocated dynamically vectorint vectorsize int firstindex 0 m private int array int size int first int last To instantiate two onedimensional arrays one consisting of 5 elements beginning with index 0 and the other consisting of 10 elements beginning with index 1 vector arrayA5 vector arrayBlO l Example A matrix class can also be created for two dhnenmonalhuegeranaysPohlp189 class matrix public matrix constructor space is allocated dynamically matrixiht horow int hocol int rowihdex 0 int colihdex O m private int mat stores the base address of an array of pointers to int which in turn stores a base address for each row of the matrix type int row int col int begrow int ehdrow int begcol int ehdcol CHAPTER 9 ALGORITHM EFFICIENCY AND SORTING Defn An internal sort is a sort in which the array is suf ciently small so as to t into internal memory Defn An in situ sort is a sort in which the unsorted and sorted arrays occupy the same space possibly with a small amount of auxiliary working storage For simplicity we will consider ascending sorts of arrays in all of our algorithms Example Typical array for sorting 54821736 12 3 56 7 8 A Selection Sort Principle 0 1St pass nd the largest value and place it the last slot 0 2quot l pass nd the 2quot l largest value and place it the 2quot l to last slot 0 11th pass nd the 11th largest value and place it the 11th to last slot Notes 0 For an array of size 11 make 11 passes o The last pass is really not necessary C Code for Selection Sort Carrano Helman and Veroff pp 447448 typedef tweo arrayitem DataType void selectionSortDataType theAIray int n Sorts the items in an array into ascending order last index of the last item in the subarray of items yet to be sorted largest index of the largest item found for int last n 1 last gt 1 last select largest item in theArray0last int largest indexOfLargesttheArray last l swap largest item theArraylargest with theArraylast swaptheArraylargest theArraylast int indexOfLargestconst DataType theAIray int size Finds the largest item in an array int indexSoFar 0 index of largest item found so far for int currentlndex l currentlndex lt size currentIndex if theArraycurrentIndex gt theArrayindexSoFar indexSoFar currentlndex return indexS oFar void swapDataTypeamp x DataTypeamp y Swaps two items DataType temp x X Y y temp Performance 0n2