# Questions tagged [decision-tree]

The tag has no usage guidance.

42 questions
Filter by
Sorted by
Tagged with
20 views

### Subtrees of decision tree for comparison sort are recurrences?

Consider sorting on $n$ distinct elements, where all $n!$ permutations are possible. I think a decision tree for comparison sort can can be uniquely characterized as $T(a,n!)$ where $a$ is the ...
33 views

### Definition of an algebraic decision tree

I am trying to understand what an algebraic decision tree is but wikipedia lacks a formal definition, just an intuition. So I need to check if my understanding is correct. From what I have read it ...
286 views

### Can we create a decision tree for any comparison sorting algorithm even if it is very complicated?

I am reading an algorithm book. Any comparison sort must make $\Omega(n\log(n))$ comparisons in the worst case to sort $n$ elements. Can we create a decision tree for any comparison sorting algorithm ...
1 vote
21 views

### How to come up with combination a short-circuit evaluation table?

(a || b) || (c && d)) Given the above, how do I derive the table below: a b c d output T - - - TRUE F T - - TRUE F F T T TRUE F F T F FALSE F F F - FALSE I'm told that this is short ...
710 views

### Decision tree for searching element in sorted-array

Given the problem of having a sorted array $A$, an element $x$ to be searched for in the array $A$, what is a lower-bound on the process of finding $x$ in $A$? The answer is $\Omega(\log n)$ ...
1 vote
42 views

1 vote
98 views

### Can inputs in the decision tree model be computed?

The Wikipedia definition of the decision tree model says that it allows the sign functions of certain classes to be computed in constant time (and presumably also memory). My questions, still ...
473 views

### how does the shap algorithm work in polynomial time?

I'm trying to understand how the shap algorithm calculates in polynomial time an estimation to the feature attribution function that satisfies the shapely value attributes (specifically for tree based ...
82 views

### SMO, Random forest and Bayes net algorithms: why does Random forest perform better?

I analyzed a dataset using those 3 different algorithms. As I can see, Random forest performs better in most cases. My dataset is composed of 4000 instances of two classes (class A 2000 elements, ...
1 vote
109 views

### Rummy Card Game Bot

in my beginner’s computer science class, we are asked to create an bot for a variant of rummy. It has to make logical moves as it needs to beat other very simple bots. I wanted to know how you would ...
1 vote
144 views

### How to convert a decision tree to an automaton?

From what I know, a problem can be transformed to a yes/no answer, which can be described by a decision tree. Solution to a problem also can be represented by a set of strings (a language), which ...
1 vote
390 views

### Why decision tree method for lower bound on finding a minimum doesn't work

(Motivated by this question. Also I suspect that my question is a bit too broad) We know $\Omega(n \log n)$ lower bound for sorting: we can build a decision tree where each inner node is a comparison ... 1 vote
154 views

1 vote
115 views

### How to handle missing attribute's value with ID3 algorithm?

i am working with ID3 algorithm, and i know that classic ID3 basically can handle missing data. But i am trying to code this algorithm, so what should i do if there is missing attribute's value in ...
98 views

### Decision Tree for searching an element in an n*n matrix

I just learnt decision tree concept in class. I have a question for homework. It says to prove that for searching an element in n*n matrix the lower bound is logn and prove it using decision tree. My ...
1 vote
231 views

### Lower bound for merging $m$ sorted arrays (decision tree leaves count - permutations)

I need some help understanding how to calculate the lower bound on the time complexity of merging $m$ sorted arrays of length $n$. The bound should be $nm \lg(m)$. I need to prove this using a ...
302 views

### How to calculate information gain in ID3?

I am trying to implement a decision tree classifier using ID3 algorithm. According to Aritificial Intelligence - A Modern Approach, information gain of attribute A ...
797 views

### Random Forest - Conditional Permutation Importance

I've been looking for the most unbiased algorithm to find out the feature importances in random forests if there are correlations among the input features. Besides the most commonly preferred ...
46 views

### Finding maximum takes at least $\lceil n/2 \rceil$ comparisons

We are given an array $A$ with $n$ elements, $n \in \mathbb{N}$ and all elements are in the set $\{1,2,3, \cdots, n \}$. I want to prove that finding the maximum in $A$ (that is, outputting the index ...
52 views

### decision trees and numeric attributes

I have been reading a book about Decision Trees and it caught my attention the following part: In case of numeric attributes, decision trees can be geometrically interpreted as a collection of ...
31 views

### Classify/Distinguish between 8008 binary grids, with 13 queries

I have $8008$ binary grids of size $6 \times 10$ (they are all grids with the property described below), which I want to distinguish between with at most $13$ queries. A query will determine if the ...
1 vote
50 views

### Attribute Selection for minimum number of clusters

I have a table consisting of some headers $P, Q, R, S$ (shown in blue in Table 1). According to the headers, the column $T$ is populated using some predefined logic. Now, any of the headers $P,Q,R,S$ ...
186 views

### What do Arora and Barak mean by $x|_S$ in their definition of certificate complexity?

I am having much trouble understanding the following definition (of certificate complexity - for decision trees) from Arora and Barak's book Computational Complexity: A Modern Approach. Perhaps there ...
38 views

### Avoiding collisions in space and time

Say I have an image, represented as a 2D array of pixel values. Also, say I have a set of points on that image where each has a current (x, y) position and a Destination (x, y) associated with it. I ...
1 vote
2k views

### What machine learning training algorithm to use for this kind of string dataset?

I am working on a project where I have to train the following data-set using machine learning algorithm. One of my friend suggested decision tree, but I have never seen a situation where independent ...
86 views

### Decision Tree Learning Deviation - Russell and Norvig

I am working through the Russell and Norvig AI book and came across the following on the top of page 706. The section concerns Decision Tree pruning and testing a given attribute against the null ...
1k views

### What is the main difference between binary decision tree and binary decision diagram(BDD)?

What is the main difference between binary decision tree and binary decision diagram(BDD)? From what I can tell I only understand that a binary decision diagram is a more compact representation ...
1 vote
51 views

### Connected Components - Linear Decision Trees

What does connected components mean in the context of non-graphs? Graphs have vertices and the vertices are connected by edges. Hence, you can build a spanning tree (for example) by systematically ...
I am currently studying for a test on data structures. I have to find the lower and upper bounds for the following problem: An array is called a zigzag array if there are $1 \leq i \leq j \leq n$ so ...
I am currently studying for a test on data structures. I have to find the lower and upper bounds for the following problem: Input: an array with $n$ numbers. Output: boolean answer for the ...