**Question 4.1-1:**What does $\textit{Find-Maximum-Subarray}$ return when all elements of $A$ are negative?

The procedure would return the single element of maximum value. This is expected since the maximum subarray must contain at least one element. This can be computed by note that $\textit{Find-Max-Crossing-Subarray}$ will always return the array of solely the midpoint and that $\textit{Find-Maximum-Subarray}$ always finds the maxium of $\{leftsum, rightsum, and crosssum\}$

**Question 4.1-2:**Write pseudocode for the brute-force method of solving the max-subarray problem. Your solution should run in $\theta(n^2)$ time.

`max_i =`

*nil*

max_j =*nil*

max_sum = -∞

for i in 0..len(A):

cur_sum = 0

for j in i..len(A):

cur_sum += A[j]

if cur_sum > max_sum:

max_sum = cur_sum

max_i = i

max_j = j

return (max_i, max_j, max_sum)**Question 4.1-3:**Implement both the brute-force and recursive algorithms for the maximum-subarray problem on your own computer. What problem size $n_0$ gives the crossover point at which the recursive algorithm beats the brute-force algorithm? Then, change the base case of the recursive algorithm to use the brute-force algorithm whenever the problem size is less than $n_0$. Does that change the crossover point?

*This question asks a question that is specific to the implementation, and the computer on which it is run. I will therefore be skipping it in this writeup.*It is worthwhile to note that it is almost guarenteed that changing he implementation to use the brute force method for values less than $n_0$ is very likely to change $n_0$.**Question 4.1-4:**Suppose we change the definition of the maximum-subarray problem to allow the result to be an empty subarray, where the sum of the values of an empty subarray is 0. How would you change any of the algorithms that do not allow empty subarrays to permit an empty subarray to be the result?

For the brute force algorithm it would be rather trivial to add a check, and if the return max_sum is > 0 return the empty array.

For the recursive divide and conquer algorithm is is sufficient to just change the $\textit{Find-Max-Crossing-Subarray}$ in a manner similar to the brute force method. If $\textit{Find-Max-Crossing-Subarray}$ return the correct value, then $\textit{Find-Maximum-Subarray}$ will do the correct thing.

**Question 4.1-5:**Develop a nonrecursive linear-time algorithm for the maximum-subarray problem.

^{[1]}If one knows a previous answer to the max-subarray problem for a given prefix of the array than any new element consists of only two cases: being part of the maximum subarray or not being part of the maximum subarray. It is easier to explain with pseudocode:

`max_start = 0`

max_end = 0

max_sum = A[0]

max_with_j = A[0]

for j in 1..len(A):

# If J is in a maximum-subarray, either j is going to being the maximum on its, or it will will add to the current max

max_with_j = max(A[j], max_with_j + x)

Determine if J is in a maximum-subarray

if max_with_j >= max_sum:

max_sum = max_with_j

max_end = j

#Set the starting value if j is the sole element of a new subarray

if max_with_j == A[j]:

max_start = j

return (max_start, max_end, cur_max)

## Monday, June 15, 2015

### Blogging My Way Through CLRS Section 4.1

## Sunday, March 29, 2015

### FreeBSD SMB Client under OSX Host

I recently purchased a new Macbook Pro and wanted to get a FreeBSD Virtual Machine set up in order to continue doing development work on it. Unfortunately, FreeBSD as a guest does not support native folder sharing so I decided to try using a samba mounted.

I decided to set up my VM to have two network interfaces: a NATed interface for internet access and a host-only interface for access to SMB and ssh.

The NAT networking configuration looks like:

NetworkName: FreeBSDNatNetwork IP: 10.0.2.1 Network: 10.0.2.0/24 IPv6 Enabled: Yes IPv6 Prefix: DHCP Enabled: Yes Enabled: Yes Port-forwarding (ipv4) SSH IPv4:tcp:[]:5022:[10.0.2.4]:22 Port-forwarding (ipv6) FreeBSD ssh:tcp:[]:6022:[fd17:625c:f037:2:a00:27ff:fefc:9dab]:22 loopback mappings (ipv4)

The Host-Only networking configuration looks like:

Name: vboxnet0 GUID: 786f6276-656e-4074-8000-0a0027000000 DHCP: Disabled IPAddress: 192.168.56.1 NetworkMask: 255.255.255.0 IPV6Address: IPV6NetworkMaskPrefixLength: 0 HardwareAddress: 0a:00:27:00:00:00 MediumType: Ethernet Status: Up VBoxNetworkName: HostInterfaceNetworking-vboxnet0The FreeBSD configuration looks like this: The OSX sharing configuration looks like:

Unfortunately, when attempting to actually mount the SMB filesystem with:
`mount_smbfs -I 192.168.56.1 //eax@192.168.56.1/shared_vbox`

I get the error `mount_smbfs: can't get server address: syserr = Operation timed out`

I tried installing the package `net/samba36`

and found that I needed the `--signing=off`

flag to let it work:

It seems based on this setup and research that FreeBSD can not natively mount an OSX samba share. It might be possible to use `sysutils/fusefs-smbnetfs`

. Other people have recommended NFS or sshfs.