Introduction to Information Technology

Two propositions are logically equivalent when they always have the same truth value in every possible case — that is, their truth tables are identical.

Let $p$: "An integer is even" and $q$: "It is odd".

"Not even" is $\neg p$, so the statement "If an integer is not even, then it is odd" is

$\neg p \rightarrow q$

The general term in the expansion of $(x+2y)^{10}$ is

$T_{r+1} = \binom{10}{r} x^{10-r}(2y)^r$

For the 7th term, $r+1=7 \Rightarrow r=6$:

$T_7 = \binom{10}{6} x^{4}(2y)^6$

$= 210 \cdot x^4 \cdot 64y^6$

$= 13440x^4y^6$

Seventh term = $\boxed{13440x^4y^6}$

A recursive algorithm is one that solves a problem by calling itself on smaller instances of the same problem, until it reaches a base case that can be solved directly.

Sum Rule: If a task can be done in one of $m$ mutually exclusive ways or in one of $n$ other mutually exclusive ways, then the total number of ways to do the task is $m + n$.

Product Rule: If a task consists of two successive steps, where the first step can be done in $m$ ways and, for each of these, the second step can be done in $n$ ways, then the total number of ways to complete the task is $m \times n$.

In permutation, the order of selection matters (e.g., arranging 3 books on a shelf); in combination, the order does not matter (e.g., choosing 3 books from a set).

A wheel graph $W_n$ is a graph with $n$ vertices formed by joining one extra vertex (the hub) to every vertex of a cycle $C_{n-1}$ (the rim). It has $2(n-1)$ edges.

Example: $W_4$ is a triangle $C_3$ (rim vertices $v_1, v_2, v_3$) with a hub $h$ joined to all three. It has 4 vertices and $3 + 3 = 6$ edges.

A game tree is a diagram that represents all possible moves and their outcomes in a game, with the initial position at the root and each branch showing a player's possible choices.

Degree of a tree: The degree of a tree is the maximum degree among all the nodes (vertices) of the tree, i.e. the highest number of children any single node has.

Example: Consider a tree with root A having children B, C, D, where B has children E and F.

• Degree of A = 3, B = 2, C = 0, D = 0, E = 0, F = 0
• Degree of the tree = max(3, 2, 0, 0, 0, 0) = 3

Any three applications of graph:

1. Social networks — modelling friendships, followers and connections between people.
2. Maps and navigation — finding shortest routes between locations (e.g., Google Maps).
3. Computer networks — representing and routing data between connected devices.

Proof by contraposition

We must show: if (n) is not even (i.e. (n) is odd), then (n^3+5) is not odd (i.e. (n^3+5) is even).

Assume (n) is odd. Then (n=2k+1) for some integer (k).

Substitute into (n^3+5):

[ n^3+5=(2k+1)^3+5 ]

[ =(2k)^3+3(2k)^2(1)+3(2k)(1)^2+1^3+5 ]

[ =8k^3+12k^2+6k+1+5 ]

[ =8k^3+12k^2+6k+6 ]

[ =2(4k^3+6k^2+3k+3) ]

Since (4k^3+6k^2+3k+3) is an integer, (n^3+5) is even, i.e. it is not odd.

Thus we have proved the contrapositive: if (n) is odd, then (n^3+5) is even. Therefore, the original statement is true — if (n^3+5) is odd, then (n) must be even. (\blacksquare)

To prove: (n^3+2n) is divisible by 3 for all (n\in \mathbb{N}).

Let (P(n): n^3+2n) is divisible by 3.

Base case: For (n=1), [ 1^3+2(1)=3 ] which is divisible by 3. So (P(1)) is true.

Induction hypothesis: Assume (P(k)) is true, i.e. [ k^3+2k=3m ] for some integer (m).

Induction step: For (n=k+1), [ (k+1)^3+2(k+1) ] [ = k^3+3k^2+3k+1+2k+2 ] [ = (k^3+2k)+3k^2+3k+3 ] [ = 3m+3(k^2+k+1) ] [ = 3\left(m+k^2+k+1\right) ] which is divisible by 3. Thus (P(k+1)) is true whenever (P(k)) is true.

