Homework Assignment 1

Question 1. Trace Tables

Trace table is a table that shows the values of relevant variables or expressions at each step of a program from start to finish.

Each column of the table represents a variable or expression in the program. Each row of the table represents a single step of the program.

Use the table above to trace the search algorithm/code above. Add rows to the table as needed.

Trace tables are a useful tool for understanding the flow of control and mapping of inputs to outputs in a program. They are often used for debugging.

Consider the block of code below that solves the following search problem:

Problem: Given two inputs:

1. list of n numbers data and

2. a number called query,

return output last location of query in list, if it exists, otherwise return -1

Code:

def search(data, query):         # line 1
   for i in range(len(data)):    # line 2
      if data[i] == query:       # line 3
         return i                # line 4
   return -1                     # line 5

For inputs: data = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] and query = 5, the trace table would look like this:

data = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] and query = 5

For the function search above create a trace table for the following sets of inputs:

• data=range(10) and query = 0

• data=range(10) and query = 10

and answer the total number of lines of code executed for each set of inputs by counting the number of rows in the trace table.

For the following sets of inputs, answer the total number of lines of code executed without creating a trace table:

• data=range(1000*1000) and query = 0

• data=range(1000*1000) and query = 1000*1000

---

Question 2. Best Case, Worst Case

On the axes below, plot the number of lines of code executed for the function search from Q1 for the following inputs:

Plot the number of lines of code executed for the function search from Q1 for given inputs.

• Line 1:

  • data=range(1) and query = 0

  • data=range(2) and query = 0

  • data=range(4) and query = 0

  • data=range(6) and query = 0

  • data=range(10) and query = 0

• Line 2:

  • data=range(2) and query = 1

  • data=range(4) and query = 3

  • data=range(6) and query = 5

  • data=range(8) and query = 7

  • data=range(10) and query = 9

Which of the two lines above is the best case scenario? Which is the worst case scenario?

Describe in words what the best case scenario and worst case scenario mean for this function in terms of inputs.

---

Question 3. Pseudocode

What value is returned by the each of the functions below?

Express your answer in terms of the input n.

1.1.

function loop(n)
    r ← 0
    for i ← 0 to n-1 do
        r ← r + 1
    return r

1.2.

function twoloops(n)
    r ← 0
    for i ← 0 to n-1 do
        r ← r + 1
    
    for j ← 0 to n-1 do
        r ← r + 1
    return r

1.3.

function threeloops(n)
    r ← 0
    for i ← 0 to n-1 do
        r ← r + 1
    
    for j ← 0 to n-1 do
        r ← r + 1

    for k ← 0 to n-1 do
        r ← r + 1

    return r

1.4.

function twonestedloops(n)
    r ← 0
    for i ← 0 to n-1 do
        for j ← 0 to n-1 do
            r ← r + 1
    return r

1.5.

function threenestedloops(n)
    r ← 0
    for i ← 0 to n-1 do
        for j ← 0 to n-1 do
            for k ← 0 to n-1 do
                r ← r + 1
    return r

1.6.

function function_call(n)
    a ← loop(n) //from 1.1
    b ← loop(n) //from 1.1
    r ← a + b
    return r

1.7.

function function_call_in_loop(n)
    r ← 0
    for i ← 0 to n-1 do
        a ← loop(n) //from 1.1
        r ← r + a
    return r

1.8.

function repeatedly_half(n)
    r ← 0
    while n > 2 do
        n ← n / 2
        r ← r + 1
    return r

1.9.

function repeatedly_divide(n, c)
    r ← 0
    while n > c do
        n ← n / c
        r ← r + 1
    return r

---