York University ITEC 2620N Assignment 1: Sorted List and Tree Solution

This document presents the solution to Assignment 1 for ITEC 2620N, a course at York University. The assignment focuses on fundamental programming concepts and data structures. Part A of Question 1 addresses the time complexity of adding elements to a sorted linked list, discussing insertion at the head, tail, and within the list. Part B of Question 1 involves drawing a binary tree based on its in-order and post-order traversals. Question 2 delves into the time complexity analysis of a method designed to determine the uniqueness of elements within an array, with a detailed explanation of the algorithm's efficiency. The document also includes references to relevant academic sources.

Running head: PROGRAMMING
Programming
Name of the Student
Name of the University
Author Note:

1PROGRAMMING
Table of Contents
Answer to Question 1..........................................................................................................2
Part A...............................................................................................................................2
Part B...............................................................................................................................2
Answer to Question 2..........................................................................................................3
References............................................................................................................................4

2PROGRAMMING
Answer to Question 1
Part A
Ans:
Insertion of new element in the sorted linked list requires updating the head pointer
newnode->next = head;
head = newnode;
Insertion at the tail requires to place a pointer on the tail element so that element can be
easily added and updated at the tail pointer
tail->next = newnode;
tail = newnode;
Insertion of new element in the sorted link list requires O (1) time if all the place of
insertion is already known. Considering the sorted linked list, the element can be inserted
without proper acknowledgement where the inserted element will go. It will take O (n) times if
search is to carried on the whole list for finding where the elements goes.
Part B
The in-order traversal of a binary tree processes the nodes in the order
ATAA. The post-order traversal of the same binary tree processes the nodes in the order
AATA. The final tree is given below:

3PROGRAMMING
Fig 1: Tree Traversals
(Source: Created by Author)
Answer to Question 2
The best way to do the sorting is to complete the whole thing in O (nLogn) time. Apart
from this, hashing can be done for worst complexity of O(n) which requires some sort of extra
space. The main goal should be make use of bitwise operator for this particular solution which is
O(n) time and make use of O (1) for extra space. The complete solution is not that much easy

4PROGRAMMING
like XOR solution. It is mainly done so that all the required elements tend to appear for odd
number of times in this case. The idea can be taken from here. A loop should run for all the
required elements in this array. After the competition of each iteration two required values are
taken into consideration like ones and twos.
Ones: the bits tend to appear in 1st time or 4th time or 7th time
Twos: the bit tends to appear in 2nd time or 5th time or 8th time.
Ones and twos are mainly initialized as a zero. For each of the element in the given array
the common set of bits are in the new element and in the previous value of one. The common set
bits are actually some bits which should be added to twos.

5PROGRAMMING
Bibliography
Lemire, D., Boytsov, L. and Kurz, N., 2016. SIMD compression and the intersection of sorted
integers. Software: Practice and Experience, 46(6), pp.723-749.
Parmar, V.P. and Kumbharana, C.K., 2015. Comparing Linear Search and Binary Search
Algorithms to Search an Element from a Linear List Implemented through Static Array,
Dynamic Array and Linked List. International Journal of Computer Applications, 121(3).
Russell, S.J. and Norvig, P., 2016. Artificial intelligence: a modern approach. Malaysia; Pearson
Education Limited.
Sajana, T., Rani, C.S. and Narayana, K.V., 2016. A survey on clustering techniques for big data
mining. Indian Journal of Science and Technology, 9(3).