Homework #1

Due Date: Monday, April 11th at 9pm.

The following homework exercises are intended to help you practice some of the programming concepts introduced in weeks 1 and 2, up to loops. You may not use arrays to solve any of these problems.

Getting Started

You will be using a new repository for each homework in this course. Start by verifying that your GITHUB_USERNAME environment variable is set correctly by running the following:

echo $GITHUB_USERNAME

If you do not see your GitHub username, please revisit the “Environment variable setup” section of Lab #1.

Now you will work through a series of steps to initialize your Homework #1 repository.

Step 0: Verify that your repository has been created on GitHub.

Make sure you have accepted the Homework #1 invitation URL that was posted on Ed and that your repository has been created on GitHub. To verify that your repository exists, open a browser tab to this URL: https://github.com/uchicago-cmsc15200-spr-22/hw1-GITHUB_USERNAME where GITHUB_USERNAME is replaced by your GitHub username. If you are not able to open this URL successfully, please ask for help.

Step 1: Create a directory for your Homework #1 repository:

cd
mkdir -p cmsc15200/hw1-$GITHUB_USERNAME
cd cmsc15200/hw1-$GITHUB_USERNAME

The purpose of the initial cd is to make sure you are starting from your home directory.

Notice how we’re using the GITHUB_USERNAME variable that we defined earlier. When you run the above commands, the shell will automatically replace the text $GITHUB_USERNAME with your GitHub username.

The purpose of the second cd is to move you to the directory where you will do your work for this homework. Run pwd to make sure you are in the right place. (A little sanity checking goes a long way towards avoiding mistakes.)

Step 2: Run this command to initialize a local repository:

git init

Step 3: Run this command to connect your local repository to your Homework #1 repository on GitHub:

git remote add origin git@github.com:$GITHUB_152_ORG/hw1-$GITHUB_USERNAME.git

This command will not generate any output, if it ran successfully.

Step 4: Run these commands to connect your repository to the “upstream” repository that we will use to distribute code for this homework and to pull the initial files for the homework:

git remote add upstream git@github.com:$GITHUB_152_ORG/hw1-upstream
git pull upstream main

If these commands were successful, you will see something roughly of the form:

remote: Enumerating objects: 9, done.
remote: Counting objects: 100% (9/9), done.
remote: Compressing objects: 100% (9/9), done.
remote: Total 9 (delta 0), reused 9 (delta 0), pack-reused 0
Unpacking objects: 100% (9/9), 1.53 KiB | 9.00 KiB/s, done.
From github.com:uchicago-cmsc15200-spr-22/hw1-upstream
 * branch            main       -> FETCH_HEAD
 * [new branch]      main       -> upstream/main

The exact number of files and/or objects may differ. If you get an error, please ask for help. It is important to pay attention to the error messages from git commands. Don’t just blindly run them. Make sure the output looks sensible and does not contain any errors or warnings.

Step 5: Set the name of the branch:

git branch -M main

This command will not generate any output, if it runs successfully.

Step 6: And finally, upload your local Git repository to GitHub, by running:

git push -u origin main

If this command fails, please ask for help; you likely made a mistake setting up your environment variables or in Step 3.

Step 7: Do a sanity check.

Run ls. If everything went smoothly, you should find the following files in your Homework #1 directory:

README.md
homework1.h
homework1.c
student_test_homework1.c
test_homework1.c