Hence, by mathematical induction, (n^3+2n) is divisible by 3 for all natural numbers (n). (\blacksquare)

Pigeonhole Principle: If (n) objects are placed into (m) boxes and (n > m), then at least one box must contain more than one object. In general, if (n) objects are put into (m) boxes, at least one box contains at least (\lceil n/m \rceil) objects.

The given set is
[ {1,3,5,7,9,11,13,15} ]

The pairs that add up to 16 are: [ (1,15),\ (3,13),\ (5,11),\ (7,9) ]

So there are 4 such pairs. If we select 4 numbers, we could select exactly one number from each pair and still not get a pair adding to 16. But if we select 5 numbers, then by the pigeonhole principle, since there are only 4 pairs (boxes) and 5 selected numbers (objects), at least two selected numbers must come from the same pair. Those two numbers will add up to 16.

[ \boxed{\text{Minimum number to be selected} = 5} ]

Euclidean Algorithm to Compute GCD of Two Positive Integers

Idea: Repeatedly replace the larger number by the remainder obtained when the larger is divided by the smaller, until the remainder becomes zero. The last non-zero divisor is the GCD.

Algorithm (in words):

1. Start.
2. Read two positive integers $a$ and $b$.
3. While $b \neq 0$, repeat:
   • Set $r = a \bmod b$ (remainder of $a$ divided by $b$)
   • Set $a = b$
   • Set $b = r$
4. The GCD is the final value of $a$.
5. Display $a$ and stop.

Pseudocode:

START
  INPUT a, b
  WHILE b ≠ 0 DO
      r ← a MOD b
      a ← b
      b ← r
  END WHILE
  PRINT "GCD =", a
END

Example: For $a = 48$, $b = 18$:

Since $b = 0$, the GCD is $a = 6$.

Simple Graph

A simple graph is an undirected graph in which no two vertices are connected by more than one edge, and no edge connects a vertex to itself (no loops). In other words, between any pair of vertices there is at most one edge, and self-loops are not allowed.

Example: Three vertices A, B, C with edges AB and BC. There is only one edge between any pair and no loop — this is a simple graph.

Multi Graph

A multigraph is a graph that allows multiple (parallel) edges between the same pair of vertices. However, loops are generally not permitted in a multigraph.

Example: Vertices A and B connected by two or three separate edges (say e₁, e₂, e₃) between them. Since more than one edge joins the same pair of vertices, it is a multigraph.

Pseudo Graph

A pseudograph is a graph that allows both multiple edges between the same pair of vertices and loops (an edge from a vertex to itself).

Example: Vertices A and B joined by two parallel edges, and vertex A also having a loop e₃ from A back to A. Since it contains both a parallel edge and a loop, it is a pseudograph.

Summary

Binary Search Tree (BST)

A binary search tree is a binary tree in which every node satisfies the BST property: the value in the left subtree of a node is smaller than the node's value, and the value in the right subtree is greater than the node's value. This property holds for every node in the tree, so searching, insertion and deletion can be done in O(log n) time on average.

Construction of the BST from: 8, 3, 1, 10, 6, 14, 7

Insert each value one by one, comparing with the root and moving left (if smaller) or right (if greater).

• Insert 8 → becomes the root.
• Insert 3 → 3 < 8, so goes to the left of 8.
• Insert 1 → 1 < 8 (left), 1 < 3 (left), so goes to the left of 3.
• Insert 10 → 10 > 8, so goes to the right of 8.
• Insert 6 → 6 < 8 (left), 6 > 3 (right), so goes to the right of 3.
• Insert 14 → 14 > 8 (right), 14 > 10 (right), so goes to the right of 10.
• Insert 7 → 7 < 8 (left), 7 > 3 (right), 7 > 6 (right), so goes to the right of 6.

The resulting binary search tree is:

            8
          /   \
         3     10
        / \      \
       1   6      14
            \
             7

