ÿþ<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> <title>CS 1800 Discrete Structures</title> <style type="text/css"> .date { white-space: nowrap } .final { background-color: #ff0 } .exam { background-color: #ff0 } .holiday { background-color: #bff } .canceled { background-color: #4af } .week-separator { background-color: #0af } .olhw { background-color: #fcc } .gem { background-color: #fcc } .whw { background-color: #fac } .due { background-color: #fcf } table, th, td { border: 1px black solid } table { border-collapse: collapse } th, td { padding: .3ex } th { background-color: #ffd700 } </style> </head> <body> <center> <h2>CS 1800 Discrete Structures: Spring 2013 Schedule</h2> <h4>College of Computer and Information Science, Northeastern University</h4> <h3> <a href="index.html">Home Page</a> </h3> <p> Last Modified <script language="javascript"><!-- document.write(document.lastModified) //--></script></p> <table> <tr> <th>Date</th> <th>Topics</th> <th>Reading</th> <th>Exercises</th> </tr> <tr> <td class="date">Mon Jan 7</td> <td class="class"> <div>Overview and Course Organization</div> </td> <td></td> <td class=""></td> <!-- <td class="due"> <div class="due">Get online homework account</div> </td> --> </tr> <tr> <td class="date">Wed Jan 9</td> <td class="class"> <div style="font-weight: bold">Module 1: Computers and Computing</div> <div>Binary Representation of Numbers</div> <div>Converting Between Binary and Decimal</div> </td> <td> <div>Ch. 1 Introduction</div> <div>1.1 Binary Representation</div> <div>1.5 Converting Between Decimal and Binary</div> </td> <td rowspan="2" class="olhw"> <div class="olhw">Book: Chapter 1 Exercises</div> <p> <div class="olhw">OLHW1: Binary, Octal, Hex</div> </td> </tr> <tr> <td class="date">Thu Jan 10</td> <td class="class"> <div>Representing Negative Numbers</div> <div>Two's Complement</div> </td> <td> <div>1.2 Bytes</div> <div>1.3 Hexadecimal Representation</div> <div>1.4 Octal Representation</div> <div>1.6 Representing Negative Numbers: Two's Complement</div> </td> </tr> <tr class="week-separator"> <td colspan="6">&nbsp;</td> </tr> <tr> <td class="date">Mon Jan 14</td> <td class="class"> <div>Wrap-up of Number Representations</div> <div>Logic Gates and Circuits</div> </td> <td> <div>Ch. 2 Introduction</div> <div>2.2 Basic Logic Gates: AND, OR, NOT</div> <div>2.3 More Logic Gates: NAND, NOR, XOR, XNOR</div> </td> <td rowspan="3" class="olhw"> <div class="olhw">Book: Chapter 2 Exercises</div> <div class="olhw">Book: Chapter 3 Exercises</div> <p> <div class="olhw">OLHW2: Logic, Logic Gates</div> </td> </tr> <tr> <td class="date">Wed Jan 16</td> <td class="class"> <div>Logical Completeness</div> <div>Logic Gates and Circuits, contd.</div> </td> <td> <div>2.4 Binary Arithmetic: Ripple Carry Adders</div> </td> </tr> <tr> <td class="date">Thu Jan 17</td> <td class="class"> <div>Logic and Logical Equivalence</div> </td> <td> <div>Ch. 3 Introduction</div> <div>3.1 Truth Values</div> <div>3.2 Truth Tables</div> <div>3.3 Logical Equivalence</div> </td> </tr> <tr class="week-separator"> <td colspan="6">&nbsp;</td> </tr> <tr> <td class="date"> <div>Mon Jan 21</div> </td> <td colspan="3" class="holiday">Martin Luther King Jr.'s Birthday observed, no classes</td> </tr> <tr> <td class="date">Wed Jan 23</td> <td class="class"> <div>Laws of Logical Equivalence</div> <div>Logic Wrap-up</div> <div style="font-weight: bold">Module 2: Cryptography</div> <div>Shift Ciphers</div> </td> <td> <div>Ch. 4 Introduction</div> <div>4.1 Simple Shift Ciphers</div> <div>4.2 Encoding</div> <div>4.3 The mod Function</div> </td> <td rowspan="2" class="olhw"> <div class="olhw">Book: Chapter 4 Exercises</div> <p> <div class="olhw">OLHW3: Modular Arithmetic, Linear Encryption</div> </td> </tr> <tr> <td class="date">Thu Jan 24</td> <td class="class"> <div>Simple Substitution Ciphers</div> <div>Modular Arithmetic</div> </td> <td> <div>4.4 Simple Substitution Ciphers</div> <div>4.5 Modular Arithmetic</div> </td> </tr> <tr class="week-separator"> <td colspan="6">&nbsp;</td> </tr> <tr> <td class="date">Mon Jan 28</td> <td class="class"> <div>Powers Modulo <em xmlns="">n</em></div> <div>Prime Numbers</div> <div>Prime Number Decomposition</div> </td> <td> <div>4.6 Powers mod <em xmlns="">n</em></div> <div>5.1 Divides</div> <div>5.2 Primes</div> <div>5.3 Division</div> </td> <td rowspan="3" class="olhw"> <div class="olhw">Book: Chapter 5 Exercises</div> <p> <div class="olhw">OLHW4: Prime Decomposition, GCD, LCM</div> </td> </tr> <tr> <td class="date">Wed Jan 30</td> <td class="class"> <div>GCD, LCM</div> <div>Euclidean Algorithm</div> <div>Extended Euclidean Algorithm</div> </td> <td> <div>5.4 Greatest Common Divisor and Least Common Multiple</div> <div>5.5 Euclidean Algorithm</div> <div>5.6 Extended Euclidean Algorithm</div> </td> </tr> <tr> <td class="date">Thu Jan 31</td> <td class="class"> <div>Multiplicative Inverse</div> <div>Linear Ciphers</div> <div>Public-Key Cryptography</div> </td> <td> <div><a href="handouts/RSA/RSA.pdf">RSA Handout</a></div> </td> </tr> <tr class="week-separator"> <td colspan="6">&nbsp;</td> </tr> <tr> <td class="date">Mon Feb 4</td> <td class="class"> <div>Review for Test 1</div> </td> <td> <div>Chapters 1 to 5</div> </td> <td class=""> <div><a href="handouts/Test1/Test1-sample.pdf">Sample Problems for Test 1</a> (<a href="handouts/Test1/Test1-sample-solutions.pdf">Solutions</a>)</div> </td> </tr> <tr> <td class="date">Wed Feb 6</td> <td class="exam"> <div>Test 1</div> </td> <td></td> <td class=""></td> </tr> <tr> <td class="date">Thu Feb 7</td> <td class="class"> <div style="font-weight: bold">Module 3: Combinatorics</div> <div>Sets</div> </td> <td> <div>Ch. 6 Introduction</div> <div>6.1 Set Basics</div> <div>6.2 Set-Builder Notation</div> <div>6.3 Venn Diagrams</div> <div>6.4.1-6.4.5 Set Operations</div> </td> <td class=""></td> </tr> <tr class="week-separator"> <td colspan="4">&nbsp;</td> </tr> <tr> <td class="date">Mon Feb 11</td> <td class="class"> <div>Sets (Continued)</div> </td> <td> <div>6.4.6 Power Set</div> <div>6.4.7 Cartesian Product</div> <div>6.5 Computer Representation of Sets</div> </td> <td rowspan="3" class="olhw"> <div class="olhw">Book: Chapter 6 Exercises</div> <p> <div class="olhw">OLHW5: Sets, Set Operations, Power Set, Cartesian Product</div> </td> </tr> <tr> <td class="date">Wed Feb 13</td> <td class="class"> <div>Simple Counting</div> <div>Product and Sum Rules</div> <div>Inclusion-Exclusion Principle</div> <div>Pigeonhole Principle</div> </td> <td> <div>Ch. 7 Introduction</div> <div>7.1 Basic Rules</div> <div>7.2 Inclusion-Exclusion Principle</div> <div>7.3 Pigeonhole Principle</div> </td> </tr> <tr> <td class="date">Thu Feb 14</td> <td class="class"> <div>Permutations</div> <div>Combinations</div> </td> <td> <div>7.4 Permutations</div> <div>7.5 Combinations</div> </td> </tr> <tr class="week-separator"> <td colspan="6">&nbsp;</td> </tr> <tr> <td class="date"> <div>Mon Feb 18</div> </td> <td colspan="3" class="holiday">Presidents' Day, no classes</td> </tr> <tr> <td class="date">Wed Feb 20</td> <td class="class"> <div>Pascal's Triangle</div> <div>Binomial Theorem</div> <div>Balls in Bins</div> </td> <td> <div>7.6 Binomial Theorem</div> <div>7.7 Balls in Bins</div> </td> <td rowspan="2" class="olhw"> <div class="olhw">Book: Chapter 7 Exercises</div> <p> <div class="olhw">OLHW6: Simple Counting, Inclusion-Exclusion, Pigeonhole Principle</div> <p> <div class="olhw">OLHW7: Permutations and Combinations</div> </td> </tr> <tr> <td class="date">Thu Feb 21</td> <td class="class"> <div>Probability Basics</div> <div>Division of Stakes</div> </td> <td> <div>Ch. 8 Introduction</div> <div>8.1 Definitions and Basic Properties</div> <div>8.2 (Probability) Examples</div> </td> </tr> <tr class="week-separator"> <td colspan="6">&nbsp;</td> </tr> <tr> <td class="date">Mon Feb 25</td> <td class="class"> <div>More Probability Basics</div> <div>Conditional Probability</div> </td> <td> <div>8.3 Conditional Probability and Bayes Theorem</div> </td> <td rowspan="3" class="olhw"> <div class="olhw">Book: Chapter 8 Exercises</div> <p> <div class="olhw">OLHW8: Probability</div> <p> <div class="olhw">OLHW9: Conditional Probability</div> </td> </tr> <tr> <td class="date">Wed Feb 27</td> <td class="class"> <div>Bayes Theorem</div> <div>Monty Hall Problem</div> </td> <td> </td> </tr> <tr> <td class="date">Thu Feb 28</td> <td class="class"> <div>Pancakes Problem</div> <div>Puppies Problem ("Two Boys")</div> </td> <td> </td> </tr> <tr class="week-separator"> <td colspan="6">&nbsp;</td> </tr> <tr> <td class="date"> <div>Mon Mar 4</div> </td> <td colspan="3" class="holiday">Spring Break &ndash; NO CLASS</td> </tr> <tr> <td class="date"> <div>Wed Mar 6</div> </td> <td colspan="3" class="holiday">Spring Break &ndash; NO CLASS</td> </tr> <tr> <td class="date"> <div>Thu Mar 7</div> </td> <td colspan="3" class="holiday">Spring Break &ndash; NO CLASS</td> </tr> <tr class="week-separator"> <td colspan="6">&nbsp;</td> </tr> <tr> <td class="date">Mon Mar 11</td> <td class="class"> <div>Expectation</div> </td> <td> </td> <td class=""></td> </tr> <tr> <td class="date">Wed Mar 13</td> <td class="class"> <div>Review for Test 2</div> </td> <td> <div>Chapters 6 to 8</div> </td> <td class=""> <div><a href="handouts/Test2/Test2-sample.pdf">Sample Problems for Test 2</a> (<a href="handouts/Test2/Test2-sample-solutions.pdf">Solutions</a>)</div> </td> </tr> <tr> <td class="date">Thu Mar 14</td> <td class="exam"> <div>Test 2</div> </td> <td></td> <td class=""></td> </tr> <tr class="week-separator"> <td colspan="6">&nbsp;</td> </tr> <tr> <td class="date">Mon Mar 18</td> <td class="class"> <div style="font-weight: bold">Module 4: Algorithmic Analysis</div> <div>Searching and Analysis</div> </td> <td> <div>9.1 Algorithms for Search</div> <div>9.2 Analysis of Algorithms</div> </td> <td rowspan="3" class="olhw"> <div class="olhw">Book: Chapter 9 Exercises</div> <p> <div class="olhw">OLHW10: Sorting and Searching</div> </td> </tr> <tr> <td class="date">Wed Mar 20</td> <td class="class"> <div>Sorting</div> </td> <td> <div>9.3 Algorithms for Sorting</div> </td> </tr> <tr> <td class="date">Thu Mar 21</td> <td class="class"> <div>Sequences</div> </td> <td> <div>10.1 Sequences</div> </td> </tr> <tr class="week-separator"> <td colspan="6">&nbsp;</td> </tr> <tr> <td class="date">Mon Mar 25</td> <td class="class"> <div>Sums</div> </td> <td> <div>10.2 Series and Partial Sums</div> </td> <td rowspan="3" class="olhw"> <div class="olhw">Book: Chapter 10 Exercises</div> <div class="olhw">Book: Chapter 11 Exercises</div> <p> <div class="olhw">OLHW11: Sequences and Summations</div> </td> </tr> <tr> <td class="date">Wed Mar 27</td> <td class="class"> <div>Recurrences</div> <div>Proof by Induction</div> </td> <td> <div>11.1 Specifying Recurrences</div> <div>11.2 Solving Recurrences</div> </td> </tr> <tr> <td class="date">Thu Mar 28</td> <td class="class"> <div>Sorting Analysis</div> <div>Growth of Functions</div> </td> <td> <div>Ch. 12 Growth of Functions</div> </td> </tr> <tr class="week-separator"> <td colspan="6">&nbsp;</td> </tr> <tr> <td class="date">Mon Apr 1</td> <td class="class"> <div style="font-weight: bold">Module 5: Networks</div> <div>Graphs</div> </td> <td> <div>Ch. 13 Introduction</div> <div>13.1 Simple Graphs</div> <div>13.3 Graph Data Structures</div> </td> <td rowspan="3" class="olhw"> <div class="olhw">Book: Chapter 13 Exercises</div> <p> <div class="olhw">OLHW12: Graphs</div> </td> </tr> <tr> <td class="date">Wed Apr 3</td> <td class="class"> <div>Graph Problems</div> </td> <td> <div>13.4 Graph Problems</div> </td> </tr> <tr> <td class="date">Thu Apr 4</td> <td class="class"> <div>More Graphs</div> </td> <td> <div>13.4 Graph Problems</div> <div>13.5 Graph Theory</div> </td> </tr> <tr class="week-separator"> <td colspan="6">&nbsp;</td> </tr> <tr> <td class="date">Mon Apr 8</td> <td class="class"> <div style="font-weight: bold">Module 6: Relations</div> <div>Relations</div> </td> <td> <div>Ch. 14 Introduction</div> <div>14.1 Examples</div> <div>14.2 Properties of Relations</div> <div>14.3 Equivalence Relations</div> </td> <td class=""></td> </tr> <tr> <td class="date">Wed Apr 10</td> <td class="class"> <div>Review for Test 3</div> </td> <td> <div>Chapters 9 to 14</div> </td> <td class=""></td> </tr> <tr> <td class="date">Thu Apr 11</td> <td class="exam"> <div>Test 3</div> </td> <td></td> <td class=""></td> </tr> <tr class="week-separator"> <td colspan="6">&nbsp;</td> </tr> <tr> <td class="date"> <div>Mon Apr 15</div> </td> <td colspan="3" class="holiday">Patriots' Day, no exams or classes</td> </tr> <tr> <td class="date">Wed Apr 17</td> <td class="class"> <div>Wrap-up and review</div> </td> <td> <div>Chapters 1 to 14</div> </td> <td class="olhw"> <div class="olhw">OLHW12: Review</div> </td> </tr> <tr class="week-separator"> <td colspan="6">&nbsp;</td> </tr> <tr> <td class="date">Tue Apr 23</td> <td class="final"> <div>FINAL EXAM</div> </td> <td></td> <td class=""></td> </tr> </table> </center> </body> </html> ÿþÿþ