along with some other files. These files should also be in your repository on Github (see https://github.com/uchicago-cmsc15200-spr-22/hw1-GITHUB_USERNAME where GITHUB_USERNAME is replaced by your GitHub username.)

Also, if you run:

git status .

in your hw1-GITHUB_USERNAME directory, the result should be:

On branch main
Your branch is up to date with 'origin/main'.

nothing to commit, working tree clean

You are now set to do the work required for Homework #1.

Note

The repositories created by GitHUb Classroom can be a bit hard to find from the standard GitHub interface. Fortunately, there is a page that lists your repositories for this course. We strongly recommend creating a bookmark in your browser to it: https://github.com/uchicago-cmsc15200-spr-22.

Compiling and testing your code

We will use the same testing infrastructure as Lab #2. Feel free to skim or skip this section.

Instead of compiling your code by hand using clang, you will be using make, a tool that automatically builds executables from source code. make reads a file, called Makefile, that specifies how to construct a target program. We will provide the necessary makefiles.

For the this homework, the Makefile has targets for compiling your code with tests that you write, for compiling your code with our automated tests, and for cleaning up generated files. To use this file to compile your code, run one of the following commands from the Linux command-line:

$ make student_test_homework1

$ make test_homework1

$ make

The first command will compile your code in homework1.c along with any tests you have added to student_test_homework1.c and will, if possible, generate an executable (student_test_homework1). To run the resulting executable, you can run:

$ ./student_test_homework1

We have provided some simple tests as examples in student_test_homework1.c. You should add tests of your own as your work on your code.

The second command will compile your code with our automated tests and will, if possible, generate an executable (test_homework1). To run all of the tests using the resulting executable, run this command from the command line:

$ ./test_homework1 -f --verbose

The -f flag tells the test code to stop after the first failure. The --verbose flag generates information about which specific tests passed and failed.

The tests are broken into suites. To run a specific suite or test, you can add a filter. For example, to run all of the tests in are_friendly suite, you would run:

$ ./test_homework1 -f --verbose --filter="are_friendly/*"

To run a specific test, replace the * with the name of the test. For example, the first test in the are_friendly suite, you would run:

$ ./test_homework1 -f --verbose --filter="are_friendly/test0"

The code in test_homework1.c is easily readable. If you fail a test, look for the corresponding suite and test in test_homework1.c to see the arguments passed to your function and the expected result. Don’t just tinker with your code in the hopes of hitting upon a solution. Instead, try to reason through why your code is failing on those specific inputs and what it means more generally about potential flaws in your implementation.

Exercises

  1. Two integers are called “friendly” if they share a common divisor. Complete the function are_friendly, which takes two integers num1 and num2 and an integer divisor, and returns true if num1 and num2 are friendly with respect to the divisor, and false otherwise.

    For example, the call are_friendly(12, 15, 3) should return true, since both 12 and 15 are divisible by 3.

  2. Complete the function degree_of_friendship, which takes two integers num1 and num2 and returns the number of divisors that num1 and num2 have in common (that is, how “friendly” they are). You can assume that the input to this function is positive.

    For example, the call degree_of_friendship(12, 15) should return 2. The divisors of 12 are 1, 2, 3, 4, 6, and 12, and the divisors of 15 are 1, 3, 5, and 15. So, 12 and 15 have the divisors 1 and 3 in common. Divisors do not need to be prime.

  3. In mathematics, an integer has “even parity” if it is even. Complete the function has_even_parity, which takes an integer num and returns true if num has even parity, and false otherwise. For example, the call has_even_parity(5) should return false, since 5 is not even. You may not use the modulus operator (%) or any function that uses the modulus operator for this problem.

  4. In this problem, you will implement Goldschmidt’s algorithm for computing the square root of a number \(N\). Goldschmidt’s algorithm uses an estimate for \(\frac{1}{\sqrt{N}}\) and begins with:

    \begin{eqnarray} &b_0= N \\ \\ &Y_{0} \approx \frac{1}{\sqrt{N}}\\ \\ &x_{0}= N Y_{0} \end{eqnarray}

    Each step of the algorithm computes a new estimate \(x_n\) for \(\sqrt{N}\) as follows:

    \begin{eqnarray} &b_{n}=b_{n - 1} Y^2_{n-1} \\ \\ &Y_{n}=\frac{3 - b_{n}}{2}\\ \\ &x_{n}=x_{n-1} Y_{n} \end{eqnarray}

    The algorithm has converged when \(\lvert b_n - 1 \rvert\) is small.

    Complete the function goldschmidt, which returns an approximation to the square root of a number, computed using Goldschmidt’s algorithm. The parameters to goldschmidt are:

    • \(N\)

    • an initial estimate for \(\frac{1}{\sqrt{N}}\)

    • the maximum number of iterations to perform

    • a specified convergence tolerance

    In this function, you should implement Goldschmidt’s algorithm, updating \(b_n\), \(Y_n\), and \(x_n\) until the maximum number of iterations has been reached, or when \(\lvert b_n - 1 \rvert\) is less than the specified tolerance (whichever comes first). The final approximation of \(\sqrt{N}\) is \(x_n\).

    You can assume that the input to this function is positive. You can also use the fabs function from math.h in your implementation. You should not use any other functions from math.h.

  5. Complete the function index_of_highest_1, which takes an unsigned integer num and returns the index of the highest-order (leftmost) 1 bit in its binary representation. Return -1 if num does not contain any 1s. You may not use the modulus operator (%), the division operator (/), or the multiplication operator (*) for this problem. You can use addition or subtraction as needed.

    The indices of the bits of a number are enumerated starting with zero for the lowest-order (rightmost) bit. For example, the binary number 10110 has a 0 at index 0, a 1 at index 1, a 1 at index 2, a 0 at index 3, and a 1 at index 4.

    The call index_of_highest_1(12) should return 3. The binary representation of 12 is 1100, so the highest-order 1 is located at index 3.

  6. Consider a positive integer \(n\). \(n\) is called “narcissistic” if each digit of \(n\) raised to the number of digits in \(n\) and added together returns \(n\).

    For example, the number \(153\), which has three digits, is narcissistic. Raising each digit to the power of \(3\) and adding them gives \(1^3 + 5^3 + 3^3 = 153\), itself. Another example is \(9474\), since \(9^4 + 4^4 + 7^4 + 4^4 = 9474\).

    Compete the function is_narcissistic, which takes a positive integer num and returns true if num is narcissistic, and false otherwise. You may use the pow function from math.h in your implementation. You should not use any other functions from math.h.

Note: As described above, you can use the math.h functions fabs in Exercise #4 and pow function in Exercise #6. You should not use fabs or pow in other exercises, or any other functions from math.h in any exercise.

Grading

For this assignment, the weights will be:

  • Completeness: 60%

  • Code Quality: 40%

The code quality score will be determined by code clarity, style, and whether your implementation stays within the allowed constructs for each exercise.

Preparing your submission

There are three things you should do before you submit your work.

First, make sure you have added the required information to the header comment in homework1.c:

  • your name,

  • the names of anyone beyond the course staff you discussed the assignment with, and

  • links to any resources that you used other than course materials and the course textbook.

Please remove the explanation for what is required. Note: write None in the relevant field, to indicate that you did not use any sources and/or consult anyone beyond the course staff.

Second, remove directives, such as:

// YOUR CODE HERE

// Replace 0.0 with an appropriate return value

from your code. Make sure to recompile and rerun the tests after you make these changes. It is easy to introduce a syntax error at this stage.

Third, add, commit, and push your work to GitHub.

And finally, get your directory into a clean state. Run make clean to remove any executables that are laying around.

Submission

To submit your work, you will need to add, commit, and push your code to GitHub. Before you upload your code to GitHub, run git status . to make sure you did not forget to add/commit any of the required files. Then upload your submission to Gradescope under the “Homework #1” assignment. Make sure to choose the right assignment on Gradescope!

You are welcome to upload your code to Gradescope multiple times before the deadline, but it is wildly inefficient to use Gradescope as a compute server. You should test your code on the CS Linux machines and only upload it when you think you are finished or when you are getting close to the deadline and want to do a “safety” submission.

You are responsible for making sure that the code you upload compiles and runs. You will get zero credit for code that does not compile.

Finally, a reminder that we will not accept late work.