NAME CSE 331 Introduction to Algorithm Analysis and Design Sample Mid term Exam I Spring 2023 Past exam created by Prof Atri Rudra DIRECTIONS cid 136 Closed Book Closed Notes except for one 8 1 2 11 review sheet cid 136 Time Limit 50 minutes cid 136 Answer the problems on the exam paper cid 136 Make sure you write your NAME on the paper cid 136 If you need extra space use the back of a page 1a 1b 1c 1d 1e 1f 1g 1h Total 5 5 5 5 5 5 5 5 40 FEW GENTLE REMINDERS cid 136 You can quote any result that we covered in class or any problem that was there in a homework or recitation but remember to explicitly state where you are quoting a result from cid 136 If you get stuck on some problem for a long time move on to the next one cid 136 The ordering of the problems is somewhat related to their relative difficulty However the order might be different for you cid 136 You might be better off by first reading all questions and answering them in the order of what you think is the easiest to the hardest problem Keep the points distribution in mind when deciding how much time to spend on each problem 1 1 8 5 40 points Each of the questions below have two parts For the first part you need to give a justification for the statement and is worth 2 points For the second part answer True or False and briefly JUSTIFY your answer A correct answer with no or totally incorrect justification will get you 1 out of the total 3 points An incorrect answer irrespective of the justification will get you 0 out of 3 points You can assume part 1 when answering part 2 regardless of the correctness of your justification for part 1 But in case you want to use part 2 to answer part 1 your justification for part 2 must be correct Recall that a statement is true only if it is logically true in all cases while it is is false if it is not true in some case a Consider an arbitrary instance of the stable marriage problem with n men and n women Part 1 Argue why the following statement is TRUE There are n n n 1 1 many possible perfect matchings Part 2 Is the following statement true or false Also remember to briefly JUSTIFY your answer There are at most n stable matchings for the instance True False Please CIRCLE your answer b Let f n log log n and g n 101010101010 Part 1 Argue why the following statement is TRUE f n is g n Part 2 Is the following statement true or false Also remember to briefly JUSTIFY your answer f n is O g n True False Please CIRCLE your answer 2 c Let f n nn and g n 2400n Part 1 Argue why the following statement is TRUE f n 2n log2 n Part 2 Is the following statement true or false Also remember to briefly JUSTIFY your answer f n is g n True False Please CIRCLE your answer d Let a1 an be n integers Part 1 Argue why the following statement is TRUE Let ai 0 1 for each i n Then the n numbers can be sorted in O n time Part 2 Is the following statement true or false Also remember to briefly JUSTIFY your answer n for every i n Then the n integers a1 an can be n ai Let sorted in O n time True False Please CIRCLE your answer 3 e Consider the BFS algorithm with its input graph G in adjacency list format Part 1 Argue why the following statement is TRUE The input size for BFS is n m Part 2 Is the following statement true or false Also remember to briefly JUSTIFY your answer BFS is a linear time algorithm Recall that an algorithm is a linear time algorithm if it runs in time O N on inputs of size N True False Please CIRCLE your answer f For any graph recall that running the BFS algorithm implicitly computes a BFS tree Note BFS tree is not rooted Part 1 Argue why the following statement is TRUE A BFS tree can be computed explicitly in O m n time Part 2 Is the following statement true or false Also remember to briefly JUSTIFY your answer Every graph has a a unique BFS tree for it True False Please CIRCLE your answer 4 g Recall that a directed graph is strongly connected if and only if every pair of vertices have directed paths from one to the other Part 1 Argue why the following statement is TRUE A directed graph has at most n2 edges in it Part 2 Is the following statement true or false Also remember to briefly JUSTIFY your answer Any directed graph on n vertices with at least n 1 edges is strongly connected True False Please CIRCLE your answer h Recall that any graph can be represented in adjacency matrix format Part 1 Argue why the following statement is TRUE Adjacency matrix takes n2 space Part 2 Is the following statement true or false Also remember to briefly JUSTIFY your answer There is an O n2 time algorithm that for any graph on n vertices given in its adjacency matrix converts it into its adjacency list representations True False Please CIRCLE your answer 5
View Full Document
Unlocking...