Search Results

The heuristic function ℎ(𝑛) in the A* algorithm should always underestimate the true cost to reach the goal from node 𝑛n to ensure that the algorithm remains both complete and optimal. This is known as the heuristic being admissible. The following are the reasons why A* algorithm must be admissible: If the heuristic is admissible (i.e., it never overestimates the true cost), A* is guaranteed to find the shortest path. This is because A* will never ignore a potentially optimal path due to an overestimated cost. A* will always terminate and find a solution if one exists when the heuristic is admissible and the cost of each step is finite. The algorithm ensures that all possible paths are considered, and the best path is selected.

A predicate logic sentence w is satisfiable if there exists some interpretation in which w is true. A predicate logic sentence is unsatisfiable (i.e., it is a contradiction ) if it is not satisfiable (in other words, there exists no interpretation in which it is true). It is valid if every interpretation is true. We know that, P implies Q can be written as, ~P ∨ Q. Therefore, the sentence becomes, ~P ∨ Q → ~P Further solving, ~P ∨ Q → ~P = ~(~P ∨ Q) ∨ ~P = P ∧ ~Q ∨ ~P = P ∨ ~P ∧ ~Q = TRUE ∧ ~Q = ~Q Now, ~Q can either be true or false. Hence, the sentence is satisfiable.

In Disjunctive Normal Form, all terms are seperated by disjunction. We know that A→B = ¬A ∨ B. Therefore, R→S can be written as ¬R ∨ S. The whole equation now becomes, (~P∨~Q) & ¬R ∨ S Further, (~P & ¬R ∨ S) ∨ (~Q & ¬R ∨ S) This is the Disjunctive Normal Form.

We know that P is true. So, ~P should be false. We also know that Q is false, so ~P ∨ Q is false. We know that R is true, so (~P ∨ Q) & R is false. We know that S is true, so S ∨ (~R & Q). Therefore, the statement essentially becomes false → true. This eventually means that the statement is false.

In artificial intelligence (AI), a conceptual graph (CG) is a formalism for representing knowledge in a structured and graph-based way. It is a type of semantic network that captures the relationships between concepts through nodes and edges. Conceptual graphs were introduced by John F. Sowa in the late 1970s as a way to represent the meaning of natural language expressions in a form that could be used for automated reasoning and knowledge processing. A conceptual graph is composed of nodes and edges that form a bipartite graph: Concept Nodes (C): Denoted by rectangles. Represents entities. Relation Nodes (R): Denoted by circles. Represents abstract concepts. Each edge in the graph connects a concept node to a relation node, and each relation node is connected to one or more concept nodes. The first step is to find the concept nodes and relation nodes. Concept Nodes: [Motorbike] represents the concept of a motorbike. [Handle] representing the concept of a handle. Relation Node: (Has) representing the relationship between the motorbike and the handle. We can also write it as: ∀x (x:Motorbike) → ∃y (y:Handle) [ (x) --(Has)--> (y) ] The same can be represented in First Order Predicate Logic as: ∀x : Motorbike(x)→∃y : Handle(y)∧Has(x,y)

While answering this questions, we have to keep in mind Contextual Dependency Actions. These are given in the table below. The chocolate is getting ATRANS, since its the transfer of ownership and not the transfer of physical location. The contextual dependency structure for this is given belo

We have been given the following question: Find whether the following set is unifiable or not. If unifiable, find the most general unifier(m.g.u.). w = {PARENTS(x, FATHER(x), MOTHER(bill)), PARENTS(bill, FATHER(bill), y)} There are three conditions for unification of two sets: Predicate symbol must be the same. Number of arguments in both statements must be identical. If two similar variables are present in the SAME expression, then unification fails. Since all three conditions are met, we can unify the above sets. PARENTS(x, FATHER(x), MOTHER(bill)) PARENTS(bill, FATHER(bill), y) In the first sentence, x can be replaced with bill and MOTHER(bill) can be replaced with y to form the second sentence. Hence, the most general unifier is m.g.u. = [x/bill,MOTHER(bill)/y]

