IT 279: Algorithms and Data Structures, Week 2 recap

Progress Check on Algorithm Analysis

 

1. Put these in order from lowest to highest.

Lowest

O(1)

O(log n)

O(n)

O(n log n)

O(n2)

O(n3)

Highest

2. The actual running time of a given function is determined by the expression 3n + 4 + 5n2.

What is the Big-Oh notation that accurately describes the function? c. O(n^2)

a. O(n)

b. O(3n)

c. O(n^2)

 

d. O(5n^2)

 

3. You have analyzed a particular program to be O(n^2). Then you have run some tests with the program, producing the following table of input size and running times.

Input size	Running time in seconds
100	0.010
400	0.091
1600	1.435

Which of the following is correct? b
a. The running times indicate that the program's computational complexity is lower than O(n^2).

b. The running times indicate that the program's computational complexity probably is O(n^2).

c. The running times indicate that the program's computational complexity is greater than O(n^2).

d. None of the above is correct.

4. What is the complexity of the following code segment:

for (int i = 0; i < n; i++)
{ 
  for (int j = 0; j < n; j++)
  { 
    cout << "I am a loop" << endl; 
  } 
  for (int k = 0; k < n; k++)
  { 
    cout << "I am also a loop" << endl; 
  } 
}

n^2: The inner loops will each have a running time of n, for a total of 2n. But in Big-Oh notation, we drop the constant, so that's just n. Then we multiply that by the outer loop, which runs n times. So we end up with O(n^2)

 

Big-O analysis:

sum = 0;

for( i = 0; i < n; ++i )

    for( j = 0; j < i * i; ++j )

        for( k = 0; k < j; ++k )

            ++sum;

 

n^5: n * n^2 * n^2

 

sum = 0;

for( i = 1; i < n; ++i )

    for( j = 1; j < i * i; ++j )

        if( j % i == 0 )

            for( k = 0; k < j; ++k )

                ++sum;

n^4: n * n^2 * n

 

Q. An algorithm takes 0.5 ms for input size 100. How long will it take for input size

500 if the running time is the following (assume low-order terms are negligible)?

a. linear : 2.5ms

b. O(N logN)

c. quadratic 250000/10000 * 0.5 = 25 * 0.5 = 12.5ms

d. cubic

 

 

Q. An algorithm takes 0.5 ms for input size 100. How large a problem can be solved in 1 min if the running time is the following (assume low-order terms are negligible)?

 

1m = 60,000 ms

 

a.    linear

0.5 :100 =  60000 : x

 

X = 6000000/0.5 = 12,000,000

 

 

c. quadratic

x^2/100^2 * 0.5 = 60,000

x^2 = 60000 * 10000 / 0.5

x^2 = 1,200,000,000

x = 34641.0161514

 

 

 

Linked list in C++

 

struct

struct Node
{
    int data;
    Node* next;
    
    Node(int data = 0, Node* next = nullptr){
    this->data = data;
    this->next = next; 
    }
}

 

Insertion Code (given temp)

Node* insertNode = new Node(6, temp->next);
temp->next = insertNode;

 

Searching a Linked List

public Node* searchList(Node* head, int valToFind)
{
	Node* curNode = head;
    while(curNode && curNode->data != valToFind)
    {
    	curNode = curNode->next;
    }
    return curNode;
}

 

Deletion Code (given temp)

Node* deleteNode = temp -> next;

temp->next = deleteNode->next;

delete deleteNode;

 

Cannot write as: 

temp->next = temp->next->next;

- We will get a memory leak

 

Double linked list (Java)

Insertion Code(after temp)

Node insertNode = new Node(8);
insertNode.next = temp.next;
insertNode.prev = temp;
temp.next = insertNode;
insertNode.next.prev = insertNode;

 

Progress Check on Lists

1. One approach to implementing the List ADT is to use a linked list. The other main approach (which you almost certainly learned first) is to use a(n) array.

 

2.

Assume you have the following C++ Node class:
class Node
{
public:
    int dataVal;
    Node* next;

    Node(int data = 0; Node* next = nullptr) : dataVal(data), next(next) {}
};

Which of the following correctly creates a new node with the value 6 and inserts it at the front of a list? Assume the variable head points to the beginning of the list.

Node* newNode = new Node(6, head);

head = newNode;

 

3.

True or false: Deleting the head and the tail of a linked list will always free all of the memory in the list.

