http:^^cs.nyu.edu^cs^dept_info^course_home_pages^spr96^g22.2233^more-course-info.html

This data set contains WWW-pages collected from computer science departments of various universities

Class-12: 4/18/96 -- Chapter 6 completed + <!WA38><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/class-notes/class12.ps#class-12">Some Additional Material</A>
</td>
</tr>

<! Row 13 --------------------->
<tr>
<td align=center >
Class-12: Chapter 7 + <!WA39><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/class-notes/class13.ps#class-13">Some Additional Material</A>
</td>
</tr>

<! Row 14 --------------------->
<tr>
<td align=center >
<!A HREF="class-notes/class14.ps#class-14">Class-14: 5/2/96</A>
</td>
</tr>

</table>
</center>
<!WA40><IMG SRC="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/images/line.gif">
<H3><A NAME="homework">Homework/Exam Policy</A></H3>

Weightage for final grade:
<br>
<br>
Homeworks: 30 percent
<br>
No Mid-term
<br>
Final: 70 percent
<br>
<br>
Note-1:
<br>
All homeworks regardless of their total points will carry EQUAL
weight in the final grade.
<br>
<br>
Note-2:
<br>
Please note that a good on-time homework record can boost
your final grade, if you are on the fence.
<br>
<br>
Note-3:
<br>
Homeworks may be emailed to the TA ([e-mail]).
For those of you who submit hardcopy homework (instead of email'ing
a soft copy):
<br>
If you plan to return the homework outside the class
and office hours, please make arrangements with the TA
(fangzhe@cs) and leave it in his mailbox instead of mine.
<br>
<br>

<!WA41><IMG SRC="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/images/line.gif">
<H3><A NAME="hw-assign">Assigned Homeworks</A></H3>

<hr>
Homework-5:     <blink>Due: Apr 25</blink> (points same as in Text)
<ul>
<li>
5.1 - 5.16 (You can use Fig. 5.47 in Prob. 5.7)
<li>
6.1-6.3, 6.8-6.9
<br>
I strongly urge you to go through the example on pp. 389,
covering Figs. 6.25 to 6.29.
</ul>
<hr>
Homework-4:     <blink>Due: Apr 4</blink> (points same as in Text or shown in large brackets)
<ul>
<li>
4.1 - 4.19
<li>
4.26 - 4.30
<li>
4.39, 4.41, 4.42
<li>
Using the algorithm in Fig. 4.41, carry out the following addition in binary:
-0.625 + 1.4375. Assume 5 bits of precision (4 bits after decimal). You
must show all steps. [10]
<li>
Using the algorithm in Fig. 4.43, carry out the following multiplication in 
binary: -0.625 x 1.4375. Assume 5 bits of precision (4 bits after decimal). You
must show all steps. [10]
</ul>

<hr>
Homework-3:     <blink>Due: Mar 21</blink> (points shown in large brackets)

<ol>
<li>
Text B.7 [15]
<br><br>

<li>
Text B.8 [15]
<br><br>

<li>
Text B.12 [15]
<br><br>

<li>
Consider the following gate called
IMPLICATION gate which implements the following
function: C = A -> B :

<br>
A=F, B=F => C=T
<br>
A=F, B=T => C=T
<br>
A=T, B=F => C=F
<br>
A=T, B=T => C=T
<br>

a) Can you build an invertor using this gate? [5]
<br>
b) Is this gate universal? Explain your answer. [10]
<br><br>


