Q1. Given the following Doubly_Linked_List program, Node.h #ifndef NODE_H #defin
ID: 3671026 • Letter: Q
Question
Q1. Given the following Doubly_Linked_List program,
Node.h
#ifndef NODE_H
#define NODE_H
class Node
{
friend class Doubly_Linked_List;
public:
Node();
Node(int a);
~Node();
int getAge();
private:
Node* prev;
int age;
Node* next;
};
#endif
Node.cpp
#ifndef NODE_CPP
#define NODE_CPP
#include <iostream>
using namespace std;
#include "Node.h"
Node::Node()
{
prev= NULL;
age = 0;
next = NULL;
}
Node::Node(int a)
{
prev= NULL;
age = a;
next = NULL;
}
Node::~Node()
{
}
int Node::getAge()
{
return age;
}
#endif
Doubly_Linked_List.h
#ifndef DOUBLY_LINKED_LIST_H
#define DOUBLY_LINKED_LIST_H
#include "Node.h"
class Doubly_Linked_List
{
public:
Doubly_Linked_List();
~Doubly_Linked_List();
void insert_new_node_to_front(Node &newNode);
void insert_new_node_to_back(Node &newNode);
void remove_node_from_front();
void remove_node_from_back();
void display_doubly_linked_list_from_front();
void display_doubly_linked_list_from_back();
bool check_palindrome();
private:
Node* head;
Node* tail;
};
#endif
Doubly_Linked_List.cpp
#ifndef DOUBLY_LINKED_LIST_CPP
#define DOUBLY_LINKED_LIST_CPP
#include <iostream>
using namespace std;
#include "Doubly_Linked_List.h"
Doubly_Linked_List::Doubly_Linked_List()
{
head = NULL;
tail = NULL;
}
Doubly_Linked_List::~Doubly_Linked_List()
{
}
void Doubly_Linked_List::insert_new_node_to_front(Node &newNode)
{
// if doubly linked list is empty
if ((head == NULL) && (tail==NULL))
{
head = &newNode;
tail = &newNode;
}
else
{
newNode.next = head;
head->prev = &newNode; // <--- BUG CAUSING check_palindrome() crash
head = &newNode;
}
}
void Doubly_Linked_List::insert_new_node_to_back(Node &newNode)
{
// if doubly linked list is empty
if ((head == NULL) && (tail==NULL))
{
head = &newNode;
tail = &newNode;
}
else
{
tail->next = &newNode;
newNode.prev = tail; // <--- BUG CAUSING check_palindrome() crash
tail = &newNode;
}
}
void Doubly_Linked_List::remove_node_from_front()
{
Node* tempNode;
if (head != NULL)
{
if (head == tail)
{
head = NULL;
tail = NULL;
}
else
{
tempNode = head;
tempNode = tempNode->next;
tempNode->prev = NULL;
head = tempNode;
};
};
}
void Doubly_Linked_List::remove_node_from_back()
{
// YOUR CODE STARTS HERE
}
void Doubly_Linked_List::display_doubly_linked_list_from_front()
{
Node* tempNode;
tempNode = head;
while (tempNode != NULL)
{
cout << tempNode->getAge() << " ";
tempNode = tempNode->next;
}
cout << endl;
}
void Doubly_Linked_List::display_doubly_linked_list_from_back()
{
Node* tempNode;
tempNode = tail;
while (tempNode != NULL)
{
cout << tempNode->getAge() << " ";
tempNode = tempNode->prev;
}
cout << endl;
}
bool Doubly_Linked_List::check_palindrome()
{
// YOUR CODE STARTS HERE
}
#endif
main.cpp
#include <iostream>
using namespace std;
#include "Node.h"
#include "Doubly_Linked_List.h"
int main()
{
Doubly_Linked_List dll;
Node node1(10);
dll.insert_new_node_to_front(node1);
Node node2(20);
dll.insert_new_node_to_front(node2);
Node node3(20);
dll.insert_new_node_to_back(node3);
dll.display_doubly_linked_list_from_front();
dll.display_doubly_linked_list_from_back();
cout << "Is it palindrome?" << dll.check_palindrome() << endl;
system("PAUSE");
return 0;
}
output
20 10 20
20 10 20
Is it palindrome?1
Press any key to continue . . .
Q1.1 Complete the method, void Doubly_Linked_List::remove_node_from_back() in Doubly_Linked_List.cpp.
[ANSWER]
Q1. Complete the method, bool Doubly_Linked_List::check_palindrome() in Doubly_Linked_List.cpp.
[ANSWER]
Q1.3 A doubly linked list and the values of the links are given below. The arrow in each node indicates that the address of the node to which it is pointing is stored in that node. For example, the first node is at memory location 02 in hex, and the second node is at memory location 49 in hex.
Fill in the blanks.
Statement
Value
head®value
tail®next
tail
head = head®next®next®next
tail®prev®prev
Q2 Big-Oh definition describes how algorithms (in run time) respond to changes in input size. Let f(n) and g(n) be functions mapping nonnegative integers to real numbers. We say that f(n) is O(g(n)) if there is a real number constant c > 0 and the integer constant n0 ³ 1 such that
f(n) £ c ´ g(n), for n ³ n0.
Big-Oh provides an upper bound on the growth rate of the algorithm.
Use the Big-Oh definition to show that 20 + 10nlogn + 5 is O( ).
[ANSWER]
Q3. For each of the following three program fragments:
a. Run each of the following code, record the times, and plot the graph (x-axis along with the values of n and y-axis along with the actual running times) using Excel.
b. (20 Points) Using Big-Oh definition, give an analysis of the running time (Big-Oh will do).
(1)
int sum = 0;
for (int i=0; i<n; i++)
++sum;
(2)
int sum = 0;
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
++sum;
[ANSWER]
Statement
Value
head®value
tail®next
tail
head = head®next®next®next
tail®prev®prev
Explanation / Answer
Q2. In Part1, expression is not displayed clearly.
Use the Big-Oh definition to show that 20 + 10nlogn + 5 is O( ).
[ANSWER]
The time complexity of 20 + 10nlogn + 5 is O(nlogn)
Use the Big-Oh definition, we need C>0 and n0>=1 such that
20+10nlogn+5 <= C nlogn for n>=n0.
This is true for C= 35 and n0 =2.
Q3.
b. (20 Points) Using Big-Oh definition, give an analysis of the running time (Big-Oh will do).
(1)
int sum = 0;
for (int i=0; i<n; i++)
++sum;
[ANSWER]
int sum = 0; ----------- It runs O(1) times
for (int i=0; i<n; i++) ---This loop runs O(n) times.
++sum; ------------ It runs O(1) times
The Big-O time complexity is O(n).
Use the Big-Oh definition, we need C>0 and n0>=1 such that
n<=C n for n>=n0.
This is true for C=1.
(2)
int sum = 0;
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
++sum;
[ANSWER]:
int sum = 0; ----------- It runs O(1) times
for (int i=0; i<n; i++) --- This loop runs O(n) times.
for (int j=0; j<n; j++)-- This loop runs O(n) times.
++sum; -------- It runs O(1) times
The Big-O time complexity is n * n = O(n^2)
Use the Big-Oh definition, we need C>0 and n0>=1 such that
n^2 = C n^2 for n>= n0.
This is true for C=1 and n0 =2
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.