Homework 1
CS 300, Parallel and Distributed Computing (PDC)
Note: In homework assignments, we will use the following abbreviations.
-
[h] Do problem by hand only (computer check is optional).
-
[hc] Try problem by hand, then check on the computer.
-
[c] Work the problem on the computer. Thinking it out ahead of time is encouraged but optional.
When a problem is marked [HC], be as complete and accurate as possible in your handwritten draft---try to anticipate every subtlety.
- Homework 1 Due 9/12/2018
-
-
Setup
-
[c]
On a CS lab or classroom machine in the RNS Link, create a subdirectory to hold your work on this assignment, as follows.
-
Log in (not to
mist
orhelios
, but just to a CS lab or classroom machine). -
% cd ~ % mkdir PDC % mkdir PDC/hw1 % cd PDC/hw1
(Don't enter the
%
sign: it stands for thecsh
shell prompt on a CS lab or classroom machine.)
-
-
-
Prime numbers
-
[hc]
Write a program
primes.cpp
that determines the prime numbers between 2 andN=1000
, inclusive, using the following Sieve of Eratosthenes approach.Note: Recall that a prime number is an integer greater than 1 that is divisible by only 1 and itself. We say that integer a divides integer b if b is divisible by a, i.e., a × m = b for some other integer m.
Write the following steps out on paper, first:
-
Create an array
num
ofN
bytes, all initialized at 1 exceptnum[0] = num[1] = 0
. (The value 1 will represent true, and 0 will represent false.) -
Define an
int
variablep
for holding one prime number. Invariant: At all times, ifk
> 1 thennum[k]
will indicate whether there is some prime less thanp
that dividesk
.Initialize
p
at the smallest prime number, 2 (so the invariant will be true at the outset). -
Next, write a nested loop to "mark out" non-primes divisible by
p
.-
The inner loop should set
num[p*i] = 0
fori
=2, 3, ..., untilp*i
≥N
. This marks each numberp*i
as a non-prime. -
The outer loop should perform the inner loop for each prime
p
, starting withp
=2. After performing the inner loop, the next prime will be the first indexk
>p
such thatnum[k] == 1
.
Note: This outer loop can obviously stop when
p
>N
. In fact, it can stop as soon asp
>sqrt(N)
(can you explain why?). -
-
Finally, write a C++
main()
that defines the variablesnum[]
andp
, carries out the nested loop, then prints all numbersk
such thatnum[k]
=1 after the nested loop. The output will be the primes between 2 andN
, inclusive2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...
Now implement your program on a CS lab or classroom computer.
-
-
[c]
Use your program
primes.cpp
to determine how many primes are there between 2 and 1,000,000, inclusive
-
-
Delivery
-
First, on a Link computer,if you haven't already done so, carry out the following steps:
-
Parts A and B1 only of this document
-
Enter
% git config --global user.name "Your Name" % git config --global user.email "username@stolaf.edu" % git config --global core.editor "emacs"
(enter a different editor besidesemacs
if preferred.)
This enables you to perform
git
operations from the command line without entering your password each time. -
-
Next, connect your
~/PDC
directory to yourstogit
repository as follows:% cd ~/PDC % git init % git remote add origin git@stogit.cs.stolaf.edu:pdc-f18/username.git
This only needs to be done once to associate your~/PDC
directory to yourgit
repository.Note: Check your work carefully on the
git remote add
command above.-
You can check the remote repository your directory is currently associated with using
% git remote -v
-
If you find you have made a mistake and you need to associate with your directory with a different remote repository, enter
% git remote remove origin
then perform anothergit remote add
command.
-
-
Finally, add your files to your repository on
stogit
using these commands:% cd ~/PDC/hw1 % git add primes.cpp % git commit -a -m "HW1 submission" % git pull origin master % git push origin master
Homework, labs, and projects will all be submitted using
git
, a widely used revision control/repository system. The CS-managedstogit
server already contains a repository/username
for your St. Olafusername
-
-