Two_dimensional_arrays_Advanced Computer Science.pdf

Abstract data structures 5.1.4 - 5.1.5 Two dimensional arrays Exit skills. Students should be able to" Describe the characteristics of two-dimensional arrays. Construct algorithms using two-dimensional arrays. ) A one-dimensional array should many cases, data comes be considered as a single...

Abstract data structures 5.1.4 - 5.1.5 Two dimensional arrays Exit skills. Students should be able to" Describe the characteristics of two-dimensional arrays. Construct algorithms using two-dimensional arrays. ) A one-dimensional array should many cases, data comes be considered as a single line of elements. However, in in the form of a data table. Each element in a 2D array must be of the same type, either a primitive or object type. Take, for example, five exam scores of a student, as a data record, and represent it as a row of information. The data records for ten students, would then be a table of 10 rows. Below is the visualization of this collection of - Alot of information and examples of two-dimensional arrays can be found in the book ~ Core Computer Science for the IB Diploma Program’. Student 2 Index 0 Index 1 Index 0 98 7 - Student 10 Index 9 88 Index 1 68 7 Index 2 65 88 86 90 Table 5.2: Two dimensional array Scores 2D arrays are indexed by two subscripts. The indices must be integers. The first one refers to <he row, while the second to the column. Scores[1][1] refers to Exam 2 of the second student. Its value is 77. . /This //It /5 program will print students will the with Scores = [[S88,68,65,73,67], 5 use the contents exams array of each Scores the array. which is a 2D ARRAY. 177,77,88,78,901, 153,63,74,85,72], i 177,717,68,78,91], 128,86,90,56,81]1 STUDENT = 0 =EE2M = 0 Zoop STUDENT from O to 4 output STUDENT +1, loop EXAM from 0 to 4 output ==d end loop loop "----", "Student” "Exam ", EXAM+l, Scores[STUDENT] [EXAM] OUTPUT 1 Student ---—--——--——--—---2 Exam Exam Exam Exam Exam 1 2 3 4 5 98 68 65 73 67 Student ---- Exam 1 77 ---- Exam 2 77 ---- Exam ---- Exam ---- Exam 3 Student 3 4 5 88 78 90 —--—- Exam 1 53 ---- Exam 2 63 ---- Exam 3 74 ---- Exam 4 85 ---- Exam 5 72 4 Student --—- Exam 1 77 ---- Exam 2 77 ---- Exam 3 68 ---- Exam 4 78 ---- Exam 5 91 5 Student --—- Exam -—-- Exam 1 2 88 86 ---- Exam 3 90 ------- Exam Exam 4 5 56 81 g Scores = [[98,68,65,73,67], [77,77,88,78,90], [53,65,74,85,72], [77,77,68,78,91], [88,86,90,56,81]] STUDENT = EXAM = 0 loop 0 STUDENT from 0 to 4 output STUDENT +1, loop EXAM from 0 to 4 "Student” if (Scores[STUDENT] [EXAM] mod 10 output "----", "Exam ", EXAM+l, end end if end loop loop OUTPUT = 5) then Scores[STUDENT] [EXAM] 1 Student ---- Exam 2 Student 3 Student ---- Exam ---- Exam 4 Student 5 Student 3 65 2 4 65 85 3 Programming Example 8: Finds and outputs the number of “8”s each score contains. It also outputs the total number of appearance of digit “8”. Scores = [[98,68,65,73,67], [77,77,88,78,90], [77,77,88,78,91], [88,86,90,56,81]] STUDENT = EXAM = 0 0 TCOUNTER = 0 loop STUDENT from output loop 0 to STUDENT EXAM X=1 from COUNTER = 3 +1, 0 to "Student" 4 0 X = Scores [STUDENT] [EXAM] loop while X>0 if X mod 10 COUNTER end end COUNTER, end TCOUNTER if X = while output = = 8 then COUNTER = div + TCOUNTER (X, 1 +1 10) 2 "----", "The "eight(s)" grade of " A total of ", TCOUNTER, "eights OUTPUT Student —------ The The grade grade of of exam exam 1 2 has has 1 1 eight(s) eight(s) ---- The grade of exam 3 ---- has The 0 eight grade of exam —--- The grade of exam 4 5 has has 0 0 eight(s) eight(s) 2 ", EXAM+1, "has", end loop loop output 1 exam (s) Student ---- The grade of exam 1 has 0 eight(s) —---- The grade of exam 2 has 0 eight ---- (s) The grade of exam 3 —---- has The 2 eight grade (s) of exam 4 has 1 eight(s) —---- The grade of exam 5 has 3 Student —--- The grade 0 eight of exam 1 has 0 eight(s) (s) appear in all grades" ---- The grade of exam 2 has 0 eight(s) ---- The grade of exam 3 has 2 eight(s) ---- The grade of exam 4 has 1 eight(s) ---- The grade of exam 5 has 0 eight(s) 4 Student ---- The grade of exam 1 has 2 eight(s) ------——--- The The The of of of exam exam exam 2 3 4 has has has 1 0 0 eight(s) eight(s) eight(s) —-—- The of exam 5 has 1 eight(s) A total grade grade grade grade of 12 eights appear in all grades 5.1.6 - 5.1.7 Stacks Exit skills. Students should be able to': Describe the characteristics and applications of a stac Construct algorithms using the access methods ofa Trace algorithms that use stacks. Characteristics A stack stores a set of elements in a particular order and allows access only to the last item inserted. Items are retrieved in the reverse order in which they are inserted. The stack is a Last-In, First-Out data (LIFO) structure. The elements of a stack may be numbers, Boolean values, characters, objects, arrays, strings, etc. Stacks utilize three methods: 1. push(). Pushes an item onto a stack. 2. pop().Removes and returns the last item entered in the stack. 3. isEmpty (). Tests if a stack is empty. It will return true if stack contains no elements. Suppose we want to add the elements 5, 4, 3 in a stack named Numbers. The following diagram explains this situation: |i Stackis initially empty. f i { § { b | Numbers.push (5) | 5 was added to the stack. = 5 | Numbers .push(4) | 4 was added to the stack N S B e} | | Numbers .push (3) I 3 was added to the stack Suppose we want to remove all the elements from the stack. The following example presents this situation: 3 | Stack contains 3 numbers. 4 5 e 2 5 —— y‘ Top element was removed from the stack. This element was | the number 3. 3 was assigned to variable X | X = Numbers.pop () ~ Top element was removed from the stack. This element was S - the number 4. 4 was assigned to variable x T ————— S L | Top element was removed from the stack. This element was the number 5. 5 was assigned to variable X. Stack is empty. Aoplications o : The back button of a web browser uses a stack to function. Every time a URL is visited it is stored on a stack. The last address that was visited is on the top of the stack. The first address that was visited during the current web session is on the bottom of the stack. If one selects the Back button, he/she begins to visit the previous pages they have visited in reverse order. » Microprocessors usually use a stack to handle methods. Suppose a method, A, which returns an integer, with parameters b and ¢ of type integer, is called. In Java this would look like this: int ¢ = A(a, b); The method header would look like this: public static int A(int b, int c) The method body should look like this: {method return body r} When As called, its return address, as well as b and c are pushed onto the microprocessors sz=c<. When the method zooped returns z, the return address and the parameters (arguments) are off the stack. The overall process is more complicated, but further explanation ==yond the scope of this book. is Recursive methods also utilize the system stack to keep track of each recursive call. e is memory of block This to used required data temporary store for program execution. The calls are nested inside each other. Initially, all recursive calls are unfolded and pushed onto the stack, until the base case is reached and then all necessary. In the following example recursive calls are popped from the stack, when time a run generate will return 4. The right-hand because the recursive program fragment code left-hand the error fragment will reach the question (int n) code will never terminating condition. { { a) } { <= int 0) -2; a) static public { int void main(String[] | 1 = question(111); System.out.println("1l= "+1); } OUTPUT 1=4 //==== Reverse and store === a stack and a collection. This algorithm uses an array, reverses them, It reads names from the array, and stores the contents of the stack using the stack, inside the collection. NAMES = ["Kostas", NAMES_C = new STACK_NAMES = "Markos", "Anna", "Mary", "Takis"] Collection() new Stack () I=0 loop I from 0 to 4 STACK_NAMES .push (NAMES [I]) end loop output "Add names in the collection:" output "===== loop while NOT(STACK_NAMES.isEmpty()) NAME = STACK_NAMES.pop() NAMES_C.addItem (NAME) output end + A OUTPUT java.lang.StackOverflowError:null Programming Example 9: Use of a staék, an arrdy and a collection. /! " } Algorithms // // // // I (question (n#100)+3); 1 ("1= System.out.println } (n return question(111); = 1 int if return else main(String[] void static public { (question( return static public -2; return else } { 0) <= (n if n)| question(int int static public Rec_Demo class public Rec_Demo class public loop NAME, "was entered in the collection" output "" output "Names loop while output end loop stored in the collection:" NAMES C.hasNext () NAMES_ C.getNext () OUTPUT 24d names in the collection: Tzkis was entered in the collection ¥=ry was entered in the collection 2Znna was entered in the collection M=rkos was entered in the collection Eostas was entered in the collection “he following program uses 4 stacks to solve the Towers of Hanoi problem: //Declaration Stack() new Stack() new new new new //a new //a new Stack() //a Stack() //a Array() Array() Array() [SPa, SPb, stack new stack new stack variables stack //auxiliary //auxiliary //auxiliary SPc, of SPd] array array array //an to to to array use use use of OO0OO0OWN KO = initialization nn ib i Il nn e T new b m Hopooo and = new //the number of disks = © 3 o ) I3 o (] H ® !%‘ ~ a= b B 0 H '] o S i o s 5 in in in four display display display stacks method method method //The following //of the method program method is the starting point TowersofHanoi (n) loop I from m = n-I 0 to n-1 PEGS[1] .push (m) end loop display() move(n,1,2,3) end method //This is method move(n, if n>0 a recursive then move(n-1, t a, = PEGS[a] PEGS[c] a, method b, c, .pop() used to solve the problem c) b) .push (t) display() move (n-1, end if end method b, a, c) //The following method is used to visualize the //pegs and the disks. Three auxiliary arrays are //used so as to method display () output "" output " | A | loop I from daa[I] 0 display to B | C NUM-1 the contents = = the PEGS[2].pop()//put PEGS[3].pop()//put loop da I = db dc fl 0 to stack. elements elements of the of of the the stack stack stack to to to an an an array array array NUM-1 daa[I] = = = if from elements the the loop end each |" = PEGS[1].pop()//put dbb[I] dce[I] of dbb[I] dcc[I] String(da)//covert £f1 == fl="-" "null" to string then end if £2 = String(db) if £2 == "null" //covert then to string //covert then to string fF2="—n end if £3 = String(dec) if £3 == "null" £3=1om end if output=UEIWETE end loop loop I from 0 SIS to W ED - ) . f3, TN NUM-1 m = NUM-1-I PEGS[1] .push(daa[m]) PEGS[2] .push(dbb[m]) PEGS[3] .push(dcc[m]) end loop end method //put //put //put the the the elements elements elements of of of the the the array array array daa dbb decc back back back to to to the the the stac stack stac FORMATED OUTPUT Ve v AN N I MmN v 11 a1 UH Qe o1l 1| a1 2 L dHNm vw % M vl ma Vel Mo VvNmSn 8 Mmoo = L T N il S 8 | o1l dam q Ve 1 1l 8 vNn a1 UH Ly 1ol 2 U me <t 1l Mmoo g1l g S ol g1l 2 aAHNwn R 1 me dsn w MeEHNmS me veem @ g vam -l I o g 1 oL N dowin 4 U Mo = morn & me @ vNMm mea i1 UM 1 vawm AL me S e M s me = UHNI Mmoo Ao morornt gaNm v 1 gl 1ol mo Q VMmN v ol % a0 S il I meNmS Vs Aoan UMl I gl doamn v S VUHNM Moy © ve @ ~ Ot MmN 1 g1 @ CHNm ol o1 1l morr @i 1 A=l 11l monl 1 L MmN || | ol S & 2 s o aun 0 A HNMmIIn 5 | 1 |l 5.1.8-5.1.9 Queues ‘ Exit skills. Students should be able to'" | Describe the characteristics and applications of queues. | Construct algorithms using the access methods of queues. Characteristics of queues A queue stores a set of elements in a particular order and allows access only to the first item inserted. Items are retrieved in the order in which they are inserted. The queue is a First-In, First-Out (FIFO) data structure. The elements of a queue may be numbers, Boolean values, characters, objects, arrays, etc. Queues utilize three methods: 1. engqueue (). Puts anitem into the end of the queue. dequeue (). Removes and returns the first item entered in the queue. 3. isEmpty (). Tests if a queue is empty. It will return true if queue contains elements. Suppose we want to add the elements 5, 4 and 3 in a queue named Numbers. The following example presents this situation: \:Dj . | Queue initially empty Numbers . enqueue (5) ~ 5 was added to the queue 7 Numbers.enqueue (4) 4 was added to the queue Numbers .enqueue (3) 3 was added to the queue Suppose we want to remove all the elements from the queue. The following example presents this situation: Queue contains 3 numbers . X = Numbers.dequeue () First element was removed from the queue. This element was the number 5. 5 was assigned to variable X. X = Numbers.dequeue () First element was X = First was was removed from the queue. This element the number 4. 4 was assigned to variable X. Numbers .dequeue () { element was removed from the queue. This element the number 3. 3 was assigned to variable X. Queue is _empty. no Applications of queues to used are Queues e model physical queues, such as people waiting in line supermarket checkout. displays queue print The e the documents that are waiting to be printed. at a These documents will follow the first-send first-print policy. When sending data over the internet, various data packets wait in a queue to be e sent. A server usually serves various requests. In most cases these requests are stored in a queue. The first-come first-served request procedure is followed. o Algorithms that use queues Programming Example 11: Use of a queue and arrays. all students A small school uses two buses to transport students. As soon as the buses arrive, The enter a queue and a teacher uses a registry to check which students are present. the following algorithm uses two arrays to represent the school buses, a queue to represent queue, and an array to represent the registry: "Nikos", "John", ["Roger", = BUS1 "Marion", "Hellen"] "Alex"] "Takis", "Eliza", "Bill", BUS2 = ["Nora", "Leo", "Nikos", "Elina", "John", ["Alex", = REGISTRY "Roger"] "Takis", "Eliza", "Bill", "Nora", "Hellen", Queue () new = STUDENTS nn A= //Queue for "Marion", Students I=0 = 1 FOUND //copy loop students I from 0 to from 4 BUS1l STUDENTS . enqueue (BUS1[I]) end loop //copy students from BUS2 loop I from 0 to 4 STUDENTS . enqueue (BUS2[I]) end loop NOT (STUDENTS.isEmpty()) while loop A = STUDENTS.dequeue () loop I from 0 to 12 if REGISTRY[I] = A then FOUND = 1 end if end loop if end FOUND output end loop = 1 then A, "is not absent" if OUTPUT 4 Roger is not absent John is not absent Nikos is not absent Marion is not absent Hellen is not absent Nora Bill is is not not absent absent Eliza is not absent Takis is not absent Alex is not absent Programming Ekarhhle 12: Use of queues, arrays and a collection. A supermarket has two express cashiers. The array CASHIER1 enter the queue CUSTOMER1, while the array CASHIER2 contains the customers that contains the customers that enter the queue CUSTOMER2. The TIME collection stores the names of the customers that waited more than 60 secs, counting from the moment that their turn to be served had come. The supermarket administration wishes to minimize the waiting for these two express cashiers. A questionnaire customers is sent stored by email, from in the collection the TIME administration of the supermarket, to the to understand why this situation took place. A message that outputs the overall slower express cashier is output at the end of the day. CASHIER]1 = ["Roger", CASHIER2 = ["Nora", CUSTOMERL = new CUSTOMER2 = new TIME = new A= B=0 c1 =0 c2=0 I=0 Dl =0 D2 =0 TOT B = 0 TOTC = 0 FOUND = 1 "John", "Bill", Queue () Queue () "Eliza", "Marion"] "Takis"] //Queue for //Queue CUSTOMER1 for CUSTOMER2 Collection() //copy CUSTOMER1 from loop I from 0 to 3 end "Nikos", CASHIERL CUSTOMERI.enqueue(CASHIERl[I]) loop //copy CUSTOMER2 from CASHIER2 loop I from 0 to 3 CUST . enqueu OM e (CASHI ER ER2[I] 2 ) end loop loop D1 while = NOT(CUSTOMERl.isEmpty()) (CUSTOMERLI . dequeue () ) Cl = Math.floor ((Math.random() * 100) to generate random times between 1 sec + 1)// to 100 use sec of random function then C1>60 if //only waiting customers more than 60 secs enter collection TIME.addItem(D1) "end if TOTB = TOT_B + C1 end loop loop while D2 = C2 NOT (CUSTOMER2.isEmpty ()) (CUSTOMER2.dequeue ()) = if Math.floor((Math.random() * 100) + 1) C2>60 then TIME.addItem (D2) end if TOT_C = TOT_C + C2 end loop TIME.resetNext () loop while output end if TIME.hasNext() TIME.getNext () loop TOT_B > TOT _C then//outputs output "CASHIER] is slower" else output end "CASHIER2 is the slower cashiexr slower" if A POSSIBLE OUTPUT Roger John Bill Eliza CASHIER2 is slower 5.1.10 Arrays as static stacks and queues Exit skills. Students should be able to': i | Explain push and pop operations, and test on empty/full stack. | Explain enqueue and dequeue operations, and test on empty/full queue. { Algorithms to implement stacks using an array The program starts with an array of 10 elements. The methods used are the following: the