This document contains details of experiments conducted as part of a "Design and Analysis of Algorithm Lab" course. It includes 10 experiments covering algorithms like binary search, heap sort, merge sort, selection sort, insertion sort, quick sort, knapsack problem, travelling salesman problem, minimum spanning tree (using Kruskal's algorithm), and N queen problem (using backtracking). For each experiment, it provides the objective, program code implementation, and result. The document is submitted by a student to their professor for the lab session.
The document contains 10 programs related to sorting and graph algorithms. Program 1-7 implement different sorting algorithms - insertion sort, selection sort, heap sort, quick sort, counting sort, merge sort and radix sort. Program 8 implements the greedy knapsack problem. Program 9 implements the travelling salesman problem. Program 10 implements Kruskal's algorithm to find the minimum spanning tree of a graph.
The document discusses recursion, including:
1) Recursion involves breaking a problem down into smaller subproblems until a base case is reached, then building up the solution to the overall problem from the solutions to the subproblems.
2) A recursive function is one that calls itself, with each call typically moving closer to a base case where the problem can be solved without recursion.
3) Recursion can be linear, involving one recursive call, or binary, involving two recursive calls to solve similar subproblems.
This document discusses asymptotic notations which are mathematical tools used to analyze the time and space complexity of algorithms. It introduces Big O, Big Omega, and Big Theta notations. Big O notation represents the upper bound and worst case time complexity. Big Omega notation represents the lower bound and best case time complexity. Big Theta notation defines the average time complexity of an algorithm. Examples are provided for how to determine the asymptotic notation of polynomial functions.
The document discusses algorithm analysis and asymptotic notation. It defines algorithm analysis as comparing algorithms based on running time and other factors as problem size increases. Asymptotic notation such as Big-O, Big-Omega, and Big-Theta are introduced to classify algorithms based on how their running times grow relative to input size. Common time complexities like constant, logarithmic, linear, quadratic, and exponential are also covered. The properties and uses of asymptotic notation for equations and inequalities are explained.
This document discusses sparse matrices. It defines a sparse matrix as a matrix with more zero values than non-zero values. Sparse matrices can save space by only storing the non-zero elements and their indices rather than allocating space for all elements. Two common representations for sparse matrices are the triplet representation, which stores the non-zero values and their row and column indices, and the linked representation, which connects the non-zero elements. Applications of sparse matrices include solving large systems of equations.
Prim's algorithm is used to find the minimum spanning tree of a connected, undirected graph. It works by continuously adding edges to a growing tree that connects vertices. The algorithm maintains two lists - a closed list of vertices already included in the minimum spanning tree, and a priority queue of open vertices. It starts with a single vertex in the closed list. Then it selects the lowest cost edge that connects an open vertex to a closed one, adds it to the tree and updates the lists. This process repeats until all vertices are in the closed list and connected by edges in the minimum spanning tree. The algorithm runs in O(E log V) time when using a binary heap priority queue.
The document contains 10 programs related to sorting and graph algorithms. Program 1-7 implement different sorting algorithms - insertion sort, selection sort, heap sort, quick sort, counting sort, merge sort and radix sort. Program 8 implements the greedy knapsack problem. Program 9 implements the travelling salesman problem. Program 10 implements Kruskal's algorithm to find the minimum spanning tree of a graph.
The document discusses recursion, including:
1) Recursion involves breaking a problem down into smaller subproblems until a base case is reached, then building up the solution to the overall problem from the solutions to the subproblems.
2) A recursive function is one that calls itself, with each call typically moving closer to a base case where the problem can be solved without recursion.
3) Recursion can be linear, involving one recursive call, or binary, involving two recursive calls to solve similar subproblems.
This document discusses asymptotic notations which are mathematical tools used to analyze the time and space complexity of algorithms. It introduces Big O, Big Omega, and Big Theta notations. Big O notation represents the upper bound and worst case time complexity. Big Omega notation represents the lower bound and best case time complexity. Big Theta notation defines the average time complexity of an algorithm. Examples are provided for how to determine the asymptotic notation of polynomial functions.
The document discusses algorithm analysis and asymptotic notation. It defines algorithm analysis as comparing algorithms based on running time and other factors as problem size increases. Asymptotic notation such as Big-O, Big-Omega, and Big-Theta are introduced to classify algorithms based on how their running times grow relative to input size. Common time complexities like constant, logarithmic, linear, quadratic, and exponential are also covered. The properties and uses of asymptotic notation for equations and inequalities are explained.
This document discusses sparse matrices. It defines a sparse matrix as a matrix with more zero values than non-zero values. Sparse matrices can save space by only storing the non-zero elements and their indices rather than allocating space for all elements. Two common representations for sparse matrices are the triplet representation, which stores the non-zero values and their row and column indices, and the linked representation, which connects the non-zero elements. Applications of sparse matrices include solving large systems of equations.
Prim's algorithm is used to find the minimum spanning tree of a connected, undirected graph. It works by continuously adding edges to a growing tree that connects vertices. The algorithm maintains two lists - a closed list of vertices already included in the minimum spanning tree, and a priority queue of open vertices. It starts with a single vertex in the closed list. Then it selects the lowest cost edge that connects an open vertex to a closed one, adds it to the tree and updates the lists. This process repeats until all vertices are in the closed list and connected by edges in the minimum spanning tree. The algorithm runs in O(E log V) time when using a binary heap priority queue.
Modules allow grouping of related functions and code into reusable files. Packages are groups of modules that provide related functionality. There are several ways to import modules and their contents using import and from statements. The document provides examples of creating modules and packages in Python and importing from them.
The document describes programs to implement various operations on singly linked lists including insertion, deletion, counting nodes, creating a list, traversing a list, and copying a list. It provides functions for insertion at the beginning, end, and before/after a given node. Deletion functions remove from the beginning, end, or by item value. Counting returns the total nodes or occurrences of a value. Traversal and copying print or duplicate the list.
Templates allow functions and classes to operate on generic types in C++. There are two types of templates: class templates and function templates. Function templates are functions that can operate on generic types, allowing code to be reused for multiple types without rewriting. Template parameters allow types to be passed to templates, similar to how regular parameters pass values. When a class, function or static member is generated from a template, it is called template instantiation.
This document discusses arrays in C programming. It defines an array as a collection of the same type of data elements stored in contiguous memory locations that are accessed via an index. It provides the syntax for declaring a 1-dimensional array, which specifies the type, array name, and number of elements. An example declares and initializes an integer array of size 5. The document also shows examples of summing the elements of a hardcoded and user-input array using indexing and loops.
- An array is a collection of consecutive memory locations that all have the same name and type. An array allows storing multiple values of the same type using a single name.
- Arrays in C++ must be declared before use, specifying the type, name, and number of elements. Elements are accessed using an index.
- The main advantages of arrays are that they allow storing and processing large numbers of values efficiently using a single name. Arrays also make sorting and searching values easier.
The Collections Framework (java.util)- Collections overview, Collection Interfaces, The Collection classes- Array List, Linked List, Hash Set, Tree Set, Priority Queue, Array Deque. Accessing a Collection via an Iterator, Using an Iterator, The For-Each alternative, Map Interfaces and Classes, Comparators, Collection algorithms, Arrays, The Legacy Classes and Interfaces- Dictionary, Hashtable ,Properties, Stack, Vector More Utility classes, String Tokenizer, Bit Set, Date, Calendar, Random, Formatter, Scanner
The document discusses time and space complexity analysis of algorithms. Time complexity measures the number of steps to solve a problem based on input size, with common orders being O(log n), O(n), O(n log n), O(n^2). Space complexity measures memory usage, which can be reused unlike time. Big O notation describes asymptotic growth rates to compare algorithm efficiencies, with constant O(1) being best and exponential O(c^n) being worst.
The document discusses linked lists as an alternative to arrays for storing data in memory. Linked lists allow for easy insertion and removal of nodes anywhere in the list by using pointers to link nodes together rather than storing them in contiguous memory blocks. The key aspects of linked lists covered are the node structure containing data and a pointer to the next node, initializing an empty list, traversing the list, and common operations like insertion and deletion at different positions. Different types of linked lists are also introduced.
This document discusses different types of sorting algorithms. It describes internal sorting and external sorting, with internal sorting handling all data in memory and external sorting requiring external memory. Bubble sort, selection sort, and insertion sort are briefly explained as examples of sorting methods. Bubble sort works by comparing adjacent elements and swapping if out of order, selection sort finds the minimum element and selection sort inserts elements into the sorted position. Pseudocode and examples are provided for each algorithm.
This document discusses the greedy algorithm approach and the knapsack problem. It defines greedy algorithms as choosing locally optimal solutions at each step in hopes of reaching a global optimum. The knapsack problem is described as packing items into a knapsack to maximize total value without exceeding weight capacity. An optimal knapsack algorithm is presented that sorts by value-to-weight ratio and fills highest ratios first. An example applies this to maximize profit of 440 by selecting full quantities of items B and A, and half of item C for a knapsack with capacity of 60.
Hash table in data structure and algorithmAamir Sohail
The document discusses hash tables and their use for efficient data retrieval. It begins by comparing the time complexity of different data structures for searching, noting that hash tables provide constant time O(1) search. It then provides examples of using hash tables to store student records and complaints by number. Key aspects covered include hash functions mapping data to table indices, minimizing collisions, open and closed addressing for collisions, and linked lists or probing as solutions. Types of hash functions and their parameters are defined. The document aims to explain the core concepts of hashing, hash functions, hash tables and approaches for handling collisions.
This document discusses functions and methods in Python. It defines functions and methods, and explains the differences between them. It provides examples of defining and calling functions, returning values from functions, and passing arguments to functions. It also covers topics like local and global variables, function decorators, generators, modules, and lambda functions.
This document provides information about priority queues and binary heaps. It defines a binary heap as a nearly complete binary tree where the root node has the maximum/minimum value. It describes heap operations like insertion, deletion of max/min, and increasing/decreasing keys. The time complexity of these operations is O(log n). Heapsort, which uses a heap data structure, is also covered and has overall time complexity of O(n log n). Binary heaps are often used to implement priority queues and for algorithms like Dijkstra's and Prim's.
This document discusses arrays in C++. It begins by introducing arrays and their need, then describes the different types of arrays including single, two, and multi-dimensional arrays. It explains how arrays are stored in contiguous memory locations and indexed starting from zero. The document also covers array initialization, unsized array initialization, and using strings as arrays in C++.
Kickstart your data science journey with this Python cheat sheet that contains code examples for strings, lists, importing libraries and NumPy arrays.
Find more cheat sheets and learn data science with Python at www.datacamp.com.
All data values in Python are encapsulated in relevant object classes. Everything in Python is an object and every object has an identity, a type, and a value. Like another object-oriented language such as Java or C++, there are several data types which are built into Python. Extension modules which are written in C, Java, or other languages can define additional types.
To determine a variable's type in Python you can use the type() function. The value of some objects can be changed. Objects whose value can be changed are called mutable and objects whose value is unchangeable (once they are created) are called immutable.
Python functions allow for reusable code through defining functions, passing arguments, returning values, and setting scopes. Functions can take positional or keyword arguments, as well as variable length arguments. Default arguments allow functions to specify default values for optional parameters. Functions are objects that can be assigned to variables and referenced later.
Static Data Members and Member FunctionsMOHIT AGARWAL
Static data members and static member functions in C++ classes are shared by all objects of that class. Static data members are initialized to zero when the first object is created and shared across all instances, while static member functions can only access other static members and are called using the class name and scope resolution operator. The example program demonstrates a class with a static data member "count" that is incremented and accessed by multiple objects to assign increasing code values, and a static member function "showcount" that prints the shared count value.
This document provides an introduction and overview of NumPy, a Python library used for numerical computing. It discusses NumPy's origins and capabilities, how to install NumPy on Linux, key NumPy concepts like the ndarray object, and how NumPy can be used with Matplotlib for plotting. Examples are given of common NumPy operations and functions for arrays, as well as plotting simple graphs with Matplotlib.
Constructors, Destructors, call in parameterized Constructor, Multiple constructor in a class, Explicit/implicit call, Copy constructor, Dynamic Constructors and call in parameterized Constructor
The document contains programs for various sorting and searching algorithms like insertion sort, selection sort, bubble sort, linear search, binary search, etc. It also includes programs for stack operations, queue operations, tower of Hanoi, infix to postfix conversion and postfix evaluation. Each program is written in C language and contains the main logic/code to implement the given algorithm or data structure operation.
This document provides C programs to implement various data structures and algorithms. It is divided into two parts. Part A includes programs to find GCD using recursion, generate Pascal's triangle using binomial coefficients, find Fibonacci numbers recursively, implement Towers of Hanoi recursively, find the largest and smallest element in an array, write even and odd numbers to separate files, store student records in a file, and sort city names alphabetically. Part B includes programs to sort arrays using insertion, quick, merge, selection and bubble sort and perform linear and binary searches recursively. It also includes programs to implement stacks, queues, linked lists and binary trees.
Modules allow grouping of related functions and code into reusable files. Packages are groups of modules that provide related functionality. There are several ways to import modules and their contents using import and from statements. The document provides examples of creating modules and packages in Python and importing from them.
The document describes programs to implement various operations on singly linked lists including insertion, deletion, counting nodes, creating a list, traversing a list, and copying a list. It provides functions for insertion at the beginning, end, and before/after a given node. Deletion functions remove from the beginning, end, or by item value. Counting returns the total nodes or occurrences of a value. Traversal and copying print or duplicate the list.
Templates allow functions and classes to operate on generic types in C++. There are two types of templates: class templates and function templates. Function templates are functions that can operate on generic types, allowing code to be reused for multiple types without rewriting. Template parameters allow types to be passed to templates, similar to how regular parameters pass values. When a class, function or static member is generated from a template, it is called template instantiation.
This document discusses arrays in C programming. It defines an array as a collection of the same type of data elements stored in contiguous memory locations that are accessed via an index. It provides the syntax for declaring a 1-dimensional array, which specifies the type, array name, and number of elements. An example declares and initializes an integer array of size 5. The document also shows examples of summing the elements of a hardcoded and user-input array using indexing and loops.
- An array is a collection of consecutive memory locations that all have the same name and type. An array allows storing multiple values of the same type using a single name.
- Arrays in C++ must be declared before use, specifying the type, name, and number of elements. Elements are accessed using an index.
- The main advantages of arrays are that they allow storing and processing large numbers of values efficiently using a single name. Arrays also make sorting and searching values easier.
The Collections Framework (java.util)- Collections overview, Collection Interfaces, The Collection classes- Array List, Linked List, Hash Set, Tree Set, Priority Queue, Array Deque. Accessing a Collection via an Iterator, Using an Iterator, The For-Each alternative, Map Interfaces and Classes, Comparators, Collection algorithms, Arrays, The Legacy Classes and Interfaces- Dictionary, Hashtable ,Properties, Stack, Vector More Utility classes, String Tokenizer, Bit Set, Date, Calendar, Random, Formatter, Scanner
The document discusses time and space complexity analysis of algorithms. Time complexity measures the number of steps to solve a problem based on input size, with common orders being O(log n), O(n), O(n log n), O(n^2). Space complexity measures memory usage, which can be reused unlike time. Big O notation describes asymptotic growth rates to compare algorithm efficiencies, with constant O(1) being best and exponential O(c^n) being worst.
The document discusses linked lists as an alternative to arrays for storing data in memory. Linked lists allow for easy insertion and removal of nodes anywhere in the list by using pointers to link nodes together rather than storing them in contiguous memory blocks. The key aspects of linked lists covered are the node structure containing data and a pointer to the next node, initializing an empty list, traversing the list, and common operations like insertion and deletion at different positions. Different types of linked lists are also introduced.
This document discusses different types of sorting algorithms. It describes internal sorting and external sorting, with internal sorting handling all data in memory and external sorting requiring external memory. Bubble sort, selection sort, and insertion sort are briefly explained as examples of sorting methods. Bubble sort works by comparing adjacent elements and swapping if out of order, selection sort finds the minimum element and selection sort inserts elements into the sorted position. Pseudocode and examples are provided for each algorithm.
This document discusses the greedy algorithm approach and the knapsack problem. It defines greedy algorithms as choosing locally optimal solutions at each step in hopes of reaching a global optimum. The knapsack problem is described as packing items into a knapsack to maximize total value without exceeding weight capacity. An optimal knapsack algorithm is presented that sorts by value-to-weight ratio and fills highest ratios first. An example applies this to maximize profit of 440 by selecting full quantities of items B and A, and half of item C for a knapsack with capacity of 60.
Hash table in data structure and algorithmAamir Sohail
The document discusses hash tables and their use for efficient data retrieval. It begins by comparing the time complexity of different data structures for searching, noting that hash tables provide constant time O(1) search. It then provides examples of using hash tables to store student records and complaints by number. Key aspects covered include hash functions mapping data to table indices, minimizing collisions, open and closed addressing for collisions, and linked lists or probing as solutions. Types of hash functions and their parameters are defined. The document aims to explain the core concepts of hashing, hash functions, hash tables and approaches for handling collisions.
This document discusses functions and methods in Python. It defines functions and methods, and explains the differences between them. It provides examples of defining and calling functions, returning values from functions, and passing arguments to functions. It also covers topics like local and global variables, function decorators, generators, modules, and lambda functions.
This document provides information about priority queues and binary heaps. It defines a binary heap as a nearly complete binary tree where the root node has the maximum/minimum value. It describes heap operations like insertion, deletion of max/min, and increasing/decreasing keys. The time complexity of these operations is O(log n). Heapsort, which uses a heap data structure, is also covered and has overall time complexity of O(n log n). Binary heaps are often used to implement priority queues and for algorithms like Dijkstra's and Prim's.
This document discusses arrays in C++. It begins by introducing arrays and their need, then describes the different types of arrays including single, two, and multi-dimensional arrays. It explains how arrays are stored in contiguous memory locations and indexed starting from zero. The document also covers array initialization, unsized array initialization, and using strings as arrays in C++.
Kickstart your data science journey with this Python cheat sheet that contains code examples for strings, lists, importing libraries and NumPy arrays.
Find more cheat sheets and learn data science with Python at www.datacamp.com.
All data values in Python are encapsulated in relevant object classes. Everything in Python is an object and every object has an identity, a type, and a value. Like another object-oriented language such as Java or C++, there are several data types which are built into Python. Extension modules which are written in C, Java, or other languages can define additional types.
To determine a variable's type in Python you can use the type() function. The value of some objects can be changed. Objects whose value can be changed are called mutable and objects whose value is unchangeable (once they are created) are called immutable.
Python functions allow for reusable code through defining functions, passing arguments, returning values, and setting scopes. Functions can take positional or keyword arguments, as well as variable length arguments. Default arguments allow functions to specify default values for optional parameters. Functions are objects that can be assigned to variables and referenced later.
Static Data Members and Member FunctionsMOHIT AGARWAL
Static data members and static member functions in C++ classes are shared by all objects of that class. Static data members are initialized to zero when the first object is created and shared across all instances, while static member functions can only access other static members and are called using the class name and scope resolution operator. The example program demonstrates a class with a static data member "count" that is incremented and accessed by multiple objects to assign increasing code values, and a static member function "showcount" that prints the shared count value.
This document provides an introduction and overview of NumPy, a Python library used for numerical computing. It discusses NumPy's origins and capabilities, how to install NumPy on Linux, key NumPy concepts like the ndarray object, and how NumPy can be used with Matplotlib for plotting. Examples are given of common NumPy operations and functions for arrays, as well as plotting simple graphs with Matplotlib.
Constructors, Destructors, call in parameterized Constructor, Multiple constructor in a class, Explicit/implicit call, Copy constructor, Dynamic Constructors and call in parameterized Constructor
The document contains programs for various sorting and searching algorithms like insertion sort, selection sort, bubble sort, linear search, binary search, etc. It also includes programs for stack operations, queue operations, tower of Hanoi, infix to postfix conversion and postfix evaluation. Each program is written in C language and contains the main logic/code to implement the given algorithm or data structure operation.
This document provides C programs to implement various data structures and algorithms. It is divided into two parts. Part A includes programs to find GCD using recursion, generate Pascal's triangle using binomial coefficients, find Fibonacci numbers recursively, implement Towers of Hanoi recursively, find the largest and smallest element in an array, write even and odd numbers to separate files, store student records in a file, and sort city names alphabetically. Part B includes programs to sort arrays using insertion, quick, merge, selection and bubble sort and perform linear and binary searches recursively. It also includes programs to implement stacks, queues, linked lists and binary trees.
1. The document contains 10 code snippets implementing various data structures and algorithms in C/C++ like linear search, binary search, merge sort, quick sort, selection sort, bubble sort, stack implementation using array, Fibonacci series using recursion, queue implementation using array, and binary search tree operations like insertion, deletion, display and traversal.
2. The codes include functions for searching an element, sorting arrays, implementing stacks and queues as well as common operations on binary search trees.
3. Main functions are included to accept user input, call the relevant functions and output the results of operations like searching, sorting or tree traversals.
The document contains 8 questions related to data structures and algorithms in C programming. Question 1 asks to write a program to search a number from a list using linear and binary search. Question 2 asks to write a program to search a number recursively using binary search. Question 3 asks to write a program to find the factorial of a number recursively and non-recursively and compare performance. The remaining questions ask to write programs for sorting, matrix multiplication using Strassen's algorithm, minimum spanning tree using Kruskal's algorithm, and other algorithms.
This document contains some programs of C using Data structures, like Stack, LinkedList, queue, Fibonacci series, addition and multiplication of two matrices,etc.
The document contains a data structures lab manual with experiments on various data structure topics like arrays, stacks, queues, linked lists, and binary search trees. It includes C programs and explanations for inserting and deleting elements from arrays, stacks and queues. It also includes programs for matrix operations, sparse matrix representation, linear and binary searches. The experiments cover basic operations on common data structures.
The documents contain program code snippets for various sorting and searching algorithms in C programming language including selection sort, bubble sort, quick sort, merge sort, insertion sort, binary search and linear search. The programs take input from the user, implement the respective algorithms to sort or search arrays of numbers, and output the results.
The document contains questions and program code snippets related to data structures and algorithms topics.
1) The first section contains a program to remove negative values from a queue using arrays as the underlying data structure.
2) The second section shows functions to implement enqueue, dequeue and display operations on a circular queue using arrays.
3) The third section contains a program to implement an ascending priority queue as a linked list.
The document contains C code examples for various algorithms and programs including:
1. A program to check if a year is a leap year by checking if the year is divisible by 400, 100, or 4.
2. Code to add the digits of a number by extracting the remainder of successive divisions by 10.
3. Code to convert a decimal number to binary using bitwise operators.
4. Code to store the binary conversion in a string using pointers and dynamic memory allocation.
5. Programs to check for palindrome numbers, print patterns like pyramids and triangles, calculate Fibonacci series with and without recursion, perform linear and binary search of arrays, insert elements into arrays, and sort arrays using
The document provides code snippets to copy the contents of one array into another array in reverse order using different approaches like loops, pointers, and functions. It also includes code to reverse an array without using additional memory by swapping elements, and to reverse an array using pointers.
1. The document provides code snippets for implementing various sorting algorithms including heap sort, quicksort, merge sort, radix sort, bucket sort, and insertion sort. It also includes code for graph algorithms like Dijkstra's algorithm, Warshall's algorithm, and the knapsack problem using dynamic programming.
The document is a lab manual for data structures using C programming. It contains 12 programs related to data structures and algorithms including linear search, binary search, sorting algorithms like bubble sort, selection sort, insertion sort, quick sort and merge sort. Each program contains the aim, code and output for a different data structure operation or algorithm implementation. The manual provides examples and step-by-step instructions for students to complete various exercises to learn data structures and algorithms using the C programming language.
The program takes input of the order of a square matrix and its elements. It prints the elements of the matrix. It then calculates the trace of the matrix by adding the elements along the principal diagonal and prints the trace. The matrix elements are freed at the end.
The document provides solutions to various problems involving 1D arrays in C and Python. It includes programs to:
1. Reverse the elements of an array
2. Determine if an array contains all even, odd, or mixed elements
3. Count the number of even and odd elements in an array
4. Check if two arrays are equal
5. Find the sum of perfect square elements in an array
6. Find the minimum scalar product of two vectors
7. Find the smallest and largest elements in an array
8. Print all distinct elements in an array
9. Check if two arrays are disjoint
For each problem, it provides the algorithm, C and Python solutions, sample input/output,
The document provides examples of basic C programs that demonstrate fundamental programming concepts like printing values, arithmetic operations, arrays, functions, conditionals, loops, and matrices. The programs cover topics such as printing and reading integers, adding/multiplying numbers, swapping values, checking vowels/consonants, Armstrong numbers, palindromes, summing matrices, and finding the transpose of a matrix.
The document describes three different sorting algorithms: linear search, binary search, and insertion sort. Linear search iterates through an array sequentially to find a target value. Binary search divides the array in half on each step to quickly locate a value. Insertion sort iterates through the array and inserts each element into the sorted portion, building up the sorted array.
The document contains summaries of 12 programs implementing various operating system concepts like memory management algorithms, CPU scheduling algorithms, and page replacement algorithms. It includes programs for first fit, best fit, worst fit, priority scheduling, producer consumer problem, FCFS, SJF, SRTF, round robin, and page replacement algorithms like FIFO, LRU, and optimal page replacement. For each program, it lists the code, inputs/outputs and provides a brief 1-2 line description.
Similar to design and analysis of algorithm Lab files (20)
The document discusses HTML, including its definition as a markup language used to create web pages, its purpose to tell browsers how to display web page elements, and the requirements and basic implementation of HTML using tags. It also lists different versions of HTML and references for learning more.
Machine learning ppt
college presentation on Machine Learning Programming releated them. explain each and every Point in detail so. thats why they are easily to explain in the
Seminar topic on holography, they are used for final year student or 3rd year student to get selection of topic on seminar and explain in front of collage students
This document contains descriptions of several code optimization practicals:
1. It describes taking an input string, generating three-address intermediate code, and then optimizing the code by combining operations like multiplication and addition wherever possible.
2. It provides an example input and output showing the original three-address code and optimized code.
3. The code optimization involves identifying operators like * and + and generating temporary variables to store sub-expressions, combining operations wherever adjacent operations use the same operands.
Python lab manual all the experiments are availableNitesh Dubey
The document describes 10 experiments related to Python programming. Each experiment has an aim to write a Python program to perform a specific task like finding the GCD of two numbers, calculating square root using Newton's method, exponentiation of a number, finding the maximum of a list, performing linear search, binary search, selection sort, insertion sort, merge sort, and multiplying matrices. For each experiment, the algorithm and Python program to implement it is provided. The output for sample test cases is also given to verify the programs.
Web Technology Lab files with practicalNitesh Dubey
The document describes several experiments using HTML, CSS, JavaScript, Java, and SQL to develop web applications.
Experiment 1 involves creating a CV using HTML and JavaScript and displaying it on different websites. Experiment 2 creates a student details form in HTML that sends data to a database.
Experiment 3 uses JavaScript to display browser information on a web page. Experiment 4 develops a calculator application using JavaScript.
Experiment 5 defines document type definitions and cascading style sheets to style an XML document about books.
Experiment 6 connects to a database using JDBC and SQL. It retrieves and updates data, designing a simple servlet to query a book database.
Theory of automata and formal language lab manualNitesh Dubey
The document describes several experiments related to compiler design including lexical analysis, parsing, and code generation.
Experiment 1 involves writing a program to identify if a given string is an identifier or not using a DFA. Experiment 2 simulates a DFA to check if a string is accepted by the given automaton. Experiment 3 checks if a string belongs to a given grammar using a top-down parsing approach. Experiment 4 implements recursive descent parsing to parse expressions based on a grammar. Experiment 5 computes FIRST and FOLLOW sets and builds a LL(1) parsing table for a given grammar. Experiment 6 implements shift-reduce parsing to parse strings. Experiment 7 generates intermediate code like Polish notation, 3-address code, and quadruples
Here are the steps to develop a UML use case diagram for the given problem:
1. Identify the system and actors
The system is the "Supermarket Loyalty Program". The actors are "Customer" and "Supermarket Staff".
2. Identify the use cases
The key use cases are:
- Register for Loyalty Program
- Make Purchase
- View Purchase History
- Generate Prize Winners List
- Reset Purchase Entries
3. Draw and label the use case diagram
Draw oval shapes for the use cases and stick figures for the actors. Connect the actors to related use cases with lines. Label all elements.
4. Add descriptions to use cases
Principal of programming language lab files Nitesh Dubey
The document discusses the benefits of exercise for mental health. Regular physical activity can help reduce anxiety and depression and improve mood and cognitive functioning. Exercise causes chemical changes in the brain that may help alleviate symptoms of mental illness and boost overall mental well-being.
The document discusses the benefits of meditation for reducing stress and anxiety. Regular meditation practice can help calm the mind and body by lowering heart rate and blood pressure. Making meditation a part of a daily routine, even if just 10-15 minutes per day, can offer improvements to mood, focus, and overall well-being over time.
Computer Organization And Architecture lab manualNitesh Dubey
The document discusses the implementation of various logic gates and flip-flops. It describes half adders and full adders can be implemented using XOR and AND gates. Binary to gray code and gray to binary code conversions are also explained. Circuit diagrams for 3-8 line decoder, 4x1 and 8x1 multiplexer are provided along with their truth tables. Finally, the working of common flip-flops like SR, JK, D and T are explained through their excitation tables.
industrial training report on Ethical hackingNitesh Dubey
This document outlines an industrial training report on ethical hacking conducted at Alison Online Training Institute. It begins with an introduction to ethical hacking and the different types of hacking. It then discusses the role of security and penetration testers and different penetration testing methodologies. The document provides an overview of what can and cannot be done legally as an ethical hacker. It also discusses the basics of networking and what it takes to be a successful security tester.
Project synopsis on face recognition in e attendanceNitesh Dubey
This document provides a project synopsis for a face recognition-based e-attendance system. It discusses developing an automated attendance system using face recognition technology to address issues with traditional manual attendance methods, such as being time-consuming and allowing for fraudulent attendance. The objectives are to help teachers track and manage student attendance and absenteeism more efficiently. The proposed system uses face detection and recognition algorithms to automatically mark student attendance based on detecting faces in the classroom. It includes modules for image capture, face detection, preprocessing, database development, and postprocessing for recognition. Feasibility analysis indicates the technical feasibility of the system using existing technologies. Methodology diagrams show the training and recognition workflows that involve face detection, feature extraction, and classification.
This document provides an overview of the system analysis conducted for developing a Human Resource Management System (HRMS) for BittCell Systems Pvt. Ltd. Key aspects of the analysis included collecting requirements, studying the current manual system, identifying needs and limitations, and conducting a feasibility study. Tools used in the analysis included data collection, charting, dictionaries, and ER diagrams to understand information flow and relationships. The proposed HRMS aims to increase efficiency by automating employee registration, leave management, payroll, and training processes.
Industrial training report on core java Nitesh Dubey
This document discusses the installation and configuration of Java. It begins with an overview of Java and its key features like platform independence. It then discusses the Java platform and how bytecode is run by the Java Virtual Machine (JVM) across different operating systems. The document also covers installing Java, configuring variables, writing and running a basic Java program, and some Java concepts like packages, classes, objects, and modifiers.
SEWAGE TREATMENT PLANT mini project reportNitesh Dubey
This document provides information about a research project analyzing the quality of treated sewage water from shipboard sewage treatment plants. Water samples were taken from 32 ships and analyzed for parameters like coliform bacteria, suspended solids, and biological oxygen demand. The results showed that none of the treated sewage water samples met standards in the MARPOL Annex IV regulations. The document also describes regulations for sewage discharge, potential health and environmental risks of untreated sewage, and common types of sewage treatment systems used on ships.
synopsis report on BIOMETRIC ONLINE VOTING SYSTEMNitesh Dubey
The document summarizes the design of a biometric-based online voting system. It discusses including voter secrecy, authentication, vote verification and accuracy. The design goals are to safely transfer votes from the user's computer to the server and securely store cast votes. The system will use fingerprint biometrics for voter verification and only allow each verified voter to cast one vote. It will also provide manuals for voters before the election and allow vote verification before finalizing.
A.I. refers to the capability of machines to imitate intelligent human behavior. The history of A.I. began in the 1950s but has improved greatly in recent decades with advances like Sophia robot. A.I. is needed because humans have physical limitations, while robots can perform dangerous jobs. A.I. is created through a combination of programming, hardware, and sensors. It has many applications like healthcare, education, industry, finance, and customer support. While A.I. provides benefits like low error rates and replacing humans in dangerous jobs, there are also disadvantages such as high costs, lack of creativity, and potential unemployment. The future of A.I. could include automated transportation, cyborg technology
Sajjad Ali Khan submitted a seminar on object-oriented programming that covered key concepts like classes, objects, messages, and design principles. The content included definitions of objects, classes, and messages. It discussed why OOP is used and requirements for object-oriented languages like encapsulation, inheritance, and dynamic binding. Popular OO languages were listed and concepts like polymorphism were explained with examples.
Online train ticket booking system project.pdfKamal Acharya
Rail transport is one of the important modes of transport in India. Now a days we
see that there are railways that are present for the long as well as short distance
travelling which makes the life of the people easier. When compared to other
means of transport, a railway is the cheapest means of transport. The maintenance
of the railway database also plays a major role in the smooth running of this
system. The Online Train Ticket Management System will help in reserving the
tickets of the railways to travel from a particular source to the destination.
Sachpazis_Consolidation Settlement Calculation Program-The Python Code and th...Dr.Costas Sachpazis
Consolidation Settlement Calculation Program-The Python Code
By Professor Dr. Costas Sachpazis, Civil Engineer & Geologist
This program calculates the consolidation settlement for a foundation based on soil layer properties and foundation data. It allows users to input multiple soil layers and foundation characteristics to determine the total settlement.
Call Girls In Tiruppur 👯♀️ 7339748667 🔥 Free Home Delivery Within 30 Minutes
design and analysis of algorithm Lab files
1. Department of Computer Science & Engineering
Lucknow Institute of Technology
Lucknow
Session (2019-20)
Practical lab
Files
“Design and Analysis of Algorithm Lab”
(RCS 552)
Submitted To:- Submitted By:-
Ms. Arti Singh Nitesh Kumar Dubey
(Asst. professor) B.Tech ( 5th semester)
Dept. of Computer Science Computer Science & Engg.
& Engineering 1836210903
2. Index
Sr .no Experiment Signatures Remarks
1
2
3
4
5
6
7
8
9
10
Program for Recursive Binary & Linear
Search.
Program for Heap sort
Program for Merge sort
Program for selection sort
Program for Insertion sort
Program for Quick sort
Knapsack Problem using Greedy Solution
Perform Travelling Salesman Problem
Find Minimum Spanning Tree Using
Kruskal’s algorithm
Implement N Queen Problem using
Backtracking
3. Experiment:- 1
Objective: - Program for Recursive Binary & Linear Search.
Program Binary Search
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
int main()
{
int c, first, last, middle, n, search, array[100];
printf("Enter number of elements:n");
scanf("%d",&n);
printf("Enter %d integers:n", n);
for (c = 0; c < n; c++)
scanf("%d",&array[c]);
printf("Enter the value to find:n");
scanf("%d", &search);
first = 0;
last = n - 1;
middle = (first+last)/2;
while (first <= last) {
if (array[middle] < search)
first = middle + 1;
else if (array[middle] == search) {
printf("%d is present at index %d.n", search, middle+1);
break;
}
else
last = middle - 1;
middle = (first + last)/2;
}
4. if (first > last)
printf("Not found! %d is not present in the list.n", search);
return 0;
}
Program Linear search :-
#include <stdio.h>
#include <conio.h>
int search(int [], int, int);
int main()
{
int size, index, key;
int list[20]; int count = 0; int i;
printf("Enter the size of the list: ");
scanf("%d", &size);
index = size;
printf("Printing the list:n");
for (i = 0; i < size; i++)
{
list[i] = rand() % size;
printf("%dt", list[i]);
}
printf("nEnter the key to search: ");
scanf("%d", &key);
while (index > 0)
{
index = search(list, index - 1, key);
/* In an array first position is indexed by 0 */
printf("Key found at position: %dn", index + 1);
count++;
}
5. if (!count)
printf("Key not found.n");
return 0;
}
int search(int array[], int size, int key)
{
int location;
if (array[size] == key)
{
return size;
}
else if (size == -1)
{
return -1;
}
else
{
return (location = search(array, size - 1, key));
}
}
Result:- Binary search
Linear search
6. Experiment: - 2
Objective: - Program for heap sort
Program
#include<stdio.h>
#include <conio.h>
void create(int []);
void down_adjust(int [],int);
void main()
{
int heap[30],n,i,last,temp;
printf("Enter no. of elements:");
scanf("%d",&n);
printf("nEnter elements:");
for(i=1;i<=n;i++)
scanf("%d",&heap[i]);
heap[0]=n;
create(heap);
while(heap[0] > 1)
{
//swap heap[1] and heap[last]
last=heap[0];
temp=heap[1];
heap[1]=heap[last];
heap[last]=temp;
heap[0]--;
down_adjust(heap,1);
}
printf("nArray after sorting:n");
for(i=1;i<=n;i++)
printf("%d ",heap[i]);
}
10. Experiment:- 4
Objective :- Program for selection Sort
#include <stdio.h>
#include <conio.h>
int main()
{
int array[100], n, c, d, position, swap;
printf("Enter number of elementsn");
scanf("%d", &n);
printf("Enter %d integersn", n);
for (c = 0; c < n; c++)
scanf("%d", &array[c]);
for (c = 0; c < (n - 1); c++)
{
position = c;
for (d = c + 1; d < n; d++)
{
if (array[position] > array[d])
position = d;
}
if (position != c)
{
swap = array[c];
array[c] = array[position];
array[position] = swap;
}
}
11. printf("Sorted list in ascending order:n");
for (c = 0; c < n; c++)
printf("%dn", array[c]);
return 0;
}
Result:-
12. Experiment:- 5
Objective: - Program for Insertion sort
Program
#include <stdio.h>
#include <conio.h>
int main()
{
int n, array[1000], c, d, t;
printf("Enter number of elementsn");
scanf("%d", &n);
printf("Enter %d integersn", n);
for (c = 0; c < n; c++)
scanf("%d", &array[c]);
for (c = 1 ; c <= n - 1; c++) {
d = c;
while ( d > 0 && array[d-1] > array[d]) {
t = array[d];
array[d] = array[d-1];
array[d-1] = t;
d--;
}
}
printf("Sorted list in ascending order:n");
13. for (c = 0; c <= n - 1; c++) {
printf("%dn", array[c]);
}
return 0;
}
Result:-
14. Experiment:- 6
Objective:- Program for Quick Sort
Program
#include <stdio.h>
#include <conio.h>
void quicksort (int [], int, int);
int main()
{
int list[50]; int size, i;
printf("Enter the number of elements: ");
scanf("%d", &size);
printf("Enter the elements to be sorted:n");
for (i = 0; i < size; i++)
{
scanf("%d", &list[i]);
}
quicksort(list, 0, size - 1);
printf("After applying quick sortn");
for (i = 0; i < size; i++)
{
printf("%d ", list[i]);
}
printf("n");
return 0;
}
void quicksort(int list[], int low, int high)
{
int pivot, i, j, temp;
if (low < high)
{
15. pivot = low;
i = low;
j = high;
while (i < j)
{
while (list[i] <= list[pivot] && i <= high)
{ i++;
}
while (list[j] > list[pivot] && j >= low)
{ j--;
}
if (i < j)
{
temp = list[i];
list[i] = list[j];
list[j] = temp;
}
}
temp = list[j];
list[j] = list[pivot];
list[pivot] = temp;
quicksort(list, low, j - 1);
quicksort(list, j + 1, high);
}
}
Result :-
16. Experiment:- 7
Objective: - Knapsack Problem using Greedy Solution
Program
# include<stdio.h>
#include <conio.h>
void knapsack(int n, float weight[], float profit[], float capacity) {
float x[20], tp = 0;
int i, j, u;
u = capacity;
for (i = 0; i < n; i++)
x[i] = 0.0;
for (i = 0; i < n; i++) {
if (weight[i] > u)
break;
else {
x[i] = 1.0;
tp = tp + profit[i];
u = u - weight[i];
}
}
if (i < n)
x[i] = u / weight[i];
tp = tp + (x[i] * profit[i]);
printf("nThe result vector is:- ");
for (i = 0; i < n; i++)
printf("%ft", x[i]);
printf("nMaximum profit is:- %f", tp);
}
17. int main() {
float weight[20], profit[20], capacity;
int num, i, j;
float ratio[20], temp;
printf("nEnter the no. of objects:- ");
scanf("%d", &num);
printf("nEnter the wts and profits of each object:- ");
for (i = 0; i < num; i++) {
scanf("%f %f", &weight[i], &profit[i]);
}
printf("nEnter the capacityacity of knapsack:- ");
scanf("%f", &capacity);
for (i = 0; i < num; i++) {
ratio[i] = profit[i] / weight[i];
}
for (i = 0; i < num; i++) {
for (j = i + 1; j < num; j++) {
if (ratio[i] < ratio[j]) {
temp = ratio[j];
ratio[j] = ratio[i];
ratio[i] = temp;
temp = weight[j];
weight[j] = weight[i];
weight[i] = temp;
temp = profit[j];
profit[j] = profit[i];
profit[i] = temp;
}
}
}
knapsack(num, weight, profit, capacity);