Homework Set #1 (two problems) will be due on the second Thursday of
the semester (9/5/24) at the beginning of class (7pm; NO late homework
accepted!).

Also printed here is a sneak peek at part of Homework Set #2 (problem 2.1
below).  The last day to drop or add a class is Monday, 9/9/24, so I
recommend that you attempt to solve problem 2.1 by Sunday night.  If you
can't get it right (you can, if you wish, send me a URL pointing at your
2.1 work and I'll [pre-]evaluate it by Sunday), you should seriously consider
dropping the course and try again in a better-prepared future semester.
[I will grade Homework Set #1 quickly and email you the grade you earned
on the first two problems well before Monday's drop/add deadline.]

Our textbook is referenced below.  The entire text is available online at
https://edoras.sdsu.edu/~carroll/CS460Baase.pdf

1.1 ("1.1" means "problem #1 in HW set #1"):  TWO parts to this question!
Consider the eight properties in Lemma 1.1 (on Page 15 of Baase).
1.1a: Derive property 8 directly from Definition 1.3 (also on page 15)
and the other seven properties listed in Lemma 1.1.
In this proof, make sure you do not leave out any steps.  (Explicitly
cite reasons for each step of your proof [you might, for example,
find it necessary to cite property 2 as the reason for a step].)

Note that to get a feel for the procedure, you typically would start with
the assertion and simplify it until you reach something like m=m.  Such a
reduction is NOT a proof, but with luck, it looks very much like the proof
'written backward'.  A real proof will start with simple facts you know to be
true (such as m=m), and become progressively more complicated until you reach
the desired conclusion (the equality stated in part 8 of Lemma 1.1).

DON'T turn in a backwards derivation -- present a real proof!
The sequence of statements in the left-hand column in the proof of Theorem 3.5
(page 110 of Baase) is an excellent example of what I've described.
The two-column format shown is a great way to present the justifications
for each step, and helps you double-check that you haven't made an
illogical leap of faith along the way.

Reminder: Pencil and paper submissions are fine.  As long as your
work is legible, there's no need to typeset it all fancy-like.

1.1b: Use the definition of logarithm (Definition 1.3) to justify that
      lg (lg (lg (lg 65536))) = 1
...by solving a series of exponential equations (show your work!).
As explained on page 15, "lg x" means: "the base-2 log of x".

1.2: Suppose you are given floating-point numbers a, b, c, and d, and you
must compute the two quantities
x = ab+bc+ad-cc
and
y = ab+cc+cd
As written, the equations suggest doing seven multiplications, though clearly
if cc is computed and stored in an intermediate variable, then only six
multiplications are needed.  This could be expressed algorithmically as:
temp1 = c*c
x = a*b + b*c + a*d - temp1
y = a*b + temp1 + c*d
which clearly illustrates how to compute the result with six multiplications.
That still is not very efficient, though.

Note that divisions 'cost' as much as multiplications, so don't try to
replace a multiplication with several divisions.  (Rather, as the problem
indicates, your goal is to replace a multiplication with some additions
and/or subtractions.)  Trying to simulate a multiplication with a few million
repeated additions would likewise not be considered an acceptable answer.

By cleverly computing more complex intermediate quantities,
show how to compute x AS WELL AS y by using only a total of three
multiplications (instead of the six or seven multiplications suggested above;
it's OK to do a few extra assignments, additions, and/or subtractions.)
Hint: try to make clever use of the distributive law.

Note that the requirement is not 3 for EACH equation, but 3 multiplications
in total for BOTH equations).  That is, show the pseudocode for a program
that will accept a,b,c,d as input and print BOTH x and y as output, using
only 3 "*" operators in your code.  Clearly state your algorithmic steps,
naming your intermediate quantities, and showing the order in which you
compute them [like the sample pseudocode using temp1 shown above].

You will likely have lots of scratchwork to help justify how you derived
your formula[s], and this is likely to obscure exactly what steps comprise
your final algorithm, and the order in which they should be executed.  So:

CLEARLY INDICATE YOUR PSEUDOCODE and enclose it in a box, with the relevant
steps in the proper order, so that I can figure out what assignment
statements actually comprise your algorithm.

Never forget that it is important that you work out each of these
problems on your own, not as a group.  There are dozens of different
ways to come up with equations that pare down the number of
multiplications, so group-work will be especially obvious here.
Remember that the point of these problems is to give you the
experience you need to survive the exams -- looking over a
pre-made answer is of no help in *learning* how to do it yourself.
[Review the course policy on cheating, because I monitor bad behavior
closely.]

Also remember that you're not entirely on your own -- if you get
stuck (or can't figure out how to start), email me, and we'll find
a way to push you a bit further forward.  And I'll precheck your
homework as many times as you like, so there's no reason not to
get 100% on everything.  Start early, and take full advantage of
my insane pregrading policies!

When emailing me, please DO NOT send me attachments -- there are
only limited situations in which I can gracefully handle those.
If there's something you want me to look over (that's more than
just plain text in an email message!), fling it up on the web
somewhere and send me the URL (e.g., google docs, etc.)




The Homework Set #2 problem requires a little more background, and I'll
go over the hints below in class once we reach that point in the lectures.
But the above two problems can be tackled right away, as they only
rely on concepts from previous courses.  [And 'right away' is crucial,
as you will likely need a lot of time to get problem 2.1 solved.]


Continued on page 2...


The following problem is NOT due on 9/5/24; it will be due the following
week, and may also involve an [as yet unspecified] problem 2.2.
It's included here to give you a better sense of the type of exercise
and thinking we will be doing in this course.  Trying to solve it now
may help you determine if you're ready to take CS460 this semester.
So here it is:


2.1: The Average-Behavior analysis of Algorithm 1.1 (Page 36) makes several
simplifying assumptions; in particular, it is assumed that no value shows up
in two different places in the array.  The formula (shown on Page 37) is
much more complex if the elements are not distinct.  In this problem, you
are asked to analyze one such scenario:

For simplicity, assume that n (the array size) is at least 4.
Assume that three of the elements in an n-element array are identical,
and that the remaining elements are all distinct.  Assume the array is
unsorted (so the elements are 'randomly scattered' throughout the array,
with three of them taking on a single common value).

Develop a formula for A(n), in terms of n and q (based on the definitions
of A, n, and q as on Pages 35, 35, and 37).

(This third problem is harder than the first two, so it will be worth more
points than the others.)  Here are some hints that may help:

Note that under the conditions given in this last homework problem,
the short paragraph on Page 36 only has to be modified slightly for the new
worst case analysis; the worst case scenario is very close to the way it was
before.  Alas, you will find that the average case analysis is substantially
more difficult to compute under our new circumstances.  Note that I'm only
asking you to show your work for the average case analysis -- you do not
have to write up a justification for the worst case formula.

If a given K is not found, it will take just as long to discover that.
However, if the value of K matches a value in the array, we know that
one of two things will happen:
the value will occur just once (like it did in the original analysis),
or
it must occur in three places in the array.

So, that special value is more likely that it will be found 'earlier' than
values that only occur once, since it occurs in three spots, not just one spot.
Thus, you will have to present a much more complex argument for the special
multiply-occurring value.

For example, consider the chance that it will take 4 attempts before the element
K is found in the array.  For this to happen, we must have something like
1st: not-K
2nd: not-K
3nd: not-K
4th: K
5th, 6th, 7th,..., nth slots: two of these slots contains the other
instances of K (since if you happen to be looking for that 'special'
repeated value, it will appear in the array three times). So,
to determine the likelihood that it will take exactly four 'basic operations'
(comparisons) to find K, you need to find out how likely this situation is.
To do that, you have to count the ways this could happen, which amounts
to counting how you can distribute the remaining occurrences of K in the
remaining n-4 positions.  In effect, you have to choose two of the n-4 slots
to put the other copies of K in. (ALTERNATELY, you can compute the probability
of finding the not-K,not-K,not-K,K sequence of events.)

So, that's the thinking needed if the value shows up (first) in the fourth slot.
Similar calculations have to be done when K shows up in the very first slot,
and when it shows up for the first time in the second slot, in the third slot,
etc.  Why don't you have to worry about the multiply-occurring key K showing
up for the first time in the very last slot?

You may find the problem is incompletely specified.  If so, make sure you state
your assumptions that led to the formula you developed.  IN PARTICULAR:
You will have to decide how likely it is we are searching for that 'special'
repeated value -- are we only as likely to be looking for it as for any
of the other (unique) values?  Or will you be searching for it three times
as often as for the unique values?  (Either assumption is OK, but your
formula will be different, depending on which scenario you choose, so
be EXPLICIT about your assumptions!)

REMEMBER that the deadline for HW#1 is Thursday, 9/5/24 at 7:00pm.
[And remember that problem 2.1 outlined just above will NOT be due for a while.]

NO late homework accepted!

(I don't want people getting into traffic accidents racing to class,
so there are circumstances in which you can get around the 7:00pm cutoff.
If it's a bit after 7:00, the rules are:
You must enter the classroom by the door at the front of the room.
you must fling your homework on the front table BEFORE taking your seat --
don't be polite and wait till after class; I won't accept it that late.)