ESc-101 Algorithms and Programming

• EL1 - Warmup Programs
• Write a program to display "Hello World".
• 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