CS 102
ASSIGNMENT
Deadline - November 12, 23:59 hrs
A. Please submit Python codes for solving the following questions. Please put suitable comments
in your codes so that they are easy to understand.
B. For questions 1-6, please use the data structures mentioned before each question within [ ].
For question 7, you may use any suitable data structure.
C. Please try to optimize your algorithms as much as possible. Calculate and submit the time and
space complexities for each of the algorithms you propose.
D. Please do not copy from the internet or any other source. Suitable plagiarism checkers would
be applied and if found to be copied, the corresponding submission would receive zero marks.
E. Each submission should be a single zip/[Link] file containing all the codes and other
necessary files. From each group only one person should submit. The group number should
be mentioned in the submitted file name.
1. [STACK] A knight's tour is a sequence of moves of a knight on a chessboard such that the
knight visits every square exactly once. Standard chess rules apply. A knight can move two
squares in one direction and one square either horizontally or vertically, in either order. Given
an integer n, find a knight's tour of an n x n chessboard.
2. [QUEUE] Given a stream of characters, print the first non-repeating character for each new
character arriving in the stream. At any point there are only repeated characters/ no
non-repeating characters, print - as output. You can assume that ‘-’ will not be present as any
of the input characters.
Input: aabc Input: aac
Output: a- bb Output: a- c
3. [QUEUE] Given that integers are read from a data stream. Find the median of elements read
so far in an efficient way.
Input: 5 15 1 3
Output: 5 10 5 4
At any point, if the number of inputs seen till now are even, the median is the average of two
middle elements in the sorted stream.
[Hint: Use priority queues]
4. [LINKED LIST] Write a program to merge two unsorted linked lists. Given lists l1 = (4, 2, 7)
and l2 = (5, 1), after return from merge the list should be changed to sorted list = (1,2,4,5,7).
Input: List 1 = 3 -> 1 -> 5, List 2 = 6-> 2 -> 4
Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6
Input: List 1 = 4 -> 7 -> 5, List 2 = 2-> 1 -> 8 -> 1
Output: 1 -> 1 -> 2 -> 4 -> 5 -> 7 -> 8
5. [BINARY SEARCH TREE] Suppose, a BST is called a height balanced binary search tree if
the difference between heights of left and right subtrees is not more than one for all nodes of
the tree. Write a code to check if a given BST (supplied the inorder and preorder as input) is
height balanced or not.
6. [BINARY TREE] Write a code to find the lowest common ancestor of two given nodes in a
binary tree and the distances of those two nodes from that ancestor. Assume that the nodes
might or might not be present in the tree. So, you need to begin with locating those two nodes
in the binary tree.
7. [SEARCHING/SORTING] In an input sequence, for example (20, 30, 4, 5, 1, 42, 36, 100,
200). First arrange the numbers in a separate list according to the number of digits (for
example 20, 30, 42, 36 will be in the same group) then sort each list separately. Use the
suitable data structure and sorting algorithm. Finally display the completely sorted list.