The given question is "In the following two-ply game tree, the terminal nodes show the utility values computed by the utility function. Use the Minimax algorithm to compute the utility values for other nodes in the given game tree." Now, in minimax algorithm in the MIN nodes, we select a value from the children which is minimum. So, the value in B will be 2, C will be -1 and D will be -3. Now, in MAX node, which is A, we will select the maximum value from the direct children of the node. Hence, the value of A will be 2.

The Context Free Grammar for "Ram hit the ball" is: S → NP VP NP → N VP → V NP N → Ram ∣ ball V → hit NP → DET N DET → the Explanation for this CFG is: S is the start symbol. NP (Noun Phrase) can be a single noun (N) or a determiner (Det) followed by a noun (N). VP (Verb Phrase) is a verb (V) followed by a noun phrase (NP). N represents the nouns in the sentence ("Ram" and "ball"). V represents the verb in the sentence ("hit"). DET represents the determiner ("the").

A heuristic function is a key concept in artificial intelligence, particularly in the context of search algorithms. It is a function that estimates the cost or value of a specific state in a problem space. The primary purpose of a heuristic function is to guide the search process towards the most promising paths, thus improving the efficiency and effectiveness of the search. For example, In the A* search algorithm, a heuristic function (often denoted as ℎ(𝑛)) estimates the cost from the current node to the goal. A software agent is an autonomous computer program that performs tasks on behalf of users or other programs with some degree of independence or autonomy. Software agents operate without direct human intervention, making decisions based on predefined rules or learning from their environment. There are various types of software agents, including: Intelligent Agents: Capable of learning and adapting to new situations (e.g., recommendation systems). Mobile Agents: Can move across different networked environments to perform tasks (e.g., data collection agents). Multi-Agent Systems: Consist of multiple interacting agents that work together to solve complex problems (e.g., swarm robotics, collaborative filtering).

