Write a program to accept two numbers as input and print the sum.
Write a program to print all the elements in an array.
Write a program to search for a key in an unordered array.
Write a program to search for a key in an sorted array using Binary Search.
EL2 - Write Programs to:
Generate all fibonacci numbers less that n(integer).
Search for the first 1 in an array containing series of zeros followed by ones
EL3 - Implemenent the following:
Print the first n Fibonacci numbers 1,1,2,3,5, ... using iteration.
Given an (n x n) matrix A of integer elements, transpose the matrix
in situ (in place). Initially, use only one temporary location to exchange the elements. Then exchange integer elements without using a temporary location.
EL4 - Programs with Recursion:
Find the nth Fibonacci number using recursion. Contrast with the iterative approach.
Solve the Towers of Hanoi problem using recursion.
EL5 -Quicksort:
Create an array of 100 (or any specified number of) random integers. Use quicksort to sort these integers.
EL6 -Revision Lab:
Catch up on programs not understood or get doubts on programming clarified from TAs.
EL7 -Stacks:
Implement a stack as an array and as a linked list. The following operations should be supported - PUSH, POP, TOP(displays top of stack), DISPLAY(prints whole stack).
Midterm
EL8 -Elimination of Duplicates from a Linked List:
Create a linked list of integers and eliminate all duplicates.
Create a linked list of strings and eliminate all duplicates.
EL9 -Binary Search Tree:
Write a program to accept a sequence of numbers from user and use them to populate a Binary Search Tree.
In the above program add code to implement search, inorder traversal,preorder traversal and postorder traversals.
(Optional)Search for a key and find its successor and Predecessor
(Optional)Search for a key and delete it. The delete operation should preserve the Binary Search Tree property
EL10 -String Operations:
Write a program to read a list of strings from a file.
Sort the strings read in the step above with.
Bubble Sort
Selection Sort
Insertion Sort
EL11 -Heapsort:
Write a program to accept a sequence of unsorted numbers from user and sort them using Heapsort.
EL12 - A Simple Greedy Algorithm for Travelling Salesman Problem:
Write a greedy algorithm to find a tour (possibly suboptimal) in a complete graph using Nearest City Heuristic.
(Optional)Write a greedy algorithm to find a tour (possibly suboptimal) in a complete graph using Smallest Edge Heuristic.
(Optional)Write a program using backtracking with recursion to find the optimal tour for a input graph.
EL13 -Kth Order Statistic:
Write a program using Quicksort like partitioning logic to find the kth minimum element of an unsorted array. You must not sort the array.
Miniproject 1 - Linked List Implementation of a Stack with Constant Time
Push, Pop, and Findmin
Suppose you are implementing a stack of integers using a singly linked list. The top of the stack will be the first element in the linked list and the bottom of the stack will be the last element in the linked list. It is easy to see that both push and pop operations can be implemented easily in worst case O(1) time (that is, constant time). Suppose now that you want to implement one more operation findmin which will find and return a minimum element in the stack by maintaining an additional linked list which correctly keeps track of the minimum element all the time by suitably updating the links when a push or pop operation is performed. If it is required that the findmin operations should also have a worst case running time of O(1), then how do you implement the additional list, push operation, pop operation, and findmin operation. Note that all three operations must run in worst case constant time. Implement your idea and carry out experimentation on a set of data.
Miniproject 2 - Implementation of Skip List Data Structure
Skip list is an interesting data structure proposed by William Pugh, which enables binary search
performance to be obtained using linked lists (rather than arrays).
The objective of this miniproject
is to implement search, insert, and delete operations for the skip list data structure and
carry out experimentation on a real world data sets. For an excellent account of this data structure,
you may look up William Pugh's article "Skip List Cookbook" which is available from the web.
Miniproject 3 - Implementation of Hash Tables
Hashing is an interesting data structure which provides a way of searching for a key
in constant time on an average. It is mainly of two types, open hash tables and closed hash
tables. For a detailed description of this programming assignment,
click here.
Miniproject 4 - Huffman Coding
Suppose we have messages consisting of sequences of characters. In each message, the characters are independent and appear with a known probability in any given position; the probabilities are the same for all positions.
We wish to encode each character into a sequence of 0s and 1s so that no code for a character is the prefix of the code for any other character. This prefix property allows us to decode a string of 0s and 1s by repeatedly deleting prefixes of the string that are codes for characters.
Given a set of characters and their probabilities, the Huffman algorithm finds a code with the prefix property
such that the average length of a code for a character is a minimum.
For a detailed description of the Hufman algorithm,
click here. The Huffman code construction can be done
in an interesting and efficient way using binary trees. The purpose of this miniproject is to
implement the Huffman algorithm. A more detailed description of this miniproject
can be found here.
Miniproject 5 - Comparison of AVL Trees and Splay Trees
Numerous variants of binary search trees have been proposed over the years. Two such variants are
AVL Trees and
Splay Trees. Both these data structures
are based on rotating the given binary search trees using left rotations or right rotations or
double rotations. Understand carefully the notion of rotation of a binary search tree and
implement AVL trees and splay trees.
Miniproject 6 - Application of Heaps
The binary (min or max) heap data structure is useful in many applications: implementing
the Dijkstra's shortest path algorithm efficiently; implementing Kruskal's minimal
spanning tree algorithm efficiently; in implementing simulation packages, etc.
You have already understood the Dijkstra's algorithm and the Kruskal's algorithm.
Implement these two algorithms using heaps.
Miniproject 7 - Median of Medians Algorithm for Order Statistics
Blum, Floyd, Pratt, Rivest, and Tarzan have proposed a famous algorithm that finds the "k"th
smallest or largest element in a list of "n" elements. This algorithm finds the
"k"th element in worst case O(1) time. For details of this fascinating algorithm,
click here. The purpose
of this miniproject is to implment this algorithm.
Miniproject 8 - Optimal Solution to TSP using Branch and Bound
You have studied the branch and bound technique for finding an optimal solution to the
travelling salesman problem. Generate a complete graph with n vertices and random costs for all the edges.
Let the costs be positive integers uniformly distributed between 1 and 100.
For the above graph, compute an optimal Hamiltonian tour using the
branch and bound technique. Do not under-estimate the effort
involved in this project.
Miniproject 9 - Computing Nash Equilibria in Strategic Form Games