2ePx8Jx7

1\documentclass[12pt]{article}%
2\usepackage{amsfonts}
3\usepackage{fancyhdr}
4\usepackage{comment}
5\usepackage[a4paper, top=2.5cm, bottom=2.5cm, left=2.2cm, right=2.2cm]%
6{geometry}
7\usepackage{times}
8\usepackage{amsmath}
9\usepackage{changepage}
10\usepackage{amssymb}
11\usepackage{graphicx}%
12\setcounter{MaxMatrixCols}{30}
13\newtheorem{theorem}{Theorem}
14\newtheorem{acknowledgement}[theorem]{Acknowledgement}
15\newtheorem{algorithm}[theorem]{Algorithm}
16\newtheorem{axiom}{Axiom}
17\newtheorem{case}[theorem]{Case}
18\newtheorem{claim}[theorem]{Claim}
19\newtheorem{conclusion}[theorem]{Conclusion}
20\newtheorem{condition}[theorem]{Condition}
21\newtheorem{conjecture}[theorem]{Conjecture}
22\newtheorem{corollary}[theorem]{Corollary}
23\newtheorem{criterion}[theorem]{Criterion}
24\newtheorem{definition}[theorem]{Definition}
25\newtheorem{example}[theorem]{Example}
26\newtheorem{exercise}[theorem]{Exercise}
27\newtheorem{lemma}[theorem]{Lemma}
28\newtheorem{notation}[theorem]{Notation}
29\newtheorem{problem}[theorem]{Problem}
30\newtheorem{proposition}[theorem]{Proposition}
31\newtheorem{remark}[theorem]{Remark}
32\newtheorem{solution}[theorem]{Solution}
33\newtheorem{summary}[theorem]{Summary}
34\newenvironment{proof}[1][Proof]{\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
35
36\newcommand{\Q}{\mathbb{Q}}
37\newcommand{\R}{\mathbb{R}}
38\newcommand{\C}{\mathbb{C}}
39\newcommand{\Z}{\mathbb{Z}}
40
41\begin{document}
42
43\title{Theoretical Assignment 3}
44\author{Harsh Thakur 160279}
45\date{\today}
46\maketitle
47\section{Problem 1}
48Starting from the root.\newline
49\begin{verbatim}
50    int counter=0;
51    function(node,k,x){
52        if(x>node->val){
53            counter++;
54            if(counter>k){
55                return;
56            }
57        }
58        function(node->left,k,x);
59        function(node->right,k,x);
60    }
61\end{verbatim}
62Finally if counter is greater than k, that means x is greater than at least k elements then return false, otherwise returrn true.
63If we encounter a value greater than x, its subtree will not be traversed, all nodes visited will have parent node less than x, so at max the number of nodes which have value greater than x are 2(k-1)-(k-1)=k-1. Finally k-1 nodes greater than x are visited and k nodes less than x are visited.So final time complexity is O(2k-1)=O(k).
64
65\section{Problem 2}
66\subsection {}
67Using DFS starting from any random node,deleting edges that have been traversed, if the algorithm leads us to a previously visited node we can say that that the graph is cyclic.
68As a cyclic path containing V (max) nodes contains V edges, therefore the algorithm goes through V-1 edges at maximum and its time complexity is O(E+V)=O(2V)=O(V).  
69\subsection{}
70There are two conditions for a graph to be a tree-\newline
71(a) It must be acyclic.\newline
72(b) It must be connected.\newline
73From the previous part we can check if the graph is acyclic in O(V) time.\newline
74Now starting DFS from a random node we can check if at the end all nodes are visited, using a boolean array.Since before the process terminates it would have visited V-1 edges, time complexity is O(V+V-1)=O(V). The boolean array can also be examined in O(V) time, the overall time complexity remains O(V).
75\section{Problem 3}
76\subsection{Outline}
77We will generate a graph in which the nodes are the words contained in the dictionary. We will add an edge between the words which can be interchanged into one other with the allowed edits in one step. Now we know the source and destination nodes and apply Djikstra's algorithm to find the least distance.
78\subsection{Edge building}
79\subsubsection{Words of the same length}
80Consider them as strings a and b.\newline
81For these nodes to be connected the only possible operation is replacement. We will check each corresponding letter.
82\begin{verbatim}
83    int counter=0;
84    while(int i=0;i<a.length;i++){
85        if(a[i]!=b[i]{
86            counter++;
87        }
88    }
89    if(counter==1){
90        return true;
91    }
92\end{verbatim}
93\subsubsection{Words of different lengths}
94Consider them as strings a and b(a.length >b.length).\newline
95We will create a temporary string t by deleting a letter at position i and compare with b, if in the iteration of i from 0 to a.length-1, t=b then our iteration will stop and return true.
96\subsection{Finally}
97Give each edge a weight 1 and apply Dijkstra's Algorithm to find the shortest path between the source and the final node, print the path in reverse starting from the final node and then its parent node(According to Dijkstra's algorithm) and so on until source node is reached.
98\subsection{Time Complexity}
99Edge Building takes- O(c\^{}2 d)\newline
100Djiskstra Algorithm executes in O(ElogV), maximum number of edges is O(d\^{2}).\newline
101Therefore worst time complexity is O(d\^{2}logd).
102\section{Problem 4}     
10342 and 52 map to 2, 23 and 33 map to 3, 34 maps to 4 and 46 maps to 6.\newline
104Since the collision handling technique is linear probing and 52 will be inserted in any empty position after 42 same is the case with 33.\newline
105To get the table configuration as shown in the problem statement there are two possibilities.\newline
106(a)46 is inserted before 52\newline
107In this case 42, 23, 34 and 46 are inserted first in 4!=24 ways and then 52 is inserted in 1 way then 33 is inserted in 1 way.\newline
108(b)46 is inserted after 52\newline
109In this case 42,23,34 are inserted first in 3!=6 ways and then 52 is inserted in 1 way then 46 is inserted in 1 way and lastly 33 is inserted in 1 way.\newline
110So total number of ways of insertion to get the table shown =30.
111\section{Problem 5}
112
113\section{Problem 6} 
114\subsection{Preconditions}
115There are only two types of graph in which this type of traversal is possible.\newline
116(a)All nodes have even degree. If there is a way to enter it, there is a way to exit.\newline
117(b)There are exactly 2 nodes of odd degree.We start from one of the nodes and end our traversal at the other one.
118\subsection{Algorithm}
119Generate a graph where islands are nodes and bridges are edges.\newline
120The algorithm starts from the node of odd degree(if it exists otherwise any node will do).\newline
121At each iteration, choose an edge, check if the edge under consideration is deleted, it does not disconnect the graph. In other words, "bridges" are less preferred as compared to "non-bridges".The algorithm will now move to the node at the other side of this edge and delete the edge. In the end there will be no edges left and we will have traversed all the edges without repetition(because of edge deletion).
122
123       
124                       
125                       
126  
127  
128  
129  
130  
131  
132  
133  
134  
135  
136
137
138
139
140\end{document}