False: We need to delete each node of the list, which could be none if the list is empty, one if it has just one element, or many. This requires a loop. The only case in which deleting the head and the tail would work is if the list contains exactly two elements.

 

Progress Check on Data Structure Review

1. Which of the following is NOT true of abstract data types (ADTs)? b

a. An ADT does not include implementation-specific details such as a head pointer for a stack (which could be implemented as either an array or a linked list).

b. ADTs are always implemented as classes.

c. We can create an ADT for an integer.

d. ADTs are not specific to any particular language.

 

-> b. ADTs are often implemented as classes, but they don't have to be. We can implement ADTs in languages that do not have classes.

 

 

2. Which of the problems below would be best solved using a queue? d

a. Implementing unlimited undo and redo in an application.

b. Searching for a particular item in a library of video titles.

c. Evaluating a postfix expression.

d. Implementing a waiting list system where no one is allowed special priority.

 

3. Which of the following is NOT an operation we would typically implement for a stack? b

a. push

b. insert

c. pop

d. isEmpty

 

Algorithm Analysis

Breakeven point

 

The "breakeven point" in time complexity refers to the input size (n) at which two algorithms have the same performance. It's where one algorithm starts to outperform the other. By identifying this point, one can make informed decisions on which algorithm to use based on the expected size of the input.

 

Linked Lists & Stacks & Queues

 

Abstract Data Type

- Specification of a data type, including operations.

- Describes data and operations in an implementation-independent way.

- Characteristics: Encapsulation, Data Abstraction, Modularity, Information Hiding, Standardization

Common examples of ADTs include:

• Lists
• Stacks
• Queues
• Trees
• Graphs

- ADT is not directly usable

- Most ADTs can be implemented in multiple ways

 

Circular lists

Circular lists, or circular linked lists, are a type of linked list where the last node in the list points back to the first node instead of having a null reference.

Benefits of Circular Lists:

1. Continuous Looping: One of the primary advantages of a circular list is the ability to loop through the list continuously. For example, in multimedia applications or games where you need to rotate through elements repeatedly, a circular list provides an efficient way to cycle through the list without checking for the end and resetting.
2. Simplified Insertion/Deletion at End: In a singly linked list, inserting an element at the end requires traversal of the entire list to reach the last node. But, in a circular linked list with a reference to the first node (or last node), you can easily access its predecessor and make insertions or deletions more efficiently.
3. Applications in Algorithms: Circular lists can be useful in specific algorithms and problem-solving scenarios, like the Josephus problem or certain round-robin scheduling algorithms.
4. Equal Distribution: In scenarios where tasks need to be distributed evenly among several entities, a circular list ensures that once the end is reached, the distribution starts again from the beginning.
5. Fixed Memory Allocation: In certain embedded system applications where memory is limited, a circular buffer (a specialized kind of circular list) can be useful. It provides a fixed-size structure where new data overwrites old data when the buffer is full.
6. Ease in Navigation: Moving either direction (in the case of a doubly circular linked list) becomes easier, as there's no strict "end" to the list. One can move to the previous element from the first node or to the next element from the last node directly.

 

 

Stack

LIFO(Last-In, First-Out)

Ex) backtracking, web browsers, parenthesis matching, and Syntax parsing

 

Queue

FIFO(First-In, First-out)

Ex) handling requests, ordering processes, web servers

 

The two primary options for implementing stacks or queues are:

1. Array (or Dynamic Array) Implementation:
   • Stack: An array can be used to implement a stack by using an index (often called the "top" index) to keep track of the top element. The push operation adds an element at the position indicated by the "top" index, and the pop operation removes it. When using a dynamic array (like an ArrayList in Java or a List in Python), the stack can grow or shrink as needed.
   • Queue: An array can be used to implement a queue by using two indices: "front" and "rear". The enqueue operation adds an element at the rear, and the dequeue operation removes the element from the front. A circular array can help in efficient use of space in the array, especially when items are continuously enqueued and dequeued.
2. Linked List Implementation:
   • Stack: A singly linked list can implement a stack where the push operation inserts elements at the head of the list, and the pop operation removes them from the head. This approach ensures O(1) time complexity for these operations.
   • Queue: A doubly-ended linked list (or a singly linked list with tail pointer) can implement a queue. The enqueue operation inserts elements at the tail, and the dequeue operation removes them from the head. Again, with this approach, both operations can be done in O(1) time if we maintain pointers to both the head and tail of the list.