UNIT 4: Artificial Intelligence & Java Programming

(Based on RGPV Past Exam Papers)

1.0 ARTIFICIAL INTELLIGENCE CONCEPTS

1.1 Problem Solving & Search Algorithms

1.1.1 Uninformed Search Strategies

Breadth-First Search (BFS)

• Algorithm: Explores all nodes at current depth before moving to next level. Uses a queue (FIFO).

• Properties:

  • Complete (finds solution if exists).

  • Optimal for uniform step costs.

  • Time & Space Complexity: $$\displaystyle O(b^d) $$, where $b$ = branching factor, $d$ = solution depth.

• Advantage: Guarantees shortest path.

• Disadvantage: High memory usage.

Depth-First Search (DFS)

• Algorithm: Explores as far as possible along a branch before backtracking. Uses a stack (LIFO).

• Properties:

  • Not complete in infinite-depth spaces.

  • Not optimal.

  • Time Complexity: $$\displaystyle O(b^m) $$, Space Complexity: $O(bm)$, where $m$ = max depth.

• Advantage: Low memory usage.

• Disadvantage: Can get stuck in deep non-solution branches.

[!TIP]

Exam Focus: BFS uses queue, DFS uses stack. Compare completeness and optimality in tabular form.

Comparative Analysis: BFS vs DFS

1.1.2 Informed Search Strategies

A Algorithm*

• Evaluation Function:

$$f(n) = g(n) + h(n)$$

• $g(n)$: Actual cost from start to node $n$.

• $h(n)$: Heuristic estimate from $n$ to goal.

