Dealing with Logs: Given that \( \log_{10}4 = 0.6020 \) and \( \log_{10}5 = 0.6989 \) , find the value of \( \log_{20}10 \)....
Series Sum: Compute the sum of the following series: \( \sum_{i=1}^n i \times 2^i\)....
Series Sum 2: Compute the sum of the following series: \( \sum_{i=1}^n i^2 \times 2^i\)....
Series Sum 3: Which of the following two terms is larger: \( \sum_{i=1}^n i^2 \) or \( \sum_{i=1}^{n^2} i \)....
ADT for a circle: We define an ADT specification for a point in a two dimensional space as follows:
Name: \(\texttt{point}\)Use: \(\texttt{float, Boolean}\)Functions:\(\begin{array}{p{1cm} l l l} & \textbf{Init} & \texttt{float} \times \texttt{float} & \rightarrow \texttt{point}\\ & \textbf{Move} & \texttt{point} \times \texttt{float} \times \texttt{float} & \rightarrow \texttt{point}\\ & \textbf{Distance} & \texttt{point} \times \texttt{point} & \rightarrow \texttt{float}\\ & \textbf{Equal} & \texttt{point} \times \texttt{point} & \rightarrow \texttt{Boolean}\\ \end{array}\)...
ADT for a tuple of n floats: We define \(\texttt{tuple}\) ADT allowing to manipulate, for any value of \(n\), the tuple of floats \((x_1,\cdots,x_n)\), as follows:
Type: \(\texttt{tuple}\)Use: \(\texttt{float, integer}\)Functions:\(\begin{array}{p{1cm} l l l} & \textbf{Create} & \texttt{integer} & \rightarrow \texttt{tuple} \text{ (creates a tuple with null elements)}\\ & \textbf{Assign} & \texttt{tuple} \times \texttt{integer} \times \texttt{float} & \rightarrow \texttt{tuple} \text{ (assigns a value to the } i^{th} \text{ element } x_i \text{ of a tuple)}\\ & \textbf{Nth} & \texttt{tuple} \times \texttt{integer} & \rightarrow \texttt{float} \text{ (returns the } n^{th} \text{ element of a tuple)}\\ & \textbf{Rank} & \texttt{tuple} & \rightarrow \texttt{integer} \text{ (number of a tuple elements)}\\ & \textbf{Sum} & \texttt{tuple} \times \texttt{tuple} & \rightarrow \texttt{tuple}\\ & \textbf{Product} & \texttt{tuple} \times \texttt{float} & \rightarrow \texttt{tuple} \text{ (multiplies all tuple elements by a given float)}\\ \end{array}\)...
ADT for a set of pairs of values: A set of pairs consists of \(\texttt{key}-\texttt{value}\) pairs where the keys belong to a given type \(\texttt{key_type}\) and values to another type \(\texttt{val_type}\).
The set \(\{\texttt{<size-170>, <age-18>, <weight-71>, <number-12>}\}\)...
Asymptotic Analysis 23: Give the worst case time complexity of the following function. Justify your answer.
i = 1;while (i < n) { j = 2; while (j < n) j = j * j; i++;}
...
Asymptotic Analysis 24: How do these pairs of functions compare asymptotically:
$$n^{17}$$ and $$2^n$$
$$2^{n^2}$$ and $$10^n$$
...
ADT for a Deque: Complete the following abstract data type \(\texttt{Q2En}\) (Queue with 2 ends), which is a linked structure of elements supporting the insertion and removal of elements at the beginning and at the end, by including operators allowing to: create a \(\texttt{Q2En}\)...
ADT for a drink distributor: We would like to model a soft drink distributor available to the employees of a company. We assume that there are several types of drinks belonging to type \(\texttt{t_drink}\). There are 2 types of users: customers and service agents.
Operations to ...
ADT for a polynomial: Given the following polynomial of maximum degree \(N_{Max}\):
\( P(x)=a_n x^n + a_{n-1} x^{n-1} + \cdots a_1 x + a_0 \)
where \(n\) (polynomial degree) \(\leq\) \(n_{max}\) and \(a_i\) are real numbers.
The operations of the abstract data type \(\texttt{Polynomial}\)...
ADT for Ternary trees: We define the abstract data type \(\texttt{Ternary_Tree}\) (3 children tree) as follows:
Type: \(\texttt{TT(element)}\)Use: \(\texttt{Boolean}\)
Functions:\(\begin{array}{p{1cm} l l l l} & \textbf{Init}: & \texttt{TT} & \rightarrow \texttt{TT} & \text{// creates an empty TT} \\ & \textbf{Construct}: & \texttt{element} \times \texttt{TT} \times \texttt{TT} \times \texttt{TT} & \rightarrow \texttt{TT} & \text{// construct a tree by giving the root value and its 3 children} \\ & \textbf{LeftChildren}: & \texttt{TT} & \rightarrow \texttt{TT}& return TT left children \\ & \textbf{MiddleChildren}: & \texttt{TT} & \rightarrow \texttt{TT} & \text{// return TT middle children} \\ & \textbf{RightChildren}: & \texttt{TT} & \rightarrow \texttt{TT} & \text{// return TT right children} \\ & \textbf{Root}: & \texttt{TT} & \rightarrow \texttt{element} & \text{// return root value} \\ & \textbf{isEmpty}: & \texttt{TT} & \rightarrow \texttt{Boolean} & \text{// test if TT is empty}\\ & \textbf{Rotation}: & \texttt{TT} & \rightarrow \texttt{TT} & \text{// replace left subtree by middle subtree, middle subtree by right subtree, and right subtree by the left one and leave the root unchanged. If the tree is empty then the operation has no effect} \\ & \textbf{CutM}: & \texttt{TT} & \rightarrow \texttt{TT} & \text{// replace the middle subtree by an empty tree} \\ \end{array}\)...
ADT for Intervals: A non empty interval of integer is defined by two integers $$[lowerb, upperb]$$ where:
$$lowerb$$ is the lower bound, $$upperb$$ the upper bound, and $$lowerb \leq upperb$$;
empty interval $$[]$$ is defined as having no lower bound nor upper bound.
W...
ADT for Inverted Phonebooks: Consider the ADT \(\texttt{IP}\) (inverted phonebook) which is a set of entries, each consisting in the phone number and the name of a person, that is used to find the person name from his phone number (like True caller):
Type: \(\texttt{IP}\)Paramet...
ADT for priority queues: Consider the ADT \(\texttt{PQ}\) (priority queue) which is a data structure used by a computer system to deal with processes having each a unique identifier and a priority. It is obvious that the processes having the highest priority will be executed...
Leap years: Since 1582 are leap years those years divisible by 4, except for century years (equal to100*S) where S is not divisible by 4.Example :1988, 1600, 2000 are leap years.1987, 1700, 1800, 1900 are not.
Write a program that reads a year and displays the c...
Real and complex solutions of a second degree equation: Write a program that calculates the solutions of a second degree equation \(ax^2+bx+c=0\). Display
INFINITE for infinite solutions
NO SOLUTION for no solutions
ottherwise, dislpay single, double or 2 solutions on one line (all numbers rounded to 2 ...
Real solutions of a third degree equation: Write a program that calculates the real solutions of a third degree equation \(x^3 +ax^2+bx+c=0\).
The analytical method to follow:
calculate $Q=\frac{a^2-3b}{9}$ and $R=\frac{2a^3-9ab+27c}{54}$
If $R^2<Q^3$, we have 3 solutions
$x_1=-2\sqrt{Q}\c...
Value of a complicated series: Write a program that takes an integer $n$ and displays the value of $U_n$ respecting: $U_1=1$ ;$U_n=\sum_{i=1}^{n-1}\frac{U_i}{(i-1)!}$ for n>0 ;
Write a program that asks the user to enter an integer a and then prints the series elements from $U...
Replace occurrences in an array: Write a recursive function that replaces all the occurrences of an integer I1 in an arrayof integers by some another integer I2....
Closest value of an element in an array: Write a recursive function that, given an integer X, determines the position of the closest value of X in an array.Prototype : int closest(int tab[], int N, int X, int position)Write a main function to test your program....
Game trees: One application of trees is to game playing by computer. We illustrate this application by writing a C program to determine the "best" move in tic-tac-toe from a given board position.
Assume that there is a function evaluate that accepts a board posi...
A Mazing Problem: The rat-in-a-maze experiment is a classical one from experimental psychology. A rat (or mouse) is placed through the door of a large box without a top. Walls are set up so that movements in most directions are obstructed. The rat is carefully observe...
Implementation of a compiler and interpreter for a programming language: Implement a compiler and interpreter for a programming language where each program consists of a single arithmetic expression preceded by a sequence of assignment statements with arithmetic expressions involving integers and variables named with sing...
Intersection node of 2 linked lists: Given the following list structure:typedef ... element;typedef struct cell { element data; struct cell * next;} *list;
Suppose we have two simply linked lists that can intersect at a given node to become a single linked list. The position o...
Connected Components: In graph theory, a component, sometimes called a connected component, of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.
Write a p...
Infix to Postfix Expression and Evaluation: We are interested in evaluating mathematical expressions containing different operators and integer operands. Mathematical expressions are usually written in infix notation, and in order to the computer to evaluate its value, it needs to rewrite the ...
Sorting an array using two stacks: We want to sort an array of $N$ integers in decreasing order using a stack. To do this, you should use two stacks: a current stack ($\texttt{$S_1$}$) and an auxiliary stack ($\texttt{$S_2$}$) that will be used temporarily for eventual pops.
Write ...
Static implementation of a priority queue: We want to manage a set of processes in a computer system. Each process has a unique id and a priority. It is obvious that the processes having highest priority will be executed first. The processes with equal priority will be executed in FIFO. The m...
Bipartite Graph: In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets $U$ and $V$ such that every edge connects a vertex in $U$ to one in $V$. Vertex sets $U$ and $V$...
Valid vertices in a graph: Consider the following linked list representation of a directed weighted graph
typedef struct node { int vertexNumber; int weight; struct node * next; // circular linked list} node;
typedef struct { int V; in...
Build a tree from preorder traversal: Write a function that given an expression tree with the following properties:
leaves are represented with * and internal node with +.
each node has either 0 or 2 children.
Given the preorder traversal of a tree, construct the tree.
Example: for the f...
Postfix Expression Evaluation using Expression trees: Your job is to read a postfix expression, convert it into an expression tree and then evaluate the tree.
The input expression is a string composed of digits (0 till 9) and operators (/, *, -, +, ^ (denotes exponentiation) and # (denotes unary minus)...
Path between 2 nodes in a binary tree: The input to your program will be a string of letters which symbolize the nodes of a binary tree. The order of appearance of the letters is the pre-order traversal of the tree. A 0(zero) in the string specifies that the relevant child is null. Your p...
Min-max heaps: A $\texttt{Min-Max Heap}$ is a hybrid data structure between a $\texttt{Min Heap}$ and a $\texttt{Max Heap}$. More precisely, it is a perfect $\texttt{BT}$ in which:
nodes on an even level are smaller than those of their descendants (direct or indir...
Lowest common ancestor in a BST: Given pointers to two nodes in a BST dynamically implemented, write a function that returns a pointer to their lowest common ancestor. Restrictions:
Time complexity of your function: $O(\log{n})$, where $n$ is the number of nodes.
Usage of stacks an...
Robin Hood Hashing: Robin Hood Hashing is an alternative hashing collision resolution technique similar to the Coalesced, Cuckoo and Hopscotch techniques.
The idea is that a new key may displace a key already inserted, if its probe count is larger than that of the k...
Level Ancestor problem: Let $T$ be a rooted binary tree dynamically implemented with $n$ nodes, and let $v$ be a node of $T$. The level ancestor query $LA(v,d)$ returns the ancestor of node $v$ at depth $d$, where the depth of a node $m$ in a tree is the number of edges on ...
Calkin-Wilf tree: The Calkin-Wilf tree is a complete binary tree. The tree is rooted at the number 1, and any rational number expressed in simplest terms as the fraction $\frac{a}{b}$ has as its two children the numbers $\frac{a}{a+b}$ and $\frac{a+b}{b}$. Every posit...
Stern-Brocot tree: The Stern-Brocot tree is an elegant construction to represent the set of all positive fractions. It was independently discovered by German mathematician Moritz Stern in 1858 and by French watchmaker Achille Brocot in 1861.
The construction starts at ...
Display What: Write a program that reads a number on the keyboard without telling the user to enter a value and then displays the word $\texttt{what?!}$ on the screen and then go to a new line....
Integer part: Write a program that reads a real number on the keyboard without telling the user to enter a value and then displays its integer part on the screen and then go to a new line....
Closest value to the average: Write a program that reads 3 integers number on the keyboard without telling the user to enter the values and then displays on the screen the value of the closest integer to their average and then go to a new line....
ATM money withdrawal: Knowing that ATMs should withdraw the minimum number of notes for each withdrawal, write a program that reads an amount of money in LL on the keyboard without telling the user to enter the value and then displays on the screen the minumum numbers of ...
KM conversion: Seeing that 1 mile is equal to 1609 meters or 1760 yards, and that 1 yard is equal to 3feet and that 1 foot is equal to 12 inches, write a program that reads a real number of kilometers and converts it to miles, yards, feets (all 3 in integer) and in...
Dealing with Logs: Given that \( \log_{10}4 = 0.6020 \) and \( \log_{10}5 = 0.6989 \) , find the value of \( \log_{20}10 \)....
Series Sum: Compute the sum of the following series: \( \sum_{i=1}^n i \times 2^i\)....
Series Sum 2: Compute the sum of the following series: \( \sum_{i=1}^n i^2 \times 2^i\)....
Implementation of a compiler and interpreter for a programming language: Implement a compiler and interpreter for a programming language where each program consists of a single arithmetic expression preceded by a sequence of assignment statements with arithmetic expressions involving integers and variables named with sing...
Lowest common ancestor in a BST: Given pointers to two nodes in a BST dynamically implemented, write a function that returns a pointer to their lowest common ancestor. Restrictions:
Time complexity of your function: $O(\log{n})$, where $n$ is the number of nodes.
Usage of stacks an...