<li>
[I added this problem beyond the ones mentioned in class on 3/7]
<br>
Using the laws of Boolean algebra on page B-6 (without using
truth tables), prove the following:
<ol>
<li>
These are known as "Consensus Theorems": [10]
<ol>
<li>
XY + X'Z + YZ = XY + X'Z
<li>
(X + Y) (X' + Z) (Y + Z) = (X + Y) (X'+ Z)
</ol>
Note-1:  X' refers to complement or invert of X, and so on.
<br>
Note-2: The redundant term "YZ" or "(Y + Z)" are also called 'consensus'
<br>
<blink>Note-3:</blink> Earlier (prior to Mar 18) part 2 had a typo.
The correct third term is (Y+Z).  It was mistyped as: (Y'+Z).
However, Note-2 had the proper redundant term.

<li>
Use the consensus theorems to prove the following: [15]
<br>
ABCD + B'CDE + A'B' + BCE' = A'B' + BCE' + ACDE

<li>
Use the consensus theorem to prove the following addition theorem: [10]
<br>
(X + Y) (X' + Z) = XZ + X'Y

<li>
Use the theorems above to show: [20]
<br>
(A + B + C') (A + D' + E) (A + B + D) (A' + C)
= AC + A'BD' + A'BE + A'C'DE
</ol>
<br><br>

<li>
Show the PLA implementation (similar to Figs. B.6 or B.7) of the following
functions: [10]
<ol>
<li>
F1 = A'BD + ABD + AB'C' + B'C
<li>
F2 = C + A'BD
<li>
F3 = BC + AB'C' + ABD
</ol>
<br><br>

<li>
Text B.13 [15].
<br><br>

<li>
Using D flip-flops and other combinational logic elemnts, if needed,
construct the following:
<ol>
<li>
A 4-bit counter which has the following counting sequence: [10]
0001, 0010, 0100, 1000, 0001, ...

<li>
A 4-bit register which has the initial content of 0000 and shifts left
a '1' on each clock tick, starting at the least-significant-bit
position. [10]

<li>
A 4-bit register which has the initial content of 0000 and shifts right
a '1' on each clock tick, starting at the most-significant-bit
position. [10]
<br>
<blink>Note:</blink> Prior to Mar 18, there was typo here and it incorrectly said:
'least-significant' instead of 'most-significant'.  You cannot
shift right starting as least-significant-bit position!
</ol>
<br><br>


<li>
Modify the state diagram in Fig. B.28 for the following modifed
traffic controler: [15]
<br>
North-South road has priority over East-West road. So, NSlite
should normally be green and trun to red only if a) there
is a car waiting on E-W road and there is no car on N-S road,
or, b) there is a car waiting on E-W road for more than 4 mins.
The EWlite should turn to red if there is no car on E-W road.
or if there is car waiting on N-S road for more than 2 mins.

</ol>

<hr>
<strong>Homework-2:</strong> 	<blink>Due: Mar 7</blink>
(points same as the problem rating given in Text)
<br>
<br>
All problems from the Text, Chapter 3:
<br>
<br>
3.1 through 3.8
<br>
3.12 through 3.22
<br>
3.26
<br>
3.37 through 3.38
<br>
<br>
<hr>
<strong>Homework-1:</strong> 	<blink>Due: Feb 22</blink> (points shown in large brackets)

<br>
<br>
Problem 1:
<br>
Exercise 1.A on slide-11 of class-1 notes [5]
<br>
<br>

Problem 2:
<br>
Repeat Problem 1 with the two cost-model improvements
suggested in slide-11 of class-1 notes. [5]
<br>
<br>

Problem 3:
<br>
Text 2.14 [10], 2.15 [5], 2.16 [10], 2.17 [5], 2.18 [5], 2.19 [10]
<br>
<br>

Problem 4:
<br>
Repeat the class example (slide 26) with System-3
execution times for normalization, i.e., using System-3
execution times as the relative measures of workloads.
In other words, you need to calculate average execution rates
(normalized with respect to System-3 execution times)
of the four systems using unweighted and weighted
versions of arithmetic, geometric, and harmonic means.
Note that the  workload represented by program i,
i.e., w<sub>i</sub> will be given by its execution
time on System-3, i.e., t<sub>i3</sub>.
<br>
[20]
<br>
<br>

Problem 5:
<br>
Text 2.32 [5] 2.33 [10], 2.34 [10]
<br>
<hr>

<!WA42><IMG SRC="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/images/line.gif">
<H3><A NAME="hw-sols">Solutions to Assigned Homeworks</A></H3>

<p>
<center><table border=1 cellspacing=0 cellpadding=0 width=375>
<tr>
<! Row 1 --------------------->
<td align=center >
<!WA43><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/solutions/solutions1.ps#solutions-1">Solutions-1</A>
</td>
</tr>

<tr>
<! Row 2 --------------------->
<td align=center >
<!WA44><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/solutions/solutions2.ps#solutions-2">Solutions-2</A>
</td>
</tr>

<tr>
<! Row 3 --------------------->
<td align=center >
<!WA45><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/solutions/sol31.ps#solutions-31">Solutions-3, Part-1</A>
<!WA46><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/solutions/sol32.ps#solutions-32">Solutions-3, Part-2</A>
<!WA47><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/solutions/sol33.ps#solutions-33">Solutions-3, Part-3</A>
<!WA48><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/solutions/sol34.ps#solutions-34">Solutions-3, Part-4</A>
<!WA49><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/solutions/sol35.ps#solutions-35">Solutions-3, Part-5</A>
<!WA50><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/solutions/sol36.ps#solutions-36">Solutions-3, Part-6</A>
</td>
</tr>

<tr>
<! Row 4 --------------------->
<td align=center >
<!WA51><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/solutions/solutions4.ps#solutions-4">Solutions-4</A>
</td>
</tr>

<tr>
<! Row 5 --------------------->
<td align=center >
<!WA52><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/solutions/solutions5.ps#solutions-1">Solutions-5</A>
</td>
</tr>

</table>
</center>