• Properties:

  • Optimal if $h(n)$ is admissible (never overestimates true cost) and consistent (for every node $n$ and successor $n'$, $h(n) \leq c(n,n') + h(n')$).

  • Uses priority queue (min-heap) ordered by $f(n)$.

Example: 8-Puzzle Problem

• $g(n)$ = Depth of node.

• $h(n)$ = Number of misplaced tiles.

• Admissibility Check: Misplaced tiles never overestimates moves (each misplaced tile requires at least 1 move).

[!TIP]

Common Pitfall: If $h(n)$ is not admissible, A* may not be optimal.

1.1.3 Heuristic Design

Manhattan Distance Heuristic

• For grid-based problems (e.g., maze, 8-puzzle):

$$h(n) = \sum_{i=1}^{8} |x_i - x_i^{goal}| + |y_i - y_i^{goal}|$$

(Sum of horizontal + vertical distances of each tile from goal position).

• Admissible for sliding-tile puzzles (never overestimates moves).

1.1.4 Local Search Algorithms

Hill Climbing

• Steps:

  1. Evaluate current state.

  2. Generate neighbor states.

  3. Move to neighbor with best heuristic (steepest ascent).

  4. Repeat until goal or no improvement.

• Variants:

  • Steepest-ascent: Evaluate all neighbors.

  • First-choice: Move to first better neighbor.

  • Stochastic: Randomly select neighbors.

Problems in Hill Climbing

[!TIP]

Exam Question: "Explain problems in Hill Climbing" – define each with example.

1.2 Production Systems

1.2.1 Production Rules

• Structure: IF (condition) THEN (action).

  Example: IF (jug4 = 0) AND (jug3 < 3) THEN (fill jug3).

• Characteristics:

  • Modularity: Rules independent.

  • Simplicity: Easy to understand.

  • Uniformity: Same format for all knowledge.

  • Declarative: Specify what not how.

1.2.2 Problem Formulation

• State Space: Set of all possible states.

• Operators: Actions transforming state (e.g., Fill, Empty, Pour).

• Goal Test: Check if current state satisfies goal (e.g., jug4 = 2).

• Path Cost: Number of steps or resource used.

1.2.3 Classic Problems

Water Jug Problem (4-gal & 3-gal)

• State: $(x, y)$ where $x$ = water in 4-gal jug, $y$ = water in 3-gal jug.

• Operators:

  1. Fill jug completely.

  2. Empty jug.

  3. Pour from one jug to another until source empty or destination full.

• Solution Steps (to get 2 gal in 4-gal jug):

$$(0,0) \xrightarrow{\text{Fill 3-gal}} (0,3) \xrightarrow{\text{Pour 3→4}} (3,0) \xrightarrow{\text{Fill 3-gal}} (3,3) \xrightarrow{\text{Pour 3→4}} (4,2) \xrightarrow{\text{Empty 4-gal}} (0,2) \xrightarrow{\text{Pour 3→4}} (2,0)$$

8-Puzzle Problem

• State: 3x3 grid with 8 tiles + blank.

• Operators: Move blank up/down/left/right.

• Goal: Tiles in order 1-8 with blank at bottom-right.

1.3 Knowledge Representation

1.3.1 Properties of Good KR Systems

1. Representational Adequacy: Express required knowledge.

2. Inferential Adequacy: Derive new knowledge.

3. Inferential Efficiency: Derive quickly.

4. Clarity/Understandability: Human-readable.

5. Expressive Adequacy: Capture complex relationships.

1.3.2 Representation Techniques

Predicate Logic (First-Order Logic)

• Syntax:

  • Predicates: Loves(Ram, x), Person(x).

  • Quantifiers: $\forall$ (for all), $\exists$ (there exists).

  • Connectives: $\land$, $\lor$, $$\displaystyle \rightarrow $$, $\neg$.

English to Predicate Logic Conversions:

Schematic Nets (Semantic Networks)

• Structure:

  • Nodes: Objects/concepts (e.g., Cat, Animal).

  • Arcs: Relations (e.g., is-a, has-property).

• Reasoning via Inheritance:

  • Cat is-a Animal → Cat inherits breathes property from Animal.

Fuzzy Logic

• Fuzzy Set: Membership function $$\displaystyle \mu_A(x) \in [0,1] $$.

• Example: $$\displaystyle A = 1/x_1 + 0.3/x_2 + 0.5/x_3 + 0.2/x_4 $$ means $$\displaystyle \mu_A(x_1)=1 $$, $$\displaystyle \mu_A(x_2)=0.3 $$, etc.

1.4 Reasoning & Inference

1.4.1 Reasoning Directions

Forward Chaining (Data-Driven)

• Start with known facts, apply rules to infer new facts until goal reached.

• Example:

  
  Facts: Fido is a dog, Dogs bark.  
  
  Rule: IF x is a dog THEN x barks.  
  
  → Infer: Fido barks.  
  
  

• Use: Monitoring, control systems.

Backward Chaining (Goal-Driven)

• Start with goal, find rules that conclude goal, then prove antecedents.

• Example:

  
  Goal: Fido barks?  
  
  Rule: IF x is a dog THEN x barks.  
  
  → Subgoal: Is Fido a dog? (Yes from facts).  
  
  

• Use: Diagnosis, problem-solving.

Comparison:

1.4.2 Types of Reasoning

Monotonic Reasoning

• Adding knowledge never retracts conclusions.

• Example: Classical logic.

Non-Monotonic Reasoning

• Conclusions may be retracted with new evidence.

• Need: Real-world defaults (e.g., "Birds fly" unless penguin).

1.4.3 Rule-Based Inference

Resolution Technique

• Principle: Refutation by contradiction.

• Steps:

  1. Convert statements to clausal form (CNF).

  2. Negate goal.

  3. Apply resolution rule:

$$\frac{P \lor Q, \neg P \lor R}{Q \lor R}$$

4. If empty clause derived, goal proven.

Unification

• Process of making two literals identical by variable substitution.

• Example: Unify Loves(x, Ram) and Loves(John, y) → $\{x/John, y/Ram\}$.

1.5 Game Playing & Decision Making

1.5.1 Minimax Algorithm

• Game Tree: Nodes = game states, edges = moves.

• Max Nodes: AI’s turn (maximize score).

• Min Nodes: Opponent’s turn (minimize AI’s score).

• Minimax Decision:

$$\text{value}(n) = \begin{cases} \text{utility}(n) & \text{if terminal} \\ \max_{a} \text{value}( \text{successor}(n,a) ) & \text{if Max node} \\ \min_{a} \text{value}( \text{successor}(n,a) ) & \text{if Min node} \end{cases}$$

• Example: Simple tree with values – choose move leading to max of min values.

[!TIP]

Exam: Draw game tree, label min/max nodes, compute bottom-up.

1.6 Uncertainty Management

1.6.1 Fuzzy Set Theory

Given:

$$A = 1/x_1 + 0.3/x_2 + 0.5/x_3 + 0.2/x_4$$

$$B = 0.5/x_1 + 0.4/x_2 + 0.1/x_3 + 1/x_4$$

Operations:

• Union: $$\displaystyle \mu_{A \cup B}(x) = \max(\mu_A(x), \mu_B(x)) $$

$$A \cup B = 1/x_1 + 0.4/x_2 + 0.5/x_3 + 1/x_4$$

• Intersection: $$\displaystyle \mu_{A \cap B}(x) = \min(\mu_A(x), \mu_B(x)) $$

$$A \cap B = 0.5/x_1 + 0.3/x_2 + 0.1/x_3 + 0.2/x_4$$

• Difference: $$\displaystyle \mu_{A-B}(x) = \min(\mu_A(x), 1-\mu_B(x)) $$

$$A-B = 0.5/x_1 + 0.6/x_2 + 0.9/x_3 + 0.2/x_4$$

• Complement: $$\displaystyle \mu_{\neg A}(x) = 1 - \mu_A(x) $$

$$\neg A = 0/x_1 + 0.7/x_2 + 0.5/x_3 + 0.8/x_4$$

1.6.2 Probabilistic Reasoning

Bayes’ Theorem:

$$P(A|B) = \frac{P(B|A) \cdot P(A)}{P(B)}$$

• Application: Update belief about hypothesis $A$ given evidence $B$.

Bayesian Networks:

• Directed acyclic graph (DAG) with conditional probability tables (CPTs).

• Nodes = random variables, edges = direct influence.

1.7 Machine Learning & Neural Networks

1.7.1 Neural Network Learning Paradigms

1.8 Expert Systems

1.8.1 Components

1. Knowledge Base: Rules/facts.

2. Inference Engine: Forward/backward chaining.

3. User Interface: Interaction.

4. Explanation Facility: Justify conclusions.

5. Knowledge Acquisition: Tools to add rules.

1.8.2 Development Process

1. Problem selection (well-defined domain).

2. Knowledge elicitation (interviews with experts).

3. Rule-based vs. model-based representation.

1.9 Natural Language Processing (NLP)

1.9.1 Natural Language Understanding (NLU)

• Syntax Analysis: Parsing sentence structure (e.g., constituency/dependency parsing).

• Semantic Analysis: Meaning representation (e.g., logical form, word senses).

• Pragmatic Analysis: Context, speaker intent, discourse.

• Challenges:

  • Lexical Ambiguity: "Bank" (river/financial).

  • Syntactic Ambiguity: "I saw the man with the telescope."

  • Semantic Ambiguity: "Every student read a book" (same/different book?).

2.0 JAVA PROGRAMMING FOR ENTERPRISE SYSTEMS

2.1 Core Object-Oriented Concepts

2.1.2 Constructors

• Purpose: Initialize object state.

• Types:

  1. Default: No args, sets default values.

  2. Parameterized: Takes arguments.

  3. Copy Constructor: Takes object of same class.

• Overloading: Multiple constructors with different parameters.

Example: Circle Area using Constructor

class Circle {  

    double radius;  

    Circle(double r) { radius = r; }  

    double area() { return Math.PI * radius * radius; }  

}  

2.1.3 Modifiers

• static:

  • Class-level (shared by all objects).

  • Static methods cannot access instance variables.

  • Static block: Executes once when class loads.

• final:

  • Variable: Constant (cannot reassign).

  • Method: Cannot override.

  • Class: Cannot inherit.

2.1.4 Inheritance and Polymorphism

Dynamic Method Dispatch (Runtime Polymorphism)

• Superclass reference refers to subclass object.

• Overridden method called based on actual object type at runtime.

class Animal { void sound() { System.out.println("Animal sound"); } }  

class Dog extends Animal { void sound() { System.out.println("Bark"); } }  

Animal a = new Dog(); a.sound(); // Output: Bark  

Abstract Class vs Interface

2.2 Exception Handling

2.2.1 Fundamentals

• Hierarchy: Throwable → Error (system) / Exception (program).

• Checked Exceptions: Must handle (e.g., IOException).

• Unchecked Exceptions: RuntimeException subclasses (e.g., NullPointerException).

2.2.2 Keywords

• try: Block with exception-prone code.

• catch: Handles exception.

• finally: Always executes (cleanup).

• throw: Explicitly throw exception.

• throws: Declare exception in method signature.

• assert: Debugging (enable with -ea).

Example:

try { int d = 10/0; }  

catch (ArithmeticException e) { System.out.println("Divide by zero"); }  

finally { System.out.println("Cleanup"); }  

2.2.3 Custom Exceptions

class MyException extends Exception {  

    MyException(String msg) { super(msg); }  

}  

2.3 Multithreading

2.3.1 Thread Creation

• Extend Thread: Override run().

• Implement Runnable: Pass to Thread constructor (preferred).

2.3.2 Thread Lifecycle

New → Runnable → Running → Blocked/Waiting → Terminated.

2.3.3 Synchronization

• Need: Prevent race conditions (e.g., two threads updating same variable).

• synchronized:

  • Method: synchronized void method() {...}

  • Block: synchronized(obj) {...}

2.3.4 Inter-Thread Communication

• wait(): Thread waits, releases lock.

• notify()/notifyAll(): Wake waiting threads.

• Must call inside synchronized block.

Example: Producer-Consumer

synchronized void produce() {  

    while (queueFull) wait();  

    addItem(); notifyAll();  

}  

2.3.5 Example Programs

Three Threads with Different Delays:

class MyThread extends Thread {  

    int delay; String msg;  

    MyThread(String m, int d) { msg=m; delay=d; }  

    public void run() {  

        while(true) {  

            System.out.println(msg); Thread.sleep(delay*1000);  

        }  

    }  

}  

// Main: new MyThread("Hello!",1).start(); etc.  

2.4 Input/Output (I/O) Streams

2.4.1 Stream Hierarchy

• Byte Streams: InputStream/OutputStream (binary data).

• Character Streams: Reader/Writer (text, Unicode).

2.4.2 File I/O

• FileReader/FileWriter: Basic character streams.

• BufferedReader/BufferedWriter: Buffered for efficiency.

Example: Copy File

BufferedReader br = new BufferedReader(new FileReader("input.txt"));  

BufferedWriter bw = new BufferedWriter(new FileWriter("output.txt"));  

String line;  

while ((line = br.readLine()) != null) bw.write(line + "\n");  

br.close(); bw.close();  

2.5 Graphical User Interface (Swing)

2.5.1 Components

• Top-Level: JFrame, JDialog.

• Basic: JButton, JLabel, JTextField.

2.5.2 Event Handling

• Event Source: Component (e.g., button).

• Event Listener: Interface (e.g., ActionListener).

• Event Object: ActionEvent.

Example: Sum of Two Numbers

JFrame f = new JFrame();  

JTextField t1 = new JTextField(10), t2 = new JTextField(10);  

JButton b = new JButton("Add");  

b.addActionListener(e -> {  

    int sum = Integer.parseInt(t1.getText()) + Integer.parseInt(t2.getText());  

    JOptionPane.showMessageDialog(f, "Sum = " + sum);  

});  

2.6 Applets

2.6.1 Lifecycle

1. init(): Initialize (called once).

2. start(): Resume execution (called after init or when page revisited).

3. stop(): Suspend (when page hidden).

4. destroy(): Final cleanup (before garbage collection).

2.6.2 Applet vs Application

• Applet: Runs in browser, security restrictions (no file/network access without permission).

• Application: Standalone, full permissions.

2.7 Database Connectivity (JDBC)

2.7.1 Architecture

• JDBC API: Java interfaces (Connection, Statement, ResultSet).

• Driver Manager: Manages database drivers.

• JDBC-ODBC Bridge: Legacy (Type 1 driver).

2.7.2 Steps for Database Access

1. Load Driver: Class.forName("com.mysql.jdbc.Driver");

2. Establish Connection:

   
   Connection con = DriverManager.getConnection("jdbc:mysql://localhost:3306/db", "user", "pass");  
   
   

3. Create Statement:

   
   Statement stmt = con.createStatement();  
   
   // or PreparedStatement for parameters  
   
   

4. Execute Query:

   • ResultSet rs = stmt.executeQuery("SELECT * FROM table"); (SELECT)

   • int rows = stmt.executeUpdate("INSERT INTO table VALUES(...)"); (INSERT/UPDATE/DELETE)

5. Process ResultSet:

   
   while (rs.next()) {  
   
       String name = rs.getString("name");  
   
   }  
   
   

6. Close Resources: rs.close(); stmt.close(); con.close();

2.7.3 JDBC-ODBC Bridge

• Purpose: Translate JDBC calls to ODBC (for databases without native JDBC driver).

• Configuration:

  1. Configure ODBC data source (Control Panel → Administrative Tools → ODBC).

  2. Load bridge driver: Class.forName("sun.jdbc.odbc.JdbcOdbcDriver");

  3. Connection URL: "jdbc:odbc:DSNName"

2.8 Networking in Java

2.8.1 Socket Programming

• Server: ServerSocket server = new ServerSocket(port);

• Client: Socket socket = new Socket("localhost", port);

2.8.2 Streams over Sockets

// Server  

Socket client = server.accept();  

BufferedReader in = new BufferedReader(new InputStreamReader(client.getInputStream()));  

PrintWriter out = new PrintWriter(client.getOutputStream(), true);  

2.8.3 Example: Client-Server Communication

Server:

ServerSocket ss = new ServerSocket(1234);  

Socket s = ss.accept();  

BufferedReader br = new BufferedReader(new InputStreamReader(s.getInputStream()));  

PrintWriter pw = new PrintWriter(s.getOutputStream(), true);  

String msg = br.readLine();  

pw.println("Echo: " + msg);  

s.close(); ss.close();  

Client:

Socket s = new Socket("localhost", 1234);  

BufferedReader br = new BufferedReader(new InputStreamReader(s.getInputStream()));  

PrintWriter pw = new PrintWriter(s.getOutputStream(), true);  

pw.println("Hello");  

System.out.println(br.readLine());  

s.close();  

2.9 Java Beans & JNDI

2.9.1 Java Beans

• Characteristics:

  • No-arg constructor.

  • Private properties with public getter/setter (getX(), setX()).

  • Implements Serializable.

• Events: addXListener(), removeXListener().

2.9.2 Introspection

• BeanInfo Interface: Provide explicit bean information (properties, events).

• Introspector.getBeanInfo(MyBean.class): Automatically discovers getter/setter patterns.

• Use: IDE tools (e.g., NetBeans) use introspection for property editors.

2.9.3 JNDI (Java Naming and Directory Interface)

• InitialContext: Entry point for naming operations.

• Methods:

  | Method | Purpose | |--------|---------| | bind(name, obj) | Bind object to name (fails if exists) | | rebind(name, obj) | Bind/rebind (overwrite) | | lookup(name) | Retrieve object | | createSubcontext(name) | Create new context | | getAttributes(name) | Get attributes | | modifyAttributes(attrs, mods) | Modify attributes |

2.10 Memory Management

2.10.1 Garbage Collection

• Automatic: JVM reclaims memory from unreachable objects.

• System.gc() / Runtime.gc(): Hints (not guaranteed).

• finalize(): Called before GC (deprecated in Java 9+).

• Generational GC:

  • Young Generation (Eden, Survivor spaces): Short-lived objects.

  • Old Generation: Long-lived objects.

  • Minor GC (young) vs Major GC (old).

2.11 Packages & Access Protection

2.11.1 Packages

• Create: package com.example; (first statement).

• Import: import com.example.*; or specific class.

2.11.2 Access Levels

2.12 Control Flow Statements

2.12.1 Selection

• if, if-else, if-else-if, switch-case (byte, short, int, char, String, enum).

2.12.2 Iteration

• for (traditional: for(int i=0; i<n; i++); enhanced: for(int x: arr)).

• while (pre-test).

• do-while (post-test).

2.12.3 Jump

• break: Exit loop/switch.

• continue: Skip current iteration.

• return: Exit method.

Example: nth Prime Number

int count = 0, num = 2;  

while (count < n) {  

    if (isPrime(num)) count++;  

    if (count == n) System.out.println(num);  

    num++;  

}  

boolean isPrime(int n) {  

    for (int i=2; i<=Math.sqrt(n); i++) if (n%i==0) return false;  

    return true;  

}  

2.13 Miscellaneous Important Topics

2.13.1 String Class

• Immutable: Cannot change content.

• Common Methods:

  • length(), charAt(i), substring(begin, end), equals(), indexOf(), toUpperCase().

2.13.2 Arrays

• Declaration: int[] arr = new int[5];

• Multi-dimensional: int[][] matrix = new int[3][4];

2.13.3 Command Line Arguments

public static void main(String[] args) {  

    System.out.println("Args: " + args.length);  

}  

Final Exam Strategy:

1. AI Section: Focus on algorithms (A*, Minimax), conversions (predicate logic, fuzzy ops), and comparisons (BFS/DFS, forward/backward chaining).

2. Java Section: Write syntax-perfect code for:

• Multithreading (synchronization, inter-thread comm).

• JDBC steps.

• Swing event handling.

• Applet lifecycle.

3. Diagrams: Draw game trees for Minimax, state-space for water jug.

4. Definitions: Memorize key terms (admissible heuristic, monotonic reasoning, etc.).

\boxed{\text{Revise past paper questions chronologically – patterns repeat!}}