Design and Analysis of Algorithms

1. Frame a tabulation listing the problems discussed in Unit I and II with the time complexity of each problem.( Rem, CO1,CO2) 2. Multiply these numbers 981*1234 using Divide and conquer Concept and analyze its efficiency (App,CO2) 3. A graphic designer is working on a project that involves manipulating large images. The designer needs to perform matrix multiplications to apply transformations to the images. If the matrices are 1024x1024, and the standard matrix multiplication algorithm takes O(n^3) time, how much faster would Strassen's algorithm be?(Ana,CO2) 4. A thief has a knapsack that can hold a maximum weight of 8 kg. The thief wants to steal the following items: Item Weight Value Laptop 3 1000 Jewelry 2 800 Camera 1 400 Cash 2 600 Using dynamic programming, determine the optimal subset of items to include in the knapsack to maximize the total value while not exceeding the weight capacity.(App,CO3) 5. Using Warshall’s Algorithm construct the Transitive Closure of the directed graph shown below (App,CO3)

Design and Analysis of Algorithms

Case Study Scenarios & Questions: (CO5,App/Ana) 1. Resource Allocation/Scheduling (e.g., Project Management): Scenario: A company needs to schedule tasks with deadlines and dependencies. Questions: Design a greedy algorithm for task scheduling. Analyze its time complexity. Is it optimal? What if tasks have varying weights/profits? (Leads to Knapsack/DP). 2. Data Matching & Recommendation Systems (e.g., HR/Marketing): Scenario: A promotion decision relies on an algorithm, but internal candidates seem better. Questions: How does the algorithm work? What are its inputs (features)? What biases might exist (e.g., gender, race)? How to balance algorithmic efficiency with human fairness and ethical considerations?. 3. Risk Assessment (e.g., Criminal Justice): Scenario: Using COMPAS software for recidivism risk scores. Questions: Analyze the algorithm's inputs, outputs, and accuracy. Discuss the ethical implications of disproportionate minority risk classification. How do judges use (or misuse) these scores?. 4. Network Optimization (e.g., GIS/Logistics): Scenario: Finding the cheapest route across varying terrain. Questions: Apply Dijkstra's or Prim's algorithm. How does friction of distance affect the cost function? How to optimize for multiple criteria (cost, time)?. 5. Data Analysis (e.g., Microarray/Genomics): Scenario: Analyzing large datasets of gene expression. Questions: What algorithms are used for clustering or pattern finding? How to handle Big Data?.