Design an algorithm to nest the boxes so that the number of visible boxes is as small as possible. Your answer must contain the following parts specified explicitly. • Explain how you formulate the problem into a flow-network problem. Meaning how you construct a flow network with capacities of edges and the specified vertices s and t. • Explain by justification why “the maximum flow value” or “minimum cut size” should correspond to the actual answer to the problem. • How much time does the construction of flow network take, and how much time does the Ford Fulkerson’s Algorithm take when the Ford-Fulkerson’s algorithm runs in time O(value(flow)(|V| + |E|)-time. 1
Explain the main steps of the algorithm. Give a precise explanation of the explicit polynomial running time of your algorithm. You can write either the pseudocode or the plain text description of your algorithm. But make sure to write proper explanation so that your claimed running time is consistent with your algorithm. For instance, if your algorithm runs in O(nm)-time, then explain why it is O(mn). Similarly, if your algorithm runs in O(m+n)-time, then explain why your algorithm runs in O(n+m)-time. Finally, give a short explanation why your algorithm correctly finds all the cut vertices. Example: If the directed graph is as per the figure below, then your algorithm should output all the red colored vertices.1
5/5 - (1 vote)
Guidelines for submission: If your algorithm is based on dynamic programming, then you must write your solution using the following format in that order. • Subproblem definition. • Recurrence of the subproblem. • The specific subproblem(s) that solves the actual problem. • Algorithm description. • Explanation of the running time of your algorithm.Problem: Farmers Boggis, Bunce and Beans have set-up an obstacle course for Mr. Fox. The course consists of a long row of booths, each with a number written at the door of the booth. Formally, Mr. Fox is given an array A[1,2, . . . , n] where A[k] denotes the number written at the door of the k-th booth. Each number A[k] can be positive, negative or zero. Everybody agrees to the following rules. • At each booth, Mr. Fox must say either RING or DING. • If Mr. Fox says RING at the k-th booth, then he earns a reward of A[k] chickens if A[k] > 0 and pays a penalty of −A[k] chickens if A[k] < 0. • If Mr. Fox says DING at the k-th booth, then he earns a reward of A[k] chickens if A[k] < 0 and pays a penalty of −A[k] chickens if A[k] > 0. • Mr. Fox is forbidden to say the same word more than three times a row. What it means is that if Mr. Fox says RING in booths 5, 6, and 7, then Mr. Fox must say DING at booth 8. Conversely if Mr. Fox says DING in booths 6, 7, 8, then he must say RING at booth 9. • All accounts will be settled at the end after Mr. Fox visits every booth in the order given and the umpire calls “Hot Box”. Mr. Fox will not have to carry chickens through the obstacle course. • Finally, if Mr. Fox violates any of the rules, or if he ends the obstacle course owing the farmers chickens, the farmers will shoot him. Design an efficient algorithm that computes the largest number of chickens that Mr. Fox earns by running the obstacle course given the array A[1,2, . . . , n] of numbers as the input. The running time of your algorithm must be polynomial in n. 1
5/5 - (1 vote)
Instructions: • It is an OPEN book exam. However, we trust you will not take cross-group help and will not use ChatGPT for this exam. • The final evaluation will be based on the demonstration of your submitted script running on MySQL. • List your assumptions, if any. We will accept all reasonable assumptions. Let us design a DB for the following requirements: • A highly popular ‘McM Sangeet company’ plans to organize a competition for searching the right talents to train them for creating music albums. The company advertises their recruitment requirements on different channels (both print and digital media) for inviting talents by submitting their personal information, prior experience, and a 2-5 minutes media file, which is of either an audio file (for songs) or a video (for songs and/or playing music instruments), to a given URL in the advertisement. The company writes in the advertisement that the shortlisted candidate will be informed by Phone and/or Email. • A candidate can submit more than one entry and has an option to provide more than one phone number in the submission, which are unique to him/her. • Different music groups (pop, classic, leisure, evergreen, …) are formed to create the music albums (audio/video). Every member belongs to one or more music group which is moderated by a director who himself/herself is a member of the group. Each member has a different role to play in each album. …). • The McM decides the price of the album after analysing the data collected from its trailer release, and then the album is released to distributors who eventually will sell it online. 1 Design and draw an ER diagram. Your E-R diagram should clearly — • Identify all entities (Sole/Generalized/Weak…) and their attributes (atomic, multivalued, derived) Identify relationships between these entities and attributes of relationship • Identify and underline the primary key of each entity • Identify entity relationship participation and cardinality constraints Question 2: Convert your above E-R diagram into relational schemas and implement these tables in MySQL with proper primary keys and other constraints. Populate each relation with a few data instances (say 8-10 tuples in each relation). (10) B. List all participants who have submitted both Audio and Video files. C. List all members who have been the member of more than one album D. List all members of ‘Pop’ music group who are not part of any other music group. E. List all distributors who sold all types of albums Question 4: (You need to submit the script for these queries as like question-2 above.) Write and execute the following SQL statement on relational schemas of Question 2 implemented in MySQL. B. List all members who have been the member of more than one group. (2) C. List all members of ‘Pop’ music group who are not part of any other music group. (2) D. List all participants who have submitted both Audio and Video files. (2) E. The McM company would like to analyze the data for “Which advertisement channel has been effective that attracted maximum number of entry submissions?” (2) 2
Assignment-2• Your submission should be a single zip file 2022xxx HW2.zip (Where 2020xxx is your roll number). Include all the files (code and report with theory questions) arranged with proper names. A single .pdf report explaining your codes with results, relevant graphs, visualization and solution to theory questions should be there. The structure of submission should follow: 2022xxx HW2 |− code rollno.py/.ipynb |− report rollno.pdf |− (All other files for submission) • Anything not in the report will not be graded. • Your code should be neat and well commented.1. (10 points) Section A (Theoretical) (b) Imagine that you are designing a smart room-cleaning robot for your home. It needs to be able to navigate through the house, detect obstacles, collect dust, sweep the floors, remove dirt etc. Now answer the following questions – (i) (1 point) What kind of robot is it? (ii) (1 point) What sensors will you use to solve this problem? Will you use Passive or active sensors? Give reasons for the same. (iii) (1 point) What kind of effectors will be required for this problem statement? Give reasons for the same. (Hint – effectors for movement, collecting dust, mopping the floors, etc.)? (iv) (1 point) Think of the type of knowledge base and reasoning that can be used for making this robot intelligent. 2. (10 points) Section B (Code Implementation) (a) Write a Python script that takes a text corpus (e.g., a collection of news articles) as input and performs the following tasks: (i) (0.5 points) Tokenizes the text into individual words or phrases. (ii) (0.5 points) Removes stop words (e.g., ”the”, ”and”, ”a”, etc.) from the tokenized text. (iii) (0.5 points) Performs stemming or lemmatization to reduce words to their base form. (iv) (0.5 points) Counts the frequency of each word or phrase in the text. (v) (0.5 points) Outputs the most frequent words or phrases in the text, along with their frequency count. Pick a set of 3 different random images from the data set for each augmentation task [In case storing entire 1.27 GB folder is a problem, make a folder of first 10 images and then randomly select 3 images each time]. (i) Resize (ii) Pad (iii) Grayscale (iv) Contrast (v) Saturation Page 2Figure 1: Page 3
Assignment-1• Your submission should be a single zip file 2022xxx HW1.zip (Where 2020xxx is your roll number). Include all the files (code and report with theory questions) arranged with proper names. A single .pdf report explaining your codes with results, relevant graphs, visualization and solution to theory questions should be there. The structure of submission should follow: 2022xxx HW1 |− code rollno.py/.ipynb |− report rollno.pdf |− (All other files for submission) • Anything not in the report will not be graded. • Your code should be neat and well commented.1. (11 points) Section A (Theoretical) (i) A credit card company wants to use ML to determine whether to approve or reject an applicant’s credit card application. (ii) A hospital wants to use ML to predict patient outcomes and develop personalized treatment plans. (iv) A law enforcement agency wants to use ML to identify potential suspects in a criminal investigation. Provide a detailed explanation for your answer for each scenario, highlighting the potential benefits and risks associated with the use of ML. 2. (9 points) Section B (Code Implementation) (i) Load the titanic dataset, print the shape and show the first ten rows and the last ten rows from the dataset. (ii) Find if there exist any null values in the dataset. (iii) Plot the countplot from the training dataset and comment on it. (iv) Find inference on how many males and females survived using groupby() and count() methods on training dataset. (v) Plot countplot for ‘Pclass’ feature showing count of Survived vs Dead on training data. Comment on it. (vi) Find the oldest, youngest and the average of the person who survived. (vii) Display a crosstab (available in pandas library) depicting males and females survived or died for each ‘Pclass’. Also explain your observations. (viii) ‘SibSp’ feature indicates whether a person is alone or with his family. Siblings = {brother, sister} and Spouse = {husband, wife}. Plot the crosstab for SibSp showing how many persons survived or died. Also plot factorplot for SibSp vs Survived. Comment on your observations. Note – Plots should have proper labels, titles and legends. (i) playlist(Name, Songs): This predicate creates a new playlist with the given Name and an empty list of Songs. (ii) add song(Name, Title, Artist, UpdatedPlaylist): This predicate adds a new song with the given Title and Artist to the playlist with the given Name. The UpdatedPlaylist should be a new playlist with the added song. Page 2 (iii) display playlist(Name): This predicate displays the Name of the playlist and the list of Songs in the playlist. Your Prolog program should make use of the following built-in predicates: • cut: Use the cut predicate to prevent backtracking and ensure that only one solution is found for each predicate call. • fail: Use the fail predicate to explicitly fail a predicate and force backtracking. • list: Use the list data structure to store the songs in each playlist. • append: Use the append predicate to concatenate lists when adding a new song to a playlist. Page 3
● There is only one bonus problem – a group project. It is given in the end. ● If any details are missing – make reasonable assumptions and state them as comments at the top of the program. ● Any changes/clarifications to the problems will be highlighted in blue. Question 1. Print the pattern given below using recursion – no loops are allowed. You are given a value n print a diamond which will have 2n-1 rows, and 2n columns, as shown in the figure. (In the top row print n+n stars, in the next (n-1) stars on left and right and 2 blanks in the middle, and so on till you have 1 star each on left and right; then you reverse this). Suggestion: Have two recursive functions – one to print the top half, and other to print the bottom half.Question 2. 24 hr format)” If in the record, a student is shown to enter even if he had previously entered the campus, i.e., two ENTER entries before EXIT, take the first one. Similarly, there can be two consecutive EXIT entries from the campus for a student – if so, take the last one. You are given the data for one day (A sample data file can be downloaded from File). If for a student there is EXIT but there is no ENTRY – it means he/she came the day before; similarly if ENTRY but no EXIT, it means that the student will leave next day. To avoid special situations, it is best if you first sort this data w.r.t time. Note: Use of inbuilt libraries like datetime, etc. is not allowed. Convert this data into a nested dictionary. The keys should be the name and value should be another dictionary containing a list of gate no, crossing type, time. Use this dictionary to answer the following queries (for querying, you can write a small loop and ask for a number between 1 and 3 – nothing given can be the end). 1) Given a student name (as input), show the record of students moving in/out of campus (as a list of tuples) in the day (in a output text file), and whether currently present in campus or not. Take another input for current time as well. 2) Given the start time and the end time (in 24hr format, both inclusive) as input, determine all the students who entered the campus during this, and all students who exited the campus during this time. Save the result into an output text file, with the format similar as the input data file. 3) Given the gate number (as input), determine the number of times students have entered the campus through that gate, and the number of times students have exited the campus from that gate. Question 3. For names of the input files – you can hard code it in a list, and then process them one by one. Or you can name the files as FILE1.txt to FILEn.txt, and take an integer input regarding the number of files and then read them. You need to write out the output files in this directory itself. To score an answer file first determine: F1 factor = (Unique words/Total words) F2 factor = (total occurrences the top 5 most occurring words)/Total words F3 factor = (number of sentences >35 words or < 5 words)/Total sentences F4 factor = (Frequency of consecutive [comma+full-stop+colon+semicolon]/Total words) F5 factor = 1 if (Total word count > 750 words), else 0. Net score is: 4 + F1*6 + F2*6 -F3 – F4 – F5. Slight change in the score formula – but older one is also fine. Some clarifications: 1. The total sentence count needs to be computed after discounting repeated full stops. For example – I am a student of IIIT Delhi… Here, there are a few consecutive full-stops. We will, however, consider this as a single sentence. And increase the count of consecutive full-stops/ commas/ semi-colons/ colons /hyphens by one regardless of how many full-stops there are (.. is one and ….. is also one, so is .,.,.,). 2. Consider words of the same spelling but different cases as the same word. Output is to be written in the file scores.txt , as follows: 1. Write the filename on one line. 2. On the next line, write the student’s score with the text “score: ”[without quotes]. 3. On the next line, write out the five most used words in descending order of usage. 4. On the next line, write out five randomly selected words from the submission. (Points 3 and 4 help to see whether the assignment submission is valid, by checking whether the words are actual English words or not. Your program does not have to check whether these are English words – this explanation is given just to tell you why points 3 and 4 are to be done.) Extension (voluntary – i.e. you decide if you want to do it). For similarity score computation of File1 with File2, first: 1. Determine fCW: common words, with the common frequency in both (i.e. minimum of frequency in the two files) 2. Use fCW to determine nSW – which is the sum of all the frequencies of common words to get the total number of same words 3. Use fCW to get the number of unique words common to both submissions(nSUW). Similarity score for File1 sim_index (with File2 is): sim _index = 100% x [(nSW/total words in File1)+(nSUW/total unique words in File 1)]/2 For eg, if the two submissions are: File1: My name is Sheldon Is. File2: fCW = {“My”:1, “Name”:1, “is”:2 } nSW = 1 + 1 + 2 = 3 nSUW = 3 (“My”, “Name” and “is”) sim_index for File1 = 100% x (⅘ + ⅗ )/2 = 70% Output into a file named plag.txt. One line needs to be printed for each submission with a similarity score of >50%, structure of which is: curfile targetfile sim-index separated by spaces Where: The file that is currently being evaluated -> curFile The file against which the highest similarity has been detected -> targetFile Similarity score of curFile against targetFile -> sim_index For example: 2023224.txt 2023343.txt 67% 2023236.txt 2023168.txt 54% . . . Questions 4, 5, 6 – This statement is for the next three problems. Change to: [80, 65, 50, 40] (i.e. A above 80, B between 80 and 65, …, F below 40) Develop this program and use it for grading the “IP” course. The assessments and the grading policy is given below (in the main program steps) The main program can be something like (rough sketch): 1. cname, credits = “IP”, 4 2. assessments = [(“labs”, 30), (“midsem”, 15), (“assignments”, 30), (“endsem”, 25)] 3. policy = [80, 65, 50, 40, 30] 4. create-IP course (cname, credits, assessments, policy) 6. doGrading – call a function/method 7. Loop asking for what operation (1, 2, 3); perform the operation till no input given Question 4. Write this program using class and objects – it seems that “Course” and “Student” will be natural classes. Write this program using classes and objects. You must have at least two main classes for course and student. The answer to this question should be be in a .txt file, containing: f Advantages of using OO 1. 2. Advantages of using Dictionaries 1. 2. Disadvantage of using OO 1. 2. Disadvantage of using dictionaries 1. 2. Performance comparison for grading operation (give in each line: value of N; time taken by two approaches in seconds, and which is faster and by how much). 1. N: 2. Time by OO: 3. Time by dictionary: 4. X is faster; fraction of time x took is: Performance comparison for search operation (give in each line: value of N; time taken by two approaches in seconds, and which is faster and by how much). 1. N: 2. Time by OO: 3. Time by dictionary: 4. X is faster; fraction of time x took is: ==== Bonus Problem – a group project. Develop an application of your choice in a group of 2 or 3 students. You can use whatever libraries/packages you want. The project should require a reasonable amount of python code with a few functions and/or a few classes. Your group will have to demonstrate the working of the project separately from the rest of the assignment. These demos will probably be scheduled after the final exam – and you will be allowed to demo them remotely or in person.
• You should do this assignment alone. • Do not copy or turn in solutions from other sources. You will be penalized if caught. • You can use any concurrency library to help with your implementation. The data structure implementation obviously has to be your own. Submission • Submission will be through Canvas. • Submit a compressed file called “⟨roll⟩-assign5.tar.gz”. The compressed file should have the following structure. — roll — — roll-assign5.pdf — — — — — — — — — — • We encourage you to use the LATEX typesetting system for generating the PDF file. You can use tools like Tikz, Inkscape, or Draw.io for drawing figures if required. You can alternatively upload a scanned copy of a handwritten solution, but make sure the submission is legible. • You will get up to two late days to submit your assignment, with a 25% penalty for each day. Evaluation • Write your programs such that the exact output format (if any) is respected. • We will primarily use the GPU3 department server for evaluation. Implement a concurrent open-addressing-based hash table using Pthreads. Implement support for the following operations. Listing 1: Operations supported by the bounded partial stack data structure void batch_insert(HashTable *ht, KeyValuePairs *kv_pairs, bool* result); void batch_delete(HashTable *ht, KeyList *key_list, bool* result); void batch_loopkup(HashTable *ht, KeyList *key_list, uint32_t* result); 1 2 3 The third parameter result is a boolean array to indicate the success of an insert (duplicate keys are not allowed) or delete query. For batch_lookup(), result will contain the values if present, and a negative value otherwise to indicate a failure. Adapt the driver to the exact prototype that you design. Description • Key and the value are four bytes (unsigned int) each. • The APIs work on a batch of items. • Use double hashing for resolving collisions. You should test different hash functions and compare their performance. • Assume that the concurrency is limited to operations in a batch. Each batch contains of operations of the same type. For example, there can be concurrent insertions of 10000 key and value pairs in a batch. • Use threading to issue concurrent calls to the hash table data structure (e.g., OpenMP). • Assume the maximum load factor is 0.8. • We will provide random keys and values (via files) that will be input to the hash table for testing. – random_keys_insert.bin – random_values_insert.bin – random_keys_delete.bin – random_keys_search.bin • Empirically ensure the correctness of your code with unit tests. The unit test cases can contain a fixed sequence of operations. Include the test cases as separate function calls (e.g., test1 and test2). • Use compile time flag USE_TBB to switch between the two versions. • Use the best hash functions (determined empirically from bullet (iii)) for comparing with TBB. Submission (i) A header file that implements the hash table, (ii) Extend the driver code to make calls to the hash table and compute the throughput of the kernels (e.g., 1000 inserts per second), (iii) Compare the throughput of your implementation with different primary and secondary hash functions (include all hash functions in the header file), (iv) Extend the driver to use a concurrent hash table using Intel TBB, (v) Implement a print method which can be invoked after every operation (e.g., batch_insert()) to check the content of the hash table, (vi) Compare the throughput of the TBB and Pthread implementations. Implement an “unbounded, total, lock-free” concurrent stack using linked lists. The stack will contain only positive 4-byte integer values. Listing 2: Operations supported by the unbounded total lockfree stack data structure int pop(); void push(int v); 1 2 Since the Stack is unbounded and total, we do not need APIs like isEmpty() and isFull(). Listing 3: Possible definition of a linked list node class Node { public: int value; Node *next; } 1 2 3 4 5 • Unlike Problem 1, concurrency means different threads can make individual calls to push() and pop(), • Your implementation should be non-blocking, i.e., you should not use locks, • You can maintain a pointer to the top of the stack as follows: std::atomic top, • A pop() operation on an empty stack should return a negative integer, i.e., it will not block, • Ignore OOM issues while implementing the push() operation, • Use random_values_insert.bin from Problem 1 to generate a sequence of random values to be pushed, • Whether a thread issues a push() or a pop() can be decided based on probability, • Lock-free implementations are vulnerable to the ABA problem. An easy fix that is mostly correct is to maintain the count of pop operations performed on the stack. A CAS operation should then compare both the top pointer and the count. Submission (i) A header file that implements the concurrent stack, (ii) Extend the driver code from Problem 1 to work with stacks, (iii) Report the time taken to complete n concurrent operations, where n ∈ {1e5,1e6,1e7}, (iv) Implement a print method which can be invoked from the driver to check the content of the stack, (v) Evaluate the scalability (strong) of your implementation with threads (e.g., 1,2,4,8, and 16).
• You should do this assignment alone. • Do not copy or turn in solutions from other sources. You will be penalized if caught. • You can tweak the compilation commands in the Makefile to suit your compiler version and the target architecture. Include the updated Makefile with exact compilation instructions for each programming problem (e.g., arch and code flags to nvcc). • Refer to the CUDA C++ Programming Guide for documentation on the CUDA APIs and their uses. Submission • Submission will be through Canvas. • Submit a compressed file called “⟨roll⟩-assign4.tar.gz”. The compressed file should have the following structure. — roll — — roll-assign4.pdf — — — — — — — — — — — — — — — — — — — — • We encourage you to use the LATEX typesetting system for generating the PDF file. You can use tools like Tikz, Inkscape, or Draw.io for drawing figures if required. You can alternatively upload a scanned copy of a handwritten solution, but make sure the submission is legible. • You will get up to two late days to submit your assignment, with a 25% penalty for each day. Evaluation • Write your programs such that the exact output format (if any) is respected. • We will primarily use the GPU3 department server for evaluation. Consider the following code. #define N 64 double in[N][N][N], out[N][N][N]; for (i=1; i
• You should do this assignment alone. • Do not copy or turn in solutions from other sources. You will be penalized if caught. Submission • Submission will be through Canvas. • Submit a compressed file called “⟨roll⟩-assign2.tar.gz”. The compressed file should have the following structure. — roll — — roll-assign2.pdf — — — — — — — — — — The PDF file should contain descriptions for the first two problems, and your solution for the last problem. • We encourage you to use the LATEX typesetting system for generating the PDF file. You can use tools like Tikz, Inkscape, or Draw.io for drawing figures if required. You can alternatively upload a scanned copy of a handwritten solution, but make sure the submission is legible. • You will get up to two late days to submit your assignment, with a 25% penalty for each day. Evaluation • Write your programs such that the exact output format (if any) is respected. • We will evaluate your implementations on a Unix-like system, for example, recent Debianbased distributions installed on KD first floor labs. • We will evaluate the implementations with our own inputs and test cases, so remember to test thoroughly. You are given a multithreaded program with N threads. The program reads N files, and should report the total number of words and lines processed by all the threads. We provide a driver source code for the problem. Your task is to analyze the source code, and identify and report the performance bugs present in the source code, if any. If a performance bug is identified, provide a manually fixed version. Describe your modifications to the source code and report the performance gain. Use the following commands to compile the attached driver and run the sample test case. make ./problem1.out 4 ./test1/input You can use the perf c2c tool to identify some forms of performance bugs. You can use the following links to learn more about using perf. • C2C – False Sharing Detection in Linux Perf • perf c2c man page Input The input to your program will be a path to a file, say input. The file input lists the full paths of N source files that are to be processed by N threads. Read the contents of the file input into a shared data structure X. Each thread will then pick one file from the shared data structure to analyze. A thread reads its file one line at a time and divides the line into tokens. The thread updates a counter to track the words encountered by the threads and updates the shared variable to track the total number of places the line. Example File 1: ABC, EFG HIJK. LMNOP QRST. File 2: ABC EF HI LMNOPQ RST UV Expected Output: Thread 0 counter: 6 Thread 1 counter: 5 Total words processed: 11 Total lines processed: 4 Write a C++ program that takes five arguments from the command line: a string that represents the path to an input file to be read (say R), an integer representing the number of producer threads (say T), an integer representing the number of lines each thread should read from the file (say L), an integer representing the size of a shared buffer (say M), and a string that represents the path to an output file (say W). Assume the file R to be read contains N lines. The program will launch the required number of threads T. After all the threads are created, the threads will contend for access to R to repeatedly read L consecutive lines. Then, each thread will write its share of L consecutive lines atomically to a FIFO shared buffer. A dedicated consumer thread (not included in T) keeps reading from the shared buffer and writes its contents to the destination file W. • Blank lines are also counted. • The input file can have more than T*L lines. • The problem requires synchronization (barriers, mutexes, and condvars) at multiple places. • All threads should acquire locks only for the minimum required duration (e.g., reader thread reading L lines). • Use a conditional variable instead of busy waiting for synchronizing accesses to the shared buffer across producer and consumer threads. • You are not allowed to use concurrent data structures, but you can use other STL data structures like std::vector and std::atomic. • The application should terminate properly after all threads are done. The goal of this problem is to achieve correctness. So, test your code thoroughly with different possible inputs. Consider the following loop nest. for i = 1, N-2 for j = i+1, N A(i, j-i) = A(i, j-i-1) – A(i+1, j-i) + A(i-1, i+j-1) 1 2 3 List all flow, anti, and output dependences, if any, using the Delta test. Show your computation. Assume all array subscript references of array A are valid.
• You should do this assignment alone. • Do not copy or turn in solutions from other sources. You will be penalized if caught. Submission • Submission will be through Canvas. • Submit a compressed file called “⟨roll⟩-assign1.tar.gz”. The compressed file should have the following structure. — roll — — roll-assign1.pdf — — — — — The PDF file should contain solutions for the first three problems, and your description and results for the fourth problem. Show your computations where feasible and justify briefly. • We encourage you to use the LATEX typesetting system for generating the PDF file. You can use tools like Tikz, Inkscape, or Draw.io for drawing figures if required. You can alternatively upload a scanned copy of a handwritten solution, but make sure the submission is legible. • You will get up to two late days to submit your assignment, with a 25% penalty for each day. Consider the following loop. float s = 0.0, A[size]; int i, it, stride; for (it = 0; it < 1000 * stride; it++) { for (i = 0; i < size; i += stride) { s += A[i]; } } 1 2 3 4 5 6 7 Assume an 8-way set-associative cache with a capacity of 256 KB, line size of 64 B, and word size of 4 B (for float). The cache is empty before execution and uses an LRU replacement policy. Given size=32K, determine the total number of cache misses on A for the following access strides: 1, 4, 16, 64, 2K, 8K, 16K, and 32K. Consider all the three kinds of misses: cold, capacity, and conflict. Consider a cache of size 64K words and lines of size 8 words. The matrix dimensions are 1024×1024. Perform cache miss analysis for the kij and the jik forms of matrix multiplication (shown below) considering direct-mapped and fully associative caches. The arrays are stored in row-major order. To simplify the analysis, ignore misses from cross-interference between elements of different arrays (i.e., perform the analysis for each array, ignoring accesses to the other arrays). Listing 1: kij form for (k = 0; k < N; k++) for (i = 0; i < N; i++) for (j = 0; j < N; j++) C[i][j] += A[i][k] * B[k][j]; 1 2 3 4 Listing 2: jik form for (j = 0; j < N; j++) for (i = 0; i < N; i++) for (k = 0; k < N; k++) C[i][j] += A[i][k] * B[k][j]; 1 2 3 4 Your solution should have a table to summarize the total cache miss analysis for each loop nest variant and cache configuration, so there will be four tables in all. Justify your computations. Consider the following code. #define N (4096) double y[N], X[N][N], A[N][N]; for (k = 0; k < N; k++) for (j = 0; j < N; j++) for (i = 0; i < N; i++) y[i] = y[i] + A[i][j] * X[k][j]; 1 2 3 4 5 6 Assume a direct-mapped cache of capacity 16 MB, with 32 B cache lines and a word of 8 B. Assume that there is negligible interference between the arrays A, X, and y (i.e., each array has its 16 MB cache for this question), and arrays are laid out in the row-major form. Estimate the total number of cache misses for A, X, and y. Assume a naïve O(n3) sequential matrix multiplication kernel (ijk form) for matrices of dimensions 4096×4096 (given). (i) Implement an optimized version of the sequential matrix multiplication implementation using loop blocking. Experiment with different block dimensions (for e.g., 4×4 to 32×32). Use a table to report the speedup of your optimized implementation over the sequential implementation for the different block sizes that you have tried. The first three columns will be the block sizes for matrices A, B, and C, and the last column will report the speedup compared to the sequential version. (ii) Note the block size that works best for your setup. Remember that the cache hierarchy will influence the optimal block dimensions. Justify the improved performance by tracking performance counters with PAPI. List the PAPI version and the performance counters you have used. • Do not change the ijk loop order. • Create separate functions for your optimized variants for ease of debugging and evaluation. • You should time your code on a noiseless system (i.e., no concurrent applications are running). Take times for 3–5 runs, and use the arithmetic mean. • Report the cache hierarchy for the system you will use. • Ensure that you are using relatively recent versions of PAPI (v5.7+). • We will try to reproduce your results.
This assignment is intended to introduce you to the process manipulation facilities in the Linux Operating System, which originate from the Unix Operating System from which Linux is a dialect. You are to implement the program described below on a Linux machine. The program needs to be implemented in C or C++ and compiled with gcc or g++. Command Execution You are to write a program doit that takes another command as an argument and executes that command. For instance, executing: % ./doit wc foo.txt would invoke the wc “word count” command with an argument of foo.txt, which will output the number of lines, words and bytes in the file “foo.txt” (which is assumed to exist in the current directory). Note the wc command will work on any file containing text. After execution of the specified command has completed, doit should display statistics that show system resources the command used. In particular, doit should print: 1. the amount of CPU time used (both user and system time) (in milliseconds), 2. the elapsed “wall-clock” time for the command to execute (in milliseconds), 3. the number of times the process was preempted involuntarily (e.g. time slice expired,preemption by higher priority process), 4. the number of times the process gave up the CPU voluntarily (e.g. waiting for a resource), 5. the number of major page faults, which require disk I/O, and 6. the number of minor page faults, which could be satisfied without disk I/O. 7. the maximum resident set size used, which is given in kilobytes. Basic Command Shell exit—causes your shell to terminate. cd dir—causes your shell to change the directory to dir. set prompt = newprompt—causes your shell to change the prompt to newprompt. The prompt is one of many shell variables that an actual shell will maintain, but this is the only one you need to handle in your shell. < current directory is changed to dir (if successful) > ==>ls < listing of files in the current directory > < statistics about this ls command > ==>set prompt = myprompt: < change string used for your shell prompt > myprompt:exit % < back to the shell prompt > Background Tasks For the final two points of the project, you need to extend your basic command shell to handle background tasks—you should not create a new executable for this portion of the project. A background task is indicated by putting an ampersand (‘&’) character at the end of an input line. When a task is run in background, your shell should not wait for the task to complete, but immediately prompt the user for another command. Note that any output from the background command will be directed to the terminal display and will intermingle with output from your shell and other commands. With background tasks, you will need to modify your use of the wait() system call so that you check the process id that it returns. The returned process id might correspond to a background task rather than the currently invoked foreground task. In this case, your shell should print out the process id of the completed background task along with the command name. You also need to add an additional built-in command to your shell: jobs—lists all background tasks A sample session with background tasks is given below with comments given in . % ./doit ==>sleep 5 & [1] 12345 < indicate background task and its process id > ==>jobs [1] 12345 sleep < print process id and command name for tasks > ==>ls < listing of files in the current directory > < statistics about this ls command > ==>cat foo.txt [1] 12345 Completed < indicate that the background jobs is complete > < statistics about this sleep command > < print the file foo.txt > < statistics about this cat command > ==>exit % < back to the shell prompt > If the user tries to exit the shell before all background tasks have completed then your shell should refuse to exit and wait() until these tasks have completed. You should also observe how your mini-shell works in comparison to a regular Linux shell. Does it have all the same features? What limitations does it have? You should include your observations as a comment in your code that is turned in. Helpful Hints The following system calls might be useful: fork() — create a new process. To get help information about these routines, use the Linux “man” command. For instance, entering “man fork” will display the manual page entry for fork on the terminal. The manual pages are organized into sections. Section 1 is for Linux commands, Section 2 is for system calls and Section 3 is for library routines. Some entries are contained in more than one section. For example to obtain information about the system call wait() (rather than the command wait) use “man 2 wait” where the section is explicitly given. Submission of Assignment Submit your project as directed in class using the assignment name “proj1”. At a minimum you should submit your program code and a file showing execution of your program on test cases for your program. The script command is useful for doing so.
5/5 - (1 vote)
Modify your existing project web site with new features including a product detail page, a login feature, an administrator page, and support for transactions. 1. Sample web site 2. Start with the setup for lab 7 for either Java, PHP, or Node.js. If you have an existing Docker container for lab 7, you do not need to download and setup lab 7 again. 3. Download starter code for Java, PHP, or Node.js. These code files should be ADDED to your existing lab 7 project. There is a new main page (index.jsp/php), an administrator page (admin.jsp/php), and images in the img folder. The four new code files to change: validateLogin.jsp/php, product.jsp/php, admin.jsp/php, and ship.jsp/php. 4. Your output does not have to look exactly like the sample (feel free to make it look better!). The product page will show details on the product including images. An image can be retrieved from a local folder using a URL or stored as a binary object in the database. +1 mark – for modifying product listing page to go to product detail page when click on product name +1 mark – for adding link to “add to cart” and to “continue shopping” Screenshot+1 mark – for checking user is logged in before accessing page Screenshot+1 mark – for displaying error message if attempt to access page and not logged in Screenshot+3 mark -for using transactions to either process the shipment and ship all items (up to 3) or generate an error Test by entering URL like: http://localhost/shop/ship.jsp?orderId=1 Screenshot – Successful Shipment with orderId=1 Screenshot – Unsuccessful Shipment with orderId=3Submission
Lab 7: Building a Database-enabled Web Site using PHP Please follow the setup instructions located in the assign/setup directory. The sample code for these examples is code/304_lab7_starter_php.zip. Example 1 Here is the code to show “Hello World!” using PHP: “` “` Click for a demonstration of the Hello World code The URL of the PHP file is: http://localhost/HelloWorld.php Modify the code using a text editor. Try and change the code so that the output looks like this: Hello World Again! 1 2 3 4 5 Click here for a demonstration of the Hello World Again code Solution – HelloWorldAgain.php Example 2 Example code to query the workson database and return some answers in a table. To query the COSC 304 database, the url is host = cosc304_mysql, database = workson and put in your user id and password. There is also sample code for SQL Server. Example 3 Modify the sample PHP code for querying WorksOn such that for each department you list its projects and then its employees. The output should look like this (click here). Solution – WorksOnDeptEmpProj.php Example 4 You can pass and receive parameters between PHP pages. An example is to create an HTML form that collects user input and then passes this information to a PHP file to perform the query and return the answers. Query Form Example PHP Code for Performing Query Example 5 Create your own query form for the WorksOn database. Your form should have boxes for the Employee name and Project name that accept partial matches (using LIKE ‘%queryString%’). The PHP file should receive the parameters and create a query that lists all WorksOn records where the employee name and project name are as specified. Show the count of the # of records at the bottom of the page. An example query form and system is available. Solution – HTML File Solution – EmpProjQuery.php Lab 7 Assignment
Lab 6: Using Java/JDBC with MySQL and Microsoft SQL Server This assignment practices developing Java code that uses JDBC to connect to a MySQL database. Customer (CustomerId, CustomerName) Employee (EmployeeId, EmployeeName, Salary, SupervisorId) Product(ProductId, ProductName, ListPrice) Orders (OrderId, OrderDate, CustomerId, EmployeeId, Total) OrderedProduct (OrderId, ProductId, Quantity, Price) Initial Steps Download the starter code and unzip. The starter code has a SQL DDL script to create the database, a JUnit test program called TestOrderJDBC.java, and the code file to edit called OrderJDBC.java. It also contains the MySQL JDBC JAR file. Use VSCode to edit the code files. You will need to install the Java extension to compile and run. Write the code to complete the methods in OrderJDBC.java (look for TODO items).
