Year / University: Fall 2009 / IIIT-B
Grade: A
Instructor: Prof. G.N.S Prasanna
Textbooks:
Introduction to Algorithms. by Cormen, Leiserson and Rivest.
The Art of Computer Programming. by Donald Knuth.
Numerical Recipes. by Press, et al.
Following are the assignments and projects done as part of this course.
Computation vs Disk Access Time Comparison Insertion Sort / Merge Sort / Matrix Multiplication
Performance Evaluation of Fibonacci Series Computation (using Matrix form)
Finding the Shortest Path Using Ant Colony Optimization
The project aims to find the shortest path between two objects in the presence of obstacles when the coordinates one of the objects is unknown. We solve this by simulating the behavior of Ants in finding food. When an ant returns to its colony after finding food, it lays down a trail of chemical called pheromone along its path which attracts other ants to follow the trail. The pheromone evaporates over time and eventually, the trails along all paths except the shortest path (may not be the global minimum) evaporates. This causes almost all ants to follow the current shortest path until another ant found an even shorter path (by wandering randomly). The simulation reports the length of the shortest path found after a fixed number of iterations. Our results show the error to be less than one percent of the optimal solution with a reasonable number of iterations.
Downloads: Source Code
Our implementation provides several tunable parameters that give the simulation a finer control. These parameters can be modified in the source file: arun/aco/GlobalSettings.java. Following table lists some of the parameters and their description.
In our simulation, the GUI displays ants as black dots, food as blue rectangular block, pheromone trails change their color as it evaporates, where red trails imply highest intensity which fades away as it evaporates. Obstacles are shown as green rectangular block. The number of ants, location of food and the obstacles are configurable in the source code.
Efficient Implementation of a Sorting Algorithm
In this assignment, we implemented a heap sort both using C and Java. The programs were then evaluated with large inputs of 1 - 10 million numbers.
Downloads: Source Code ( C ) Readme Test Case Source Code (Java)
Computation vs Disk Access Time Comparison Insertion Sort / Merge Sort / Matrix Multiplication
In this assignment, we aim to find the dominating factor between computation time and disk access time for three different algorithms - insertion sort, merge sort and matrix multiplication. We found that the computation time is the dominant factor for insertion sort and matrix multiplication, whereas the disk access time was the dominant factor for merge sort.
Downloads: Excel Charts
Performance Evaluation of Fibonacci Series Computation
This is a homework based on a lecture from Prof. Muralidhara V.N as part of the Algorithms course. He presented three different approaches to find the Fibonacci series - Standard recursion, Iterative and Matrix form. I implemented these approaches with the aim to determine which approach performs the best, in terms of time and memory in computing the highest number in the series.
Downloads: Source Code
Matlab Assignments
The purpose of this assignment is to effectively use the Matlab tool to solve complex mathematical problems like Fourier transform, SVD decomposition, entropy conparison, etc.
Downloads: Questions Source Code Output Plots
MS Excel Assignments
The purpose of this assignment was to improve our fluency with MS Excel and at the same time understand its limitations with respect to both integer number precision and floating point IEEE 754 standard.
Downloads: Source Code
CPLEX Assignment
In this assignment we used the CPLEX tool to solve certain optimization problems using linear programming. The software allows users to write a script in which we can specify the constraints and objective function. The solver then executes the script and finds a set of local and globally optimal solutions.
Downloads: Questions Source Code
Video Lecture Annotation
Annotated the lecture session covering graph traversal and MST algorithms - Kruskal's and Prim's. Detailed annotation of the video and added subtitles, where the audio of the professor was not clear. Created an animation for the opening screen. Also created a credits video template where a picture of each group member appears.