Inorder traversal check: 1, 3, 6, 7, 8, 10, 14 — the values come out in ascending order, which confirms the tree is a valid BST.

Let the propositions be:

• (p): You send me an e-mail message.
• (q): I will finish writing the program.
• (r): I will go to sleep early.
• (s): I will wake up feeling refreshed.

Hypotheses:

1. (p \to q) (If you send me an e-mail message, then I will finish writing the program)
2. (\neg p \to r) (If you do not send me an e-mail message, then I will go to sleep early)
3. (r \to s) (If I go to sleep early, then I will wake up feeling refreshed)

Conclusion to prove: (\neg q \to s) (If I do not finish writing the program, then I will wake up feeling refreshed)

Proof:

Explanation:

• From (p \to q), its contrapositive (\neg q \to \neg p) is logically equivalent.
• Chaining (\neg q \to \neg p) with (\neg p \to r) gives (\neg q \to r).
• Chaining (\neg q \to r) with (r \to s) gives (\neg q \to s).

Thus the three hypotheses validly lead to the conclusion: If I do not finish writing the program, then I will wake up feeling refreshed. (\blacksquare)

Chinese Remainder Theorem:
If (m_1,m_2,\dots,m_n) are pairwise relatively prime positive integers, then the system [ x\equiv a_1\pmod{m_1},\quad x\equiv a_2\pmod{m_2},\quad \dots,\quad x\equiv a_n\pmod{m_n} ] has a unique solution modulo (M=m_1m_2\cdots m_n).

The solution is [ x\equiv a_1M_1y_1+a_2M_2y_2+\cdots+a_nM_ny_n\pmod M, ] where [ M_i=\frac{M}{m_i} ] and (y_i) is the inverse of (M_i) modulo (m_i).

Given: [ x\equiv 2\pmod 3,\qquad x\equiv 1\pmod 4,\qquad x\equiv 3\pmod 5. ]

Here, [ M=3\cdot4\cdot5=60. ]

Now, [ M_1=\frac{60}{3}=20,\qquad M_2=\frac{60}{4}=15,\qquad M_3=\frac{60}{5}=12. ]

Find inverses: [ 20\equiv 2\pmod 3,\qquad 2^{-1}\equiv 2\pmod 3. ] So, [ y_1=2. ]

[ 15\equiv 3\pmod 4,\qquad 3^{-1}\equiv 3\pmod 4. ] So, [ y_2=3. ]

[ 12\equiv 2\pmod 5,\qquad 2^{-1}\equiv 3\pmod 5. ] So, [ y_3=3. ]

Thus, [ x\equiv 2\cdot20\cdot2+1\cdot15\cdot3+3\cdot12\cdot3\pmod{60} ] [ x\equiv 80+45+108\pmod{60} ] [ x\equiv 233\pmod{60} ] [ x\equiv 53\pmod{60}. ]

Therefore, all solutions are [ \boxed{x=53+60k,\quad k\in\mathbb Z} ] or [ \boxed{x\equiv 53\pmod{60}}. ]

Check: [ 53\equiv 2\pmod 3,\qquad 53\equiv 1\pmod 4,\qquad 53\equiv 3\pmod 5. ]

Hence the required solution is (\boxed{x\equiv 53\pmod{60}}).

The figure of the two graphs is not part of the question text, so the verdict depends on the graphs given. Two graphs $G_1$ and $G_2$ are isomorphic if there is a one-to-one, onto map $f: V(G_1)\to V(G_2)$ such that

$uv \in E(G_1) \iff f(u)f(v) \in E(G_2).$

Procedure

1. Compare the number of vertices and edges. If different, the graphs are not isomorphic.
2. Compare the degree sequences (sorted lists of vertex degrees). If different, not isomorphic.
3. Compare other invariants: number of connected components, number and length of cycles, and whether a vertex of a given degree is adjacent to vertices of the same degrees.
4. If all invariants agree, try to build $f$ by matching vertices of equal degree and check that every edge is preserved (compare adjacency matrices after relabelling).

