PROBLEM 4: Consider the recursive C++ function below: void foo(unsigned int n) { if(n==0) ...
PROBLEM 4: Consider the recursive C++ function below:
|
void foo(unsigned int n) { if(n==0) cout << "tick" << endl; else { foo(n-1); foo(n-1); foo(n-1); } } |
4.A: Complete the following table indicating how many “ticks” are printed for various parameters n.
Unenforceable rule: derive your answers “by hand” -- not simply by writing a program calling the function.
|
n |
number of ticks printed when foo(n) is called |
|
0 |
|
|
1 |
|
|
2 |
|
|
3 |
|
|
4 |
4.B: Derive a conjecture expressing the number of ticks as a function of n -- i.e., complete the following:
“Conjecture: for all n≥0, calling foo(n) results in _____________ ticks being printed”
4.C: Prove your conjecture from part B (hint: Induction!)
Homework Answers
If you have any doubts, please give me comment...
4.A)
|
n |
number of ticks printed when foo(n) is called |
|
0 |
1 |
|
1 |
3 |
|
2 |
9 |
|
3 |
27 |
|
4 |
81 |
4.B) 3n ticks being printed.
Add Answer to:
PROBLEM 4: Consider the recursive C++ function
below:
void foo(unsigned int n) {
if(n==0)
...
For part 5B I already have 2^(n+1) -1, but I'm not sure how to prove it...
For part 5B I already have 2^(n+1) -1, but I'm not sure how to
prove it using induction. I am actually taking the prerequisite to
this class concurrently and we haven't gotten to that part
unfortunately so please show clear steps.
PROBLEM 5 Consider the recursive C function below: void foo (unsigned int n) cout << "tick" <<endl; if(n > ) { foo (n-1); foo(n-1) 5A: Complete the following table indicating how many "ticks" are printed for various parameters n....
Consider the following program: # include <iostream> int x = 3, y = 5; void foo(void)...
Consider the following program: # include <iostream> int x = 3, y = 5; void foo(void) { x = x + 2; y = y + 4; } void bar(void) { int x = 10; y = y + 3; foo( ); cout << x << endl; cout << y << endl; } void baz(void) { int y = 7; bar( ); cout << y << endl; } void main( ) { baz( ); } What output does this program...
Problem 1. Select the running time of each function. void print_array (int* A, int n) for...
Problem 1. Select the running time of each function. void print_array (int* A, int n) for (int í 0; i < n; ++i) cout << A[i] << endl; void print_array pairs (int* A, int n) for (inti 0; i < n; ++i) for (int j 0; j < n; ++j) cout << Ai] ALj]< endl; void print_array_start(int* A, int n) for (int i 0; i < 100 ; ++i) cout << A[i] << endl; void print_array_alt (int* A, int n)...
(C++) You are tasked with implementing a recursive function void distanceFrom(int key) on the IntList class...
(C++) You are tasked with implementing a recursive function void distanceFrom(int key) on the IntList class (provided). The function will first search through the list for the provided key, and then, recursively, change all previous values in the list to instead be their distance from the node containing the key value. Do not update the node containing the key value or any nodes after it. If the key does not exist in the list, each node should contain its distance...
You are tasked with implementing a recursive function void distanceFrom(int key) on the IntList class (provided)....
You are tasked with implementing a recursive function void distanceFrom(int key) on the IntList class (provided). The function will first search through the list for the provided key, and then, recursively, change all previous values in the list to instead be their distance from the node containing the key value. Do not update the node containing the key value or any nodes after it. If the key does not exist in the list, each node should contain its distance from...
Q5 (25pts) Consider the code: int foo(int N){ if (N <= 3) return 2; int res1 = 3*foo(N-4); int...
Q5 (25pts) Consider the code: int foo(int N){ if (N <= 3) return 2; int res1 = 3*foo(N-4); int res2 = foo(N-2); return res1-res2; } a) (6 points) Write the recurrence formula for the time complexity of this function (including the base cases) for N>=0. You do NOT need to solve it. b) (5 points) Draw the tree that shows the function calls performed in order to compute foo(8) (the root will be foo(8) and it will have a child...
2. Consider the following recursive function (Chapter 17, #9, modified) void recFun (int x) { if...
2. Consider the following recursive function (Chapter 17, #9, modified) void recFun (int x) { if (x > 10) { recFun (x / 10); cout<< X % 10; } else cout<< x; } a) What is printed by the call: recFun (268); b) How can the code be modified so that when a number is input, its digits are printed on separate lines? c) How can the code be modified so that the sum of all digits is printed?
This is for C in Linux: Problem 1: Given the following recursive function: void recursiveFunction( int...
This is for C in Linux:
Problem 1: Given the following recursive function: void recursiveFunction( int m ) printf("%d", m); if( m <= 0 ) return; if( n + 2 == 0 ) recursiveFunction( m - 1); else recursiveFunction( m - 2); What is the output when the following functions are called with these parameters? recursiveFunction( 5 ); recursiveFunction( 10 ); recursiveFunction( 0);
#include <iostream> #include <queue> using namespace std; class Graph { public: Graph(int n); ~Graph(); void addEdge(int...
#include <iostream>
#include <queue>
using namespace std;
class Graph {
public:
Graph(int n);
~Graph();
void addEdge(int src, int tar);
void BFTraversal();
void DFTraversal();
void printVertices();
void printEdges();
private:
int vertexCount;
int edgeCount;
bool** adjMat;
void BFS(int n, bool marked[]);
void DFS(int n, bool marked[]);
};
Graph::Graph(int n=0) {
vertexCount = n;
edgeCount = 0;
if(n == 0)
adjMat = 0;
else {
adjMat = new bool* [n];
for(int i=0; i < n; i++)
adjMat[i] = new bool [n];
for(int i=0;...
Q1. Write a recursive function in C++ void printNumberedChars(string str, int i=0) { ... } which...
Q1. Write a recursive function in C++ void printNumberedChars(string str, int i=0) { ... } which prints each character of the given string str on a new line, with each line numbered 1, 2, 3, …. For example calling the function with printNumberedChars("hello"); should output the following: 1. h 2. e 3. l 4. l 5. o Q2. Write a recursive function in C++ int sumArray(const int* arr, unsigned int size) { ... } which takes an array of integers,...
For part 5B I already have 2^(n+1) -1, but I'm not sure how to
prove it using induction. I am actually taking the prerequisite to
this class concurrently and we haven't gotten to that part
unfortunately so please show clear steps.
PROBLEM 5 Consider the recursive C function below: void foo (unsigned int n) cout << "tick" <<endl; if(n > ) { foo (n-1); foo(n-1) 5A: Complete the following table indicating how many "ticks" are printed for various parameters n....
Problem 1. Select the running time of each function. void print_array (int* A, int n) for (int í 0; i < n; ++i) cout << A[i] << endl; void print_array pairs (int* A, int n) for (inti 0; i < n; ++i) for (int j 0; j < n; ++j) cout << Ai] ALj]< endl; void print_array_start(int* A, int n) for (int i 0; i < 100 ; ++i) cout << A[i] << endl; void print_array_alt (int* A, int n)...
2. Consider the following recursive function (Chapter 17, #9, modified) void recFun (int x) { if (x > 10) { recFun (x / 10); cout<< X % 10; } else cout<< x; } a) What is printed by the call: recFun (268); b) How can the code be modified so that when a number is input, its digits are printed on separate lines? c) How can the code be modified so that the sum of all digits is printed?
This is for C in Linux:
Problem 1: Given the following recursive function: void recursiveFunction( int m ) printf("%d", m); if( m <= 0 ) return; if( n + 2 == 0 ) recursiveFunction( m - 1); else recursiveFunction( m - 2); What is the output when the following functions are called with these parameters? recursiveFunction( 5 ); recursiveFunction( 10 ); recursiveFunction( 0);
#include <iostream>
#include <queue>
using namespace std;
class Graph {
public:
Graph(int n);
~Graph();
void addEdge(int src, int tar);
void BFTraversal();
void DFTraversal();
void printVertices();
void printEdges();
private:
int vertexCount;
int edgeCount;
bool** adjMat;
void BFS(int n, bool marked[]);
void DFS(int n, bool marked[]);
};
Graph::Graph(int n=0) {
vertexCount = n;
edgeCount = 0;
if(n == 0)
adjMat = 0;
else {
adjMat = new bool* [n];
for(int i=0; i < n; i++)
adjMat[i] = new bool [n];
for(int i=0;...
Most questions answered within 3 hours.
-
a
carboxylic acid reacting with a strong base will form what
ion
asked 13 minutes ago -
which value if any in each pair corresponds to a
faster reaction k=18.k=137
asked 18 minutes ago -
Bus lines can be separated into two generic types, dedicated and
multiplexed.
i. What is the...
asked 2 hours ago -
This is 'Branding' course which is part of marketing.
1. As a brand manager of Nudie...
asked 2 hours ago -
You are considering the purchase of a new stock. The stock is
forecasted to pay a...
asked 2 hours ago -
vector a has componets Ax and Ay, and makes an angle theta with
the y-axis. Select...
asked 3 hours ago -
What were the problems of the american frontier after 1763 and how
did the British address...
asked 4 hours ago -
Why
isn’t pentanol (CH3 CH2 CH2 CH2 CH2 OH) very soluble in
water?
asked 4 hours ago -
In preparing its bank reconciliation for the month of April
2018, Haskins, Inc. has available the...
asked 6 hours ago -
Your job is to do the following: build a Monster class as your
base class, along...
asked 6 hours ago -
Phosgene (COCl2) reacts with ammonia
(NH3), as shown in this reaction. If 1.2 grams of
COCl2...
asked 6 hours ago -
Wefald Company sold bonds with a face value of $675,000 for
$625,000. The bonds have a...
asked 6 hours ago