Concurrent performance of function
CONCURRENT PERFORMANCE OF FUNCTIONSGraphic systems may do two or more things at one time. Multiple programs may run simultaneously. When a system is not busy on a primary task, it may process backgroundtasks (cooperative multitasking).When applications are running as truly separate tasks, thesystem may divide the processing power into time slices and allocate portions to each application.Data may also be transferred between programs. It may be temporarily stored on a "clipboard" for later transfer or be automatically swapped between programs.THE GRAPHICAL USER INTERFACE A user interface is a collection of techniques and mechanisms to interact with something. In a graphical interface the primary interaction mechanism is a pointing device of some kind. This device is the electronic equivalent to the human hand. What the user interacts with is a collection of elements referred to as objects. They can be seen, heard, touched, or otherwise perceived. Objects are always visible to the user and are used to perform tasks. They are interacted with as entities independent of all other objects. People perform operations, called actions, on objects. The operations include accessing and modifying objects by pointing, selecting, and manipulating. All objects have standard resulting behaviors.THE WEB USER INTERFACEThe expansion of the World Wide Web since the early 1990s has been truly amazing. Once simply a communication medium for scientists and researchers, its many and pervasive tentacles have spread deeply into businesses, organizations, and homes around the world.Unlike earlier text-based and GUI systems that were developed and nurtured in an organization's Data Processing and Information Systems groups, the Web's roots were sown in a market-driven society thirsting for convenience and information.Web interface design is essentially the design of navigation and the presentation of information. It is about content, not data.Proper interface design is largely a matter of properly balancing the structure and relationships of menus, content, and other linked documents or graphics. The design goal is
Dushyant Jodha
HCI NOTES
DEFINING THE USER INTERFACE• User interface, design is a subset of a field of study called human-computer interaction (HCI).• Human-computer interaction is the study, planning, and design of how people and computers work together so thata person's needs are satisfied in the most effective way.• HCI designers must consider a variety of factors:– what people want and expect, physical limitations and abilities people possess,--how information processing systems work,– what people find enjoyable and attractive.– Technical characteristics and limitations of the computer hardware and software must also be considered.• The user interface is to– the part of a computer and its software that people can see, hear, touch, talk to, or otherwise understand or direct.• The user interface has essentially two components: input and output.• Input is how a person communicates his / her needs to the computer.– Some common input components are the keyboard, mouse, trackball, one's finger, and one's voice.• Output is how the computer conveys the results of its computations and requirements to the user.– Today, the most common computer output mechanism is the display screen, followed by mechanisms that take advantage of a person's auditory capabilities: voice and sound.• The use of the human senses of smell and touch output in interface design still remain largely unexplored.• Proper interface design will provide a mix of well-designed input and output mechanisms that satisfy the user's needs, capabilities, and limitations in the most effective way possible.• The best interface is one that it not noticed, one that permits the user to focus on the information and task at hand, not the mechanisms used to present the information
Hashing
Hashing is the transformation of a string of character into a usually shorter fixed-length value or key that represents the original string.Hashing is used to index and retrieve items in a database because it is faster to find the item using the shortest hashed key than to find it using the original value. It is also used in many encryption algorithms.A hash code is generated by using a key, which is a unique value.Hashing is a technique in which given key field value is converted into the address of storage location of the record by applying the same operation on it.The advantage of hashing is that allows the execution time of basic operation to remain constant even for the larger side.Why we need Hashing?Suppose we have 50 employees, and we have to give 4 digit key to each employee (as for security), and we want after entering a key, direct user map to a particular position where data is stored.If we give the location number according to 4 digits, we will have to reserve 0000 to 9999 addresses because anybody can use anyone as a key. There is a lot of wastage.In order to solve this problem, we use hashing which will produce a smaller value of the index of the hash table corresponding to the key of the user.Universal HashingLet H be a finite collection of hash functions that map a given universe U of keys into the range {0, 1..... m-1}. Such a collection is said to be universal if for each pair of distinct keys k,l∈U, the number of hash functions h∈ H for which h(k)= h(l) is at most |H|/m. In other words, with a hash function randomly chosen from H, the chance of a collision between distinct keys k and l is no more than the chance 1/m of a collision if h(k) and h(l)were randomly and independently chosen from the set {0,1,...m-1}.RehashingIf any stage the hash table becomes nearly full, the running time for the operations of will start taking too much time, insert operation may fail in such situation, the best possible solution is as follows:Create a new hash table double in size.Scan the original hash table, compute new hash value and insert into the new hash table.Free the memory occupied by the original hash table.Example: Consider inserting the keys 10, 22, 31,4,15,28,17,88 and 59 into a hash table of length m = 11 using open addressing with the primary hash function h' (k) = k mod m .Illustrate the result of inserting these keys using linear probing, using quadratic probing with c1=1 and c2=3, and using double hashing with h2(k) = 1 + (k mod (m-1)).Solution: Using Linear Probing the final state of hash table would be:Using Quadratic Probing with c1=1, c2=3, the final state of hash table would be h (k, i) = (h' (k) +c1*i+ c2 *i2) mod m where m=11 and h' (k) = k mod m.Using Double Hashing, the final state of the hash table would be:
Counting Sort
It is a linear time sorting algorithm which works faster by not making a comparison. It assumes that the number to be sorted is in range 1 to k where k is small.Basic idea is to determine the "rank" of each number in the final sorted array.Counting Sort uses three arrays:A [1, n] holds initial input.B [1, n] holds sorted output.C [1, k] is the array of integer. C [x] is the rank of x in A where x ∈ [1, k]Firstly C [x] to be a number of elements of A [j] that is equal to xInitialize C to zeroFor each j from 1 to n increment C [A[j]] by 1We set B[C [x]] =A[j]If there are duplicates, we decrement C [i] after copying.Counting Sort (array P, array Q, int k) 1. For i ← 1 to k 2. do C [i] ← 0 [ θ(k) times] 3. for j ← 1 to length [A] 4. do C[A[j]] ← C [A [j]]+1 [θ(n) times] 5. // C [i] now contain the number of elements equal to i 6. for i ← 2 to k 7. do C [i] ← C [i] + C[i-1] [θ(k) times] 8. //C[i] now contain the number of elements ≤ i 9. for j ← length [A] down to 1 [θ(n) times] 10. do B[C[A[j] ← A [j] 11. C[A[j] ← C[A[j]-1 Explanation:Step1: for loop initialize the array R to 'o'. But there is a contradict in the first step initialize of loop variable 1 to k or 0 to k. As 0&1 are based on the minimum value comes in array A (input array). Basically, we start I with the value which is minimum in input array 'A'For loops of steps 3 to 4 inspects each input element. If the value of an input element is 'i', we increment C [i]. Thus, after step 5, C [i] holds the number of input element equal to I for each integer i=0, 1, 2.....kStep 6 to 8 for loop determines for each i=0, 1.....how many input elements are less than or equal to iFor loop of step 9 to 11 place each element A [j] into its correct sorted position in the output array B. for each A [j],the value C [A[j]] is the correct final position of A [j] in the output array B, since there are C [A[j]] element less than or equal to A [i].Because element might not be distinct, so we decrement C[A[j] each time we place a value A [j] into array B decrement C[A[j] causes the next input element with a value equal to A [j], to go to the position immediately before A [j] in the output array.Analysis of Running Time:For a loop of step 1 to 2 take θ(k) timesFor a loop of step 3 to 4 take θ(n) timesFor a loop of step 6 to 7 take θ(k) timesFor a loop of step 9 to 11 take θ(n) timesOverall time is θ(k+n) time.Note:Counting Sort has the important property that it is stable: numbers with the same value appears in the output array in the same order as they do in the input array.Counting Sort is used as a subroutine in Radix Sort.Example: Illustration the operation of Counting Sort in the array.A= ( 7,1,3,1,2,4,5,7,2,4,3) Solution:Fig: Initial A and C ArraysFor j=1 to 11 J=1, C [1, k] = Fig: A [1] = 7 ProcessedJ=2, C [1, k] = Fig: A [2] = 1 ProcessedJ=3, C [1, k] Fig: A [3] = 3 ProcessedJ=4, C [1, k] Fig: A [4] = 1 ProcessedJ=5, C [1, k] Fig: A [5] = 2 ProcessedUPDATED C is:Fig: C now contains a count of elements of ANote: here the item of 'A' one by one get scanned and will become a position in 'C' and how many times the item get accessed will be mentioned in an item in 'C' Array and it gets updated or counter increased by 1 if any item gets accessed again.Now, the for loop i= 2 to 7 will be executed having statement:C [i] = C [i] + C [i-1] By applying these conditions we will get C updated as i stated from 2 up to 7C [2] = C [2] + C [1] C [3] = C [3] + C [2] C [2] = 2 + 2 C [3] = 2 + 4 C [2] = 4 C [3] = 6 C [4] = C [4] + C [3] C [5] = C [5] + C [4] C [4] = 2 + 6 C [5] = 1 +8 C [4] = 8 C [5] = 9 C [6] = C [6] + C [5] C [7] = C [7] + C [6] C [6] = 0 + 9 C [7] = 2 + 9 C [6] = 9 C [7] = 11 Thus the Updated C is:Fig: C set to rank each number of ANow, we will find the new array BNow two Conditions will apply:B[C[A[j] ← A [j]C[A[j] ← C[A[j]-1We decrease counter one by one by '1'We start scanning of the element in A from the last position.Element in A became a position in CFor j ← 11 to 1 Step 1B [C [A [11]]] = A [11] C [A [11] = C [A [11]-1 B [C [3] = 3 C [3] = C [3] -1 B [6] = 3 C [3] = 5 Fig: A [11] placed in Output array BStep 2B [C [A [10]]] = A [10] C [A [10]] = C [A [10]]-1 B [C [4]] =4 C [4] = C [4] -1 B [8] = 4 C [4] = 7 Fig: A [10] placed in Output array BStep 3B [C [A [9]] = A [9] C [A [9] = C [A [9]]-1 B [C [2]] = A [2] C [2] = C [2]-1 B [4] = 2 C [2] = 3 Fig: A [9] placed in Output array BStep 4B [C [A [8]]] = A [8] C [A [8]] =C [A [8]] -1 B [C [7]] =7 C [A [8]] = C [7]-1 B [11] =7 C [7] = 10 Fig: A [8] placed in Output array BStep 5B [C [A [7]]] = A [7] C [A [7]] = C [A [7]] - 1 B [C [5]] = 5 C [5] = C [5] - 1 B [9] = 5 C [5] =8 Fig: A [7] placed in Output array BStep 6B [C [A [6]]] = A [6] C [A [6]] = C [A [6]] - 1 B [C [4]] = 4 C [4] = C [4] - 1 B [7] = 4 C [4] = 6 Fig: A [6] placed in Output array BStep 7B [C [A [5]]] = A [5] C [A [5] = C [A [5]] -1 B [C [2] =2 C [2] = C [2] - 1 B [3] = 2 C [2] = 2
Radix Sort
Radix Sort is a Sorting algorithm that is useful when there is a constant'd' such that all keys are d digit numbers. To execute Radix Sort, for p =1 towards 'd' sort the numbers with respect to the Pth digits from the right using any linear time stable sort.The Code for Radix Sort is straightforward. The following procedure assumes that each element in the n-element array A has d digits, where digit 1 is the lowest order digit and digit d is the highest-order digit.Here is the algorithm that sorts A [1.n] where each number is d digits long.RADIX-SORT (array A, int n, int d) 1 for i ← 1 to d 2 do stably sort A to sort array A on digit i Example: The first Column is the input. The remaining Column shows the list after successive sorts on increasingly significant digit position. The vertical arrows indicate the digits position sorted on to produce each list from the previous one.576 49[4] 9[5]4 [1]76 176 494 19[4] 5[7]6 [1]94 194 194 95[4] 1[7]6 [2]78 278 296 → 57[6] → 2[7]8 → [2]96 → 296 278 29[6] 4[9]4 [4]94 494 176 17[6] 1[9]4 [5]76 576 954 27[8] 2[9]6 [9]54 954
Linear Time Sorting
We have sorting algorithms that can sort "n" numbers in O (n log n) time.Merge Sort and Heap Sort achieve this upper bound in the worst case, and Quick Sort achieves this on Average Case.Merge Sort, Quick Sort and Heap Sort algorithm share an interesting property: the sorted order they determined is based only on comparisons between the input elements. We call such a sorting algorithm "Comparison Sort".There is some algorithm that runs faster and takes linear time such as Counting Sort, Radix Sort, and Bucket Sort but they require the special assumption about the input sequence to sort.Counting Sort and Radix Sort assumes that the input consists of an integer in a small range.Bucket Sort assumes that a random process that distributes elements uniformly over the interval generates the input.
Bucket Sort
Bucket Sort runs in linear time on average. Like Counting Sort, bucket Sort is fast because it considers something about the input. Bucket Sort considers that the input is generated by a random process that distributes elements uniformly over the intervalμ=[0,1].To sort n input numbers, Bucket SortPartition μ into n non-overlapping intervals called buckets.Puts each input number into its bucketsSort each bucket using a simple algorithm, e.g. Insertion Sort and thenConcatenates the sorted lists.Bucket Sort considers that the input is an n element array A and that each element A [i] in the array satisfies 0≤A [i] <1. The code depends upon an auxiliary array B [0....n-1] of linked lists (buckets) and considers that there is a mechanism for maintaining such lists.BUCKET-SORT (A) 1. n ← length [A] 2. for i ← 1 to n 3. do insert A [i] into list B [n A[i]] 4. for i ← 0 to n-1 5. do sort list B [i] with insertion sort. 6. Concatenate the lists B [0], B [1] ...B [n-1] together in order. Example: Illustrate the operation of BUCKET-SORT on the array.A = (0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 068) Solution:Fig: Bucket sort: step 1, placing keys in bins in sorted orderFig: Bucket sort: step 2, concatenate the listsFig: Bucket sort: the final sorted sequence
Max - Min Problem
Problem: Analyze the algorithm to find the maximum and minimum element from an array.Algorithm: Max ?Min Element (a []) Max: a [i] Min: a [i] For i= 2 to n do If a[i]> max then max = a[i] if a[i] < min then min: a[i] return (max, min) Analysis:Method 1: if we apply the general approach to the array of size n, the number of comparisons required are 2n-2.Method-2: In another approach, we will divide the problem into sub-problems and find the max and min of each group, now max. Of each group will compare with the only max of another group and min with min.Let n = is the size of items in an arrayLet T (n) = time required to apply the algorithm on an array of size n. Here we divide the terms as T(n/2).2 here tends to the comparison of the minimum with minimum and maximum with maximum as in above example.T (n) = 2 T → Eq (i)T (2) = 1, time required to compare two elements/items. (Time is measured in units of the number of comparisons)→ Eq (ii)Put eq (ii) in eq (i)Similarly, apply the same procedure recursively on each subproblem or anatomy{Use recursion means, we will use some stopping condition to stop the algorithm}Recursion will stop, when → (Eq. 4)Put the equ.4 into equation3.Number of comparisons requires applying the divide and conquering algorithm on n elements/items = Number of comparisons requires applying general approach on n elements = (n-1) + (n-1) = 2n-2From this example, we can analyze, that how to reduce the number of comparisons by using this technique.Analysis: suppose we have the array of size 8 elements.Method1: requires (2n-2), (2x8)-2=14 comparisonsMethod2: requires It is evident; we can reduce the number of comparisons (complexity) by using a proper technique.
Insertion Sor
It is a very simple method to sort the number in an increasing or decreasing order.It has various advantages:It is simple to implement.It is efficient on small datasets.It is stable (does not change the relative order of elements with equal keys)It is in-place (only requires a constant amount O (1) of extra memory space).It is an online algorithm, in that it can sort a list as it receives it.ALGORITHM: INSERTION SORT (A) 1. For k ← 2 to length [A] 2. Do key ← A[k] 3. i=k-1 4. while i>0 and A[i]>key 5. do A[i+1] ← A[i] 6. i=i-1 7. A[i+1] ← key Analysis:Input: n elements are given.Output: the number of comparisons required to make sorting.Logic: If we have n elements in insertion sort, then n-1 passes are required to find a sorted array. In pass 1: no comparison is required In pass 2: 1 comparison is required In pass 3: 2 comparisons are required ............................................................................ ............................................................................... In pass n: n-1 comparisons are required Total comparisons: T (n) = 1+2+3+...........+ n-1 = = o (n2) Therefore complexity is of order n2 Example:Illustrate the operation of INSERTION SORT on the array A = (4, 15, 7, 18, and 16).Solution:A [] =41571816For j=2 to 5 J=2, key=A [2] Key=15 I=2-1=1, i=1 While i>0 and A [1]>15 A Condition false, so no change Now=3, key=A [3] =7 I=3-1=2 I=2, key=7 While i>0 and A [2]>key Condition is true So A [2+1] ← A [2] A [3] ← A [2] i.e.4151816and i=2-1=1, i=1 while i>0 and A [1]>key A Condition false. So no change Then A [1+1] ← key A [2] ← 7 That is47151816For j=4 Key=A [4] Key = 18, i=3 Now, while 3>0 and A [3]>18 The Condition is false, No change. Similarly, j=5 Key=A [5] So key=16, i=4 Now while 4>0 and A [4]>16 Condition is true So A [5] =16 and i=4-1=3 Now while 3>0 and A [3]>16 Condition is false So A [3+1] =A [4] =16 And the sorted array is:47151618
Selection Sort
The selection sort enhances the bubble sort by making only a single swap for each pass through the rundown. Indorder to do this, a selection sort searches for the biggest value as it makes a pass and, after finishing the pass, places it in the best possible area. Similarly as with a bubble sort, after the first pass, the biggest item is in the right place. After the second pass, the following biggest is set up. This procedure proceeds and requires n-1 goes to sort n item, since the last item must be set up after the (n-1) st pass.ALGORITHM: SELECTION SORT (A) 1. k ← length [A] 2. for j ←1 to n-1 3. smallest ← j 4. for I ← j + 1 to k 5. if A [i] < A [ smallest] 6. then smallest ← i 7. exchange (A [j], A [smallest]) Analysis:Input: n elements are given.Output: the number of comparisons required to make sorting.Logic: If we have n elements in selection sort, then n-1 passes are required to find a sorted array. In pass 1: n-1 comparisons are required In pass 2: n-2 comparisons are required In pass 3: n-3 comparisons are required ............................................................................ ............................................................................... In pass n-1: 1 comparison is required Total comparisons: T (n) = (n-1) + (n-2) + (n-3) +........+ 1 = = o (n2) Therefore complexity is of order n2 Example:Sort the following array using selection sort: A [] = (7, 4, 3, 6, 5).A [] =743651 Iteration:Smallest =7 4 < 7, smallest = 4 3 < 4, smallest = 3 6 > 3, smallest = 3 5 > 3, smallest = 3 Swap 7 and 3347652nd iteration:Smallest = 4 4 < 7, smallest = 4 4 < 6, smallest = 4 4 < 5, smallest = 4 No Swap347653rd iteration:Smallest = 7 6 < 7, smallest = 6 5 < 7, smallest = 5 Swap 7 and 5345674th iteration:Smallest = 6 6< 7, smallest = 6 No Swap34567Finally, the sorted list is:34567
Merge Sort
It closely follows the divide & Conquers paradigm.Conceptually, it works as follows:Divide: Divide the unsorted list into two sublists of about half the size.Conquer: Sort each of the two sublists recursively until we have list sizes of length 1, in which case the list items are returned.Combine: Join the two sorted Sub lists back into one sorted list.The Main purpose is to sort the unsorted list in nondecreasing order.ALGORITHM-MERGE SORT 1. If p<r 2. Then q ← ( p+ r)/2 3. MERGE-SORT (A, p, q) 4. MERGE-SORT ( A, q+1,r) 5. MERGE ( A, p, q ,r) The following figure illustrates the dividing (splitting) procedure.FUNCTIONS: MERGE (A, p, q, r) 1. n 1 = q-p+1 2. n 2= r-q 3. create arrays [1.....n 1 + 1] and R [ 1.....n 2 +1 ] 4. for i ← 1 to n 1 5. do [i] ← A [ p+ i-1] 6. for j ← 1 to n2 7. do R[j] ← A[ q + j] 8. L [n 1+ 1] ← ∞ 9. R[n 2+ 1] ← ∞ 10. I ← 1 11. J ← 1 12. For k ← p to r 13. Do if L [i] ≤ R[j] 14. then A[k] ← L[ i] 15. i ← i +1 16. else A[k] ← R[j] 17. j ← j+1 In this method, we split the given list into two halves. Then recursively analyzing merge sort and dividing. We get many sorted lists.At last, we combine the sorted lists.Analysis of Merge Sort:Let T (n) be the total time taken in Merge SortSorting two halves will be taken at the most 2T timeWhen we merge the sorted lists, we have a total n-1 comparison because the last element which will be left will just need to be copied down in the combined list and there will be no comparison.So, the relational formula becomesBut we ignore '-1' because the element will take some time to be copied in merge lists.So T (n) = 2T + n.........equation 1Note: Stopping Condition T (1) =0 because at last there will be only 1 element left which need to be copied and there will be no comparison.Put 2 equation in 1 equationPutting 4 equation in 3 equationFrom Stopping Condition:Apply log both sides:log n=log2ilogn= i log2=ilog2n=iFrom 6 equation
Tower of Hanoi
1. It is a classic problem where you try to move all the disks from one peg to another peg using only three pegs.2. Initially, all of the disks are stacked on top of each other with larger disks under the smaller disks.3. You may move the disks to any of three pegs as you attempt to relocate all of the disks, but you cannot place the larger disks over smaller disks and only one disk can be transferred at a time.This problem can be easily solved by Divide & Conquer algorithmIn the above 7 step all the disks from peg A will be transferred to C given Condition:Only one disk will be shifted at a time.Smaller disk can be placed on larger disk.Let T (n) be the total time taken to move n disks from peg A to peg CMoving n-1 disks from the first peg to the second peg. This can be done in T (n-1) steps.Moving larger disks from the first peg to the third peg will require first one step.Recursively moving n-1 disks from the second peg to the third peg will require again T (n-1) step.So, total time taken T (n) = T (n-1)+1+ T(n-1)Relation formula for Tower of Hanoi is:We get,It is a Geometric Progression Series with common ratio, r=2 First term, a=1(20)B equation is the required complexity of technique tower of Hanoi when we have to move n disks from one peg to another.T (3) = 23- 1 = 8 - 1 = 7 Ans[As in concept we have proved that there will be 7 steps now proved by general equation]Program of Tower of Hanoi:#include<stdio.h> void towers(int, char, char, char); int main() { int num; printf ("Enter the number of disks : "); scanf ("%d", &num); printf ("The sequence of moves involved in the Tower of Hanoi are :\n"); towers (num, 'A', 'C', 'B'); return 0; } void towers( int num, char from peg, char topeg, char auxpeg) { if (num == 1) { printf ("\n Move disk 1 from peg %c to peg %c", from peg, topeg); return; } Towers (num - 1, from peg, auxpeg, topeg); Printf ("\n Move disk %d from peg %c to peg %c", num, from peg, topeg); Towers (num - 1, auxpeg, topeg, from peg); } Output:Enter the number of disks: 3 The sequence of moves involved in the Tower of Hanoi is Move disk 1 from peg A to peg C Move disk 2 from peg A to peg B Move disk 1 from peg C to peg B Move disk 3 from peg A to peg C Move disk 1 from peg B to peg A Move disk 2 from peg B to peg C Move disk 1 from peg A to peg