Algorithms Course (4th semester)

All my code is in C++

Lab 1

• direct_address.cpp - Implement direct addressing in a table.
• hashing_with_chaining.cpp - Implement hashing with chaining.
• linear_probing.cpp - Implement hashing by probing using different schemes. Take care of deleted slots and differentiate them from slots never occupied.
• queue_2stacks.cpp - Queue built using 2 stacks.
• sort_2_queues.cpp and sort_1_queue.cpp - Write a routine for changing a sequence of elements in a queue according to a specified input permutation using two temporary queues. Do the same using a single temporary queue.
• sort_2_stacks.cpp - Write a routine for changing a sequence of elements in a stack according to a specified permutation using two temporary stacks.
• conditional_queue_stack.cpp - A data structure that behaves like both stack and queue. If number of elements in it is more than 8, then deletion takes place like stack (LIFO) otherwise like queue (FIFO).
• stack_transfer.cpp - Tower of Hanoi using stacks

Lab 2

• merge-sort.cpp - Implement the standard equal-split version of merge sort.
• mergesort_sorted_grouped.cpp - Implement the scan, divide-into-maximal-monotonic-increasing-subarrays, merge variant of merge sort.
• find_rank.cpp - Consider an array A indexed from 1 to n, such that for some unknown index k, 1 <= k <= n, the minimum element is at position k. The elements are placed in increasing order rightwards, starting with the minimum at position k and wrapping around at position n and continuing from position 1 to position k−1. Find rank of an element in O(Log N) worst time.

Mid-semester

• heapsort.cpp - Implement Heapsort