Assignment # 02: Stack and Queue Due Date: 7th August 2020 10:59 AM P#1: Write a function named flipHalf that reverses the order of half of the elements of a Queue of integers, passed by reference as a parameter to your function. Your function should reverse the order of all the elements in odd-numbered positions (position 1, 3, 5, etc.) assuming that the first value in the queue has position 0. For example, if the queue originally stores this sequence of numbers when the function is called: index: 0 1 2 3 4 5 6 7 front {1, 8, 7, 2, 9, 18, 12, 0} back Then it should store the following values after the function finishes executing: index: 0 1 2 3 4 5 6 7 front {1, 0, 7, 18, 9, 2, 12, 8} back Notice that numbers in even positions (positions 0, 2, 4, 6) have not moved. That sub-sequence of numbers is still: (1, 7, 9, 12). But notice that the numbers in odd positions (positions 1, 3, 5, 7) are now in reverse order relative to the original. In other words, the original sub-sequence: (8, 2, 18, 0) - has become: (0, 18, 2, 8). Constraints: You may use a single stack as auxiliary storage. P#2: Write a function named isPalindrome that takes a reference to a queue of integers as a parameter and returns true if the numbers in the queue represent a palindrome (and false otherwise). A sequence of numbers is considered a palindrome if it is the same in reverse order. For example, suppose a queue called q stores these values: {3, 8, 17, 9, 17, 8, 3} Then the call of isPalindrome(q); should return true because this sequence is the same in reverse order. If the queue had instead stored these values: {3, 8, 17, 9, 4, 17, 8, 3}
The call on isPalindrome would instead return false because this sequence is not the same in reverse order (the 9 and 4 in the middle don’t match). The empty queue should be considered a palindrome. You may not make any assumptions about how many elements are in the queue and your function must restore the queue so that it stores the same sequence of values after the call as it did before. You may use one stack as auxiliary storage. P#3: Write a function named rearrange that takes a reference to a queue of integers as a parameter and rearranges the order of the values so that all of the even values appear before the odd values and that otherwise preserves the original order of the list. For example, suppose a queue called q stores this sequence of values: {3, 5, 4, 17, 6, 83, 1, 84, 16, 37} The call of rearrange(q); should rearrange the queue to store the following sequence of values: {4, 6, 84, 16, 3, 5, 17, 83, 1, 37} Notice that all of the evens appear at the front of the queue followed by the odds and that the order of the evens is the same as in the original queue and the order of the odds is the same as in the original queue. You may use one stack as auxiliary storage. P#4: Write a function named reorder that accepts as a parameter a queue of integers that are already sorted by absolute value, and modifies it so that the integers are sorted normally. For example, if a queue variable named q stores the following elements: front {1, -2, 4, 5, -7, -9, -12, 28, -34} back Then the call of reorder(q); should modify it to store the following values: front {-34, -12, -9, -7, -2, 1, 4, 5, 28} back Constraints: You may use a single stack as auxiliary storage.
P#6: Given a number n, write a function that generates and prints all binary numbers with decimal values from 1 to n. You need to use a queue for that. Input: 5 Output: 0 01 10 11 100 101 Input: 3 Output: 0 01 10 11 Input: 1 Output: 0 01
Suppose you had to write a class that implements a list using an int[] Let’s call it IntArrayList behavior: add(value), add(index, value) get(index), set(index, value) size() remove(index) indexOf(value) toString() … The list’s size will be the number of elements added to it so far. How will the list be used?
Question 1 a. Summarize the distinctions between a process, an algorithm, and a program, and give examples. b. Summarize the distinction between declarative statements and imperative statements, while giving examples. c. Explain the differences between a literal, a constant, and a variable, with examples. d. Summarize the distinction between a procedural and object-oriented programming e. Summarize the distinction between a stack and queues, with examples f. Explain the two styles of comment and their implication, giving an example for each case g. Summarize the distinction between a floating-point variable, a double, long integer, an integer and a string, specifying how much minimum memory they each can occupy in a program. h. Summarize the distinctions between an array and a pointer, while giving an example for each. Question 2 a. Sorting a vector in descending order can be done by using the algorithm below. Write a source code in C++ to implement the algorithm, given an array with elements 10, 9, -5, 6, -7, 0, -8, 1. Begin Declare ar of vector type. Initialize some values into ar in vector pattern. for (const auto &i: ar) Print “Elements after sorting”. Call sort(ar.begin(), ar.end(), greater <>()) function to sort all the elements in descending order of ar vector. for (const auto &i: ar) print all the values of variable i. End. b. Write an algorithm and a source code in C++ to add the values of an array, given that the array has the following values: 8, 5, 0, 8, 2, 6, 9, 7 c. Write a source code in C++ to sorted an array of 80, 10, 12, 2, 25, 4, 64, 90 using a bubble sort. d. Write a C++ source code to swap three variables, given their values as 2, 3 and 4
One of the applications of a stack is to backtrack—that is, to retrace its steps. As an example, imagine we want to read a list of items, and each time we read a negative number we must backtrack and print the five numbers that come before the negative number and then discard the negative number.
Show graphically representation for the following data.
1 2 3 4 5 -1 1 2 3 4 5 6 7 8 9 10 -2 11 12 -3 1 2 3 4 5
With an ASCII encoding (8 bits per character) the 16-character string “Coronavirus disease is an infectious disease caused by a newly discovered coronavirus” requires 680 bitsto send. use Huffman’s algorithm to construct a tree that is used for data compression. Calculate minimum bits of stream using Huffman’s algorithm to send the above string.
Write a program that reads a list of names and telephone numbers from a text file and inserts them into a BST tree. Once the tree has been built, present the user with a menu that allows him or her to search the list for a specified name, insert a new name, delete an existing name, or print the entire phone list. At the end of the job, write the data in the list back to the file. Test your program with at least 10 names
As part of the formal assessment for the programme you are required to submit a Data Handling and Decision-Making report. Please refer to your Student Handbook for full details of the programme assessment scheme and general information on preparing and submitting assignments. Learning Outcomes (LO): After completing the module, you should be able to: 1. Analyse methods of auditing data holdings and gap identification. 2. Critically analyse theoretical and core processes of data manipulation and mining. 3. Utilise and evaluate basic statistical concepts. 4. Appreciate ethical issues and their importance to data handling and decision making. 5. Develop a practical ability with data analysis and data mining methods to analyse and interpret data sets. 6. Make recommendations based upon the findings from data analysis. 7. Graduate Attribute – Effective Communication Communicate effectively both, verbally and in writing, using a range of media widely used in relevant professional context. Maximum word count: 5,000 words Please note that exceeding the word count by over 10% will result in a reduction in grade by the same percentage that the word count is exceeded. You must not include your name in your submission because the University operates anonymous marking, which means that markers should not be aware of the identity of the student. However, please do not forget to include your STU number.