We are going to learn another useful tool valgrind, which helps you to find bugs in programs. The official site of valgrind has a quick start guide. Part 1. squares. Use gdb and valgrind to find and correct all compiler warnings and bugs in squares.c. You may need to look at the man pages for any library functions used in the code (e.g., atoi()) to understand their function and to ensure they are being used correctly. This exercise provides us an opportunity to debug other people’s code. Completely rewriting the program will not let us learn as much. Part 2. argvcat. argvcat is a program that concatenates all the arguments in argv to a single string and prints out the concatenated string. Starter code is provided in argvcat.c. The goals of this assignment is to 1) complete the function my strcat() and 2) fix all memory leaks in the code (Of course, you just learned valgrind.) The function my strcat() has the following prototype: char * my_strcat(char *s1, char *s2); The function takes two strings, s1 and s2, as parameters and returns a new string that is the concatenation of s1 and s2. The memory space for storing the return string should be dynamically allocated from the heap. The function should request the least amount of space that is needed to hold the result. The function should not change the strings s1 or s2. For example, the function should not try to free the memory used by s1 or s2 because 1) their memory space may not be dynamically allocated, and 2) the caller may want to keep s1 or s2. You can use string functions in C library, for example, strlen() and strcat(). Read man pages to learn them. If malloc() fails, call my_error() to print an error message and exit. It is necessary to add code in the main() function to free memory. However, the changes should not affect how my strcat() is called and how the loop is constructed. The program should work as in the sample runs listed below after my strcat() is implemented, even before memory leaks are fixed. The final program should not have memory leaks. $./argvcat ./argvcat $./argvcat a 1 b 2 234 ./argvcata1b2234 $./argvcat 1 a ” ‘#.’ and more arguments ./argvcat1a#.andmorearguments 1
Part 1. make. We are going to learn another important tool, make. Your lab TA will provide an introduction to the tool and Makefile at the beginning of the lab. The full documentation for GNU Make is available here. An example of Makefile is provided. With this file in your current working directory, running the command make compiles ex-factorial.c to generate ex-factorial if the executable does not exist. If both ex-factorial.c and ex-factorial exist, running make will re-compile ex-factorial.c if it has a more recent modification timestamp than ex-factorial. The Makefile also has a clean rule that removes all object files and the ex-factorial executable – this can be used to quickly clean up the assignment folder. To do this, run the command make clean. Change the existing rules and/or add new rules in the provided Makefile to support the building of catalan in a similar way. The default rule all should update both ex-factorial and catalan executables if necessary. The clean rule needs to be revised to remove both executables. Part 2. factorial. ex-factorial reads an integer from stdin and computes its factorial. Find and fix all syntax errors and bugs in the program. This problem is an opportunity for you to practice GDB. Do not rewrite the program. It is good practice to always check user input. Improve the program to make it robust. The program calls factorial() only if a non-negative integer is entered. Otherwise, the program terminates after printing “Error: Please enter a non-negative integer. ”. There is no need to deal with overflow if the integer is too large. Part 3. Catalan numbers. The sequence of the Catalan numbers Cn, where n ≥ 0, can be defined using the following recurrence: C0 = 1 Ck = 4k − 2 k + 1 Ck−1 if k ≥ 1 The goal of this problem is to complete the catalan number() function in catalan.c, which computes a Catalan number using the above recurrence. The constraints are as follows: • The function uses the above recurrence for computing Catalan numbers. • The function does not use floating-point numbers or operations. • The function does not print anything. • The main() function should not be changed. On the next page is a sample session of running the program. 1 $ ./catalan 0 C( 0)= 1 1 C( 1)= 1 2 C( 2)= 2 3 C( 3)= 5 4 C( 4)= 14 5 C( 5)= 42 10 C(10)= 16796 14 C(14)= 2674440 15 C(15)= 9694845 20 C(20)= 6564120420 30 C(30)= 3814986502092304 32 C(32)= 55534064877048198 33 C(33)=212336130412243110 2
Welcome to Lab 1! We will learn a debug tool GDB in this lab and practice how to use it. GDB is GNU Project Debugger. It will be the main tool you will use to find bugs in your code, especially those difficult to find. The official GDB website is here. The full GDB guide is here. There are also many GDB tutorials and cheat sheets on the Internet, for example, here and here. Part 1. parity. The even parity of a binary number is defined as 1 if the number of 1’s in the number is odd, and 0 if the number of 1’s is even. For example, 9 written as a binary number is: 9 = 10012 (1) So, the even parity of this number is 0, since there are 2 1’s in its binary representation. The following code computes the even parity of integer v: unsigned int v = 19; char parity = 0; while (v) { parity = !parity; v = v & (v – 1); } Kernighan’s Algorithm An algorithm for computing the number of 1 bits in an integer is attributed to Brian Kernighan, coauthor of the C Programming Language. a Here I’ll explain why it works, because it’s not trivial. First, consider a non-zero binary number; call it v. We’ll refer to bit j as the bit j positions to the left of the least significant bit. For example, in 1012, bits 0 and 2 are set to 1, and bit 1 is set to 0. Now, suppose bit k is the rightmost bit in v that is to 1. For example, in 101002, this would be bit 2. If we subtract 1 from v, then bit k flips to a zero, and bits 0 through k − 1 flip to 1. You can see this with 101002: 1 0 1 0 0 – 1 1 0 0 1 1 Then, by bitwise anding v with v − 1, we flip bits 0 through k − 1 back to 0: 1 0 1 0 0 & 1 0 0 1 1 1 0 0 0 0 Essentially, each time we do v & (v – 1), we flip the rightmost 1-bit to a 0-bit. a It was discovered independently by several people, see: https://graphics.stanford.edu/~seander/bithacks.html but is frequently attributed to B.K. With GDB, you can see the value of variables at runtime. It is more convenient if you ask the compiler to keep useful information in the executable by specifying -g option. For example, gcc -o parity -g parity.c Then, you load the program you would like to debug into GDB. gdb ./parity 1 Now, put a breakpoint on the v = v & (v – 1) line. In the following example, the list command lists the source code around main(), the break command sets a breakpoint, and the run command starts the program. (gdb) list main 1 #include 2 3 int main(void) 4 { 5 unsigned int v = 19; 6 char parity = 0; 7 while(v){ 8 parity = !parity; 9 v = v & (v – 1); 10 } (gdb) break 8 Breakpoint 1 at 0x4004e7: file parity.c, line 8. (gdb) run The program should have stopped at the specified line. You can examine the value of v in binary format before the execution of the statement as follows: (gdb) p/t v $10 = 10011 (gdb) p/t v-1 $11 = 10010 After the execution of the statement (with an ‘n’ command), check the updated value in v. (gdb) p/t v $12 = 10010 Part 2. Running average. Write a C program average.c that reads floating-point numbers (double) from the standard input and, after reading each number, prints the running total and average of the numbers that have been read so far. The program must terminate when there is an error or the end of file (EOF) is detected at the standard input (e.g., when the user presses Ctrl-D). The block below shows a sample execution of the program in which the user provided input consists, in this order, of numbers 1, 2, 1e10 (meaning 1 × 1010), and 0: $ ./average 1 Total=1.000000 Average=1.000000 2 Total=3.000000 Average=1.500000 1e10 Total=10000000003.000000 Average=3333333334.333333 0 Total=10000000003.000000 Average=2500000000.750000 Notes: The loop needed to read the input is as follows. 2 while (scanf(“%lf”, &x) == 1) { // pay attention to %lf … }; Here x is a double variable used to store the number read in each iteration. Note the character in the middle of %lf is the letter el, not the digit 1. The while loop continues as long as scanf() returns 1, indicating it has read one double from the standard input successfully. Otherwise, the loop is terminated. Printing the running total and average formatted as in the example above can be done using printf(“Total=%f Average=%f ”, total, average); // pay attention to %f where total and average are variables of type double. Also, remember to initialize variables before using them. 3
After lab 0, you should be able to access your VM, use basic commands in a shell (e.g. to copy/remove/rename files), edit text files like C source files, compile and run simple C code, and submit your work. 1 Setting Up Your VM Before you can access your virtual machine, there is a short setup to complete. 1. Ensure you are connected to university Wi-Fi and that you have a mobile device for 2FA. If you are not connected to university Wi-Fi, you will need to use the UConn AnyConnect VPN available here. (This applies to when you are using the virtual machine for the duration of the semester to work on assignments. If you are not connected to university Wi-Fi, you need to be connected to the VPN.) 2. Open a terminal on your local machine and SSH (Secure Shell Protocol; a way of connecting remotely to the terminal of another machine in a network.) into your VM at the address [NETID]- vm.cse.uconn.edu/. If you are on Linux, you can run ssh [NETID]@[NETID]-vm.cse.uconn.edu to connect. If you are having issues with SSH or are unsure how to do so on Mac/Windows, ask your TA. 3. Enter your NetId password when prompted. You will not be able to see what you are typing as it is hidden to not reveal your password. Press enter when finished. 4. When prompted for 2FA, enter either 1 or 2 and press enter to select your preferred 2FA method. 5. You are (hopefully) now connected to your VM by SSH! Now, every command you type is run by your VM and relayed back to you in the terminal you have open! To quit the connection, you can run the command exit. 6. Run the command /opt/scripts/codefix.sh, which sets up your VSCode environment for browser usage. You should now have access to your VM in browser at the address [NETID]-vm.cse.uconn.edu! You can just enter this into your browser of choice and begin working. Two very important things to remember for the VM: 1 • BACK UP YOUR WORK! VMs are NOT backed up. Losing significant work to data loss on the VM is not an excuse. If you are done working on a file in your VM, make sure you download it to your local machine just in case. • VMs undergo maintenance from 5:30AM to 7:30AM. There is a possibility that machines are down during this time, so do not plan on having access during this block of time. 2 Shell In the shell (most likely bash), try the following commands (and explore a bit!): pwd Show the current directory (where you are). ls List the files and directories in a directory. ls -l The -l flag tells ls to show more details. mkdir adir Create a directory. Try different names. ls -l adir Lists the files in the directory ’adir’. cd adir Move into the directory ’adir’. ls -l .. List the files in the parent directory. cd Go back to your home directory. cd adir Go to ’adir’ again. echo “hi!” Print ’hi!’ to the standard output (stdout). echo “hi!” > file Save ’hi!’ to a new file called ’file’ cat file Print the contents of a file to stdout. grep “hi” file Search the file for the string ’hi’. less file View the file interactively (q to quit). rm file Permanently deletes the file. cat Read from standard input (stdin) and dump to stdout. Ctrl-D to exit. history Show history of commands. man ls Show the manual for the ’ls’ command. man cat Show the manual for the ’cat’ command. man scanf Show the manual for the ’scanf’ function. exit Exit from the shell. 3 Text editors and your first C program! To work on a project, you need to go to the corresponding directory in the virtual terminal. Normally Coding Rooms goes to the correct directory when you start a virtual terminal. Under the project directory, you can modify existing files and/or create new files (.c files, .h files, readme’s, make files, etc.). You can use the web editor, or an editor in the virtual terminal, to edit text files, which include your C source code. If you decide to learn an editor in the terminal, there are three primary options: vim, emacs, and nano. It is highly recommended to learn one of them, in addition to the web editor. Use your favorite editor to open lab0.c. If you use the editor in the Coding Rooms IDE, you can click on the Files icon (top left) and you can use use the buttons. Otherwise, here are different ways to do it in a terminal. The following three editors are available in many systems. vi lab0.c emacs lab0.c nano lab0.c 2 Add the following C code in lab0.c. If you are using the editor in the Coding Rooms IDE, changes should save automatically. Otherwise, remember to save the file after editing. #include int main(void) { printf(“Hello, World! ”); return 0; } This is your first C program! Before you can run it, you must compile it. You can do so by typing the following command in shell/console, or by clicking the ‘Run’ button in the Coding Rooms IDE. Note that you can use console/shell at the bottom of the Coding Rooms IDE. If you would like, you can also use the tips in ?? to open a visual desktop, where you can open multiple terminal windows. cc lab0.c This will compile your C code in lab0.c and create an executable called a.out. If the process fails, read the error messages, fix the error in your C file (using the text editor), and try again. If there is no error, you will see a.out in your current directory. You can optionally specify the name of the executable that is generated by the compiler. cc -o lab0 lab0.c To run your program, type ./lab0 4 Something new Revise lab0.c. Use a while loop to calculate the sum of positive even integers below 200 and print the result to the standard output. This is very similar to the sum example we have studied. Think about how much you should increase the loop control variable to get to the next even number. Your program should output the following text: Hello, World! 9900 5 Submission If you think your code works, you should submit it on gradescope. You can download the files you have worked on in the file directory interface to the left of the IDE. There is a link to gradescope in the HuskyCT, you should already be added to the course with your UConn email. Please remember to submit your work before the deadline for each assignment and exam. Enjoy! 3 Exit from an editor in terminal There are many tutorials on nano, vi/vim, and emacs. Feel free to explore and share with other students. In case you are stuck in an editor, here are the commands you can exit from the program. nano nano is very user friendly. You can see the help at the bottom of the screen. nano a.txt Start nano to edit file a.txt Ctrl-x Exit from nano. See the prompt at the bottom of the screen There are many tutorials on the Internet, for example, here. emacs Commands in emacs are control characters or prefixed a set of characters. emacs a.txt Start emacs to edit file a.txt Ctrl-x Ctrl-s Save file Ctrl-x Ctrl-c Exit from emacs Here and here are examples of cheat sheets and tutorials on emacs. vi/vim vi has three modes. Normally, you are in the normal mode when vi just starts. Press i to enter the insert mode, where you can insert/type text. Press Esc to exit from the insert mode and get back to the normal mode. If you get lost, press Esc many times to get back to the normal mode. vi a.txt Start vi/vim to edit file a.txt :wq Save the file and then exit from vi. Work in the normal mode :q! Exit from vi without saving file. Work in the normal mode Here is an example cheat sheet.
In this problem, we write code to simulate a producer and consumer problem using multiple threads. To make the problem easier to understand, we use a fast food restaurant analogy. Assume we have a fast food restaurant serving only one type of drink, one type of fries, and one type of burger.Customers order their food online and each customer can only order one drink, one fries and one burger. Since there are only type of drink, one type of fries and one type of burger, all orders are identical. Each of the these three items will be put into a queue implemented by a linked-list, which is accessed by the restaurant employees.Each employee will remove one item from the front of the linked-list and prepare the item, and put the prepared item into a sliding tray so that the item will slide down to the bottom for customers to pick up. The sliding tray has 3 columns, one for drinks, one for fries and one for burgers. A customer will pick up the food if all the 3 columns have items at the bottom of the tray.Since all the orders are identical, any customer can pick a order when it is available. Moreover, the sliding tray can hold limited number of items in each of the column. Because of this limitation, an employee needs to wait before he can put an item in the tray if the column for that item is full.To simplify the problem, we assume the number of customers is n consumer and the number of employees is n producer, and these are known before hand. Moreover, we assume all customers already made their orders online before the employees started preparing food. After that, the customers show up at the restaurant to pick up their orders.Note that multiple customers could be ordering simultaneously, and multiple employees could access the linked-list simultaneously. This implies that we need to use a mutex to protect the linked-list. Moreover, we need to make sure that all the 3 items a customer ordered are added to the linked-list together, otherwise, under certain conditions, both customers and employees can get stuck, and we will have hungry customers.We use a 2-dimensional buffer to model the sliding tray. Specifically, we define the following structure for it. typedef struct { int size; //max # of items in each column int buf[MAX][3]; int remain; //remaining # of items to serve int counts[3]; //# of items in each column pthread_mutex_t mutex; pthread_cond_t produce_cond; pthread_cond_t consume_cond; }two_d_buffer;Here size is the maximum number of items each column can hold. remain is the number of items that still need to be produced, and is initialized to 3*n customers. Note this variable can be used for producer threads to determine when to exit. The 2-dimensional array buf[MAX][3] holds items (drinks, fries and burgers). The array counts[3] indicates the number of items in each column. Figure 1 shows an example of a 2-dimensional buffer with size 5. Note we use mutex to protect the 2-dimensional buffer, and we use two condition variables to synchronize the producing and consuming activities. Specifically, we need to implement two functions for the 2-dimensional buffer. The first one is 1 Figure 1: 2d-buffer with size 5 void add_to_buffer(int item, int col, two_d_buffer *p)This function tries to add the item at the end of the column col. The function should block if that column is full. When the item added successfully, the function should update remain associated with the 2d buffer, and try to wake up the thread blocked on function remove from buffer().The second function is void remove_from_buffer(int *a, int *b, int *c, two_d_buffer *p) This function tries to remove all 3 items from the first row of the buffer, the removed items from column 0, 1 and 2, are pointed by a, b and c. The function should block if not all the items are present in the first row. If all 3 items are successfully removed from the buffer, we need to make sure the rest of the items will slide down to the right positions, and the function should try to wake up the threads that are blocked on add to buffer().The following function simulates the time needed to prepare different food items. And it is used in producer threads. void prepare(int item) { usleep((item + 1)*100); } We need to implement both the consumer thread function, and the producer thread function. Both of them share the following structure. struct thread_data { int id; list_t *p; two_d_buffer *q; int total; //total items produced by a producer pthread_barrier_t *p_barrier; }; Here p points to a linked-list, as defined below. typedef struct { node *head, *tail; pthread_mutex_t mutex; } list_t;Note the linked-list keeps track of both the head and the tail so that we can use it conveniently as a queue. Note a mutex is used since there might be multiple threads try to access the linked-list simultaneously. Note p barrier points to a barrier, which will be used to ensure no producers start producing before all the orders are put in the queue represented by the linked-list.Below is the function for consumer threads. void* thread_consume(void* threadarg) { struct thread_data* my_data = (struct thread_data*) threadarg; int id = my_data->id; list_t *p = my_data->p; node *n1 = create_node(0); node *n2 = create_node(1); node *n3 = create_node(2); //TODO //fill in code below to add n1, n2 and n3 to the linked-list pointed by p pthread_barrier_t *p_barrier = my_data->p_barrier; pthread_barrier_wait(p_barrier); two_d_buffer *q = my_data->q; int a, b, c; remove_from_buffer(&a, &b, &c, q); printf(“consumer %04d (%d %d %d) ”, id, a, b, c); pthread_exit(NULL); } Below is the function for producer threads. void* thread_produce(void* threadarg) { struct thread_data* my_data = (struct thread_data*) threadarg; list_t *p = my_data->p; pthread_barrier_t *p_barrier = my_data->p_barrier; pthread_barrier_wait(p_barrier); two_d_buffer *q = my_data->q; int done = 0; while(!done) { //TODO //fill in code below } pthread_exit(NULL); } Find the “TODO”s in the starter code food.c and fill in the necessary code. We do not need to change anything in linked-list.h. The main() function is located in food.c. Three command line arguments are required.The first one is the number of customers(consumers), the second is the number of employees(producers), and the third is the size of the 2-dimensional buffer. Below is an example output. $ ./food 5 1 1 consumer 0001 (0 1 2) consumer 0004 (0 1 2) consumer 0003 (0 1 2) consumer 0000 (0 1 2) consumer 0002 (0 1 2) total = 15In this example, there are 5 customers (consumers), and they all made orders for 1 drink, 1 fries and 1 burger.In total they ordered 15 items. There is only one employee(producer) serving all the items. Moreover, the buffer size is 1. From the output, we can see every customer picked up their order in an arbitrary order. For example, the first line of output shows that consumer 0001 is the first to pick up an order (0 1 2). The total number of items served is 15 as shown in the last line of the output. Submit food.c to gradescope. Enjoy!
In this exercise we will continue to work on the matrix ADT. An implementation of matrix ADT (abstract data type) is given in matrix.c. The API (application programming interface) functions that operates on the matrices are listed in matrix.h. One of the functions, mulMatrix(), performs matrix multiplication, which is implemented in matrix.c. In this assignment, we implement mulMatrix thread() in mmul.c, which has the same interface as mulMatrix(), but performs matrix multiplication with two threads. We only need to change mmul.c. test-mmul.c is provided to test our implementation.The program takes the following arguments from the command line: the number of rows in the first matrix, the number of columns in the first matrix, and the number of columns in the second matrix. Then it fills two matrices with random numbers, and compares the result of mulMatrix() and mulMatrix thread(). If no argument is specified, the program works on two matrices of size 6 × 6. In addition, if a command line option -t is present, test-mmul prints the time (in seconds) spent on matrix multiplications, using the average of calls.Here are some sample sessions running test-mmul. The first command multiplies a matrix of 1000 by 500 with a matrix of 500 by 800. The resulting matrix is 1000 by 800. The second command also shows the timing information, the average of calling each multiplication function 3 times. time1 is the average time on mulMatrix() and time2 is the average time on mulMatrix thread(). The numbers are likely to change in different runs. $./test-mmul 1000 500 800 Good work! $./test-mmul 100 500 300 -t3 Good work! num_runs=3 time1=0.0652 time2=0.0341 speedup=1.9132Suppose p printers need to get j print jobs done. The print jobs are already placed in a queue. The starter code printing.c defines a type job_queue_t for the queue and provides functions to operate on the queue. A printer performs the following operations in a loop. 1. Call q_num_jobs() to get the number of remaining jobs in the queue. 2. If no job is pending, exit from the loop. 3. Call q fetch job() to get a job from the queue. The function returns an integer indicating how long the job takes. 4. Use macro print_job() to print. The macro simulates the fact that different print jobs take different amounts of time to complete. 15. Keep track the number of jobs the printer has done. The function printer_single() in the starter code printing.c shows how a single printer completes all the jobs. The tasks in this problem are to use threads to simulate the process of multiple printers completing the print jobs. Each thread is a printer and performs similar operations as printer_single(). Apparently, threads need to coordinate their operations on the queue, which is shared by all printers. A mutex is defined in the job_queue_t structure for this purpose. The program printing takes optional arguments from the command line. An argument can be one of the following. • -p . Specify the number of printers. The default value is 2. • -j . Specify the number of jobs. The default value is 20. • -d. Call the demo function showing the operations of a single printer and exit. Checking results. A script check-printing.py is provided to check the output of printing. Below is an example of how to use check-printing.py. $./printing -p 5 -j 1000 | python3 ./check-printing.py If you have made check-printing.py executable by command “chmod +x ./check-printing.py”, you can run it directly. $./printing -p 5 -j 1000 | ./check-printing.py Note that it is not guaranteed that a program that passes the check is correct. We should also examine the output manually sometimes.Some synchronization errors may manifest themselves only for some values of the parameters. And even for the same parameters, errors may happen non-deterministically due to different timing and scheduling orders of the threads. You may run the program multiple times even with the same parameters.For example, the following bash command runs the above example for 10 times. (Yes, it looks like a loop in C! and it may not work in other shells.) for ((n=0;n
Your programs should close unused file descriptors in each process. They should not leave processes running in background, leave zombies behind, or have any memory leaks.Unless stated otherwise in the starter code, you may call die() to exit from the process if a system call fails. For example, die(“fork() failed.”); die(“open() failed.”);A pipeline is a sequence of external programs chained together to perform a task. The standard output of stage i of the pipeline is fed to the standard input of stage i + 1. In shells like bash, stages are separated by “|”. For example, the following pipeline contains 7 stages and counts the number of occurrences of each word in a text file.1 The output of the last stage is redirected into file counts.txt. whitman.txt is provided with the starter code. You can also try this pipeline with other text files (e.g. your C source code). cat whitman.txt | tr -s [:space:] ‘ ’ | tr -d [:punct:] | tr A-Z a-z | sort | uniq -c | sort -nr > counts.txtThe seven stages do the following. The command in each stage prints its result to stdout, and the output of the last command is redirected to counts.txt. 1. Send the contents of the file whitman.txt to stdout 2. Replace every sequence of consecutive spaces in stdin with a single line-feed 3. Delete all punctuation characters from stdin and send remaining characters to stdout4. Replace uppercase letters in stdin with lowercase letters 5. Sort the lines from stdin alphabetically 6. Collapse adjacent matching lines to a single copy preceded by the number of copies 7. Sort the lines from stdin in reverse numerical orderIn this problem, you will complete three functions in runpipeline.c so the program can start a pipeline with the programs specified at the command line. To avoid interference with the shell, pipeline stages are separated with “–” instead of “|”. To run the above bash pipeline with runpipeline, you would run the following command in bash and the resulting counts.txt should be the same. ./runpipeline cat whitman.txt — tr -s [:space:] ‘ ’ — tr -d [:punct:] — tr A-Z a-z — sort — uniq -c — sort -nr > counts.txtIn runpipeline.c, the commands for all stages are already stored in an array of Program structures, which are defined as follows. typedef struct program_tag { char** argv; // array of pointers to arguments int argc; // number of arguments int pid; // process ID of the program int fd_in; // pipe fd for stdin int fd_out; // pipe fd for stdout } Program; 1The “” at the end of first line allows the pipeline commands to continue on the next line; you can also just join the two lines when you try the pipeline in bash.argv is the array of arguments to be passed to an execv* function, and args[0] is the executable of the program. argc is the number of arguments in argv. pid is the process ID of the child process for this program. If fd in is non-negative, the file descriptor will be used for stdin for the program. If fd out is non-negative, it will be used for stdout for the program.Note that runpipeline does not redirect the input or output for the pipeline itself (that is, the input of the first command or the output of the last command). If needed, the redirection can be set on runpipeline by the shell. So the first command in the pipeline may have redirected stdin and the last one may have redirected stdout, but this should not need to be handled in runpipeline.The functions to be completed in this problem are listed below. Information on how the functions are used and what they should return can be found in the starter code. void prepare_pipes(Program *programs, int num_programs); int start_program(Program *programs, int num_programs, int cur); int wait_on_program(Program *prog);There are a few ways to create pipes. One can create all necessary pipes for the entire pipeline in prepare pipes(), or create pipes in start program() just before they are needed. If you choose to create pipes in start program(), you do not need to add any code to prepare pipes().start program() starts a program indexed by cur. The function performs necessary redirection for the program. Make sure unused file descriptors are closed.wait on program() waits for the specified process to finish and returns the exit value of the process. Dealing with many pipeline stages may look scary at the beginning. However, if we start with two stages, and go on to three stages, four stages, and more, we could find a pattern and perform operations in a loop.Then, increasing the number of stages does not increase complexity. Several programs can be helpful for testing. For example, tee saves stdin to a file, which allows us to examine the data stream at the middle stages.The following examples show how to create pipelines with various numbers of stages. To check if your code is producing correct result or behaves correctly, run the same pipeline in bash (and use “|”, instead of “–“, to connect stages). Note: you may find the test cases for this homework difficult to decipher. Comparing the results of runpipeline() to the resutls of the same pipeline in bash will be very helpful for debugging your code, as will tee and checkof. ./runpipeline echo ‘Hello, world!’ ./runpipeline echo ‘Hello, world!’ — wc ./runpipeline echo ‘Hello, world!’ — cat — wc ./runpipeline echo ‘Hello, world!’ — cat — cat — wc ./runpipeline ls — cat — tee t.out — wc ./runpipeline cat — cat — tee t.out — cat — wc
In a hacking competition, our team breaks into the adversary’s computer and finds the following files. $ ls encrypt.c encrypted-message2 encrypted-message4 encrypted-message6 encrypted-message1 encrypted-message3 encrypted-message5 encrypted-message7We cannot see the content of the seven encrypted files but we are able to see the content of file encrypt.c. #include #include #include #include #include #include #define MAX 10240 //encrypt the message and write the result to file fd void encrypt(char *message, unsigned char key, unsigned char shift, int fd) { int len = strlen(message); printf(“len = %d ”, len); int msg[len]; for(int i = 0; i= 0 && key =0 && shift
In this exercise, we write code to simulate the spread of contagious diseases. In particular, we assume: 1. There are m hosts of a certain contagious disease. 2. These hosts are located on a two dimensional grid.3. There are three different types of hosts: (a) susceptible hosts – have not been infected by the disease (b) infected hosts – have been infected by the disease and have not yet recovered (c) recovered hosts – have recovered from the disease (Note: recovered hosts will not be infected by the disease any more)Initially there is a single infected host located at (0, 0), and the rest of the m − 1 hosts are susceptible hosts, and they are randomly located on a 2D grid with edges that warp around (like Pacman). The center of the grid is at (0, 0), and the four corners are at (−k, −k),(k, −k),(k, k) and (−k, k), respectively. When a host moves outside of a border, they will appear on the opposite side. For example, if a host at (x, k) moves up, they will appear at (x, −k), where −k ≤ x ≤ k.The hosts move according to a 2D random walk. Use rand() % 4 to generate a direction according to the following mapping: • 0 – up • 1 – right • 2 – down • 3 – leftWhen a susceptible host is at the same location as one or more infected hosts, the susceptible host becomes infected and will be contagious at the next time step. An infected host will become a recovered host T time steps after they are infected. As time goes by, the number of infected hosts will eventually drop to 0.When this happens, the number of susceptible and recovered hosts will not change any more. The simulation will be stopped at this moment. In the end, we print out the proportions of hosts which are susceptible, infected, and recovered. Hint: the number of infected should always be zero at the end of the simulation!We use a structure Host to describe a host. Note how we use enum in the code. enum TYPE {S, I, R}; typedef struct Host { int id; int x, y; int t; TYPE type; } THost;Here, id is the id of a host, (x, y) is the coordinates of a host, t is the duration since a host became infected, and type is the type of a host. To speed up the simulation, we implement a hash table to save the location information of all the infected nodes. The hash table is implemented as an array of linked lists. The size of the hash table is N. In each round of the simulation, for each infected host, a copy of this host is inserted into the hash table according to the hash value calculated based on the coordinate of the host.To insert an infected host into the hash table, we first map its (x, y) coordinate to an integer. We then apply a hash function (that is given in the code) to the resulting integer. A modulo operation is applied on the result to ensure it fits into the range of the index of an array of size N. The infected node will be inserted into the front of the corresponding linked list.For each susceptible host, we apply the same mapping and hash function to look up the corresponding linked list and see whether there is an infected host with the same coordinates. If there is, this susceptible host becomes an infected host.Below is the main() function for this program. Note how we use command line arguments. Note k is the grid size parameter; m is the number of hosts; T is the duration parameter for an infected host to recover; and N is the size of the hash table. int main(int argc, char *argv[]) { if(argc != 5) { printf(“Usage: %s k m T N ”, argv[0]); return 0; } int k = atoi(argv[1]); int m = atoi(argv[2]); int T = atoi(argv[3]); int N = atoi(argv[4]); assert(k >= 0 && k = 1 && m = 1); assert(N > 0 && N
In this exercise, we use a 3D random walk to simulate a diffusion process. Imagine a particle starting at the origin (0, 0, 0) that has equal probabilities to go in 6 possible directions – left, right, backward, forward, down, and up. For example, when the particle is at (x, y, z), with equal probability 1/6, its next location is at (x − 1, y, z),(x + 1, y, z),(x, y − 1, z),(x, y + 1, z),(x, y, z − 1) or (x, y, z + 1).The particle will conduct the random walk for n steps. We are interested in the distribution of the final locations of particles after each takes n steps. Specifically, we would like to know the distribution of the distance between the final location and the origin. In order to obtain this distribution, we simulate m such particles, and check the proportion of the particles that lies within rn distance from the origin, where r is a real number between 0 and 1.Note all the particles will be within a sphere with radius n since particles only move n steps and the furthest they can go is a distance n from the origin. In our simulation, we will calculate the proportion of particles that are within rn from the origin for r = 0.05, 0.10, 0.15, . . . , 0.90, 0.95, 1.00.Below is the main() function for this program. Note how we use command line arguments. int main(int argc, char *argv[]) { if(argc != 3) { printf(“Usage: %s n m ”, argv[0]); return 0; } int n = atoi(argv[1]); int m = atoi(argv[2]); srand(12345); diffusion(n, m); return 0; } We need to implement the function void diffusion(int n, int m) { } In this function, we need to dynamically allocate memory to represent a 3D grid where x, y, z coordinates range from −n to n. For all the possible x, y, z coordinates within the range, we save the number of particles that end up at the location (x, y, z). During the simulation, if the final location of a particle is (x, y, z), the corresponding value will be incremented by 1.Generate a random number using rand() % 6. If this number is 0 or 1, you should move left or right on the x-axis, respectively. If it is 2 or 3, you should move up or down on the y-axis, respectively. If it is 4 or 5, move up or down on the z-axis, respectively. In the implementation of main, we use the below function to print out results. 1 void print_result(int *grid, int n) { printf(“radius density ”); for(int k = 1; k
In this exercise, we use the following fact to approximate π. π = X∞ i=0 4 8i + 1 − 2 8i + 4 − 1 8i + 5 − 1 8i + 6 1 16i . To approximate π, we modify the above summation so that i is summed from 0 to n, where n is a non-negative integer. π ≈ Xn i=0 4 8i + 1 − 2 8i + 4 − 1 8i + 5 − 1 8i + 6 1 16i . In our code, we first read n from the standard input as shown below. Add more code below TODO to finish the code. #include #include int main() { int n, i; printf(“n = “); scanf(“%d”, &n); //TODO //add code below printf(“PI = %.10f ”, pi); return 0; } Note we are not allowed to use power functions in this assignment. Think how we can avoid using power functions in the above summation. Below are outputs from a few example runs. These can be used to check correctness of our code. $ ./pi n = 3 PI = 3.1415924576 $ ./pi n = 5 PI = 3.1415926532A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number either equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers, while those that do not end in 1 are unhappy numbers.For example, 13 is a happy number since 1 2 + 32 = 1 + 9 = 10, 1 2 + 02 = 1 + 0 = 1. And 85 is an unhappy number since 8 2 + 52 = 64 + 25 = 89, 8 2 + 92 = 64 + 81 = 145, 1 2 + 42 + 52 = 1 + 16 + 25 = 42, 4 2 + 22 = 16 + 4 = 20, 2 2 + 02 = 4 + 0 = 4, 4 2 = 16, 1 2 + 62 = 1 + 36 = 37, 3 2 + 72 = 9 + 49 = 58, 5 2 + 82 = 25 + 64 = 89, which is a repeated result.It can be shown that if a number is an unhappy number, it will reach 4 in the above process. This can be used to check whether a number is an unhappy number. Our job is to write code to check whether a positive integer is a happy number. Part of the code is already given. As shown below, we only need to fill in the code under TODO. Note to print out the intermediate numbers to match the expected output. #include #include int main() { int n; printf(“n = “); scanf(“%d”, &n); int m = n; //TODO //add code below if(n==1) printf(“%d is a happy number. ”, m); else printf(“%d is a NOT a happy number. ”, m); return 0; } 2 Below are a few example runs. $ ./happy n = 10 1 10 is a happy number. $ ./happy n = 101 2 4 101 is a NOT a happy number. $ ./happy n = 111 3 9 81 65 61 37 58 89 145 42 20 4 111 is NOT a happy number. $ ./happy n = 888 192 86 100 1 888 is a happy number. 3
In this problem we will write a recursive function to partition a positive integer into sum of multiple distinctive positive odd numbers. Moreover, these positive odd numbers need to be within a given bound.For example, our recursive function will show how to sum up 12 different positive odd numbers to 200, and each of these odd numbers is within 30. One solution for this problem is 1 3 7 13 15 17 19 21 23 25 27 29 At the same time, the function will return 1 to indicate the solutions exist.On the other hand, if there are no solutions for a problem, our recursive function should return 0 to indicate the fact.The main function of the code is already given, as shown below. int main(int argc, char *argv[]) { if(argc != 4) return -1; int count = atoi(argv[1]); int bound = atoi(argv[2]); int value = atoi(argv[3]); //oddSum(12,30,200); //oddSum(10,20,100); //oddSum(20,20,200); oddSum(count, bound, value); return 0; }Moreover, the implementation for the function oddSum is also given as below. void oddSum(int count, int bound, int value) { if(value
Complete HW5 by implementing the circular puzzle in a Graph ADT.def list_to_graph(L):vertices = set(range(1, len(L) + 1))edges = set() for i in range(len(L)):weight = L[i]next_index = (i + weight) % len(L) edges.add((i + 1, next_index + 1, weight))edges.add((next_index + 1, i + 1, weight)) return vertices, edges Submit
You have been hired by a restaurant to create a program that manages reservations. The program should use a priority queue to keep track of customers in order of their reservation time. Each customer has a unique name. The customer also has reservation time, represented as a string in the format of HH:MM. For example, 09:25 has a higher priority than 10:30. The time is from 00:00 until 23:59. So 16:30 is 4:30pm. The program should have a menu-based interface (provided) that allows the user to choose from the six options listed below: SubmittingYou should submit the following files:RequirementsExamplesAn example of how the program should work starts on the following page.
4. def bubblesort(L): global instructions for iteration in range(len(L) – 1): for i in range(len(L) – 1 – iteration): instructions += 1 # Increment for comparison if L[i] > L[i + 1]: L[i], L[i + 1] = L[i + 1], L[i]def selectionsort(L): global instructions n = len(L) for i in range(n – 1): min_index = i for j in range(i + 1, n): instructions += 1 # Increment for comparison if L[j] < L[min_index]: min_index = j L[i], L[min_index] = L[min_index], L[i]def insertionsort(L): global instructions for i in range(1, len(L)): key = L[i] j = i – 1 while j >= 0: instructions += 1 # Increment for comparison if L[j] > key: L[j + 1] = L[j] j -= 1 else: break L[j + 1] = keydef merge(A, B): global instructions result = [] i = j = 0 while i < len(A) and j < len(B): instructions += 1 # Increment for comparison if A[i] < B[j]: result.append(A[i]) i += 1 else: result.append(B[j]) j += 1 # Extend without incrementing instructions, assuming extend isn’t a set of instructions result.extend(A[i:]) result.extend(B[j:]) return resultdef mergesort(L): if len(L) > 1: mid = len(L) // 2 A, B = L[:mid], L[mid:] mergesort(A) mergesort(B) L[:] = merge(A, B)def partition(L, low, high): global instructions pivot = L[high] i = low – 1 for j in range(low, high): instructions += 1 # Increment for comparison if L[j] L[i+1]: L[i], L[i+1] = L[i+1], L[i] instructions += 3 # Increment for swap keepgoing = True n -= 18. if __name__ == “__main__”: # Test cases test_cases = [ ([], []), ([1], [1]), ([4, 2], [2, 4]), ([1, 2, 3, 4, 5], [1, 2, 3, 4, 5]), ([5, 4, 3, 2, 1], [1, 2, 3, 4, 5]), (random.sample(range(10), 10), sorted(random.sample(range(10), 10))), ([1, 3, 2, 5, 4], [1, 2, 3, 4, 5]), ([5, 3, 1, 2, 3, 1], [1, 1, 2, 3, 3, 5]), ]for arr, description in test_cases: instructions = 0 # Reset the instruction count bubblesort(arr) print(f”{description} list instructions: {instructions}”)9. [] list instructions: 010.[1] list instructions: 011.[2, 4] list instructions: 412.[1, 2, 3, 4, 5] list instructions: 413.[1, 2, 3, 4, 5] list instructions: 4014.[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] list instructions: 13515.[1, 2, 3, 4, 5] list instructions: 1316.[1, 1, 2, 3, 3, 5] list instructions: 45 def cocktailsort(L): global instructions n = len(L) swapped = True start = 0 end = n – 1 while swapped: swapped = False # Move larger elements to the end for i in range(start, end): instructions += 1 # Increment for comparison if L[i] > L[i + 1]: L[i], L[i + 1] = L[i + 1], L[i] instructions += 3 # Increment for swap swapped = True if not swapped: break swapped = False end -= 1 for i in range(end – 1, start – 1, -1): instructions += 1 # Increment for comparison if L[i] > L[i + 1]: L[i], L[i + 1] = L[i + 1], L[i] instructions += 3 # Increment for swap swapped = True start += 1if __name__ == “__main__”: # Test cases test_cases = [ ([], []), ([1], [1]), ([4, 2], [2, 4]), ([1, 2, 3, 4, 5], [1, 2, 3, 4, 5]), ([5, 4, 3, 2, 1], [1, 2, 3, 4, 5]), (random.sample(range(10), 10), sorted(random.sample(range(10), 10))), ([1, 3, 2, 5, 4], [1, 2, 3, 4, 5]), ([5, 3, 1, 2, 3, 1], [1, 1, 2, 3, 3, 5]), ]for arr, description in test_cases: instructions = 0 # Reset the instruction count # bubblesort(arr) # print(f”{description} list instructions: {instructions}”) cocktailsort(arr) print(f”{description} list instructions: {instructions}”)“C:UsersartjsOneDrive – University of ConnecticutDocumentsSpring 24CSE 2050cse2050hw7.venvScriptspython.exe” “C:UsersartjsOneDrive – University of ConnecticutDocumentsSpring 24CSE 2050cse2050hw7invariant.py”import unittest import random from HW7 import bubblesort, selectionsort, insertionsort, mergesort, quicksortclass TestSortingAlgorithms(unittest.TestCase): global instructionsdef setUp(self): # Reset instructions count before each test self.instructions = 0def test_bubblesort(self): self.run_sort_tests(bubblesort)def test_selectionsort(self): self.run_sort_tests(selectionsort)def test_insertionsort(self): self.run_sort_tests(insertionsort)def test_mergesort(self): self.run_sort_tests(mergesort)def test_quicksort(self): # Test cases for quicksort test_cases = [ ([], []), ([1], [1]), ([4, 2], [2, 4]), ([1, 2, 3, 4, 5], [1, 2, 3, 4, 5]), ([5, 4, 3, 2, 1], [1, 2, 3, 4, 5]), (random.sample(range(10), 10), sorted(random.sample(range(10), 10))), ([1, 3, 2, 5, 4], [1, 2, 3, 4, 5]), ([5, 3, 1, 2, 3, 1], [1, 1, 2, 3, 3, 5]), ] for arr, expected in test_cases: self.instructions = 0 quicksort(arr, 0, len(arr) – 1) self.assertEqual(arr, expected)def run_sort_tests(self, sort_func): test_cases = [ ([], []), ([1], [1]), ([4, 2], [2, 4]), ([1, 2, 3, 4, 5], [1, 2, 3, 4, 5]), ([5, 4, 3, 2, 1], [1, 2, 3, 4, 5]), (random.sample(range(10), 10), sorted(random.sample(range(10), 10))), ([1, 3, 2, 5, 4], [1, 2, 3, 4, 5]), ([5, 3, 1, 2, 3, 1], [1, 1, 2, 3, 3, 5]), ]for original, expected in test_cases: arr = original[:] # Make a copy of the array to sort if sort_func == quicksort: sort_func(arr, 0, len(arr) – 1) else: sort_func(arr) self.assertEqual(arr, expected)if __name__ == ‘__main__’: unittest.main()
Many of the problems used to teach recursion are not efficiently solved with recursion – summing numbers, finding fibonaccis, and calculating factorials all have elegant but inefficient recursive solutions.Here, we look at a problem type where recursive solutions tend to be genuinely useful: exploring branching paths until we hit a dead end or find a solution. We’ll see this a lot in graphs later this semester, and it often comes up when modelling games.The basic problem abstraction is this:Stepping Game:We will model a circular board game. The board consists of a series of tiles with numbers on them.Not all boards will be solvable. See provided examples for a solveable and an unsolveable puzzle. Tips:def solve_puzzle(L, visited=None): # No helper functionif visited is None: # initialize# the rest of your work here def solve_puzzle(L): # Using a helper functionvisited = set()return _solve_puzzle(L, visited) def _solve_puzzle(L, visited):# the rest of your work here Submission:At a minimum, submit the following files:
Doubly Linked Lists (DLLs) support O(1) removal from the end of the ADT developed in Lab 4. class Node: “”””Class to define a node in a linked list””” def __init__(self, item, _next=None, _prev=None): “”””Constructor of the Node, builds the item (data) and the link to the next node _next””” self.item = item self._next = _next self._prev = _prevdef __repr__(self): “””Returns the Node data and what it is pointing to, and wthe previous node””” return f”Node({self.item}, {self._next}, {self._prev} )”def __iter__(self): “”””Allows for the iteration over Nodes””” yield self.item if self._next is not None: yield from self._nextclass DoublyLinkedList: “””Class defining the Linked List ADT and her methods””” def __init__(self, items=None): “””Initialise the LinkedList with a head, tail and length.””” self._head = None self._tail = None self._length = 0if items is not None: for item in items: self.addlast(item)def addfirst(self, item): “””Adds a new node at the beginning of the linked list.””” new_node = Node(item, self._head) if self._head is not None: self._head._prev = new_node self._head = new_node if self._tail is None: self._tail = self._head self._length += 1def addlast(self, item): “””Adds a new node at the end of the linked list.””” new_node = Node(item, None, self._tail) if self._tail is not None: self._tail._next = new_node self._tail = new_node if self._head is None: self._head = new_node self._length += 1def remove_first(self): “””Removes the first node from the linked list.””” if self._head is None: return None # or raise an exception item = self._head.item self._head = self._head._next if self._head is not None: self._head._prev = None else: self._tail = None self._length -= 1 return itemdef remove_last(self): “””Removes the last node from the linked list in O(1) time.””” if self._tail is None: return None item = self._tail.item self._tail = self._tail._prev if self._tail is not None: self._tail._next = None else: self._head = None self._length -= 1 return itemdef __str__(self): “””Formats the str magic method to return human-readable representation of linked list””” string = ‘Your linked list contains: ‘ currentnode = self._head while currentnode is not None: string += str(currentnode.item) currentnode = currentnode._next if currentnode is not None: string += ” ~and~ ” return stringdef __len__(self): “””Returns length of the linked list””” return self._lengthdef __iter__(self): “””Modifies the iter magic method to allow for iteration on linked list””” if self._head is not None: yield from self._headdef __repr__(self): “””Returns a more basic representation of the linked list””” items = [] for item in self: items.append(str(item)) return f”LinkedList({items})” import unittest from DoublyLinkedList import DoublyLinkedListclass TestDoublyLinkedList(unittest.TestCase):def test_addfirst(self): “””Test for adding a node to the beginning of a Linked List””” ll = DoublyLinkedList() ll.addfirst(1) self.assertEqual(repr(ll),”LinkedList([‘1’])”)def test_addlast(self): “””Tests for adding a node to the end of a Linked List””” ll = DoublyLinkedList() ll.addlast(5) self.assertEqual(repr(ll), “LinkedList([‘5’])”)def test_removefirst(self): “””Tests for removing the first node of a Linked List””” ll = DoublyLinkedList() ll.addfirst(1) ll.addfirst(2) removed_item = ll.remove_first() self.assertEqual(removed_item, 2) self.assertEqual(repr(ll), “LinkedList([‘1’])”) ll.remove_first() self.assertEqual(repr(ll), “LinkedList([])”) self.assertIsNone(ll.remove_first())def test_removelast(self): “””Tests removing the last node of a Linked List””” ll = DoublyLinkedList() ll.addfirst(1) ll.addfirst(2) removed_item = ll.remove_last() self.assertEqual(removed_item, 1) self.assertEqual(repr(ll), “LinkedList([‘2’])”)# Test removing from an empty list ll.remove_last() self.assertEqual(repr(ll), “LinkedList([])”) self.assertIsNone(ll.remove_last())def test_length(self): “””Tests for the length of the Linked List””” ll = DoublyLinkedList() self.assertEqual(len(ll), 0) ll.addfirst(1) self.assertEqual(len(ll), 1) ll.addlast(2) self.assertEqual(len(ll), 2) ll.remove_first() self.assertEqual(len(ll), 1) ll.remove_last() self.assertEqual(len(ll), 0)def test_str_and_repr_consistency(self): “””Test to show consistent behavior of repr and str for the Linked List””” ll = DoublyLinkedList([1, 2, 3]) expected_repr = “LinkedList([‘1’, ‘2’, ‘3’])” self.assertEqual(repr(ll), expected_repr) expected_str = ‘Your linked list contains: 1 ~and~ 2 ~and~ 3’ self.assertEqual(str(ll), expected_str)if __name__ == ‘__main__’: unittest.main()
You will be developing multiple algorithms for one problem: Given a list of unique integers and a target integer, find all pairs in the list that add up to the target. For example, given a list of integers [1, 2, 3, 4, 5] and a target integer 5, the function should return {(1, 4), (2, 3)} (a set of tuples). NOTE: It does not, and it should not, return the reverse pairs. It should not return {(1, 4), (2, 3) , (3, 2) , (4, 1)}.import unittest from hw3 import find_pairs_naive, find_pairs_optimizedclass TestPairFindingAlgorithms(unittest.TestCase):def test_basic_functionality(self): “””Using a basic list, test hw3″”” self.assertEqual(find_pairs_naive([1, 2, 3, 4, 5], 5), {(1, 4), (2, 3)}) self.assertEqual(find_pairs_optimized([1, 2, 3, 4, 5], 5), {(1, 4), (2, 3)})def test_with_negative_numbers(self): “””Using a list with negative numbers””” self.assertEqual(find_pairs_naive([-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5], 0), {(-5, 5), (-4, 4), (-3, 3), (-2, 2), (-1, 1)}) self.assertEqual(find_pairs_optimized([-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5], 0), {(-5, 5), (-4, 4), (-3, 3), (-2, 2), (-1, 1)})def test_no_pairs(self): “””Using a list and target where no two numbers can sum up to the target””” self.assertEqual(find_pairs_naive([1, 2, 3, 4], 10), set()) self.assertEqual(find_pairs_optimized([1, 2, 3, 4], 10), set())def test_large_list(self): “””Using a somewhat large list””” large_list = list(range(100)) target = 50 expected_pairs = {(10, 40), (11, 39), (1, 49), (2, 48), (18, 32), (17, 33), (8, 42), (24, 26), (9, 41), (15, 35), (0, 50), (16, 34), (19, 31), (6, 44), (22, 28), (7, 43), (23, 27), (14, 36), (5, 45), (13, 37), (20, 30), (21, 29), (12, 38), (3, 47), (4, 46)} self.assertEqual(find_pairs_naive(large_list, target), expected_pairs) self.assertEqual(find_pairs_optimized(large_list, target), expected_pairs)if __name__ == ‘__main__’: unittest.main() def find_pairs_naive(L, n): “””Utilizes O(n^2) to find a par of numbers””” pairs = set() for i in range(len(L)): for j in range(i + 1, len(L)): if L[i] + L[j] == n: pairs.add((L[i], L[j])) return pairsdef find_pairs_optimized(L, n): “””Utilizes Dictionary to find a pair of numbers””” pairs = set() seen = {} for number in L: complement = n – number if complement in seen: pairs.add((min(number, complement), max(number, complement))) seen[number] = True return pairs def measure_min_time(func, args, n_trials=10): “””Takes a function and argument input and will keep track of the results of all n_trials and return the minimum amount of execution time as float””” min_time = float(‘inf’) for _ in range(n_trials): start = time.perf_counter() func(*args) end = time.perf_counter() min_time = min(min_time, end – start) return min_time n naive optimized10 – –50 – –100 – –150 – –200 – –300 – –500 – –def compare_algorithms(): “””Compares the naive time and optimized pair finding codes and generates a table which describes the processing time of each function””” trials = [1800, 1850, 1950, 2150, 2500] print(f”ntnaivetoptimized”) for n in trials: list_to_test = generate_list(n) naive_time = measure_min_time(find_pairs_naive, [list_to_test, n], 100) optimized_time = measure_min_time(find_pairs_optimized, [list_to_test, n], 100) print(f”{n}t{naive_time:.4f}t{optimized_time:.4f}”)n naive optimized1800 0.0676 0.00011850 0.0714 0.00011950 0.0793 0.00012150 0.0970 0.00012500 0.1310 0.0002 def find_pairs_naive(L, n): “””Utilizes O(n^2) operations to take an input of a list and a number which will determine the pairs in the list that add up to the number””” pairs = set() # 1 (Assigns a variable) for i in range(len(L)): # n (Outer loop runs n times) for j in range(i + 1, len(L)): # n (Inner loop runs n times) if L[i] + L[j] == n: # 1 (Assigns a variable if true) pairs.add((L[i], L[j])) # 1 (Performs addition) return pairs #1 (Returns a value) # ———————— # 1 + 2n + 3 = O(n^2)def find_pairs_optimized(L, n): “””Utilizes O(n) operations to take an input of a list and a number which will determine the pairs in the list that add up to the number””” pairs = set() # 1 (Assigns a variable) seen = {} # 1 (Builds blank dictionary) for number in L: # n (Loop iterates n times) complement = n – number # 1 (Subtraction) if complement in seen: # 1 (Dictionary lookup) pairs.add((min(number, complement), max(number, complement))) # 1 (Adds pairs) seen[number] = True # 1 (Dictionary set operation) return pairs # 1 (Returns a value) # ______________________________ # 2 + n + 5 = O(n) n naive optimized1800 0.0692 0.00011850 0.0724 0.00011950 0.0793 0.00012150 0.1035 0.00022500 0.1327 0.0002import time import random def find_pairs_naive(L, n): “””Utilizes O(n^2) operations to take an input of a list and a number which will determine the pairs in the list that add up to the number””” pairs = set() # 1 (Assigns a variable) for i in range(len(L)): # n (Outer loop runs n times) for j in range(i + 1, len(L)): # n (Inner loop runs n times) if L[i] + L[j] == n: # 1 (Assigns a variable if true) pairs.add((L[i], L[j])) # 1 (Performs addition) return pairs #1 (Returns a value) # ———————— # 1 + 2n + 3 = O(n^2)def find_pairs_optimized(L, n): “””Utilizes O(n) operations to take an input of a list and a number which will determine the pairs in the list that add up to the number””” pairs = set() # 1 (Assigns a variable) seen = {} # 1 (Builds blank dictionary) for number in L: # n (Loop iterates n times) complement = n – number # 1 (Subtraction) if complement in seen: # 1 (Dictionary lookup) pairs.add((min(number, complement), max(number, complement))) # 1 (Adds pairs) seen[number] = True # 1 (Dictionary set operation) return pairs # 1 (Returns a value) # ______________________________ # 2 + n + 5 = O(n)def measure_min_time(func, args, n_trials=10): “””Takes a function and argument input and will keep track of the results of all n_trials and return the minimum amount of execution time as float””” min_time = float(‘inf’) for _ in range(n_trials): start = time.perf_counter() func(*args) end = time.perf_counter() min_time = min(min_time, end – start) return min_timedef compare_algorithms(): “””Compares the naive time and optimized pair finding codes and generates a table which describes the processing time of each function””” trials = [1800, 1850, 1950, 2150, 2500] print(f”ntnaivetoptimized”) for n in trials: list_to_test = generate_list(n) target = random.randint(1, n*10) naive_time = measure_min_time(find_pairs_naive, [list_to_test, target], 100) optimized_time = measure_min_time(find_pairs_optimized, [list_to_test, target], 100) print(f”{n}t{naive_time:.4f}t{optimized_time:.4f}”)def generate_list(n): “””Generates a list of random, non-repeated numbers””” return random.sample(range(1, n*10), n)if __name__ == “__main__”: compare_algorithms() import unittest from hw3 import find_pairs_naive, find_pairs_optimizedclass TestPairFindingAlgorithms(unittest.TestCase):def test_basic_functionality(self): “””Using a basic list, test hw3″”” self.assertEqual(find_pairs_naive([1, 2, 3, 4, 5], 5), {(1, 4), (2, 3)}) self.assertEqual(find_pairs_optimized([1, 2, 3, 4, 5], 5), {(1, 4), (2, 3)})def test_with_negative_numbers(self): “””Using a list with negative numbers””” self.assertEqual(find_pairs_naive([-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5], 0), {(-5, 5), (-4, 4), (-3, 3), (-2, 2), (-1, 1)}) self.assertEqual(find_pairs_optimized([-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5], 0), {(-5, 5), (-4, 4), (-3, 3), (-2, 2), (-1, 1)})def test_no_pairs(self): “””Using a list and target where no two numbers can sum up to the target””” self.assertEqual(find_pairs_naive([1, 2, 3, 4], 10), set()) self.assertEqual(find_pairs_optimized([1, 2, 3, 4], 10), set())def test_large_list(self): “””Using a somewhat large list””” large_list = list(range(100)) target = 50 expected_pairs = {(10, 40), (11, 39), (1, 49), (2, 48), (18, 32), (17, 33), (8, 42), (24, 26), (9, 41), (15, 35), (0, 50), (16, 34), (19, 31), (6, 44), (22, 28), (7, 43), (23, 27), (14, 36), (5, 45), (13, 37), (20, 30), (21, 29), (12, 38), (3, 47), (4, 46)} self.assertEqual(find_pairs_naive(large_list, target), expected_pairs) self.assertEqual(find_pairs_optimized(large_list, target), expected_pairs)if __name__ == ‘__main__’: unittest.main()
