Discrete Structures Schedule
CS 1800 Spring 2014

Last Updated:

 Week Class Date Topics Reading Due 1 1 Mon, Jan 6th Overview and Course Organization Get an online homework Account 2 Wed, Jan 8th Module 1: Computers and Computing Binary Representation of Numbers Converting Between Binary and Decimal Ch. 1 Introduction 1.1 Binary Representation 1.2 Bytes 1.5 Converting Between Decimal and Binary 3 Thur, Jan 9th Hexadecimal and Octal Representation Representing Negative Numbers Two's Complement 1.3 Hexadecimal Representation 1.4 Octal Representation 1.6 Representing Negative Numbers: Two's Complement Fri, Jan 10th OLHW1: Binary, Octal, Hex 2 4 Mon, Jan 13th Review of Two's Complement Wrap up of Binary Arithmetic Operations Basic Logic and Logic Gates Chs. 2, 3 Introductions 2.1 Transistors and Switches 2.2 Basic Logic Gates: AND, OR, NOT 5 Wed, Jan 15th Logic Gates and Logic, contd. 2.3 More Logic Gates: NAND, NOR, XOR, XNOR 3.1 Truth Values 3.2 Truth Tables 6 Thur, Jan 16th Logic and Logical Equivalence Basic circuits 3.3 Logical Equivalence 2.4 Binary Arithmetic: Ripple Carry Adders Fri, Jan 17th OLHW2: Logic, Logic Gates 3 Mon, Jan 20th MLK Day, NO CLASS 7 Wed, Jan 22nd Gem 1: Design of a CPU Lecture notes Lecture slides 8 Thurs, Jan 23rd Module 2: Encryption Caesar Shift Simple Substitution Cipher Ch. 4 Introduction 4.1 Simple Shift Ciphers 4.2 Encoding 4.3 The mod Function 4.4 Simple Substitution Ciphers Fri, Jan 24th 4 9 Mon Jan 27th Modular Arithmetic Division Algorithm Powers Modulo n 4.5 Modular Arithmetic 4.6 Powers mod n 5.1 Divides 5.3 Division 10 Wed, Jan 29th Prime Numbers Prime Number Decomposition 5.2 Primes WHW1: Binary Arithmetic and Logic 11 Thurs, Jan 30th GCD, LCM Euclid's Algorithm 5.5 Euclid's Algorithm 5.4 Greatest Common Divisor and Least Common Multiple Fri, Jan 31st OLHW3: Modular Arithmetic, Linear Encryption 5 12 Mon, Feb 3rd Extended Euclid's Algorithm Secret-sharing and public key cryptosystems 5.6 Extended Euclid's Algorithm 13 Wed, Feb 5th Gem 2: RSA Lecture notes The Mathematical Guts of RSA Encryption RSA article 14 Thurs, Feb 6th Module 3: Counting Password Spaces, Sets Set Builder Notation Ch. 6 Introduction 6.1 Set Basics 6.2 Set-Builder Notation 6.3 Venn Diagrams Fri, Feb 7th OLHW4: Prime Decomposition, GCD, LCM 6 15 Mon, Feb 10th Set Operations Computer Representation of Sets 6.4.1-6.4.4 Set Operations 6.4.5 Power Set 6.4.6 Cartesian Product 6.5 Computer Representation of Sets 16 Wed, Feb 12th Simple Counting Product and Sum Rules Inclusion-Exclusion Principle Pigeonhole Principle Ch. 7 Introduction 7.1 Basic Rules 7.2 Inclusion-Exclusion Principle 7.3 Pigeonhole Principle WHW2: Modular Arithmetic, Cryptography 17 Thurs, Feb 13th Review for Midterm 1 Chapters 1 through 5, and handouts Fri, Feb 14th OLHW5: Sets, Set Operations, Power Set, Cartesian Product 7 Mon Feb 17th President Day, NO CLASS 18 Wed, Feb 19th Midterm Exam 1 19 Thurs, Feb 20th Permutations and combinations Combinations 7.4 Permutations 7.5 Combinations Fri, Feb 21st OLHW6: Simple Counting, Inclusion-Exclusion, Pigeonhole Principle 8 20 Mon, Feb 24th More permutations and combinations Pascal's Triangle 21 Wed, Feb 26th Binomial Theorem 7.6 Binomial Theorem 22 Thurs, Feb 27th Balls in Bins 7.7 Balls in Bins Fri, Feb 28th OLHW7: Permutations and Combinations Mon, Mar 3rd SPRING BREAK - NO CLASS Wed, Mar 5th Thurs, Mar 6th 9 23 Mon, Mar 10th Counting: Problem Solving Examples Ch. 6, 7 24 Wed, Mar 12th Probability Basics Expectation and independence Ch. 8 Introduction 8.1 Definitions and Basic Properties 8.2 (Probability) Examples 25 Thurs, Mar 13th More Probability Examples Fri, Mar 14th 10 26 Mon, Mar 17th Conditional Probability Bayes Law 8.3 Conditional Probability and Bayes Theorem 27 Wed, Mar 19th Review for Midterm 2 Chapters 6 through 8 OLHW8: Probability 28 Thurs, Mar 20th Midterm Exam 2 Fri, Mar 21st 11 29 Mon, Mar 24th Module 4: Algorithms Algorithms for Searching 9.1 Algorithms for Search 9.2 Analysis of Algorithms 30 Wed, Mar 26th Algorithms for Sorting 9.3 Algorithms for Sorting 31 Thurs, Mar 27th Sequences 10.1 Sequences Fri, March 28th OLHW9: Conditional Probability and Markov Chains 12 32 Mon, Mar 31st Sums Proof by Induction 11.1 Specifying Recurrences 33 Wed, Apr 2nd Simple Recurrences 11.2 Solving Recurrences WHW3: Probability, Counting and Algorithms 34 Thurs, Apr 3rd Growth of Functions Ch. 12 Growth of Functions Fri, Apr 4th OLHW10: Sorting and Searching 13 35 Mon, Apr 7th Module 5: Networks Graph Data Structures 13.3 Graph Data Structures 13.4 Graph Problems 36 Wed, Apr 9th More Graphs Graph traversals 13.4 Graph Problems 13.5 Graph Theory 37 Thurs, Apr 10th Graphs Continued Fri, Apr 11th 14 38 Mon, Apr 14th Wrap up and Review Ch. 1 to 14 WHW4: Graphs and Algorithms OLHW11: Graphs