1. Print all anagrams of a given string.

  2. Convert a number from one base to another: C Code

  3. Program to print the size of a file (in bytes) and its contents in binary format: C Code

  4. Print the matrix in spiral order.

  5. Program to create an SLR (Simple LR) Parse table (state machine) from a CFG (Context Free Grammar): C++ Code (2011)

  6. Computer Graphics Algorithms (C++, OpenGL & GLUT):

  7. Binary tree re-construction:

    • When inorder & preorder are given: C++ code
    • When inorder & postorder are given: C++ code
  8. Adaptive A* Algorithm.

  9. Program to find the square root of a number by repeated division technique (not very efficient; divide and conquer technique): C++ Code

  10. Program to do parenthesis matching (using Stack & Tokenizer template classes): C++ Code

  11. Given string of digits like "72388" and int n, delete n characters from the string such that the resulting string contains minimal number representation; you must preserve relative position of digits. Example: if s="72388" and n=2, the answer is 238.

  12. Doubly linked list with Iterators: C++ code

  13. Merge two sorted linked lists: C++ code

  14. AVL Tree Implementation.

  15. Red-Black Tree Implementation.

  16. Static and Dynamic Huffman Encoding.

  17. Dynamic LZW Encoding.

  18. Hadoop Java Code to process a Chess Dataset (from FICS Games Database in PGN format). It was executed on Amazon EMR. Provisioning of the Hadoop cluster, running/terminating jobs and handling data transfer between EC2(VM) and S3(Object Storage) are automated by Elastic MapReduce.

  19. Handwritten Digit Recognition using Naive Bayesian classifer.

  20. Longest Increasing Subsequence (O(N log N) algorithm)

  21. Pancake Sorting Algorithm

  22. Kahn's Algorithm for Topological Sorting

  23. Kosaraju's Algorithm for finding Strongly Connected Components in a directed graph

  24. Convert a binary tree to circular doubly linked list: C++ Code

  25. Pacman Game: Developed a PacMan game that plays by itself using the minimax algorithm. The utility function uses A* search & k-means clustering (among other things). It supports multiple PacMan and ghost agents. It has a 'wormhole' feature that transports pacman agents to different locations on the board to avoid capture by the ghosts. The utility function starts using k-means clustering only when there are no dots nearby the Pacman agent. The 'k' value is calculated as sqrt(n/2) which seems to work well. (C++, OpenGL, GLUT)

  26. Convert a sorted linked list to a balanced BST (Binary Search Tree): C++ Code

  27. Given a 2D array of 0s and 1s, find a plus (+) pattern of maximum size:

  28. Trie data structure (insert & search operations):

  29. Check whether a given tree is BST (Binary Search Tree) or not: C++ Code

  30. Reverse a singly linked list in groups of a given size. For example1: Input: 1->2->3->4->5->6->7->8->NULL, size = 3, Output: 3->2->1->6->5->4->8->7->NULL. Example2: Input: 1->2->3->4->5->NULL, size = 4, Output: 4->3->2->1->5->NULL. If size = 1, no reversal happens and the list output will be the same as input: C++ code

  31. LRU Page Replacement scheme (using counters):

  32. Search for an element in a rotated and sorted array: an element in a sorted array can be found in O(log n) via binary search. But suppose we rotate a sorted array 'd' times (the value of 'd' unknown to you), how do we search for an element in O(log n) time? Assume that all the elements of the array are distinct: C++ Code

  33. Given a sorted array and a number x, write a function that counts the occurrences of x. Expected time complexity is O(log n): C++ Code

  34. Given a list of arrays, return a list of arrays, where each array is a combination of one element in each given array. Suppose the input is [[1, 2, 3], [4], [5, 6]], the output should be [[1, 4, 5], [1, 4, 6], [2, 4, 5], [2, 4, 6], [3, 4, 5], [3, 4, 6]]: C++ Code

  35. Longest Palindromic substring (expected time complexity is O(n^2) & space complexity is O(1)): C++ Code

  36. Combination sum -- given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. For example, C = [2, 3, 6, 7] & T = 7, the solution set is [2, 2, 3], [7]: C++ Code

  37. Add numbers represented as linked lists (with the most significant digit at the head; for example, 123 would be 1->2->3): C++ Code

  38. Add numbers represented as linked lists (with the least significant digit at the head; for example, 123 would be 3->2->1): C++ Code

  39. Find Longest Common Subsequece (LCS) of two given strings (Time Complexity O(mn), Space Complexity O(mn)): C++ Code

  40. Dijkstra's shortest Path Algorithm (using set and map containers):

  41. Multiply large numbers are strings (for example, "1234" * "23" = "28382"): C++ Code

  42. Given the preorder traversal of a Binary Search Tree (BST), reconstruct the tree. Expected complexity O(n):

  43. Serialize (store it in a file so that it can be later restored) and deserialize a generic binary tree: C++ Code

link="#000000" vlink="#000000" alink="#000000"