This is the official question paper of Design and Analysis of Algorithms of B.Sc. (Hons.) Computer Science Course at the University of Delhi. Question 1 is compulsory. Attempt any four questions from question 2 to question 8. Part of a question must be answered together. Some symbols may not be visible on mobile devices. Hence we recommend that you use a desktop to view the solutions to the questions. Download the Question Paper as PDF Question 1(a): Use master's theorem to give tight asymptotic bounds for the recurrence T(n) = 8 T(n/2) + θ(n²) View Solution Question 1(b): Discuss the running time of following snippet of code: count=0 for (i=l, i<=n, i++) for (j=1, j<=n, j=2*j) count++ View Solution Question 1(c): A team of explorers is visiting the Sahara desert. Due to the extreme heat, they need to stay hydrated and have brought n bottles of different sizes to carry water. After travelling a few kilometres, they run out of water but luckily find a water source. This water source has only L litres of water available, which is less than the combined capacity of all their bottles. They need to fill L litres of water using the minimum number of bottles. Describe a greedy algorithm to help them fill L litres of water using the minimum number of bottles. View Solution Question 1(d): Will the greedy strategy with the greedy parameter being value per unit weight of the items yield an optimal solution for the 0-1 knapsack problem? Justify. View Solution Question 1(e): Can dynamic programming be applied to all optimization problems? Why or why not? View Solution Question 1(f): Why is the worst-case running time for bucket sort θ(n²)? What changes would you make to the algorithm so that its worst-case running time becomes O(nlgn)? View Solution Question 1(g): Let G be a tree graph. Further, let A and B be the trees produced by performing BFS and DFS respectively on G. Can A and B be different trees? Why or why not? View Solution Question 1(h): Consider the following graph: Specify whether the above graph is bipartite or not. If yes, give the partition, else justify. View Solution Question 1(i): We are given a weighted graph G in which edge weights are not necessarily distinct. Can graph G have more than one minimum spanning tree (MST)? If yes, give an example, else justify. View Solution Question 1(j): Show that in any subtree of a max-heap, the root of the subtree contains the largest value occurring anywhere in that subtree. View Solution Question 2(a): Consider the scheduling problem wherein you are given a single resource and a set of requests having deadlines. A request is said to be late be late if it misses the deadline, Your goal is to minimize the maximum lateness. With respect to a schedule S, idle time is defined as the time during which the resource is idle, in between two requests. S is said to have an inversion when request i has been scheduled before j and d(i) > d(j), where d(i) and d(j) are the deadlines of the requests i and j respectively. Argue that all schedules with no idle time and no inversions have the same maximum lateness. View Solution Question 2(b): For each of the following sorting algorithms, merge sort and insertion sort, discuss whether or not it is (i) stable and (ii) in-place View Solution Question 3(a): Let G = (V,E) be a directed unweighted graph. Given two vertices s and t in V, what is the time required to determine if there exists at least one s-t path in G? Can we use the DFS algorithm to find the shortest-path distance from the s to t? If yes, justify, otherwise give a counter-example. View Solution Question 3(b): Suppose we perform a sequence of stack operations on a stack whose size never exceeds k. After every k operations, we make a copy of the entire stack for backup purposes. Show that the cost of n stack operations, including copying the stack, is O(n) by assigning suitable amortized costs to the various stack operations. View Solution Question 4(a): Show that, with the array representation for sorting an n-element heap, the leaves are the nodes indexed by floor(n/2+1), floor(n/2+2), …,n. What would be the location of the minimum element in the above heap? View Solution Question 4(b): Given an array A of n integers, you need to find the maximum sum of any contiguous subarray. For instance, the maximum sum of any contiguous subarray in the array -1, 2, 3, -2, 5, -6, 7, -8 is 9 (which is the sum of the subarray 2, 3, -2, 5, 6, 7). Complete the following Dynamic Programming solution for the above problem: DP[0] = A[0] For i = 1 to n DP[i] = max(A[i],____) View Solution Question 5(a): How many topological orderings does the following graph have? Specify all of them. View Solution Question 5(b): A student was asked to sort a list of n numbers in decreasing order. The student writes an algorithm that works iteratively as follows. In every iteration, the following two steps are done: Linear search is used to find the maximum element in the portion of the array which is not yet sorted. The maximum element found in step 1 is placed at the beginning of the not-yet-sorted portion of the array. This algorithm is given as input a list already sorted in descending order. What would be the time complexity of the algorithm on this input? Explain. View Solution Question 6(a)(i): What is the smallest possible depth of a leaf in a decision tree for a comparison sort? Name a sorting technique to which this smallest depth would correspond. View Solution Question 6(a)(ii): What is the minimum number of leaves in the decision tree for a comparison sort? Use this observation to derive a lower bound on the number of comparisons performed by a comparison sort in the worst case. View Solution Question 6(b): Show that at most 3*floor(n/2) comparisons are sufficient to find both the minimum and maximum in a given array of size n. View Solution Question 7(a): The BFS algorithm has been used to produce the shortest paths from a node s to all other nodes in a graph G. Can Dijkstra's algorithm be used in place of BFS? In a different scenario. Dijkstra's algorithm has been used to produce the shortest paths from a node s to all other nodes in a graph G'. Can BFS be used in place of the Dijkstra's algorithm? Explain your answers for both scenarios. View Solution Question 7(b): Write a pseudocode for the memoized recursive algorithm to compute the nth Fibonacci number. What would be its time complexity? View Solution END OF THE PAPER

The question is, "Given an array A of n integers, you need to find the maximum sum of any contiguous subarray. For instance, the maximum sum of any contiguous subarray in the array -1, 2, 3, -2, 5, -6, 7, -8 is 9 (which is the sum of the subarray 2, 3, -2, 5, 6, 7). Complete the following Dynamic Programming solution for the above problem: DP[0] = A[0] For i = 1 to n DP[i] = max(A[i],____)" This is the problem statement of Kadane's Algorithm. To solve the problem of finding the maximum sum of any contiguous subarray using a dynamic programming approach, we can use the following logic: Initialization: Define an array DP where DP[i] will store the maximum sum of any contiguous subarray that ends at index i. Initialize DP[0] to A[0] because the maximum sum of a subarray ending at the first element is just the first element itself. Dynamic Programming Transition: For each element A[i] (where i ranges from 1 to n-1), we need to decide whether to include it in the existing subarray (that ends at i-1) or start a new subarray from A[i]. Thus, DP[i] should be the maximum of: A[i] itself (which means starting a new subarray from A[i]) DP[i-1] + A[i] (which means extending the subarray ending at i-1 to include A[i]). So, the dynamic programming relation can be written as: 𝐷𝑃[𝑖]=max⁡(𝐴[𝑖],𝐷𝑃[𝑖−1]+𝐴[𝑖])