Data Structures and Algorithms Midterm

Given the function T(N) = 4N + N² + 5N + 2 defines the worst case of the runtime of a function. Which of the following would be a correct statement?

The function has the complexity of O( n²)

What is the time complexity of a recursive algorithm with the following recursion tree?

• Each circle represent a function call.

• Each function call has a T(N) = N, T(N/2) = N/2, etc.

• Use big O notation.

Hint:

• how many layers?

• How many works in each layer?

O(n log(n))

Which of the following functions describes the runtime of the following code?

for(int i = 0; i < n; ++i) {
  for(int j = 0; j < n; ++j) {
    std::cout << i << "," << j << std::endl; //treat as one op
  }
}

T(n) = 3n² + 4n + 2

Fill in the blank of a header file:

#[blank] MY_HPP
#define MY_HPP
// header contents
#endif

ifndef

Inside a Makefile, we have different things that the make command will do. Select the correct option for each position in the Makefile format

__A__: __B__
    __C__

Answer 1:

Target

Answer 2:

Prerequisites

Answer 3:

Recipe

Given the following test file, what must you create?

#include "foo.hpp"
#include <iostream>
using namespace std;

int main()
{
  Foo foo;
  if (-12345 == foo.Bar())
    cout << "Correct!\n";
}

A file named foo.hpp, A class named Foo, a method named Bar

Which if the following is a benefit of unit tests?

Gives confidence in code after a refractor

Given the following Makefile, what are the commands to use this file?

run: foo.cpp bar.cpp
    g++ -std=c++11 -o main foo.cpp bar.cpp
    ./main

clean:
    rm *.o main

make run, make, make clean

Which is the Big-O complexity for the following code?

for(int i = 0; i < n; ++i) {
  cout << i << endl;
}

for(int j = 0; j < n; ++j) {
  cout << j << endl; 
}

O(n)

Which of the following functions defines the worst case for the following code?

int index = 0;
for(int i = 0; i < n; ++i)
  if(array[i] == value)  // one unit
    index = i;        // one unit

T(N) = 4N + 3

What is the term for the case of memory not being properly released when it was no longer needed.

memory leak

What is wrong with the following code?

#include <iostream>

int computeAverageOfDoubles(int startingValues[], int length) {
  int *doubles = new int[length];
  for(int i = 0; i < length; ++i){
    doubles[i] = 2 * startingValues[i];
  }

  int total = 0;
  for(int i = 0; i < length; ++i) {
    total += doubles[i];
  }

  return total / length;
}

int main() {
  int startingValues[] = {1,2,3,4,5};
  std::cout << computeAverageOfDoubles(startingValues, 5) << std::endl;
}

There is a memory leak

max-heap

is a tree that maintains the simple property that a node’s key is greater than or equal to the node’s children’s keys

array

a data structure that stores an ordered collection of elements, where each element is directly accessible by a positional index

linked list

a data structure that stores an ordered list of items in nodes, where each node stores data and has a pointer to the next node.

abstract data type(ADT)

is a data type described by predefined user operations, without indicating how each operation is implemented.

dynamic array

An ADT for holding ordered data and allowing indexed access

List

items are ordered based on how items are added. Duplicate items are allowed

Set

Items are not ordered. Duplicate items are not allowed

Priority Queue

Items are ordered based on items’ priority. Duplicate items are allowed

Bag

Items are not ordered. Duplicate items are allowed

Abstraction

means to have a user interact with an item at a high-level ,with a lower internal details hidden from the user.

Header file guards

preprocessor directives, which cause the compiler to only include the contents of the header file once

include directive

#include directs the compiler to replace that line by the contents of the given filename

ClasName.h

contains the class definition, including data members and member functions declerations

ClassName.cpp

contains member functions definitions

make

is one project management too tha is commonly used on Unix and Linux

makefile

the make utility uses this to recompile and link a program whenever changes are made to the source or header files

code

The region where the program instructions are stored

Static memory

The region where global variables as well as static local variables are allocated. Static variables are allocated once and stay in the same memory location for the duration of a program’s execution.

The stack

The region where a function’s local variables are allocated during a function call. A function call adds local variables to the stack, and a return removes them. also called(automatic memory)

The heap

The region where the “new” operator allocates memory, and where the “delete” operator deallocates memory. The region is also called free store

dynamically allocated array

Is an array whose size and memory location are determined during runtime

new operator

allocates memory for the given type and returns a pointer to the allocated memory

memory leak

occurs when a program that allocates memory loses the ability to access the allocated memory, typically due to failure to properly destroy/free dynamically allocated memory

garbage collection

Automatic process of finding and freeing unreachable allocated memory locations

rule of three

describes a practice that if a programmer explicitly defines any one of three special member functions, then the programmer should define all three.

Copy constructor

A constructor that initializes a new object of the same class. This special member function is automatically called when an object of the same type is the argument passed by the value to a function or is initialized using an existing object at the time of declaration or allocation

Copy assignment operator

A class member function that overloads the built-in function “operator=” to copy an existing object of the same class over to the current object.

smart pointer

Is a class that wraps around a pointer to an object to simplify the memory management of the object

unique_ptr

Is a smart pointer that permits only one owner over an object

shallow copy

Creating a copy of an object by copying only the data members’ values

Algorithm efficiency

typically measured by the algorithms computational complexity

Computational complexity

the amount of resources used by the algorithm

best case

is the scenario where the algorithm does the minimum possible number of operations.

worst case

is the scenario where the algorithm does the maximum possible number of operations

space complexity

a function S(N) that represents the number of fixed-size memory units used by the algorithm for an input of size

Linear search

A search algorithm that starts from the beginning of an array, and checks each element until the search key is found or the end of the array is reached

Binary search

An algorithm for searching a sorted array. Binary search first checks the middle element of the array. If the search key is found, the algorithm returns the matching location. If the search key is not found, the algorithm repeats the search on the remaining left subarray.

constant time operation

an operation, for a given processor, always operates in the same amount of time, regardless of input values

Lower Bound

A function f(N) that is <= the best case T(N) for all values of N >=N_0

Upper Bound

A function f(N) that is >= the worst case T(N), for all values of N>= N_0

stack frame

A return causes those local variables to be discarded

recursive algorithm

An algorithm that breaks the problem into smaller subproblems and applies the same algorithm to solve the smaller subproblems

recursive function

A function that calls itself. Recursive functions are commonly used to implement recursive algorithms

recurrence relation

a recursive call that operates on half of the inout, making the runtime complexity T(N) = 0(1) + T(N / 2)

node

a structure that stores data and has links to other nodes

stack overflow

a stack frame extends beyond the memory region allocated for stack.

(O) — Big O

Upper bound: growth is at most this rate, up to a constant factor

\(\Omega\) — Big Omega

Lower bound: growth is at least this rate, up to a constant factor

\(\Theta\) — Big Theta

Tight bound: both bounds match

ls

List files and directories

mkdir practice

Create a directory named practice

cd practice

Enter that directory

cd ..

Move up one directory

rm file.cpp

remove a file

mv old.cpp new.cpp

Move or rename a file

vi file.cpp or vim file.cpp

Open a file in a text editor

ssh user@host

Connect to a remote computer

Clone

get a local copy of a repository

Status

inspect changes for the next commit

Add

stage changes for the next commit

Commit

Record staged changes locally

Push

Send local commits to the remote repository.