The document describes Experiment 1.2 from a DAA (Data Structures and Algorithms Analysis) lab course. The experiment aims to develop a program to calculate power (x,n) with O(log n) time complexity using dynamic programming. The procedure involves initializing a result variable, calculating powers of the base number x by repeatedly squaring and multiplying based on the binary representation of the exponent n, and returning the final result. Sample code implementing this recursive power function is provided. The time complexity is analyzed to be O(log n).
The document describes Experiment 1.2 from a DAA (Data Structures and Algorithms Analysis) lab course. The experiment aims to develop a program to calculate power (x,n) with O(log n) time complexity using dynamic programming. The procedure involves initializing a result variable, calculating powers of the base number x by repeatedly squaring and multiplying based on the binary representation of the exponent n, and returning the final result. Sample code implementing this recursive power function is provided. The time complexity is analyzed to be O(log n).
The document describes Experiment 1.2 from a DAA (Data Structures and Algorithms Analysis) lab course. The experiment aims to develop a program to calculate power (x,n) with O(log n) time complexity using dynamic programming. The procedure involves initializing a result variable, calculating powers of the base number x by repeatedly squaring and multiplying based on the binary representation of the exponent n, and returning the final result. Sample code implementing this recursive power function is provided. The time complexity is analyzed to be O(log n).
The document describes Experiment 1.2 from a DAA (Data Structures and Algorithms Analysis) lab course. The experiment aims to develop a program to calculate power (x,n) with O(log n) time complexity using dynamic programming. The procedure involves initializing a result variable, calculating powers of the base number x by repeatedly squaring and multiplying based on the binary representation of the exponent n, and returning the final result. Sample code implementing this recursive power function is provided. The time complexity is analyzed to be O(log n).
Download as DOCX, PDF, TXT or read online from Scribd
Download as docx, pdf, or txt
You are on page 1/ 4
Course Name: DAA Lab
INDEX
S. No. Experiment Date Conduct Viva Worksheet Total Remarks
(12) (10) (8) (30)
1 Experiment 1.1: Analyze if
stack Isempty, Isfull and if elements are present then return top element in stacks using templates and also perform push and pop operation in stack. 2 Experiment 1.2: Develop a program for implementation of power function and determine that complexity should be O(log n) . 3 Experiment 1.3: Evaluate the complexity of the developed program to find frequency of elements in a given array. 4 Experiment 1.4: i. Apply the concept of Linked list and write code to Insert and Delete an element at the beginning and end of Singly Linked List. ii. Apply the concept of Linked list and write code to Insert and Delete an element at the beginning and at end in Doubly and Circular Linked List. 5 Experiment 2.1: Sort a given set of elements using the Quick sort method and determine the time required to sort the elements. Repeat the experiment for different values of n, the number of elements in the list to be sorted. The elements can be read from a file or can be generated using the random number generator. 6 Experiment 2.2 Develop a program and analyze complexity to implement subset-sum problem using Dynamic Programming. 7 Experiment 2.3: Develop a program and analyze complexity to implement 0-1 Knapsack using Dynamic Programming. 8 Experiment 3.1: Develop a program and analyze complexity to do a depth- first search (DFS) on an undirected graph. Implementing an application of DFS such as (i) to find the topological sort of a directed acyclic graph, OR (ii) to find a path from source to goal in a maze 9 Experiment 3.2: Develop a program and analyze complexity to find shortest paths in a graph with positive edge weights using Dijkstra’s algorithm. 10 Experiment 3.3: Develop a program and analyze complexity to find all occurrences of a pattern P in a given string S. Course Name: DAA Lab
Experiment 1.2
Aim: Develop a program for implementation of power function and determine that complexity should be O(log n).
Objectives: To implement power function with O(logn) time complexity.
Input/Apparatus Used: Online GDB Complier
Procedure/Algorithm: a) Start with the base number base and the exponent exp. b) Initialize a variable result to 1 to store the final result. c) While exp is greater than 0, do the following: • If exp is odd, multiply result by base. • Sqaure base • Halve exp by integer division d) Return the value of result as the power of the number.
Sample Code: #include <iostream> using namespace std; int power(int x, unsigned int n) { int temp; if (n == 0) return 1; temp = power(x, n / 2); if (n % 2 == 0) Name: UID: Course Name: DAA Lab return temp * temp; else return x * temp * temp; } int main() { int x; cout<<"Enter value of x"<<endl; cin>>x; int n; cout<<"Enter value of n"<<endl; cin>>n; cout<<power(x,n); return 0; }
Observations/Outcome:
Time Complexity: Time complexity is O(log n) while computing power (x,n)
