Course Title: Programming Language II Course Code: CSE 111 Lab Assignment no: 6Write a Student class to get the desired output as shown below. 1. Create a Student class and a class variable called ID initialized with 0. 2. Create a constructor that takes 4 parameters: name, department, age and cgpa. 3. Write a get_details() method to represent all the details of a Student 4. Write a class method from_String() that takes 1 parameter which includes name, department, age and cgpa all four attributes in string.#Write your code here for subtasks 1-6.s1 = Student(“Samin”, “CSE”, 21, 3.91) s1.get_details() print(“———————–“) s2 = Student(“Fahim”, “ECE”, 21, 3.85) s2.get_details() print(“———————–“) s3 = Student(“Tahura”, “EEE”, 22, 3.01) s3.get_details() print(“———————–“) s4 = Student.from_String(“Sumaiya-BBA-23-3.96”) s4.get_details()# Write the answer of subtask 5 here# Write the answer of subtask 6 here#You are not allowed to change the code above OUTPUT ID: 1 Name: Samin Department: CSE Age: 21 CGPA: 3.91 ———————– ID: 2 Name: Fahim Department: ECE Age: 21 CGPA: 3.85 ———————– ID: 3 Name: Tahura Department: EEE Age: 22 CGPA: 3.01 ———————– ID: 4 Name: Sumaiya Department: BBA Age: 23 CGPA: 3.965. Explain the difference between a class variable and an instance variable. Print your answer at the very end of your code. 6. What is the difference between an instance method and class method? Print your answer at the very end Write the Assassin class so that the given code provides the expected output. 1. Create Assassin class 2. Create 1 class variable 3. Create 1 class method titled ‘failureRate()’ 4. Create 1 class method titled ‘failurePercentage()’ 5. Maximum success_rate is 100 [You are not allowed to change the code below] # Write your code herejohn_wick = Assassin(‘John Wick’, 100) john_wick.printDetails() print(‘================================’) nagisa = Assassin.failureRate(“Nagisa”, 20) nagisa.printDetails() print(‘================================’) akabane = Assassin.failurePercentage(‘Akabane’, 10) akabane.printDetails() Output: Name: John Wick Success rate: 100% Total number of Assassin: 1 ============================ Name: Nagisa Success rate: 80% Total number of Assassin: 2 ============================ Name: Akabane Success rate: 90% Total number of Assassin: 3Implement the design of the Passenger class so that the following output is produced: The assumption is Bus base-fare is 450 taka. A passenger can carry upto 20 kg for free. 50 taka will be added if bag weight is between 21 and 50 kg. 100 taka will be added if bag weight is greater than 50 kg. [You are not allowed to change the code below] # Write your code hereprint(“Total Passenger:”, Passenger.count) p1 = Passenger(“Jack”) p1.set_bag_weight(90) p2 = Passenger(“Carol”) p2.set_bag_weight(10) p3 = Passenger(“Mike”) p3.set_bag_weight(25) print(“=========================”) p1.printDetail() print(“=========================”) p2.printDetail() print(“=========================”) p3.printDetail() print(“=========================”) print(“Total Passenger:”, Passenger.count) Output: Total Passenger: 0 ========================= Name: Jack Bus Fare: 550 taka ========================= Name: Carol Bus Fare: 450 taka ========================= Name: Mike Bus Fare: 500 taka ========================= Total Passenger: 3Task 4 Implement the design of the Travel class so that the following output is produced: [You are not allowed to change the code below] # Write your code hereprint(“No. of Traveller =”, Travel.count) print(“=======================”) t1 = Travel(“Dhaka”,”India”) print(t1.display_travel_info()) print(“=======================”) t2 = Travel(“Kuala Lampur”,”Dhaka”) t2.set_time(23) print(t2.display_travel_info()) print(“=======================”) t3 = Travel(“Dhaka”,”New_Zealand”) t3.set_time(15) t3.set_destination(“Germany”) print(t3.display_travel_info()) print(“=======================”) t4 = Travel(“Dhaka”,”India”) t4.set_time(9) t4.set_source(“Malaysia”) t4.set_destination(“Canada”) print(t4.display_travel_info()) print(“=======================”) print(“No. of Traveller =”, Travel.count) Output No. of Traveller = 0 ======================= Source: Dhaka Destination:India Flight Time:1:00 ======================= Source: Kuala Lampur Destination:Dhaka Flight Time:23:00 ======================= Source: Dhaka Destination:Germany Flight Time:15:00 ======================= Source: Malaysia Destination:Canada Flight Time:9:00 ======================= No of Traveller = 4Task 5 Create an Employee Class that will have ● Two instance variable: name and workingPeriod ● A class method named employeeByJoiningYear(): o To create an Employee object by joining year for calculating the working period o It will have two Parameter name and year ● A static method experienceCheck() to check if an Employee is experienced or not o It will take working period and gender as parameter o If an employee’s working period is less than 3, he or she is not experienced [You are not allowed to change the code below] # Write your code here employee1 = Employee(‘Dororo’, 3) 3 5 Dororo Harry He is not experienced She is experiencedTask 6 Implement the design of the Laptop class so that the following output is produced [You are not allowed to change the code below] # Write your code herelenovo = Laptop(“Lenovo”, 5); dell = Laptop(“Dell”, 7); print(lenovo.name, lenovo.count) print(dell.name, dell.count) print(“Total number of Laptops”, Laptop.laptopCount) Laptop.advantage() Laptop.resetCount() print(“Total number of Laptops”, Laptop.laptopCount) Output Lenovo 5 Dell 7 Total number of Laptops 12 Laptops are portable Total number of Laptops 0 Task 7 Design Cat class for the following code to get the output as shown. You have already solved this problem in assignment 4 using constructor overloading. Now, solve this again but this time DO NOT USE CONSTRUCTOR OVERLOADING. Hint: You will have to use classmethods. [You are not allowed to change the code below] # Write your code hereprint(“Total number of cats:”, Cat.Number_of_cats) c1 = Cat.no_parameter() c2 = Cat.first_parameter(“Black”) c3 = Cat(“Brown”, “jumping”) c4 = Cat(“Red”, “purring”) c5 = Cat.second_parameter(“playing”) print(“=======================”) c1.printCat() c2.printCat() c3.printCat() c4.printCat() c5.printCat() c1.changeColor(“Blue”) c3.changeColor(“Purple”) c1.printCat() c3.printCat() print(“=======================”) print(“Total number of cats:”, Cat.Number_of_cats) Output: Total number of cats: 0 ======================= White cat is sitting Black cat is sitting Brown cat is jumping Red cat is purring Grey cat is playing Blue cat is sitting Purple cat is jumping ======================= Total number of cats: 5Task 8 Write a Cylinder class to get the desired output as shown below. 1. You will have to create a Cylinder class. 2. You will have to create 2 class variables. 3. Create a required constructor. 4. Write 2 class methods: • One that takes the height first and then the radius and then swaps • One that takes a string where the radius and height values are separated with a hyphen. Write 2 static methods: • One that calculates the area of a whole cylinder (formula: 2πr2 + 2πrh) • Another that calculates the volume of a cylinder (formula: πr2h) **Observe the output values carefully to understand how the radius and height values are changing. [You are not allowed to change the code below] # Write your code herec1 = Cylinder(0,0) Cylinder.area(c1.radius,c1.height) Cylinder.volume(c1.radius,c1.height) print(“===============================”) c2 = Cylinder.swap(8,3) c2.area(c2.radius,c2.height) c2.volume(c2.radius,c2.height) print(“===============================”) c3 = Cylinder.changeFormat(“7-13”) c3.area(c3.radius,c3.height) c3.volume(c3.radius,c3.height) print(“===============================”) Cylinder(0.3,5.56).area(Cylinder.radius,Cylinder.height) print(“===============================”) Cylinder(3,5).volume(Cylinder.radius,Cylinder.height)) Output: Default radius=5 and height=18. Updated: radius=0 and height=0. Area: 0.0 Volume: 0.0 =============================== Default radius=0 and height=0. Updated: radius=3 and height=8. Area: 207.34511513692635 Volume: 226.1946710584651 =============================== Default radius=3 and height=8. Updated: radius=7.0 and height=13.0. Area: 879.645943005142 Volume: 2001.1945203366981 =============================== Default radius=7.0 and height=13.0. Updated: radius=0.3 and height=5.56. Area: 11.045839770021713 =============================== Default radius=0.3 and height=5.56. Updated: radius=3 and height=5. Volume: 141.3716694115407Task 9 Write the Student class so that the given code provides the expected output. 1. Create Student class 2. Create 3 class variable 3. Create 1 class method for object creation 4. Create 1 class method for printing [You are not allowed to change the code below] # Write your code hereStudent.printDetails() print(‘#########################’)mikasa = Student(‘Mikasa Ackerman’, “CSE”) mikasa.individualDetail() print(‘——————————————‘) Student.printDetails()print(‘========================’)harry = Student.createStudent(‘Harry Potter’, “Defence Against Dark harry.individualDetail() print(‘——————————————-‘) Student.printDetails()print(‘=========================’)levi = Student.createStudent(“Levi Ackerman”, “CSE”) levi.individualDetail() print(‘——————————————–‘) Student.printDetails() Output: Total Student(s): 0 Other Institution Student(s): 0 ################################ Name: Mikasa Ackerman Department: CSE —————————————————— Total Student(s): 1 Other Institution Student(s): 0 =============================== Name: Harry Potter Department: Defence Against Dark Arts —————————————————— Total Student(s): 2 Other Institution Student(s): 1 =============================== Name: Levi Ackerman Department: CSE —————————————————— Total Student(s): 3 Other Institution Student(s): 1Task 10 Write the SultansDine class so that the given code provides the expected output. [You are not allowed to change the code below] # Write your code hereSultansDine.details() print(‘########################’) dhanmodi = SultansDine(‘Dhanmondi’) dhanmodi.sellQuantity(25) dhanmodi.branchInformation() print(‘—————————————–‘) SultansDine.details()print(‘========================’)baily_road = SultansDine(‘Baily Road’) baily_road.sellQuantity(15) baily_road.branchInformation() print(‘—————————————–‘) SultansDine.details()print(‘========================’)gulshan = SultansDine(‘Gulshan’) gulshan.sellQuantity(9) gulshan.branchInformation() print(‘—————————————–‘) SultansDine.details() Output: Total Number of branch(s): 0 Total Sell: 0 Taka ################################# Branch Name: Dhanmondi Branch Sell: 10000 Taka —————————————– Total Number of branch(s): 1 Total Sell: 10000 Taka Branch Name: Dhanmondi, Branch Sell: 10000 Taka Branch consists of total sell’s: 100.00% ================================ Branch Name: Baily Road Branch Sell: 5250 Taka —————————————– Total Number of branch(s): 2 Total Sell: 15250 Taka Branch Name: Dhanmondi, Branch Sell: 10000 Taka Branch consists of total sell’s: 65.57% Branch Name: Baily Road, Branch Sell: 5250 Taka Branch consists of total sell’s: 34.43% ================================ Branch Name: Gulshan Branch Sell: 2700 Taka —————————————– Total Number of branch(s): 3 Total Sell: 17950 Taka Branch Name: Dhanmondi, Branch Sell: 10000 Taka Branch consists of total sell’s: 55.71% Branch Name: Baily Road, Branch Sell: 5250 Taka Branch consists of total sell’s: 29.25% Branch Name: Gulshan, Branch Sell: 2700 Taka Branch consists of total sell’s: 15.04% Subtaks: 1. Create SultansDine class 2. Create 2 class variable and 1 class list 3. Create 1 class method 4. Calculation of branch sell is given below a. If sellQuantity < 10: i. Branch_sell = quantity * 300 b. Else if sellQuantity < 20: i. Branch_sell = quantity * 350 c. Else i. Branch_sell = quantity * 400 5. Calculation of branch’s sell percentage = (branch’s sell / total sell) * 100
Course Title: Programming Language II Course Code: CSE 111 Lab Assignment no: 5#Write your code here#Do not change the following lines of code Sample Input 1: Quiz 1 (out of 10): 10 Quiz 2 (out of 10): 10 Lab (out of 30): 30 Mid (out of 20): 20 Final (out of 30): 30Sample Output 1:Sample Input 2: Quiz 1 (out of 10): 10 Quiz 2 (out of 10): 8 Lab (out of 30): 30 Mid (out of 20): 20 Final (out of 30): 29Sample Output 2:Design the program to get the output as shown. Subtasks: 1. You will need to create 2 classes: Teacher and Course 2. Make all the variables in the Teacher class private. 3. Make all the variables in the Course class public. 4. Write the required codes in the Teacher and Course classes.[You are not allowed to change the code below]# Write your code here for subtasks 1-4t1 = Teacher(“Saad Abdullah”, “CSE”) t2 = Teacher(“Mumit Khan”, “CSE”) t3 = Teacher(“Sadia Kazi”, “CSE”) c1 = Course(“CSE 110 Programming Language I”) c2 = Course(“CSE 111 Programming Language-II”) c3 = Course(“CSE 220 Data Structures”) c4 = Course(“CSE 221 Algorithms”) c5 = Course(“CCSE 230 Discrete Mathematics”) c6 = Course(“CSE 310 Object Oriented Programming”) c7 = Course(“CSE 320 Data Communications”) c8 = Course(“CSE 340 Computer Architecture”) t1.addCourse(c1) t1.addCourse(c2) t2.addCourse(c3) t2.addCourse(c4) t2.addCourse(c5) t3.addCourse(c6) t3.addCourse(c7) t3.addCourse(c8) t1.printDetail() t2.printDetail() t3.printDetail() Output: ==================================== Name: Saad Abdullah Department: CSE List of courses ==================================== CSE 110 Programming Language I CSE 111 Programming Language-II ==================================== ==================================== Name: Mumit Khan Department: CSE List of courses ==================================== CSE 220 Data Structures CSE 221 Algorithms CCSE 230 Discrete Mathematics ==================================== ==================================== Name: Sadia Kazi Department: CSE List of courses ==================================== CSE 310 Object Oriented Programming CSE 320 Data Communications CSE 340 Computer Architecture ====================================Design the program to get the output as shown. Subtasks: 1. You will need to create 2 classes: Team and Player 2. Make all the variables in the Team class private. 3. Make all the variables in the Player class public. 4. Write the required codes in the Team and Player classes Hints: • Create a list in team class to store the player’s name in that list • Use constructor overloading technique for Team class[You are not allowed to change the code below]# Write your code here for subtasks 1-4b = Team() b.setName(‘Bangladesh’) mashrafi = Player(“Mashrafi”) b.addPlayer(mashrafi) tamim = Player(“Tamim”) b.addPlayer(tamim) b.printDetail() a = Team(“Australia”) ponting = Player(“Ponting”) a.addPlayer(ponting) lee = Player(“Lee”) a.addPlayer(lee) a.printDetail() Output: ===================== Team: Bangladesh List of Players: [‘Mashrafi’, ‘Tamim’] ===================== ===================== Team: Australia List of Players: [‘Ponting’, ‘Lee’] =====================Look at the code and the sample inputs and outputs below to design the program accordingly. 1. Write a class called Color that only adds the 3 primary colors (red, blue and yellow). 2. Write a required constructor for the class. 3. You have to use operator overloading to get the desired outputs as shown.Hint:There will be only one constructor and only one method tackling the addition operation. No other methods are required. Note: Order of the color given as input should not matter. For example, in sample input 1, if the first input was yellow and then red, the output would still be orange.#Write your code here#Do not change the following lines of codeC1 = Color(input(“First Color: “).lower()) C2 = Color(input(“Second Color: “).lower()) C3 = C1 + C2 print(“Color formed:”, C3.clr) Sample Input 1: First Color: red Second Color: yellowSample Output 1: Color formed: OrangeSample Input 2: First Color: red Second Color: blueSample Output 2: Color formed: VioletSample Input 3: First Color: yellow Second Color: BLUESample Output 3: Color formed: GreenWrite a class called Circle with the required constructor and methods to get the following output. Subtasks: 1. Create a class called Circle. 2. Create the required constructor. Use Encapsulation to protect the variables. [Hint: Assign the variables in private] 3. Create getRadius() and setRadius() method to access variables. 4. Create a method called area to calculate the area of circles. 5. Handle the operator overloading by using a special method to calculate the radius and area of circle 3. [You are not allowed to change the code below] # Write your code here for subtasks 1-5c1 = Circle(4) print(“First circle radius:” , c1.getRadius()) print(“First circle area:” ,c1.area())c2 = Circle(5) print(“Second circle radius:” ,c2.getRadius()) print(“Second circle area:” ,c2.area())c3 = c1 + c2 print(“Third circle radius:” ,c3.getRadius()) print(“Third circle area:” ,c3.area())Output: First circle radius: 4 First circle area: 50.26548245743669 Second circle radius: 5 Second circle area: 78.53981633974483 Third circle radius: 9 Third circle area: 254.46900494077323Write a class called Triangle with the required constructor and methods to get the following output. Subtasks: 1. Create a class called Triangle. 2. Create the required constructor. Use Encapsulation to protect the variables. [Hint: Assign the variables in private] 3. Create getBase(), getHeight(), setBase and setHeight() method to access variables. 4. Create a method called area to calculate the area of triangles. 5. Handle the operator overloading by using a special method to calculate the radius and area of triangle 3. [You are not allowed to change the code below] # Write your code here for subtasks 1-5t1 = Triangle(10, 5) print(“First Triangle Base:” , t1.getBase()) print(“First Triangle Height:” , t1.getHeight()) print(“First Triangle area:” ,t1.area())t2 = Triangle(5, 3) print(“Second Triangle Base:” , t2.getBase()) print(“Second Triangle Height:” , t2.getHeight()) print(“Second Triangle area:” ,t2.area())t3 = t1 – t2 print(“Third Triangle Base:” , t3.getBase()) print(“Third Triangle Height:” , t3.getHeight()) print(“Third Triangle area:” ,t3.area()) Output: First Triangle Base: 10 First Triangle Height: 5 First Triangle area: 25.0 Second Triangle Base: 5 Second Triangle Height: 3 Second Triangle area: 7.5 Third Triangle Base: 5 Third Triangle Height: 2 Third Triangle area: 5.0Observe the given code carefully. Try to understand from the given code and the outputs what to write in your class Dolls. # Write your code hereobj_1 = Dolls(“Tweety”, 2500) print(obj_1.detail()) if obj_1 > obj_1: print(“Congratulations! You get the Tweety as a gift!”) else: print(“Thank you!”)print(“=========================”) obj_2 = Dolls(“Daffy Duck”, 1800) print(obj_2.detail()) if obj_2 > obj_1: print(“Congratulations! You get the Tweety as a gift!”) else: print(“Thank you!”)print(“=========================”) obj_3 = Dolls(“Bugs Bunny”, 3000) print(obj_3.detail()) if obj_3 > obj_1: print(“Congratulations! You get the Tweety as a gift!”) else: print(“Thank you!”)print(“=========================”) obj_4 = Dolls(“Porky Pig”, 1500) print(obj_4.detail()) if obj_4 > obj_1: print(“Congratulations! You get the Tweety as a gift!”) else: print(“Thank you!”)print(“=========================”) obj_5 = obj_2 + obj_3 print(obj_5.detail()) if obj_5 > obj_1: print(“Congratulations! You get the Tweety as a gift!”) else: print(“Thank you!”) Output: Doll: Tweety Total Price: 2500 taka Thank you! ========================= Doll: Daffy Duck Total Price: 1800 taka Thank you! ========================= Doll: Bugs Bunny Total Price: 3000 taka Congratulations! You get the Tweety as a gift! ========================= Doll: Porky Pig Total Price: 1500 taka Thank you! ========================= Dolls: Daffy Duck Bugs Bunny Total Price: 4800 taka Congratulations! You get the Tweety as a gift![You are not allowed to change the code above] Subtasks: 1. Create a Doll class. 2. Create the required constructor. 3. Write a method to print the name and the price of the object 4. Use operator overloading for the addition operators. 5. Write a method to handle operator overloading for the “>” logical operator that compares the price of the objects. Hints: ● Notice that the price of each object is being checked with the price of obj in the given code. ● Notice the word Doll in the first 4 outputs and the last output. You have to print exactly as represented here. Task 8 Design a class called Coordinates with an appropriate constructor. Then perform the subtraction, multiplication and equality check operations in the given code using operator overloading. #Write your code here#Do not change the following lines of codep1 = Coordinates(int(input()),int(input())) p2 = Coordinates(int(input()),int(input()))p4 = p1 – p2 print(p4.detail())p5 = p1 * p2 print(p5.detail())point_check = (p4 == p5) print(point_check) Sample Input 1: 1 2 3 4 Sample Output 1: (-2,-2) (3,8) The calculated coordinates are NOT the same. Sample Input 2: 0 0 0 0 Sample Output 2: (0,0) (0,0) The calculated coordinates are the same.
Course Title: Programming Language II Course Code: CSE 111 Lab Assignment no: 4Suppose your little sibling wants your help to check his math homework. He is done with his homework but wants you to see if all his results are correct. Since the student with all correct results gets 3 stars. However, you want your brother to check this on his own. So, you design a calculator for him in python. You could have given your scientific calculator but you wanted to give him a basic calculator and also wanted to see if you can even design one. Subtasks: 1. Create a class called Calculator. 2. Your class shall have 1 constructor and 4 methods, namely add, subtract, multiply and divide. 3. Now, create an object of your class. After creating an object, it should print “Let’s Calculate!” 4. Then take 3 inputs from the user: first value, operator, second value 5. Now based on the given operator, call the required method and print the result. Sample Input: 1 + 2 Sample Output: Let’s Calculate! Value 1: 1 Operator: + Value 2: 2 Result: 3Write a class called Customer with the required constructor and methods to get the following output.Subtasks: 1. Create a class called Customer. 2. Create the required constructor. 4. Create a method called purchase that can take as many arguments as the user wants to give.[You are not allowed to change the code below]# Write your codes for subtasks 1-4 here.customer_1 = Customer(“Sam”) customer_1.greet() customer_1.purchase(“chips”, “chocolate”, “orange juice”) print(“—————————–“) customer_2 = Customer(“David”) customer_2.greet(“David”) customer_2.purchase(“orange juice”) OUTPUT: Hello! Sam, you purchased 3 item(s): chips chocolate orange juice —————————– Hello David! David, you purchased 1 item(s): orange juiceThe Giant Panda Protection and Research Center in the Sichuan province of southwest China, actually employs a category of workers known as panda nannies. The primary responsibility is to play with adorable panda cubs and name them, determine gender, keep track of their age and hours they sleep. So being a programmer panda nanny, you will create a code that will do all these works for you.1. Create a class named Panda and also write the constructor. 2. Access the instance attributes and print them in the given format. 3. Call instance methods to keep track of their daily hours of sleep. 4. Suppose consulting with other panda nannies you have set some criteria based on which you will make their diet plans. The criteria are: ** Mixed Veggies for pandas having 3 to 5 hours (included) of sleep daily. ** Eggplant & Tofu for pandas having 6 to 8 hours (included) of sleep daily. ** Broccoli Chicken for pandas having 9 to 11 hours (included) of sleep daily. ** Lastly if no arguments are passed then just give it bamboo leaves. Now handle this problem modifying the method designed to keep track of their daily hours of sleep and determine diet plan using method overloading.[You are not allowed to change the code below]#Write your code here for subtasks 1-4.panda1 = Panda(“Kunfu”,”Male”, 5) panda2=Panda(“Pan Pan”,”Female”,3) panda3=Panda(“Ming Ming”,”Female”,8)print(“{} is a {} Panda Bear who is {} years old”.format(panda1.name,panda1.gender,panda1.age))print(“{} is a {} Panda Bear who is {} years old”.format(panda2.name,panda2.gender,panda2.age))print(“{} is a {} Panda Bear who is {} years old”.format(panda3.name,panda3.gender,panda3.age)) print(“===========================”) print(panda2.sleep(10)) print(panda1.sleep(4)) print(panda3.sleep()) OUTPUT: Kunfu is a Male Panda Bear who is 5 years old Pan Pan is a Female Panda Bear who is 3 years old Ming Ming is a Female Panda Bear who is 8 years old =========================== Pan Pan sleeps 10 hours daily and should have Broccoli Chicken Kunfu sleeps 4 hours daily and should have Mixed Veggies Ming Ming’s duration is unknown thus should have only bamboo leavesAnalyze the given code below to write Cat class to get the output as shown. Hints: • Remember, the constructor is a special method. Here, you have to deal with constructor overloading which is similar to method overloading. • Your class should have 2 variables [You are not allowed to change the code below]#Write your code herec1 = Cat() c2 = Cat(“Black”) c3 = Cat(“Brown”, “jumping”) c4 = Cat(“Red”, “purring”) c1.printCat() c2.printCat() c3.printCat() c4.printCat() c1.changeColor(“Blue”) c3.changeColor(“Purple”) c1.printCat() c3.printCat() OUTPUT White cat is sitting Black cat is sitting Brown cat is jumping Red cat is purring Blue cat is sitting Purple cat is jumpingQuestion 5 Implement the design of the Student class so that the following output is produced:Driver Code Output # Write your code here s1 = Student() s1.quizcalc(10) print(‘——————————–‘) s1.printdetail() s2 = Student(‘Harry’) s2.quizcalc(10,8) print(‘——————————–‘) s2.printdetail() s3 = Student(‘Hermione’) s3.quizcalc(10,9,10) print(‘——————————–‘) s3.printdetail() ——————————– Hello default student Your average quiz score is 3.3333333333333335 ——————————– Hello Harry Your average quiz score is 6.0 ——————————– Hello Hermione Your average quiz score is 9.666666666666666Design a “Vehicle” class. A vehicle assumes that the whole world is a 2-dimensional graph paper. It maintains its x and y coordinates (both are integers). Any new object created of the Vehicle class will always start at the coordinates (0,0). It must have methods to move up, down, left, right and a print_position() method for printing the current coordinate. Note: All moves are 1 step. That means a single call to any move method changes the value of either x or y or both by 1. [You are not allowed to change the code below]# Write your class herecar = Vehicle() car.print_position() car.moveUp() car.print_position() car.moveLeft() car.print_position() car.moveDown() car.print_position() car.moveRight() OUTPUT (0,0) (0,1) (-1,1) ( -1,0)Design the Programmer class such a way so that the following code provides the expected output.Hint: o Write the constructor with appropriate printing and multiple arguments. o Write the addExp() method with appropriate printing and argument. o Write the prinDetails() method[You are not allowed to change the code below]# Write your code here. p1 = Programmer(“Ethen Hunt”, “Java”, 10) p1.printDetails() print(‘————————–‘) p2 = Programmer(“James Bond”, “C++”, 7) p2.printDetails() print(‘————————–‘) p3 = Programmer(“Jon Snow”, “Python”, 4) p3.printDetails() p3.addExp(5) p3.printDetails() OUTPUT: Horray! A new programmer is born Name: Ethen Hunt Language: Java Experience: 10 years. ————————– Horray! A new programmer is born Name: James Bond Language: C++ Experience: 7 years. ————————– Horray! A new programmer is born Name: Jon Snow Language: Python Experience: 4 years. Updating experience of Jon Snow Name: Jon Snow Language: Python Experience: 9 years.Design the Student class such a way so that the following code provides the expected output. Hint: • Write the constructor with appropriate default value for arguments. • Write the dailyEffort() method with appropriate argument. • Write the prinDetails() method. For printing suggestions check the following instructions. ➢ If hour
Course Title: Programming Language II Course Code: CSE 111 Lab Assignment no: 1 String1. From a given string, print the string in all uppercase if the number of uppercase letters is more than lowercase letters. Otherwise, if lowercase is greater or equal to uppercase letters, print all lowercase. The inputs will contain letters (A-Z, a-z) only.Sample Input Sample Output HOusE HOUSE ApplE apple BaNaNa banana2. Given a string, print whether it is a number, word or mixed with digit and letters. If all the characters are numeric values, print NUMBER. If they are all letters, print WORD. If it is mixed, print MIXED.Sample Input Sample Output 213213 NUMBER jhg231j213 MIXED Hello WORD3. In a given string, there will be two uppercase letters in between some lowercase letters. Print the substring from the first uppercase letter to the last uppercase letter excluding them. If there are no letters in between them, print the word BLANK. It is guaranteed that there will be only two uppercase letters in the string.Sample Input Sample Output baNgladEsh glad coDIng BLANK 4. Write a Python program to find the first appearance of the substring ‘too’ and ‘good’ from a given string. If ‘good’ follows the ‘too’, replace the whole ‘too” good’ substring with ‘excellent’ and print the resulting string. If the above does not appear, print the string as it is.Sample Input The book is not too good! This book is good too!Sample Output The book is not excellent! This book is good too!5. Create a string from two given strings by concatenating common characters of the given strings.Sample Input Sample Output harry, hermione hrrhr dean, tom Nothing in common.6. Again, you have lost your USIS password!! You went to the registrar office and requested for a new password. This time, you need to follow some rules to set your password. Otherwise, they won’t change it. The rules are At least one lowercase letter At least one uppercase letter At least one digit (0-9) At least one special character (_ , $ , #, @)Your task is to find whether a given password follows all those rules. If it breaks any rule, you have to print Lowercase Missing, Uppercase Missing, Digit Missing or Special Missing respective to the missing case. For more than one rule break, print all the rules that were broken (order doesn’t matter). If the password is ok, print OK.Sample Input ohMyBR@CU ohmybracu OhMyBR@CU20Sample Output Digit missing Uppercase character missing, Digit missing, Special character missing OK List1. Write a python program which prints the frequency of the numbers that were given as input by the user. Stop taking input when you find the string “STOP”. Do not print the frequency of numbers that were not given as input.Sample Input 10 20 20 30 10 50 90 STOPSample Output 10 – 2 times 20 – 2 times 30 – 1 times 50 – 1 times 90 – 1 times2. Write a python program that calculates the sum of N given lists and prints the highest sum and its respective list. Input starts with N and followed by N lists.Sample Input 4 1 2 3 4 5 6 10 11 12 7 8 9Sample Output 33 [10, 11, 12]3. Write a python program that prints a list which contains cross multiplication between two given lists.Sample Input 2 3 6 3 4 5Sample Output [6, 8, 10, 9, 12, 15, 18, 24, 30]Sample Input Bracu1234 Sample Output acruB1324 4. Let there are N numbers in a list and that list is said to be a UB Jumper if the absolute values of the difference between the successive elements take on all the values 1 through N − 1. For example, 2 1 4 6 10 is a UB Jumper because the absolute differences between them are 1 3 2 4 which is all numbers from 1 to (5 – 1) or 4. Write a python program that takes a number sequence as input and prints whether it is a UB Jumper or Not UB Jumper. Input will stop after getting “STOP” as input. (Number order or absolute difference order doesn’t follow any sequence.)Sample Input1 4 2 3 2 1 4 6 10 1 4 2 -1 6 STOPSample OutputUB Jumper UB Jumper Not UB Jumper5. You are given a string that contains alphanumeric characters only. Your task is to sort the string in the following manner: a. All sorted lowercase letters are ahead of uppercase letters. b. All sorted uppercase letters are ahead of digits. c. All sorted odd digits are ahead of sorted even digits.6. BRACU has n students who are regular competitive programmers. According to the ACM ICPC rules, each person can participate in the regional championship at most 5 times.The head of the BRACU ACM Chapter is recently gathering teams to participate in this championship. Each team must consist of exactly three people, at that, any person cannot be a member of two or more teams. What maximum number of teams can the head make if he wants each team to participate in the world championship with the same members at least k times?The first line of input contains two integers, n and k. The next line contains n integers: y1, y2, …, yn (0 ≤ yi ≤ 5), where yi shows the number of times the i-th person participated in the ACM ICPC Regional .Write a python program that prints how many teams can be formed according to the above problem statement.Sample Input 15 2 0 4 5 1 0Sample Input 26 4 0 1 2 3 4 5Sample Input 36 5 0 0 0 0 0 0Sample Output 1 1Sample Output 2 0Sample Output 3 2Dictionary & Tuple1. Write a Python program to combine two dictionaries into one by adding values for common keys. Input contains two comma separated dictionaries. Print the new dictionary and create a tuple which contains unique values in sorted order.Sample Input a: 100, b: 100, c: 200, d: 300 a: 300, b: 200, d: 400, e: 200Sample Output {‘a’: 400, ‘b’: 300, ‘c’: 200,’d’: 700, ‘e’: 200} Values: (200, 300, 400, 700)2. Write a python program which prints the frequency of the numbers that were given as input by the user. Stop taking input when you find the string “STOP”. Do not print the frequency of numbers that were not given as input. Use a dictionary to solve the problemSample Input 10 20 20 30 10 50 90 STOPSample Output 10 – 2 times 20 – 2 times 30 – 1 times 50 – 1 times 90 – 1 times3. Write python code to invert a dictionary. It should print a dictionary where the keys are values from the input dictionary and the values are lists of keys from the input dictionary having the same value. Make sure the program handles multiple same values.Sample Input key1 : value1, key2 : value2, key3 : value1Sample Output { “value1” : [“key1”, “key3”], “value2” : [“key2”] }4. Two words are anagrams if they contain all of the same letters, but in a different order. For example, “evil” and “live” are anagrams because each contains one “e”, one “i”, one “l”, and one “v”. Write a program that reads two strings from the user and determines whether or not they are anagrams. Use a dictionary to solve the problem.Sample Input evil liveSample Output Those strings are anagrams.5. On some basic cell phones, text messages can be sent using the numeric keypad. Because each key has multiple letters associated with it, multiple key presses are needed for most letters. Pressing the number once generates the first character listed for that key. Pressing the number 2, 3, 4 or 5 times generates the second, third, fourth or fifth character. Key Symbols 1 .,?!: 2 ABC 3 DEF 4 GHI 5 JKL 6 MNO 7 PQRS 8 TUV 9 WXYZ 0 SpaceWrite a program that displays the key presses needed for a message entered by the user. Construct a dictionary that maps from each letter or symbol to the key presses needed to generate it. Then use the dictionary to create and display the presses needed for the user’s message.Sample Input Hello, World! Sample Output 4433555555666110966677755531111
Course Title: Programming Language II Course Code: CSE 111 Lab Assignment no: 3Question 1Write a class that for running the following codes: [You are not allowed to change the code below]#Write your class code here data_type1 = DataType(‘Integer’, 1234) print(data_type1.name) print(data_type1.value) print(‘=====================’) data_type2 = DataType(‘String’, ‘Hello’) print(data_type2.name) print(data_type2.value) print(‘=====================’) data_type3 = DataType(‘Float’, 4.0) print(data_type3.name) print(data_type3.value)Output:Integer 1234 ===================== String Hello ===================== Float 4.0Subtasks:1. Create a class named DataType with the required constructor. 2. Assign name and values in constructor according to the output.Question 2Design a class called Flower with the instance variables so that after executing the following line of code the desired result shown in the output box will be printed. [You are not allowed to change the code below]#Write your class code here flower1 = Flower() flower1.name=”Rose” flower1.color=”Red” flower1.num_of_petal=6 print(“Name of this flower:”, flower1.name) print(“Color of this flower:”,flower1.color) print(“Number of petal:”,flower1.num_of_petal) print(“=====================”) flower2 = Flower() flower2.name=”Orchid” flower2.color=”Purple” flower2.num_of_petal=4 print(“Name of this flower:”,flower2.name) print(“Color of this flower:”,flower2.color) print (“Number of petal:”,flower2. num_of_petal) #Write the code for subtask 2 and 3 hereOutput:Name of this flower: Rose Color of this flower: Red Number of petal: 6 ===================== Name of this flower: Orchid Color of this flower: Purple Number of petal: 4Subtask: 1) Design the class Flower with default constructor to get the above output. 2) At the end of the given code, also print the address of flower1 and flower2 objects. 3) Do they point to the same address? Print (‘they are same’ or ‘they are different’) at the very end to answer this question.Question 3A class has been designed for this question. Solve the questions to get the desired result as shown in the output box. [You are not allowed to change the code below]class Wadiya(): def __init__(self): self.name = ‘Aladeen’ self.designation = ‘President Prime Minister Admiral General’ self.num_of_wife = 100 self.dictator = True#Write your code for subtask 1, 2, 3 and 4 hereOutput:Part 1: Name of President: Aladeen Designation: President Prime Minister Admiral General Number of wife: 100 Is he/she a dictator: True Part 2: Name of President: Donald Trump Designation: President Number of wife: 1 Is he/she a dictator: FalseSubtask: 1) Create an object named wadiya. 2) Use the object to print the values as shown in part 1 (Also print the sentence Part 1) 3) Use the same object to change and print the values in part 2 (Also print the sentence Part 2) 4) Did changing the instance variable values using the same object, affect the previous values of Part 1? (Print ‘previous information lost’ or ‘No, changing had no effect on previous value’)Question 4Design a class Joker with parameterized constructor so that the following line of code prints the result shown in the output box. [You are not allowed to change the code below]#Write your class code herej1 = Joker(‘Heath Ledger’, ‘Mind Game’, False) print(j1.name) print(j1.power) print(j1.is_he_psycho) print(“=====================”) j2 = Joker(‘Joaquin Phoenix’, ‘Laughing out Loud’, True) print(j2.name) print(j2.power) print(j2.is_he_psycho) print(“=====================”) if j1 == j2: print(‘same’) else: print(‘different’) j2.name = ‘Heath Ledger’ if j1.name == j2.name: print(‘same’) else: print(‘different’) #Write your code for 2,3 hereOutput:Heath Ledger Mind Game False ===================== Joaquin Phoenix Laughing out Loud True ===================== different sameSubtask: 1) Design the class using a parameterized constructor. 2) The first if/else block prints the output as ‘different’, but why? Explain your answer and print your explanation at the very end. 3) The second if/else block prints the output as ‘same’, but why? Explain your answer and print your explanation at the very end.Question 5Design a class called Pokemon using a parameterized constructor so that after executing the following line of code the desired result shown in the output box will be printed. First object along with print has been done for you, you also need to create other objects and print accordingly to get the output correctly. [You are not allowed to change the code below]#Write your code for class hereteam_pika = Pokemon(‘pikachu’, ‘charmander’, 90, 60, 10) print(‘=======Team 1=======’) print(‘Pokemon 1:’,team_pika.pokemon1_name, team_pika.pokemon1_power) print(‘Pokemon 2:’,team_pika.pokemon2_name, team_pika.pokemon2_power) pika_combined_power = (team_pika.pokemon1_power + team_pika.pokemon2_power) * team_pika.damage_rate print(‘Combined Power:’, pika_combined_power) #Write your code for subtask 2,3,4 hereOutput:=======Team 1======= Pokemon 1: pikachu 90 Pokemon 2: charmander 60 Combined Power: 1500 =======Team 2======= Pokemon 1: bulbasaur 80 Pokemon 2: squirtle 70 Combined Power: 1350Subtask:1) Design the Pokemon class using a parameterized constructor. The 5 values that are being passed through the constructor are pokemon 1 name, pokemon 2 name, pokemon 1 power, pokemon 2 power, damage rate respectively. After designing the class, if you run the above code the details in Team 1 will be printed. 2) Create an object named team_bulb and pass the value ‘bulbasaur’, ‘squirtle’, 80, 70, 9 respectively. 3) Use print statements accordingly to print the desired result of Team 2.Note: Power is always being calculated using the instance variables. Example: (team_pika.pokemon1_power + team_pika.pokemon2_power) * team_pika.damage_rateQuestion 6Design the Player class so that the code gives the expected output. [You are not allowed to change the code below]# Write Your Class Code Here player1 = Player() player1.name = “Ronaldo” player1.jersy_number = 9 player1.position = “Striker” print(“Name of the Player:”, player1.name) print(“Jersey Number of player:”, player1.jersy_number) print(“Position of player:”, player1.position) print(“===========================”) player2 = Player() player2.name = “Neuer” player2.jersy_number = 1 player2.position = “Goal Keeper” print(“Name of the player:”, player2.name) print(“Jersey Number of player:”, player2.jersy_number) print(“Position of player:”, player2.position)Output:Name of the Player: Ronaldo Jersy Number of player: 9 Position of player: Striker =========================== Name of the player: Neuer Jersy Number of player: 1 Position of player: Goal Keeper Question 7Design the Country class so that the code gives the expected output. [You are not allowed to change the code below]# Write your Class Code here country = Country() print(‘Name:’,country.name) print(‘Continent:’,country.continent) print(‘Capital:’,country.capital) print(‘Fifa Ranking:’,country.fifa_ranking) print(‘===================’) country.name = “Belgium” country.continent = “Europe” country.capital = “Brussels” country.fifa_ranking = 1 print(‘Name:’,country.name) print(‘Continent:’,country.continent) print(‘Capital:’,country.capital) print(‘Fifa Ranking:’,country.fifa_ranking)Output:Name: Bangladesh Continent: Asia Capital: Dhaka Fifa Ranking: 187 =================== Name: Belgium Continent: Europe Capital: Brussels Fifa Ranking: 1Question 8Write the DemonSlayer class so that the code gives the expected output. [You are not allowed to change the code below]# Write your Class Code here tanjiro = DemonSlayer(“Tanjiro”, “Water Breathing”, 10, 10) print(‘Name:’,tanjiro.name) print(‘Fighting Style:’,tanjiro.style) print(f’Knows {tanjiro.number_of_technique} technique(s) and has killed {tanjiro.kill} demon(s)’) print(‘===================’) zenitsu = DemonSlayer(“Zenitsu”, “Thunder Breathing”, 1, 4) print(‘Name:’,zenitsu.name) print(‘Fighting Style:’,zenitsu.style) print(f’Knows {zenitsu.number_of_technique} technique(s) and has killed {zenitsu.kill} demon(s)’) print(‘===================’) inosuke = DemonSlayer(“Inosuke”, “Beast Breathing”, 5, 7) print(‘Name:’,inosuke.name) print(‘Fighting Style:’,inosuke.style) print(f’Knows {inosuke.number_of_technique} technique(s) and has killed {inosuke.kill} demon(s)’) print(‘===================’) print(f'{tanjiro.name}, {zenitsu.name}, {inosuke.name} knows total {tanjiro.number_of_technique + zenitsu.number_of_technique + inosuke.number_of_technique} techniques’) print(f’They have killed total {tanjiro.kill + zenitsu.kill + inosuke.kill} demons’)Output:Name: Tanjiro Fighting Style: Water Breathing Knows 10 technique(s) and has killed 10 demon(s) =================== Name: Zenitsu Fighting Style: Thunder Breathing Knows 1 technique(s) and has killed 4 demon(s) =================== Name: Inosuke Fighting Style: Beast Breathing Knows 5 technique(s) and has killed 7 demon(s) =================== Tanjiro, Zenitsu, Inosuke knows total 16 techniques They have killed total 21 demonsQuestion 9Write the box class so that the code gives the expected output.#Write your class code hereprint(“Box 1”) b1 = box([10,10,10]) print(“=========================”) print(“Height:”, b1.height) print(“Width:”, b1.width) print(“Breadth:”, b1.breadth) print(“————————-“) print(“Box 2”) b2 = box((30,10,10)) print(“=========================”) print(“Height:”, b2.height) print(“Width:”, b2.width) print(“Breadth:”, b2.breadth) b2.height = 300 print(“Updating Box 2!”) print(“Height:”, b2.height) print(“Width:”, b2.width) print(“Breadth:”, b2.breadth) print(“————————-“) print(“Box 3”) b3 = b2 print(“Height:”, b3.height) print(“Width:”, b3.width) print(“Breadth:”, b3.breadth) Output: Box 1 Creating a Box! Volume of the box is 1000 cubic units. ========================= Height: 10 Width: 10 Breadth: 10 ——————————————— Box 2 Creating a Box! Volume of the box is 3000 cubic units. ========================= Height: 30 Width: 10 Breadth: 10 Updating Box 2! Height: 300 Width: 10 Breadth: 10 ——————————————— Box 3 Height: 300 Width: 10 Breadth: 10Question 10Design the required class from the given code and the outputs. [You are not allowed to change the code below]Hint: Number of the border characters for the top and the bottom = 1 + Number of spaces between the left side border and the first character of the button name + Length of the button name + Number of spaces between the right side border and the last character of the button name + 1NOTE: Don’t count the space or any character from the button representation to solve this problem.#Write your class code hereword = “CANCEL” spaces = 10 border = ‘x’ b1 = buttons(word, spaces, border) print(“=======================================================”) b2 = buttons(“Notify”,3, ‘!’) print(“=======================================================”) b3 = buttons(‘SAVE PROGRESS’, 5, ‘$’)Output:CANCEL Button Specifications: Button name: CANCEL Number of the border characters for the top and the bottom: 28 Number of spaces between the left side border and the first character of the button name: 10 Number of spaces between the right side border and the last character of the button name: 10 Characters representing the borders: xxxxxxxxxxxxxxxxxxxxxxxxxxxxx x CANCEL x xxxxxxxxxxxxxxxxxxxxxxxxxxxx ========================================================= Notify Button Specifications: Button name: Notify Number of the border characters for the top and the bottom: 14 Number of spaces between the left side border and the first character of the button name: 3 Number of spaces between the right side border and the last character of the button name: 3 Characters representing the borders: !!!!!!!!!!!!!!! ! Notify ! !!!!!!!!!!!!!! ========================================================= SAVE PROGRESS Button Specifications: Button name: SAVE PROGRESS Number of the border characters for the top and the bottom: 25 Number of spaces between the left side border and the first character of the button name: 5 Number of spaces between the right side border and the last character of the button name: 5 Characters representing the borders: $$$$$$$$$$$$$$$$$$$$$$$$$$ $ SAVE PROGRESS $ $$$$$$$$$$$$$$$$$$$$$$$$$
• Online submission: You must submit your solutions online on the course Gradescope site (you can find a link on the course Brightspace site). You need to submit (1) a PDF that contains the solutions to all questions to the Gradescope HW4 Paperwork assignment (including the questions asked in the programming problems), (2) x.py or x.ipynb files for the programming questions to the Gradescope HW4 Code Files assignment. We recommend that you type the solution (e.g., using LATEX or Word), but we will accept scanned/pictured solutions as well (clarity matters). • Generative AI Policy: You are free to use any generative AI, but you are required to document the usage: which AI do you use, and what’s the query to the AI. You are responsible for checking the correctness. Before you start: this homework only has programming problems. You should still have all questions answered in the write-up pdf. Also note that some sub-problems are still essentially math problems and you need to show detailed derivations. Problems 1 and 2 are two parts of one problem, so we suggest you read the description of both problems in tandem. This homework could be challenging and hope the following tips help: • Understanding of the gradient boosting tree concept. In particular, we use every single tree to compute a “gradient step”, and the sum of the gradient steps gives us the final predictions. • Understanding of the python notebook we provide. The code we provide aims to share implementations between the random forests and the GBDTs. Try to think about how different parts of the code could be re-utilized by the two models. • Debugging your code: always try to debug a small case. For example, use very few data points and build a tree with a depth of 2 or 3. Then, you can look at all the decision rules and data point assignments and check if they are reasonable. 1 Programming Problem: Random Forests [40 points] Random forests (RF) build an ensemble of trees independently. It uses bootstrap sampling (sampling with replacement, as discussed in class) to randomly generate B datasets from the original training dataset, each with the same size as the original one but might contain some duplicated (or missing) samples. Each sample has a multiplicity which is greater than or equal to zero. In your python implementation, you can use numpy.random.choice for the sampling procedure. . (1) The optimization problem for training each tree in RF is , (2) where ˆyi is the prediction produced by tree-b fb(·;θb) for data point xi, ℓ(·,·) is a loss function (detailed in Problem 2.5.3), and Ω(θb) is a regularizer applied to the parameters θb of model-b (that is, Ω(θb) measures the complexity of model-k). Most descriptions of ensemble learning in Problem 2.1 of the homework (below) can be also applied to RF, such as the definitions of fk(·;θk) and θk, except Eq. (3) and Eq. (4). Different methods can be used to find the decision rule on each node during the optimization of a single tree. A core difference between random forests and GBDTs (which we will describe in Problem 2) is the tree growing methods. Specifically, in the case of GBDT, we use the standard greedy tree-splitting algorithm; in the case of random forests, we greedily learn each tree using a bootstrapped data sample and random feature selection as described in class. That is, the key difference is the data that is being used (always original data in the case of GBDT or bootstrap sample for each tree in the case of RFs), and in the case of RFs we choose a random subset of features each time we grow a node. The underlying algorithm, however, is very similar. Therefore, to facilitate code reuse between this and the next problem, and also to make more fair the comparison between RFs and GBDTs, we ask you to use the same code base between this and the next problem (detailed in Problem 2.4 below). Each tree in the RF method is like the first tree in GBDT, as the RF method does not consider any previously produced trees when it grows a new tree (the trees are independent with RFs). With RFs, we simply start with ˆyi0. You need to notice this fact when re-using the code from GBDT, because Gj and Hj for tree-k in RF only depend on ˆyi0, not ˆ . Instructions 2-5 in Problem 2.5, however, can still be applied to RF tree building here. In this problem, you will implement RFs for both regression and binary classification problems. Please read Problem 2.1, 2.4, and 2.5 below before you start. 1. [20 points] Implement RF for regression task, and test its performance on Boston house price dataset used in Homework 2. Report the training and test RMSE. How is the performance of RF compared to least square regression and ridge regression? 2. [20 points] Implement RF for binary classification task, and test its performance on Credit-g dataset. It is a dataset classifying people described by 20 attributes as good or bad credit risks. The full description of the attributes can be found at https://www.openml.org/d/31. Report the training and test accuracy. Try your implementation on breast cancer diagnostic dataset , and report the training and test accuracy. 2 Programming Problem: Gradient Boosting Decision Trees [60 points] 2.1 Problem of Ensemble Learning in GBDTs Gradient Boosting Decision Trees (GBDT) is a class of methods that use an ensemble of K models (decision trees) . It produces predictions by adding together the outputs of the K models as follows: . (3) The resulting ˆy can be used for the predicted response for regression problems, or can correspond to the class logits (i.e., the inputs to a logistic or softmax function to generate class probabilities) when used for classification problems. The optimization problem for training an ensemble of models is , (4) where θk is the parameters for the kth model, and where ˆyi is the prediction produced by GBDT for data point xi, ℓ(·,·) is a loss function (detailed definition of losses are given in Problem 2.5.3), and Ω(θk) is a regularizer applied to the parameters θk of model-k (that is, Ω(θk) measures the complexity of model-k). , (5) Therefore, to define a tree fk(·), we need to determine the structure of the tree T ≜ (Nk ∪ Lk,E) (E is the set of tree edges), the feature dimension pj and threshold τj associated with each non-leaf node j ∈ Nk,Figure 1: An example of GBDT: Does the person like computer games? and the weight associated with each leaf node j ∈ Lk. These comprise the learnable parameters θk of fk(·;θk), i.e., . (6) To define an ensemble of multiple trees, we also need to know the number of trees K. We cannot directly apply gradient descent to learn the above parameters of GBDT because: (1) some of the above variables are discrete and some could have an exponential number of choices, including for example, the number of trees, the structure of each tree, the feature dimension choice associated with each non-leaf node, the weights at the leaf nodes; and 2) the overall decision tree process is not differentiable meaning straightforward naive gradient descent seems inapplicable. 2.2 Overview of the GBDT algorithm The basic idea of GBDT training is additive training, or boosting. As mentioned above, Boosting is a metaalgorithm that trains multiple models one after another, and in the end combines additively to produce a prediction. Boosting often aims to convert multiple weak learners (which might be only slightly better than a random guess) into a strong learner that can achieve error arbitrarily close to zero. Boosting has many forms and instantiations, including AdaBoost [6], random forests [5, 2], gradient boosting [3, 4], etc. Note that Bagging [1] is not boosting since there is no interdependence between the trainings of the different models, rather each model in Bagging is trained on a separate bootstrap data sample. GBDT training shares ideas similar to coordinate descent in that only one part of the model is optimized at a time, while the other parts are fixed. In the coordinate descent algorithm (you implemented it for Lasso), each outer loop iteration requires one pass of all the feature dimensions. In each iteration of its inner loop, it starts from the first dimension, and optimizes only one dimension of the weight vector by fixing all the other dimensions and conditioning on all the other dimensions. Each tree in GBDT is analogous to a dimension in coordinate descent, but the optimization process is different. GBDT starts from the first tree, and optimizes only one tree per time by fixing all the previous trees and we condition on all the previously produced trees. One core difference GBDT training has from coordinate descent is that GBDT training does not have the outer loop associated with coordinate descent, i.e., it only does one pass over all the trees. If it was coordinate descent, we would optimize each coordinate only once in succession. In particular, we start from one tree, and only optimize one tree at a time conditioned on all previously produced trees. This, therefore, is a greedy strategy as we spoke about in class. After the training of one tree finished, we add this new tree to our growing ensemble and then repeat the above process. The algorithm stops when we have added tmax trees to the ensemble. In the optimization of each tree, we start from a root node, find the best decision rule (a feature dimension and a threshold) and split the node into two children, go to each of the children, and recursively find the best decision rule on each of the child nodes, and continue until some stopping criterion is fulfilled (as will be explained very shortly below). In the following, we will first elaborate how to add trees one after the other, and then provide details regarding how to optimize a single tree based on a set of previous trees (which might be empty, and so this also explains how to start with the first tree). 2.3 Growing the forest: How to add a new tree? Assume that there will be K trees in the end. Therefore, we will get a sequence of (partially) aggregated predictions , from the K trees as follows: yˆi0 = 0, , According to Eq. (4), fixing all the previous k − 1 trees, the objective used to optimize tree-k is , (7) Let’s simplify the first term using Taylor’s expansion, ignoring higher-order terms: . (8) After applying Taylor’s expansion to ℓ(yi,yˆik−1 + fk(xi)), we have , (9) where gi and hi denote the first-order and second-order derivatives of ℓ(yi,yˆik−1) w.r.t. ˆyik−1, i.e., . (10) The second term Ω(θk) in Eq. (7) is a regularization term aiming to penalize the degree of complexity of tree-k. It depends on the number of leaf nodes, and the L2 regularization of wk. With GBDTs, it is defined as: . (11) We plugin Eq. (9) and Eq. (11) into Eq. (7), and after ignoring constants, we get Fk(θk) + const. , (12) 2.4 Growing a tree: How to optimize a single tree? Now we can start to optimize a single tree fk(·;θk). Look at the objective function in Eq. (12): it is a sum of |Lk| independent simple scalar quadratic functions of wjk for all the j ∈ Lk! How to minimize a quadratic function? This we know is easy, and similar to least square regression, the solution has a nice closed form. Hence, wjk minimizing Fk(θk) is . (13) We can plug the above optimal wjk into Eq. (12) and obtain an updated objective (14) However, there are still two groups of unknown parameters in θk, which are the tree structure T and the decision rules {(pj,τj)}j∈Nk. In the following, we will elaborate how to learn these parameters by additive training of a single tree. We will start from the root node and determine the associated decision rule (pj,τj); this rule should minimize the updated objective in Eq. (14), where Lk contains the left and right child of the root node. Then, the same process of determining (pj,τj) will be recursively applied to the left and right nodes, until a stopping criteria (as described below) is fulfilled. For each candidate decision rule (pj,τj), we can compute the improvement it brings to the objective Eq. (14). Before splitting node j to a left child j(L) and a right child j(R), the objective is (15) After splitting, the leaf nodes change to j(L) and j(R), and the objective becomesHence, the improvement (we usually call it the “gain”) is (17) (18) (19) Therefore, the best decision rule (pj,τj) on node j ∈ Nk is the one (out of the m × n possible rules) maximizing the gain, which corresponds to the decision rule that minimizes the updated objective in Eq. (14). That is, we wish to perform the following optimization: (20) We start from the root node, apply the above criterion to find the best decision rule, split the root into two child nodes, and recursively apply the above criterion to find the decision rules on the child nodes, the grandchildren, and so on. We stop splitting according to a stopping criterion is satisfied. In particular, we stop to split a node if either of the following events happens: 1. the tree has reached a maximal depth dmax; 2. the improvement achieved by the best decision rule for the node (Eq. (20)) goes negative (or is still positive but falls below a small positive threshold, in the following experiments, you can try this, but please report results based on the “goes negative” criterion); 2.5 Details of Practical Implementation 1. Learning rate η: You might notice that the tree growing in GBDT is a greedy process. In practice, to avoid overfitting on a single tree, and to give more chances to new trees, we will make the process less greedy. In particular, we usually assign a weight 0 ≤ η ≤ 1 to each newly added tree when aggregating its output with the outputs of previously added trees. Hence, the sequence at the beginning of Problem 2.3 becomes yˆi0 = 0, yˆi1 = ηf1(xi) = yˆi0 + ηf1(xi), yˆi2 = ηf1(xi) + ηf2(xi) = yˆi1 + ηf2(xi), ··· k yˆik = η X fk′(xi) = yˆik−1 + ηfk(xi), k′=1 ··· K yˆiK = η Xfk(xi) = yˆiK−1 + ηfK(xi). k=1 Note that this change must be applied in both training and during testing/inference. 0 ≤ η ≤ 1 is usually called the “learning rate” of GBDT, but it is not exactly the same as the variable we usually call the learning rate in gradient descent. 2. Initial prediction yˆi0: GBDT does not have bias term b like linear model y = wx+b. Fortunately, ˆyi0 plays a similar role as b. Hence, instead of starting from ˆyi0 = 0, we start from ˆ , i.e., the average of ground truth on the training set. For classification, it is also fine to use this initialization (the average of lots of 1s and 0s), but do not forget to transfer the data type of label from “int” to “float” when computing the average in this case. 3. Choices of loss function ℓ(·,·): ℓ(·,·) is a sample-wise loss. In the experiments, you should use least square loss ℓ(y,yˆ) = (y−yˆ)2 for regression problems. For binary classification problems, we use one-hot (0/1) encoding of labels y (y is either 0 or 1), and logistic regression (the GBDT output ˆy is the logit in this case, which is a real number and the input to logistic function producing class probability), i.e., ℓ(y,yˆ) = y log(1 + exp(−yˆ)) + (1 − y)log(1 + exp(ˆy)). (21) The prediction of binary logistic regression, which is the class probabilities, is Pr( , Pr(class = 0) = 1 − Pr(class = 1). (22) To produce a one-hot (0/1) prediction, we apply a threshold of 0.5 to the probability, i.e., 1, Pr(class = 1) > 0.5 (23) 0, Pr(class = 1) ≤ 0.5 4. Hyper-parameters: There are six hyper-parameters in GBDT, i.e., λ and γ in regularization Ω(·), dmax and nmin in stopping criterion for optimizing single tree, maximal number of trees tmax in stopping criterion for growing forests, and learning rate η. We will not give you exact values for these hyper-parameters, since tuning them is an important skill in machine learning. Instead, we will give you ranges of them for you to tune. Note larger dmax and tmax require more computations. Their ranges are: λ ∈ [0,10], γ ∈ [0,1], dmax ∈ [2,10], nmin ∈ [1,50], tmax ∈ [5,50], η ∈ [0.1,1.0]. In RFs, we do not have the learning rate, but there is another hyper-parameter, which is the size m′ of the random subset of features, from which you need to find the best feature and the associated decision rule for a node. You can use m′ ∈ [0.2m,0.5m]. 5. Stopping criteria: There are two types of stopping criteria needed to be used in GBDT/RFs training: 1) we stop to add new trees once we get tmax trees; and 2) we stop to grow a single tree once either of the three criteria given at the end of Problem 2.4 fulfills. 6. Acceleration: We encourage you to apply different acceleration methods after you make sure the code works correctly. You can use multiprocessing for acceleration, and it is effective. However, do not increase the number of threads to be too large. It will make it even slower. You can also try numba (a python compiler) with care. 2.6 Questions 1. [4 points] What is the computational complexity of optimizing a tree of depth d in terms of m and n? 2. [4 points] What operation requires the most expensive computation in GBDT training? Can you suggest a method to improve the efficiency (please do not suggest parallel or distributed computing here since we will discuss it in the next question)? Please give a short description of your method. 3. [8 points] Which parts of GBDT training can be computed in parallel? Briefly describe your solution, and use it in your implementation. (Hint: you might need to use “from multiprocessing import Pool” and “from functools import partial”. We also talked about multiprocessing in the recitation session.) 4. [20 points] Implement GBDT for the regression task, and test its performance on Boston house price dataset used in Homework 2. Report the training and test RMSE. How is the performance of GBDT compared to least square regression and ridge regression? 5. [20 points] Implement GBDT for the binary classification task, and test its performance on Creditg dataset. Report the training and test accuracy. Try your implementation on the breast cancer diagnostic dataset, and report the training and test accuracy. 6. [4 points] According to the results on the three experiments, how is the performance of random forests compared to GBDT? Can you give some explanations? References [1] Leo Breiman. Bagging predictors. Machine Learning, 24(2):123–140, 1996. [2] Leo Breiman. Random forests. Machine Learning, 45(1):5–32, 2001. [3] Jerome H. Friedman. Stochastic gradient boosting. Computational Statistics and Data Analysis, 38:367– 378, 1999. [4] Jerome H. Friedman. Greedy function approximation: A gradient boosting machine. Annals of Statistics, 29:1189–1232, 2000. [5] Tin Kam Ho. Random decision forests. In Proceedings of 3rd International Conference on Document Analysis and Recognition, volume 1, pages 278–282, 1995. [6] Robert E. Schapire. The strength of weak learnability. Machine Learning, 5(2):197–227, 1990.
• Online submission: You must submit your solutions online on the course Gradescope site (you can find a link on the course Brightspace site). You need to submit (1) a PDF that contains the solutions to all questions to the Gradescope HW3 PaperWork assignment (including the questions asked in the programming problems), (2) x.py or x.ipynb files for the programming questions to the Gradescope HW3 CodeFiles assignment. We recommend that you type the solution (e.g., using LATEX or Word), but we will accept scanned/pictured solutions as well (clarity matters). • Generative AI Policy: You are free to use any generative AI, but you are required to document the usage: which AI do you use, and what’s the query. You are responsible for checking the correctness. Before you start: this homework only has programming problems. You should still have all questions answered in the write-up pdf. Also note that some sub-problems are still essentially math problems and you need to show detailed derivations. 1 Programming Problem: Logistic Regression [40 points] In this problem, you will implement the gradient descent algorithm and mini-batch stochastic gradient descent algorithm for multi-class logistic regression from scratch (which means that you cannot use builtin logistic regression modules in scikit-learn or any other packages). Then you will be asked to try your implementation on a hand-written digits dataset to recognize the hand-written digits in given images. We provide an ipython notebook “logistic regression digits.ipynb” for you to complete. You need to complete the scripts below “TODO” (please search for every “TODO”), and submit the completed ipynb file. In your write-up, you also need to include the plots and answers to the questions required in this session. In this problem, you will implement a logistic regression model for multi-class classification. Given features of a sample x, a multi-class logistic regression produces class probability (i.e., the probability of the sample belonging to class k) Pr( (1) where c is the number of all possible classes, model parameter W is a d × c matrix and b is a c-dim vector, and we call the c values in z = xW +b as the c logits associated with the c classes. Binary logistic regression model (c = 2) is a special case of the above multi-class logistic regression model (you can figure out why by yourself with a few derivations). The predicted class ˆy of x is yˆ = arg max Pr(y = k|x;W,b). (2) k=1,2,···,c For simplicity of implementation, we can extend each x by adding an extra dimension with value 1, i.e., x ← [x,1], and accordingly add an extra row to W, i.e, W ← [W;b]. After using the extended representation of x and W, the logits z become z = xW. Logistic regression solves the following optimization for maximum likelihood estimation. minF(W) wherelog[Pr(, (3) W where we use a regularization similar to the ℓ2-norm in ridge regression, i.e., the Frobenius norm ∥W∥2F = . Note that W·,j is the jth column of W. 1. [15 points] Derive the gradient of F(W) w.r.t. W, i.e., ∇WF(W), and write down the gradient descent rule for W. Hint: compute the gradient w.r.t. to each Wj for every class j first. 2. [10 points] Below “2 batch gradient descent (GD) for Logistic regression”, implement the batch gradient descent algorithm with a constant learning rate. To avoid numerical problems when computing the exponential in the probability Pr(y = k|x;W,b), you can use a modification of the logits z′, i.e., z′ = z − maxzj. (4) j Explain why such a modification could avoid potential numerical problems and show that the overall result is unchanged by applying such a trick. When the change of objective F(W) comparing to F(W) in the previous iteration is less than ϵ = 1.0e − 4, i.e., |Ft(W) − Ft−1(W)| ≤ ϵ, stop the algorithm. Please record the value of F(W) after each iteration of gradient descent. Please run the implemented algorithm to train a logistic regression model on the randomly split training set. We recommend to use η = 0.1. Try three different learning rates [5.0e − 3,1.0e − 2,5.0e − 2], report the final value of F(W) and training/test accuracy in these three cases, and draw the three convergence curves (i.e., Ft(W) vs. iteration t) in a 2D plot. 3. [5 points] Compare the convergence curves: what is the advantages and disadvantages of large and small learning rates? 4. [5 points] Below “4 stochastic gradient descent (SGD) for Logistic regression”, implement the minibatch stochastic gradient descent (SGD) for logistic regression. You can reuse some code from the previous gradient descent implementation. You can start by using an initial learning rate of 1.0e−2 and a mini-batch size of 100 for this problem. You can discard the last mini-batch of every epoch if it is not full. Please remember to record the value of F(W) after each epoch and the final training and test accuracy. Run your code for different mini-batch sizes: [10, 50, 100]. Report the final value of F(W) and final training/test accuracy, and draw the three convergence curves (Ft(W) vs. epoch t) in a 2D plot. 2 Programming Problem: Lasso [60 points] You need to complete everything below each of the “TODO”s that you find (please search for every “TODO”). Once you have done that, please submit the completed ipynb file as part of your included .zip file. In your write-up, you also need to include the plots and answers to the questions required in this session. Please include the plots and answers in the pdf file in your solution. Recall that for lasso, we aim to solve: argminθ,θ0F(θ,θ0) where . (5) Remarks: Do not include θ0 in the computation of precision/recall/sparsity. However, do not forget to include it when you compute the prediction produced by the lasso model, because it is one part of the model. 1. [15 points] Implement the coordinate descent algorithm to solve the lasso problem in the notebook. We provide a function “DataGenerator” to generate synthetic data in the notebook. Please read the details of the function to understand how the data are generated. In this problem, you need to use n = 50,m = 75,σ = 1.0,θ0 = 0.0 as input augments to the data generator. Do not change the random seed for all the problems afterwards. Stopping criteria of the outer loop: stop the algorithm when either of the following is fulfilled: 1) the number of steps exceeds 100; or 2) no element in θ changes more than ϵ between two successive iterations of the outer loop, i.e., maxj |θj(t)−θj(t−1)| ≤ ϵ, where the recommended value for ϵ = 0.01, where θj(t) is the value of θj after t iterations. At the beginning of the lasso, use the given initialization function “θ,θ0 = Initialw(X, y)” to initialize θ and θ0 by the least square regression or ridge regression. You can try different values of λ to make sure that your solution makes sense to you (Hint: DataGenerator gives the true θ and θ0). Solve lasso on the generated synthetic data using the given parameters and report indices of non-zero weight entries. Plot the objective value F(θ,θ0) v.s. coordinate descent step. The objective value should always be non-increasing. 2. [5 points] Implement an evaluation function in the notebook to calculate the precision and recall of the non-zero indices of the lasso solution with respect to the non-zero indices of the true vector that generates the synthetic data. Precision and recall are useful metrics for many machine learning tasks. For this problem in specific, |{non-zero indices in θˆ} ∩ {non-zero indices in θ∗}| precision = ; |{non-zero indices in θˆ}| (6) |{non-zero indices in θˆ} ∩ {non-zero indices in θ∗}|recall = non-zero indices in θ∗}| , |{ (7) where θ∗ is the θ in true model weight, while θˆ is the θ in lasso solution. 3. [10 points] Vary λ and solve the lasso problem multiple times. Choose 50 evenly spaced λ values starting with λmax = ∥(y − y¯)X∥∞ (¯y is the average of elements in y, and ∥a∥∞ = maxj aj), and ending with λmin = 0. Plot the precision v.s. λ and recall v.s. λ curves on a single 2D plot. Briefly explain the plotted pattern and curves. On top of this, try to have fun with λ and play with this hyperparameter, explore, discover, and tell us what you have discovered. Draw a “lasso solution path” for each entry of θ in a 2D plot. In particular, use λ as the x-axis, for each entry θi in θ achieved by lasso, plot the curve of θi vs. λ for all the values of λ you tried similar to the plot we showed in class from the Murphy text (in your case, there are 50 points on the curve). Draw such curves for all the m entries in θ within a 2D plot, use the same color for the 5 features in DataGenerator used to generate the data, and use another very noticeably distinct color for other features. If necessary, set a proper ranges for x-axis and y-axis, so you can see sufficient detail. Now change the noise’s standard deviation σ = 10.0 when using “DataGenerator” to generate synthetic data, draw the lasso solution path again. Compare the two solution path plots with different σ, and explain their difference. Be complete, and clear. 4. [5 points] Use the synthetic data generation code with different parameters: (n = 50,m = 75),(n = 50,m = 150),(n = 50,m = 1000),(n = 100,m = 75),(n = 100,m = 150),(n = 100,m = 1000) (keeping other parameters the same as in Sub-Problem 1). Vary λ in the same way as in the previous question (Sub-Problem 3), and find the λ value that can generate both good precision and recall for each set of synthetic data points. For each case, draw the “lasso solution path” defined in Sub-Problem 3. 5. [25 points] This question is challenging, requiring major changes to your previous implementation as well as significant training time. Run lasso to predict review stars on Yelp by selecting important features (words) from review comments. We provide the data in hw3 data.zip. You can unzip the file and use the provided function “DataParser” in the notebook to load the data. There are three files: “star data.mtx”, “star labels.txt”, “star features.txt”. The first file stores a matrix market matrix and DataParser reads it into a scipy csc sparse matrix, which is your data matrix X. The second file contains the labels, which are the stars of comments on Yelp, is your y. The third file contains the names of features (words). For the last two txt files, you can open them in an editor and take a look at their contents. The sparse data X has size 45000 × 2500, and is split into the training set (the first 30000 samples), validation set (the following 5000 samples) and the test set (the last 10000 samples) by “DataParse”. Each column corresponds to a feature, i.e., a word appearing in the comments. Your mission is to solve lasso on the training set, tune the λ value to find the best RMSE on the validation set, and evaluate the performance of the obtained lasso model on the test set. Important to read before you start: Here, we are dealing with a sparse data matrix. Most numpy operations for dense matrices you used for implementing lasso in Sub-Problem 1 cannot be directly applied to sparse matrices here. You can still use the framework you got in Sub-Problem 1, but you need to replace some dense matrix operations (multiply, dot, sum, slicing, etc.) by using sparse matrix operations from “scipy.sparse” (please refer to https://docs.scipy.org/doc/scipy/ reference/sparse.html for details of sparse matrix operations). The sparse matrix format here aims to help you make the algorithm more efficient in handling sparse data. Do not try to directly transform the sparse matrix X to a dense one by using “X.todense()”, since it will waste too much memory. Instead, try to explore the advantages of different sparse matrix types (csc, coo, csr) and avoid their disadvantages, which are listed under each sparse matrix type in the above link. You can change the format of a sparse matrix X to another one by using (for example) “X.tocsc()” if necessary, but do not use it too often. For some special sparse matrix operations, it might be more efficient to write it by yourself. We provide an example “cscMatInplaceEleMultEveryRow” in the notebook. You can use it, or modify it for your own purpose. This will be a good practice for you to think about how to write an efficient ML algorithm. Try to avoid building new objects inside the loop, or computing anything from scratch. You can initialize them before the loop start, and use the lightest way to update them in the loop. Note any operation that seems “small” inside the loop could possibly lead to expensive computations, considering the total number of times it will be executed. You can use “if” to avoid unnecessary operations on zeros. Do not loop over matrices or vectors if not necessary: use matrix or batch operations provided by numpy or scipy instead. Try to use the most efficient operation when there are many choices reaching the same result. If you write an inefficient code here, running it will take extremely longer time. During debugging, timing each step or operation in the loop will help you figure out which step takes longer time, and you can then focus on how to accelerate it. • Explain how do you modify your implementation to make the code more efficient compared to the “naive” implementation you did for Sub-Problem 1. Compare the computational costs of every coordinate descent iteration in terms of n (number of data points) and m (number of dimensions). • Plot the training RMSE (on the training set) v.s. λ values and validation RMSE (on the validation set) v.s. λ values on a 2D plot. Use the definition of λmax in sub-problem 3 and run experiments on multiple values of λ. You can reduce the number of different λ values to 20. You can also increase the minimal λ to be slightly larger than 0 such that 0 ≤ λmin ≤ 0.1λmax. These two changes will save you some time. • Plot the lasso solution path defined in Sub-Problem 3. • Report the best λ value achieving the smallest validation RMSE you find on the validation set, and report the corresponding test RMSE (on the test set). • Report the top-10 features (words in comments) with the largest magnitude in the lasso solution w when using the best λ value, and briefly explain if/why they are meaningful.
• Online submission: You must submit your solutions online via Gradescope. You need to submit (1) a PDF that contains the solutions to all questions to the Gradescope HW2 PaperWork assignment, (2) x.py or x.ipynb files for the programming questions to the Gradescope HW2 CodeFiles assignment. We recommend that you type the solution (e.g., using LATEX or Word), but we will accept scanned/pictured solutions as well (clarity matters). • Generative AI Policy: You are free to use any generative AI, but you are required to document the usage: which AI do you use, and what’s the query. You are responsible for checking the correctness. 1 Linear Regression and Convexity [10 points] Show detailed derivations that the linear regression loss function is convex in the parameters w: L(w) = . Here y is an n-dimensional vector, X is an n × d matrix and w is a d-dimensional vector. X is of full rank. There are multiple ways to show it, but we force you to take the following approach: compute ∇L(w) using directional derivative and then compute ∇2L(w). 2 Gaussian Distribution and the Curse of Dimensionality [40 points] In this problem, we will investigate the Gaussian distribution in high dimensional space, and develop intuitions and awareness about the curse of dimensionality, a critical concept that everyone who wishes to pursue study in machine learning should understand. For a random variable x of m dimensions (i.e., x ∈ Rm) drawn from a multivariate Gaussian distribution, recall that the Gaussian density function takes the form: (1) where µ ∈ Rm is an m-dimensional mean vector and C ∈ Rm×m is an order m × m symmetric positive definite covariance matrix. When C is a diagonal matrix, then the covariance between different dimensions is zero, which is known as a axis-aligned Gaussian, and when C = σ2I, I being the m × m identity matrix, we already saw this in Homework 1 where the m = 2 (2D) Gaussian in this case has spherical (circle) shaped contours. A spherical Gaussian in m dimensions thus has the following equation form: (2) We start by examining some basic geometric properties of the sphere in m dimensional space. A sphere is generally a collection of points such that the distance of any point to the center of the sphere (we always center the sphere on origin ⃗0 for simplicity) is equal to r, the radius. In other words, we define an mdimensional sphere as Sm−1(r) = {x ∈ Rm : ∥x∥2 = r}, the set of points in m-dimensional space that are distance r from the origin (note that Sm−1(r) is the equation for the surface of the sphere, although in some fields, such as physics, they define the sphere as the surface and interior, as in {x ∈ Rm : ∥x∥2 ≤ r}). We also use Vm(r) for the volume of an m-dimensional sphere. Sm−1(r) represents the surface area of the m-dimensional sphere (meaning, e.g., that m = 2 dimensional sphere of radius r has surface area S1(r), this convention is used since the surface area is a curved m − 1 dimensional manifold embedded in m-dimensional ambient space). Please make sure you answer every question: 1. [1 points] Before we move to m dimensions, let’s talk about 2D and 3D cases. Write down the equations, in terms of the radius r, of Sm−1(r) for m ∈ {2,3} and Vm(r) for m ∈ {2,3}. 2. [5 points] Intuitively explain the following equation: . (3) 4. [5 points] Now consider all the points on the sphere Sm−1(r) (which, because of our definition of Sm−1(r) really means the surface). We wish to integrate over all of those points weighted by the Gaussian probability density p(x) of each point, where p(x) is defined as given in Equation (2). That is, we integrate over all points points x ∈ Sm−1(r) weighted by p(x). Indeed, this is an integration, but you can avoid doing the mathematical integration by utilizing the results from previous questions. Write the equation ρm(r) for the integrated density of sampled points from the Gaussian distribution lying on the surface of Sm−1(r). √ 5. [5 points] For large m, show that ρm(r) has a single maximum value at ˆr such that ˆr ≈ mσ. 6. [10 points] For large m, consider a small value ϵ ≪ rˆ (the symbol “≪” means “much less than”), and show that . (4) Hint: during your derivation, first get the expression simplified and close to the desired form. Then use Taylor expansion to get the approximation. 7. [3 points] The previous problem shows that ˆr is the radius where most of the probability mass is in a high dimension Gaussian, and moreover, as we move away from this radius, say going from ˆr to √ rˆ+ ϵ, then the total mass becomes smaller exponentially quickly in ϵ. Also, note that since ˆr ≈ mσ, for large m we have σ ≪ rˆ — since σ (the standard deviation) is in low dimensions usually used to indicate where much of the probability mass is, indeed p(x) > p(x′) whenever ∥x∥ < ∥x′∥ with the highest density value being p(0) at the origin 0. When we get to high dimensions, however, most of the mass is far away from the σ neighborhood around the origin. Taken together, this means that most of the probability mass, in a high dimensional Gaussian, is concentration in a thin skin (e.g., think of the skin of an m-dimensional apple or synthetic leather layer of an m-dimensional soccer ball) of large radius. If we only get a finite number of samples from a high-dimensional Gaussian distribution, therefore, where do most of the points reside? At what radius do they reside? For a low dimensional Gaussian distribution, where do most points reside? Write a python script that samples from an m-dimensional Gaussian. For each m ∈ {1,2,…,40}, produce 100 samples and compute the mean and standard deviation of the radii of the samples, and plot this as a function of m. Is your plot consistent with the above? Why or why not? Fully understand what you see, and clearly explain to us that you understand it and how you justify it. 3 Ridge Regression [20 points] Recall that linear regression solves , (5) Where X is the data matrix, and every row of X corresponds to a data point, y refers to the vector of labels, and w is the weight vector we aim to optimize. Specifically, X is an n × d data matrix with n data samples (rows) and d features (columns), and y is an n-dimensional column vector of labels, one for each sample. Ridge regression is very similar, and it is defined as , (6) where we add an additional regularization term to encourage the weights to be small and has other benefits as well which we will discuss in class. Please make sure you answer every question 1. [5 points] Describe (with drawings and intuitive description) one setting for (X,y), where standard linear regression is preferred over ridge regression. The drawing should show: (1) the data points (X,y); (2) the expected linear regression solution (e.g., a line); (3) expected ridge regression solution (also, e.g., a line). You need to explain the reason for why the standard linear regression is preferred. You need not do any actual calculation here. 2. [5 points] Describe (with drawings and intuitive description) one setting for (X,y), where ridge regression is preferable to linear regression. Your answer should fulfill the same requirements in part 1. 3. [5 points] Solve for the closed-form solution for ridge regression. To get the closed-form solution, you can set the gradient of the objective function F(w) in the above minimization problem to be zero and solve this equation of w. If you are not familiar with how to compute the gradient (or such derivatives), please refer to Section 2.4 of the Matrix Cookbook (https://www.math.uwaterloo.ca/~hwolkowi/ matrixcookbook.pdf) The Matrix Cookbook is extremely helpful for linear algebra. 4. [5 points] Now consider two cases: (1) where the columns (or features) of X are more than the rows (or samples); and (2) where the columns (or features) of X are highly correlated (an extreme case is where many features are identical to each other). For each of the above: (a) Can you still compute the closed-form solution of the vanilla linear regression? (b) With the closed form solution of the previous question and compared to the solution for standard linear regression, do you discover other benefits of ridge regression? 4 Bonus: Locality Sensitive Hashing (LSH) [20 points] We haven’t talked about LSH in detail in class, and this problem serves as a tutorial for LSH. This problem requires a lot of reading and thinking, though the math involved is not particularly hard. As this is a bonus problem, we suggest you leave it to the end if you have extra time and are interested in the topic. Locality sensitive hashing refers to a special property of hash functions and is closely related to approximate nearest neighbor search (NNS), i.e., we find close points to the query instead of exactly the nearest neighbor. For simplicity, suppose the design matrix X (which is n×m) consists of only binary features. This means that every data point (i.e., every row of the design matrix) has the form xi ∈ {0,1}m. Define d(xi,xj) as the hamming distance between two data points xi and xj, i.e. d(xi,xj) = Pa∈{0,1,…,m−1} |xi[a] − xj[a]|. Hamming distance simply counts the number of positions where the two binary vectors differ, and hamming distance is a proper distance metric (see https://en.wikipedia.org/wiki/Metric_(mathematics) for the full definition of a distance metric). 1. [5 points] Imagine you have the following magical oracle. Given a query point q ∈ {0,1}m, and two parameters r > 0 and c ≥ 1, (a) If ∃x ∈ X such that d(x,q) ≤ r, the oracle returns to you some point x′ ∈ X such that d(x′,q) ≤ cr. (b) If ∄x ∈ X such that d(x,q) ≤ cr, the oracle returns to you nothing. (c) Otherwise (∃x ∈ X such that d(x,q) ≤ cr but ∄x ∈ X such that d(x,q) ≤ r), the oracle is not stable, and can either return to you some point x′ such that d(x′,q) ≤ cr or return to you nothing. Suppose you want to find exactly the nearest neighbor point in X of the query point q. Using as few times as possible of calling the oracle, how do you appropriately set the values r and c in order to get back the nearest neighbor of q? Consider a family of hash functions H, where each function h is associated with a random integer a from {0,1,…,m − 1}, and given the input xi, h(xi) = xi[a]. This hash function is very simple, and merely returns coordinate a of the data point xi. Suppose we randomly pick a hash function h from H. For two inputs xi and xj, if d(xi,xj) ≤ r (r > 0), what’s a lower bound for the probability that h maps xi and xj to the same value (i.e. Pr(h(xi) = h(xj)))? We name this lower bound as p1. Similarly, if d(xi,xj) ≥ cr (c ≥ 1), what’s an upper bound for the probability that h maps xi and xj to the same value (i.e. Pr(h(xi) = h(xj)))? We name this upper bound as p2. 3. [2 points] LSH refers to the following properties. A family of hash functions is (r,c,p1,p2)-LSH (1 ≥ p1 ≥ p2 > 0, c > 1, r > 0) if: (a) Pr(h(xi) = h(xj)) ≥ p1 when d(xi,xj) ≤ r; (b) Pr(h(xi) = h(xj)) ≤ p2 when d(xi,xj) ≥ cr. Note h is a randomly sampled hash function from the family of hash functions. Intuitively, when two data points are close (d(xi,xj) ≤ r), the hash function should map them to the same output value with (relatively) high probability at least equal to p1. If two data points are faraway (d(xi,xj) ≥ cr), the hash function should map them to the same output value with (relatively) low probability at most equal to p2. The very simple hash functions from H introduced above indeed satisfies the LSH property (you can verify by comparing your answers to the two previous questions). With the dataset X, we can first hash all data points using a single function h randomly sampled from H. Then, given a query point q, we hash q with the same function h, and retrieve all data points in X that get hashed to the same value as h(q) (if any). Finally, we can iterate over the retrieved points (if not empty), and return the point closest to the query point q. As p1 ≥ p2, the hash function is more likely to hash close points into the same value than faraway points. However, the difference between p1 and p2 might be not significant enough. One simple trick to make close points more probable relative to the faraway points is to sample multiple hash functions from H, and two data points have the same hashed value if all the sampled hash functions give the same value. In other words, we define a new hash function g via the use of k randomly sampled hash functions from H, and we do this by concatenating their output together into a vector of length k. g(xi) = (h1(xi),h2(xi),h3(xi),…,hk(xi)). (7) Give a lower bound for the probability that g(xi) = g(xj) if d(xi,xj) ≤ r in terms of p1 and k. Give an upper bound for the probability that g(xi) = g(xj) if d(xi,xj) ≥ cr in terms of p2 and k. (Note that g(xi) = g(xj) if they are equal on every coordinate of the output vectors. You can also think the binary vector output of g as a binary encoding of an integer, so the output of g becomes an integer value.) Give a lower bound for he probability that ∃b ∈ {0,1,…,l−1} such that gb(xi) = gb(xj) if d(xi,xj) ≤ r. Give an upper bound for the probability that ∃b ∈ {0,1,…,l − 1} such that gb(xi) = gb(xj) if d(xi,xj) ≥ cr. 5. [7 points] Again, assume we set r appropriately so that there exists some data point x ∈ X with d(x,q) ≤ r. Let and . Consider the following two events: (a) For some x′ ∈ X, d(x′,q) ≤ r, ∃b ∈ {0,1,…,l − 1} such that gb(x′) = gb(q). (b) There are at most 4l items in X where each x in those 4l items has d(x,q) ≥ cr and for some b, gb(x) = gb(q). Show the first event happens with probability at least 1−e−1 (note that limk→∞(1−1/k)k = e−1 and (1−1/k)k < e−1). Show the second event happens with probability at least 3/4 (HINT: use Markov’s inequality https://en.wikipedia.org/wiki/Markov%27s_inequality). Give a lower bound on the probability that both events happen. 6. [2 points] The two events from the previous question happen with a constant probability. We can then boost the probability of success by running multiple independent instances so that the probability that the two events fail for all instances is negligible. For this problem, assume that the previous two events happen with certainty. Recall that we construct l hash functions, and each hash function g consists of k sampled functions from H. Given a query q, we collect all data points in X if they share the same hashed value for any gb with the query point. Now we want to iterate over the collected points and report one point as the nearest neighbor. If we only want to return a point that has distance at most cr to the query point q, how many points do we need to check? Are we guaranteed that there is a point with distance at most cr and why? 5 Programming Problem: Linear Regression [30 points] In this problem, you will implement the closed-form solvers of linear regression and ridge regression from scratch (which means that you cannot use built-in linear/ridge regression modules in scikit-learn or any other packages). Then you will try your implementation on a small dataset, the Boston housing price dataset, to predict the house prices in Boston (“MEDV”) based on some related feature attributes. We provide an ipython notebook “linear regression boston.ipynb” for you to complete. In your terminal, please go to the directory where this file is located, and run the command “jupyter notebook”. A local webpage will be automatically opened in your web browser, click the above file to open the notebook. You need to complete the scripts below the “TODOs” (please search for every “TODO”), and submit the completed ipynb file (inside your .zip file). In your write-up, you also need to include the plots and answers to the questions required in this session. The first part of this notebook serves as a quick tutorial of loading dataset, using pandas to get a summary and statistics of the dataset, using seaborn and matplotlib for visualization, and some commonly used functionalities of scikit-learn. You can explore more functionalities of these tools by yourself. You will use these tools in future homeworks. 1. [5 points] Below “1 how does each feature relate to the price” in the ipynb file, we show a 2D scatter plot for each feature, where each point associates with a sample, and the two coordinates are the feature value and the house price of the sample. Please find the top-3 features that are mostly (linearly) related to the house price (“MEDV”). 2. [5 points] Below “2 correlation matrix”, we compute the correlation matrix by pandas, and visualize the matrix by using a heatmap of seaborn. Please find the top-3 features that are mostly (linearly) related to the house price (“MEDV”) according to the correlation matrix. Are they the same as the ones in the previous question (sub-question 1)? 3. [10 points] Below “3 linear regression and ridge regression”, please implement the closed-form solver of linear regression and ridge regression (linear regression with L2 regularization). You can use numpy here. Recap: linear regression solves , (8) while ridge regression solves , (9) where X is an n×d data matrix with n data samples and d features, and y is an n-dim vector storing the prices of the n data samples, and F(w) is the objective function. Run the linear regression and ridge regression on the randomly split training set, and report the obtained coefficients w. For ridge regression, it is recommended to try different η values. 4. [5 points] Below “4 evaluation”, implement prediction function and root mean square error , (10) where ˆyi is the predicted price and yi is the true price of sample i. Apply the implementation and report the RMSE of linear regression and ridge regression on the training set and test set. Compare the training RMSE of linear regression and ridge regression, what do you find? How about the comparison of their test RMSE? Can you explain the difference? 5. [5 points] Below “5 linear models of top-3 features”, train a linear regression model and a ridge regression model by using the top-3 features you achieved in sub-question 2, and then report the RMSE on the training set and test set. Compare the RMSE of using all the 13 features: what is the difference? what does this indicate?
Instructions • Online submission: You must submit your solutions online via Gradescope. You need to submit (1) a PDF that contains the solutions to all questions to the Gradescope HW1 PaperWork assignment, (2) x.py or x.ipynb files for the programming questions to the Gradescope HW1 CodeFiles assignment. We recommend that you type the solution (e.g., using LATEX or Word), but we will accept scanned/pictured solutions as well (clarity matters). • Generative AI Policy: You are free to use any generative AI, but you are required to document the usage: which AI do you use, and what’s the query. You are responsible for checking the correctness. 1 Simpson’s Paradox [10 points] Imagine you and a friend are playing the slot machine in a casino. Having played on two separate machines for a while, you decide to swap machines between yourselves, and measure for differences in “luck”. The wins/losses for you and your friend for each machine are tabulated below. Machine 1 Wins Losses You 40 60 Friend 30 70 Machine 2 Wins Losses You 210 830 Friend 14 70 Assuming that the outcomes of playing the slot machine are independent of their history and that of the other machine, answer the following questions. 1. (3 points) Estimate the winning probability of you and your friend for each of the machines. Compare your winning probability with your friend’s on different machines. Who is more likely to win? 2. (3 points) Estimate the overall winning probability of you and your friend in the casino (assume that there are only two slot machines in the casino). Who is more likely to win? 3. (4 points) Compare your conclusions from (1) and (2). Can you explain them mathematically? I.e., write down the equations to compute the winning probabilities and compare the terms.Figure 1: Problem 2 2 Matrix as Operations [25 points] On the 2D plane, we have four vectors (all with the starting point on the origin) a1 = (1,1), a2 = (1,−1), b1 = (−0.8,1.6) and b2 = (2.6,−0.2). See Fig. 1 1. [5 points] Write down one 2 × 2 matrix W that transforms a1 to b1, and a2 to b2. 2. [5 points] Write down one rotation matrix V , which rotates clockwise by α degrees such that tan(α) = 3. Then, write down one matrix Σ, which scales the y-axis by 2, while keeping the x-axis unchanged. Finally, write down one rotation matrix U, which rotates counter-clockwise by β degrees, such that tan(β) = 1/3. Multiply three matrices together, namely UΣV , what do you discover? 3. [10 points] Compute the eigenvalues and the corresponding eigenvectors of WTW. Now consider the unit circle. Suppose every point on the unit circle gets transformed by W; what shape do you get after the transformation (consider the break-up transformations in the previous question)? What relationship do you find between the eigenvalues/eigenvectors and the transformed shape, and why? 4. [5 points] Compute the determinant of W. What’s the area of the shape transformed from the unit circle? What is the relationship between the determinant and the area of a transformed shape? Based on that, can you use one sentence to explain that the determinant of a product of two matrices is equal to the product of the determinants of the two matrices or, in other words, det(AB) = det(A)det(B)? 3 Some Practices [10 points] 1. [3 points] For a discrete random variable X of finite values, show that (E[X3])2 ≤E[X6]. (1) You only need the materials taught in class. 2. [3 points] Prove the above in a different way. Again, you only need the materials taught in class. 3. [4 points] For two PSD matrices A,B both of shape n × n, show that λA + (1 − λ)B is also PSD for 0 ≤ λ ≤ 1. 4 Density Estimation of Multivariate Gaussian [25 points] Please check the following tutorials if you are not familiar with numpy: http://cs231n.github.io/ python-numpy-tutorial/ and https://docs.scipy.org/doc/numpy-1.15.0/user/quickstart.html In this problem, you will estimate a multivariate Gaussian distribution from 2D points sampled a multivariate Gaussian distribution, and learn how to use python and matplotlib to generate simple plots in ipython notebook. If you are not familiar with jupyter notebook, please check a quick tutorial on https://jupyter-notebook-beginner-guide.readthedocs.io/en/latest/execute.html. We provide an ipython notebook “2d gaussian.ipynb” for you to complete. In your terminal, please go to the directory where this ipynb file is located, and run command “jupyter notebook”. A local webpage will be automatically opened in your web browser. Click the above file to open the notebook. You need to complete everything below each of the “TODO”s that you find (please search for every “TODO”). Once you have done that, please submit the completed ipynb file as part of your included .zip file. In your write-up, you also need to include the plots and answers to the questions required in this session. Please include the plots and answers in the pdf file in your solution. 1. [2 points] Run the first cell in the ipython notebook to generate 1000 points X (a 1000×2 matrix, each point has two coordinates) sampled from a multivariate Gaussian distribution. Estimate the mean and covariance of the sampled points and report them in your write-up. 2. [3 points] Plot the histogram for the x-coordinates of X and y-coordinates of X respectively. You can use the plt.hist() function from matplotlib. 3. [5 points] From the histogram, can you tell whether the x-coordinates of the 1000 points (the first column of X) follow some Gaussian distribution? If so, compute the mean and the variance. How about the y-coordinates? If so, compute the mean and the variance. 4. [5 points] Sample 1000 numbers from a 1D Gaussian distribution with the mean and variance of the x-coordinates you got from subproblem 3. Sample another 1000 numbers from a 1D Gaussian distribution with the mean and variance of the y-coordinates. You can use np.random.normal from numpy. Generate a new 2D scatter plot of 1000 points with the first 1000 numbers as x-coordinates and the second 1000 numbers as y-coordinates. Compared to the original 1000 points, what is the difference in their distributions? What causes the difference? 6. [5 points] Draw the histogram of the x-coordinates of the projected points. Are the x-coordinates of the projected points sampled from some Gaussian distribution? If so, compute the mean and the variance.5 KNN for Iris flowers classification [20 points] For this problem, we want to use the K nearest neighbor algorithm to classify Iris flowers. 1. [5 Points] Load the Iris data using sklearn.datasets. Calculate how many elements there are for every class. 2. [5 Points] Build a KNeighborsClassifier with k = 1 to predict the class. Train it on the whole dataset. For the classification problem, different goodness-of-fit metrics are used. For this exercise, you can use accuracy, which is defined in the formula given below. Calculate the accuracy of the KNN classifier on the iris dataset. Does this result give you meaningful information? #correctly predicted Accuracy = (2) M 3. [5 Points] Split the dataset into two parts using sklearn’s train test split. Use the following arguments: (a) X,y : the dataset (b) test size = 0.5 (use 50% of the dataset for testing) (c) shuffle = True (randomly shuffle the dataset before making a cut) (d) random state = 0 (random seed, this ensures consistent results) Use the split to find the optimal value of k. Please try different values of k from 1 to 50, fit the model on the training data, and calculate the model’s accuracy on the training data and the testing data, respectively. Plot the training accuracy and testing accuracy against the value of k. Which k value is the best? 4. [5 Points] You observed a flower and measured the following characteristics: (a) sepal width = 5.0 (b) petal width = 4.1 (c) sepal length = 3.8 (d) petal length = 1.2 Use your prediction model to classify this plant. What’s the predicted class? 6 K Means clustering [10 points] For this question, use the data in clust data.csv. We will attempt to cluster the data using k-means. But, what k should we use? 1. [5 Points] Apply k-means to this data 15 times, changing the number of centers from 1 to 15. Each time use nstart = 10 and store the within-cluster sum-of-squares/inertia value from the resulting object. The inertia measures how variable the observations are within a cluster. This value will be lower with more centers, no matter how many clusters there truly are naturally in the given data. Plot this value against the number of centers. Look for an “elbow”, the number of centers where the improvement suddenly drops off. Based on this plot, how many clusters do you think should be used for this data? 2. [2 Points] Re-apply k-means for your chosen number of centers. How many observations are placed in each cluster? What is the value of inertia? 3. [3 Points] Visualize this data. Plot the data using the first two variables and color the points according to the k-means clustering. Based on this plot, do you think you made a good choice for the number of centers? Briefly explain your conclusion.
1) There is a precious diamond that is on display in a museum at m disjoint time intervals. There are n security guards who can be deployed to protect the precious diamond. Each guard has a list of intervals for which he or she is available to be deployed. Each guard can be deployed to at most M time slots and has to be deployed to at least L time slots.Design an algorithm that decides if there is a deployment of guards to intervals such that each interval has either one or two guards deployed. (10 pts) Note: We are only looking for the largest number of SPYs not the actual location of the words. No proof is necessary.UNGRADED 4) In the network below, the demand values are shown on vertices. Lower bounds on flow and edge capacities are shown as (lower bound, capacity) for each edge. Determine if a feasible circulation exists or not. If it does, show the feasible circulation. If it doesnot, show the cut in the network that is the bottleneck. Show all your steps.5) The following graph G is an instance of a circulation problem with demands. The edge weights represent capacities and the node weights (in parantheses) represent demands. A negative demand implies source.(i) Transform this graph into an instance of max-flow problem. (ii) Now, assume that each edge of G has a constraint of lower bound of 1 unit, i.e., one unit must flow along all edges. Find the new instance of max-flow problem that includes the lower bound constraint. 6) Determine if it is possible for flow to circulate within the given network depicted as graph G. The demand values, indicated on vertices, represent either supply (if positive) or demand (if negative). Each edge also has specified lower bounds on flow and capacity. Demonstrate all necessary steps to ascertain if a feasible circulation exists within this graph. (20 pts) (a) Reduce the Feasible Circulation with Lower Bounds problem to a Feasible Circulation problem without lower bounds. (b) Reduce the Feasible Circulation problem obtained in part (a) to a Max Flow problem in a Flow Network. (c) Solve the resulting Max Flow problem and explain whether there is a Feasible Circulation in the original G. 7) USC Admissions Center needs your help in planning paths for Campus tours given to prospective students or interested groups. Let USC campus be modeled as a weighted, directed graph G containing locations V connected by one-way roads E. On a busy day, let k be the number of campus tours that have to be done at the same time. It is required that the paths of campus tours do not use the same roads. Let the tour have k starting locations A = {a1, a2, …, ak} ⊆ V . From the starting locations, the groups are taken by a guide on a path through G to some ending location in B = {b1, b2, …, bk} ⊆ V . Your goal is to find a path for each group i from the starting location, ai, to any ending location bj such that no two paths share any edges, and no two groups end in the same location bj . (a) Design an algorithm to find k paths ai → bj that start and end at different vertices, such that they do not share any edges. (b) Modify your algorithm to find k paths ai → bj that start and end in different locations, such that they do not share any edges or vertices.
Spring2024 Q1. Determine if the following statements are true or false. If true, give a brief explanation. If false give a counterexample. (10 points) (a) For a flow network, there always exists a maximum flow that doesn’t include a cycle containing positive flow. (b) If you have non-integer edge capacities, then you cannot have an integer max-flow value. (c) Suppose the maximum s-t flow of a graph has value f. Now we increase the capacity of every edge by 1. Then the maximum s-t flow in this modified graph will have a value of at most f + 1. (d) If all edge capacities are multiplied by a positive number k , then the min-cut remains unchanged. Q2. A tourist group needs to convert all of their USD into various international currencies.There are n tourists t1,t2, …,tn and m currencies c1,c2, …,cm. Each tourist tk has Fk Dollars to convert. For each currency cj , the bank can convert at most Bj Dollars to cj.Tourist tk is willing to trade at most Skj of their Dollars for currency cj. (For example, a tourist with 1000 dollars might be willing to convert up to 300 of their USD for Rupees, up to 500 of their USD for Japanese Yen, and up to 400 of their USD for Euros). Assume that all tourists give their requests to the bank at the same time. Design an algorithm that the bank can use to determine whether all requests can be satisfied. To do this, construct and draw a network flow graph, with appropriate source and sink nodes, and edge capacities. Prove your algorithm is correct by making an if-and-only-if claim (10 points) Q4. You are given a directed graph which after a few iterations of Ford-Fulkerson has the following flow. The labeling of edges indicate flow/capacity: (15 points)a) Draw the corresponding residual graph. b) Is this a max flow? If yes, indicate why. If no, find max flow. c) What is the min-cut? Q5. USC has resumed in-person education after a one-year break, with k on-site courses available this term, labeled c1 through ck. Additionally, there are n students, labeled s1 to sn, attending these k courses. It’s possible for a student to attend multiple on-site courses, and each course will have a variety of students enrolled. (20 points) (b) Assuming a viable solution is found for part (a) where each student is enrolled in exactly m courses, there arises a need for a student representative for each course from among the enrolled students. However, any single student can represent at most r (where r is less than m) courses in which they are enrolled. Develop an algorithm to check whether it is possible to appoint such representatives, building on the solution from part (a) as a foundation. Prove your algorithm is correct by making an if-and-only-if claim. Q6. Given the below graph solve the below questions using scaled version of Ford-Fulkerson. (15 points)a) Give the Δ and path selected at each iteration. b) Draw the final network graph and the residual graph c) Find the maxflow and mincut Q7:The following graph G has labeled nodes and edges between them. Each edge is labeled with its capacity. (10 points)(a) Draw the final residual graph Gf using the Ford-Fulkerson algorithm corresponding to the max flow. Please do NOT show all intermediate steps. (b) What is the max-flow value? (c) What is the min-cut? Q8. You are provided with a flow network where each edge has a capacity of one. This network is represented by a directed graph G = (V, E), including a source node s and a target node t. Additionally, you are given a positive integer k. The objective is to remove k edges to achieve the greatest possible reduction in the maximum flow from s to t in G. Your task is to identify a subset of edges F within E, where the size of F equals k, and removing these edges from G results in a new graph G’ = (V, E-F) where the maximum flow from s to t is minimized. Propose a polynomial-time strategy to address this issue. Furthermore, consider if the capacities of the edges are greater than one, and discuss whether your strategy still ensures the lowest possible maximum flow. (20 points)
Below figure provides one example to explain the problem. The example shows k=2 assembly lines and 5 stations per line. To illustrate how to evaluate the cost, let’s consider two cases: If we always use assembly line 1, the time cost will be: e1 + a1,1 + a1,2 + a1,3 + a1,4 + a1,5 +x1 If we use stations s1,1 -> s2,2 -> s1,3 -> s2,4 -> s2,5 , the time cost will be : e1 + a1,1 + t1,2+ a2,2 + t2,1 +a1,3 +t1,2+a2,4+a2,5+x2a) Define (in plain English) subproblems to be solved. (2 pts) b) Recursively define the value of an optimal solution (recurrence formula) (8 pts) c) Describe (using pseudocode) how the value of an optimal solution is obtained using iteration. Make sure you include any initialization required. (8 pts) d) What is the complexity of your solution in part b? (4 pts) Q2.There are n trading posts along a river numbered n, n – 1… 3, 2, 1. At any of the posts you can rent a canoe to be returned at any other post downstream. (It is impossible to paddle against the river since the water is moving too quickly). For each possible departure point i and each possible arrival point j(< i), the cost of a rental from i to j is known. It is C[i, j]. However, it can happen that the cost of renting from i to j is higher than the total costs of a series of shorter rentals. In this case you can return the first canoe at some post k between i and j and continue your journey in a second (and, maybe, third, fourth . . . ) canoe. There is no extra charge for changing canoes in this way. Give a dynamic programming algorithm to determine the minimum cost of a trip by canoe from each possible departure point i to each possible arrival point j. For your dynamic programming solution, focus on computing the minimum cost of a trip from trading post n to trading post 1, using up to each intermediate trading post. a) Define (in plain English) subproblems to be solved. b) Recursively define the value of an optimal solution (recurrence formula) (5 pts) c) What will be the iterative program for the above ? (5 points) d) Analyze the running time of your algorithm in terms of n. (5 pts) Q3 Alice and Bob are playing an interesting game. They both each have a string, let them be a and b. They both decided to find the biggest string that is common between the strings they have. The letters of the resulting string should be in order as that in a and b but don’t have to be consecutive. Discuss its time complexity. Write the subproblems in English, Recurrence Relation and Pseudo code as well (20 Points) a) Define (in plain English) subproblems to be solved. (2 pts) b) Write down the base cases: (2 Points) c) Write the recurrence relation: (6 Points) d) Write the pseudoCode for telling if such a string can be found and if so, find the resulting string. (8 Points) e) Write the time complexity (2 Points) UNGRADED QUESTIONS Solution: a. Define (in plain English) subproblems to be solved. (4 pts) b. Write a recurrence relation for the subproblems (6 pts) c. Using the recurrence formula in part b, write pseudocode to solve the problem. (5 pts) d. Make sure you specify : 1. base cases and their values (2 pts) 2. where the final answer can be found (1 pt) e. What is the complexity of your solution? (2 pts) Q5. Tommy and Bruiny are playing a turn-based game together. This game involves N marbles placed in a row. The marbles are numbered 1 to N from the left to the right. Marble i has a positive value mi. On each player’s turn, they can remove either the leftmost marble or the rightmost marble from the row and receive points equal to the sum of the remaining marbles’ values in the row. The winner is the one with the higher score when there are no marbles left to remove. Tommy always goes first in this game. Both players wish to maximize their score by the end of the game. Assuming that both players play optimally, devise a Dynamic Programming algorithm to return the difference in Tommy and Bruiny’s score once the game has been played for any given input. a) Define (in plain English) subproblems to be solved. (2 pts) b) Write down the recurrence relation (8 Points) c) Write down the the pseudo-code for this algorithm (8 Points) d) Write down the time complexity (2 Points): Q6. Consider a group of people standing in a line of size n. Everyone’s heights are given in an array height = [h0, h1, ….. Hn-1]. Write an efficient algorithm to find the longest subsequence of people with strictly increasing heights and return it. Give the pseudo code and the recurrence relation. For example: height = [6,1,2,3,4,5], ans = [1,2,3,4,5] a) Define (in plain English) subproblems to be solved. (2 pts) b) Write down the base cases (1 Points) c) Write down the recurrence relation (3 Points) d) Write down the pseudoCode: (4 Points) e) Write down the time complexity and space complexity (2 Points)
1. [10 points] Design a data structure that has the following properties (assume n elements in the data structure, and that the data structure properties need to be preserved at the end of each operation): a. • Find median takes O(1) time b. • Insert takes O(log n) time Do the following: 1. Describe how your data structure will work. 2. Give algorithms that implement the Find-Median() and Insert() functions. 3. [15 points] Prove or disprove the following: • T is a spanning tree on an undirected graph G = (V, E). Edge costs in G are NOT guaranteed to be unique. If every edge in T belongs to SOME minimum cost spanning trees in G, then T is itself a minimum cost spanning tree. • Consider two positively weighted graphs G = (V, E, w) and G′ = (V, E, w′) with the same vertices V and edges E such that, for any edge e in E, we have w′(e) = w(e)2 For any two vertices u, v in V, any shortest path between u and v in G′is also a shortest path in G. 4. [15 points] A new startup FastRoute wants to route information along a path in a communication network, represented as a graph. Each vertex represents a router and each edge a wire between routers. The wires are weighted by the maximum bandwidth they can support. FastRoute comes to you and asks you to develop an algorithm to find the path with maximum bandwidth from any source s to any destination t. As you would expect, the bandwidth of a path is the minimum of the bandwidths of the edges on that path; the minimum edge is the bottleneck. Explain how to modify Dijkstra’s algorithm to do this. 5. [10 points] There is a stream of integers that comes continuously to a small server. The job of the server is to keep track of k largest numbers that it has seen so far. The server has the following restrictions: • It has enough memory to store up to k integers in a simple data structure (e.g. an array), and some extra memory for computation (like comparison, etc.). • The time complexity for processing one number must be better than O(k). Anything that is O(k) or worse is not acceptable. Design an algorithm on the server to perform its job with the requirements listed above. Note: you will receive 10 points if your algorithm is efficient. This means your method must do better than the naive solution, where the weight of each node is set to 0 per time and the Dijkstra’s algorithm is applied every time for lowest-cost path searching. You will receive full points (15 points) if your algorithm has the same run time complexity as Dijkstra’s algorithm. 7. [10 points] When constructing a binomial heap of size n using n insert operations, what is the amortized cost of the insert operation? Find using the accounting method.
1. Consider a collection of n ropes which have lengths L1, L2, …, Ln, respectively. Two ropes of length L and L′ can be connected to form a single rope of length L + L′, and doing so has a cost of L + L′. We want to connect the ropes, two at a time, until all ropes are connected to form one long rope. Design an efficient algorithm for finding an order in which to connect all the ropes with minimum total cost. You do not need to prove that your algorithm is correct. (20 points)2. Suppose you want to drive from USC to Santa Monica. Your gas tank, when full, holds enough gas to drive p miles. Suppose there are n gas stations along the route at distances d1 ≤ d2 ≤ … ≤ dn from USC. Assume that the distance between any neighboring gas stations, and the distance between USC and the first gas station, as well as the distance between the last gas station and Santa Monica, are all at most p miles. Assume you start from USC with the tank full. Your goal is to make as few gas stops as possible along the way. Design an efficient algorithm for determining the minimum number of gas stations you must stop at to drive from USC to Santa Monica. Prove that your algorithm is correct. Analyze the time complexity of your algorithm. (25 points)3. Suppose you are given two sequences A and B of n positive integers. Let ai be the i-th number in A, and let bi be the i-th number in B. You are allowed to permute the numbers in A and B (rearrange the numbers within each sequence, but not swap numbers between sequences), then you receive a score of ∏1 ≤ i ≤ n aibi. Design an efficient algorithm for permuting the numbers to maximize the resulting score. Prove that your algorithm maximizes the score and analyze your algorithm’s running time (25 points).5. The array A below holds a max-heap. What will be the order of elements in array A after a new entry with value 19 is inserted into this heap? Show all your work. A = {16, 14, 10, 8, 7, 9, 3, 2, 4, 1} (10 points)
Q1. What is the tight bound on worst-case runtime performance of the procedure below? Give an explanation for your answer. (10 points) int c = 0; for(int k = 0; k
Q1) Given a graph G and two vertex sets A and B, let E(A,B) denote the set of edges with one endpoint in A and one endpoint in B. The Max Equal Cut problem is defined as follows: Given an undirected graph G(V, E), where V has an even number of vertices, find an equal partition of V into two sets A and B, maximizing the size of E(A,B). Provide a factor 2-approximation algorithm for solving the Max Equal Cut problem and prove the approximation ratio for the algorithm. (15 points) Hint: Iteratively build A and B. At each step consider a pair of vertices, and put one in each of A and B to ensure they are equal. Decide which of the two vertices goes to which side to greedily maximize E(A, B) in that step. Q2) Express the problem as a integer linear programming problem to obtain the number of students to be placed in each room. You DO NOT need to numerically solve the program. (15 points) a) Define your variables. b) Write down the objective function. c) Write the constraints. Q3) Write down the problem of finding a Min-s-t-Cut of a directed network with source s and sink t as problem as an Integer Linear Program. (20 pts) a) Define your variables. b) Write down the objective function. c) Write the constraints. Ungraded problems Q4) Suppose you have a knapsack with maximum weight W and maximum volume V . We have n dividable objects. Each object i has value mi, weights wi and takes vi volume. Now we want to maximize the total value in this knapsack, and at the same time We want to use up all the space (volume) in the knapsack. Formulate this problem as a linear programming problem. You DO NOT have to solve the resulting LP. Q5) A Max-Cut of an undirected graph G = (V,E) is defined as a cut Cmax such that the number of edges crossing Cmax is the maximum possible among all cuts. Consider the following algorithm. i) Start with an arbitrary cut C. ii) While there exists a vertex v such that moving v from one side of C to the other increases the number of edges crossing C, move v and update C. Prove that the algorithm is a 2-approximation, that is the number of edges crossing Cmax is at most twice the number crossing C.
Q2: The k-cycle-decomposition problem for any k > 1 works as follows. The input consists of a connected graph G=(V, E) and k positive integers a1, …, ak < |V|. The goal is to determine whether there exist k disjoint cycles of sizes a1, …, ak respectively, s.t., each node in V is contained in exactly one cycle. Show that this problem is NP-complete (for any k > 1). (20 pts) Q3. Given a graph G = (V, E) with an even number of vertices as the input, the HALF-IS problem is to decide if G has an independent set of size |V| / 2. Prove that HALF-IS is in NP-Complete. (20pts) Ungraded Problems Q4. In a certain town, there are many clubs, and every adult belongs to at least one club. The town’s people would like to simplify their social life by closing off as many clubs as possible, but they want to make sure that everyone will still belong to at least one club afterwards. Formally the Redundant Clubs problem has the following input and output. INPUT: List of people; list of clubs; list of members of each club; number K. OUTPUT: Yes if there exists a set of K clubs such that, after removing all these K clubs, each person still belongs to at least one club. No otherwise. Prove that the Redundant Clubs problem is NP-Complete. (20pts) Q5. You are given a directed graph G=(V,E) with weights on its edges e∈E. The weights can be negative or positive. The Zero-Weight-Cycle Problem is to decide if there is a simple cycle in G so that the sum of the edge weights on this cycle is exactly 0. Prove that this problem is NP-complete. (20pts) Hint: Use the Subset-Sum Problem
Q1) (20pts) Given a graph G = (V, E) and two integers k, m, a clique is a subset of vertices such that every two distinct vertices in the subset are adjacent. a) The Clique problem asks: Given a graph G, and a number k ≥ 0, does G have a clique of size k. Show that this problem is NP-complete. Hint: Reduce from Independent Set. b) The Dense Subgraph Problem is to determine if given graph G, and numbers k, m ≥ 0, does there exist a subgraph G′ = (V′, E′) of G, such that V′ has at most k vertices and E′ has at least m edges. Prove that the Dense Subgraph Problem is NP-Complete. Hint: Use a reduction from the Independent Set problem to show NP-hardness Hint: If x, y, and z are variables, note that there are eight possible clauses containing them: (x ∨ y ∨ z),(!x ∨ y ∨ z),(x∨!y ∨ z),(x ∨ y∨!z),(!x∨!y ∨ z),(!x ∨ y∨!z),(x∨!y∨!z),(!x∨!y∨!z) Think about how many of these are true for a given assignment of x, y, and z. 4) Consider the vertex cover problem that restricts the input graphs to be those where all vertices have even degree. Call this problem VC-EDG. Show that VC-EDG is NP-complete. (15pts) UNGRADEDPROBLEMS Q5: Let S be an NP-complete problem, and Q and R be two problems whose classification is unknown (i.e. we don’t know whether they are in NP, or NP-hard, etc.). We do know that Q is polynomial time reducible to S and S is polynomial time reducible to R. Mark the following statements True or False based only on the given information, and explain why. (i) Q is NP-complete (4pts) (ii) Q is NP-hard (4pts) (iii) R is NP-complete (4pts) (iv) R is NP-hard (4pts)
