A free tree is a connected, acyclic, undirected graph. We often omit the adjective “free” when we say that a graph is a tree. If an undirected graph is acyclic but possibly disconnected, it is a forest. Many algorithms that work for trees also work for trees also work for forests. Figure B.4(a) shows a … Read more
A rooted tree is a free tree in which one of the vertices is distinguished from the others. We call the distinguished vertex the root of the tree. We often refer to a vertex of a rooted tree as a node5 of the tree. Given figure shows a rooted tree on a set of 12 … Read more
Question Implement strstr(). Returns the index of the first occurrence of needle in haystack, or –1 if needle is not part of haystack. Solution: O(nm) runtime, O(1) space – Brute force: There are known efficient algorithms such as Rabin-Karp algorithm, KMP algorithm, orthe Boyer-Moore algorithm. Since these algorithms are usually studied in an advancedalgorithms class, … Read more
Solution of LeetCode Two Sum III – Data structure design using java add – O(n) runtime, find – O(1) runtime, O(n 2 ) space – Store pair sums in hash table: We could store all possible pair sums into a hash table. The extra space needed is in the order of O(n2 ). You would … Read more
Solution of Leetcode Two Sum II – Input array is sorted using java O(n log n) runtime, O(1) space – Binary search: For each element x, we could look up if target – x exists in O(log n) time by applying binary search over the sorted array. Total runtime complexity is O(n log n). O(n) … Read more
A date represents a single day in the proleptic Gregorian calendar in which thefirst day starts on November 24, 4713 BC. Date( month, day, year ): Creates a new Date instance initialized to the given Gregorian date which must be valid. Year 1 BC and earlier are indicated by negative year components. day(): Returns the … Read more
There are many different terms used in computer science. Some of these can have different meanings among the various textbooks and programming languages. To aide the reader and to avoid confusion, we define some of the common terms we will be using throughout the text. A collection is a group of values with no implied … Read more
An abstract data type (or ADT) is a programmer-defined data type that specifies a set of data values and a collection of well-defined operations that can be performed on those values. Abstract data types are defined independent of their implementation, allowing us to focus on the use of the new data type instead of how … Read more
An abstraction is a mechanism for separating the properties of an object and restricting the focus to those relevant in the current context. The user of the abstraction does not have to understand all of the details in order to utilize the object, but only those relevant to the current task or problem. Two common … Read more