Worked illustration: Let $G_1$ be the 4-cycle $a\!-\!b\!-\!c\!-\!d\!-\!a$ and $G_2$ the 4-cycle $1\!-\!3\!-\!2\!-\!4\!-\!1$. Both have 4 vertices, 4 edges and degree sequence $(2,2,2,2)$. The map $a\to1,\ b\to3,\ c\to2,\ d\to4$ preserves all edges, so they are isomorphic. By contrast, a path on 4 vertices has 3 edges and degree sequence $(2,2,1,1)$, so it is not isomorphic to the 4-cycle.

Applying steps 1 to 4 to the graphs in the figure gives the required conclusion.

Minimum spanning tree

A spanning tree of a connected weighted graph is a connected, acyclic subgraph containing all the vertices; a graph with $n$ vertices has a spanning tree of exactly $n-1$ edges. A minimum spanning tree (MST) is the spanning tree whose total edge weight is the smallest.

Kruskal's algorithm

1. Sort all edges in ascending order of weight.
2. Take the smallest edge not yet considered; add it to the tree if it does not form a cycle with the edges already chosen, otherwise reject it.
3. Repeat step 2 until $n-1$ edges are chosen.

Applying it

The figure is not part of the question text, so the method is shown on an example graph with vertices A to F. Apply the same steps to the graph in your figure.

Five edges are chosen for six vertices, so we stop. MST edges: A–C, D–F, B–E, C–F, B–C, with total weight

$1+2+3+4+5 = 15.$

1. Linear recurrence relation with constant coefficients

A recurrence relation of the form

where $c_1,c_2,\dots,c_k$ are constants and $f(n)$ is a function of $n$, is called a linear recurrence relation with constant coefficients.

(a) Linear homogeneous recurrence relation

If $f(n)=0$ for all $n$, then

is called a linear homogeneous recurrence relation with constant coefficients.

Example:

or the Fibonacci recurrence

(b) Linear non-homogeneous recurrence relation

If $f(n)\neq 0$, then

is called a linear non-homogeneous recurrence relation with constant coefficients.

Example:

or

2. Solve the recurrence relation

Given:

with

Step 1: Write the characteristic equation

Assume a solution of the form $a_n=r^n$. Then

Dividing by $r^{n-3}$,

so

Step 2: Factorise the characteristic equation

Try $r=1$:

So $(r-1)$ is a factor.

Now,

Factorising further,

Hence,

The roots are

Step 3: Write the general solution

Since the roots are distinct, the general solution is

i.e.

Step 4: Use the initial conditions

For $n=0$:

For $n=1$:

For $n=2$:

Subtract equation (1) from equation (2):

Subtract equation (1) from equation (3):

Adding equations (4) and (5):

Substitute $B=-1$ in equation (4):

Now substitute $B=-1$ and $C=3$ in equation (1):

Step 5: Final solution

Verification

For $n=0$:

For $n=1$:

For $n=2$:

Hence the solution is correct.

1. Shortest path problem

In a weighted graph, the shortest path problem is to find a path between two vertices (or from one source to all other vertices) for which the sum of edge weights is minimum. Weights may represent distance, cost or time. Dijkstra's algorithm solves it when all weights are non-negative.

2. Dijkstra's algorithm

Let $s$ be the source, $d[v]$ the current shortest distance to $v$ and $\pi[v]$ its predecessor.

DIJKSTRA(G, w, s)
1. for each vertex v: d[v] = infinity, pi[v] = NIL
2. d[s] = 0;  S = empty;  Q = V[G]
3. while Q is not empty
4.     u = vertex in Q with smallest d[u]; remove it from Q; add u to S
5.     for each neighbour v of u
6.         if d[u] + w(u,v) < d[v]
7.             d[v] = d[u] + w(u,v);  pi[v] = u

3. Application

The figure is not part of the question text, so the method is shown on an example graph with source $a$. Substitute the weights of your figure in the same table.

Edges: a–b 4, a–c 2, b–c 1, b–d 5, c–d 8, c–e 10, d–e 2, d–f 6, e–f 3.