Readings and Resources
Various helpful resources will be collected here.
Please note: Readings for more than 2 weeks in advance are rough. As we get closer to the date, readings will be polished and tweaked (likely reduced) to reflect the topic of the week.
Week 1: Intro, Number Representations, Logic
- Rosen: Chapter 1 Logic and Proofs
- Only 1.1 through 1.5; no 1.6-1.8:
- 1.1 Propositional Logic
- 1.2 Applications of Propositional Logic
- 1.3 Propositional Equivalences
- 1.4 Predicates and Quantifiers
- 1.5 Nested Quantifiers
- Rosen: Chapter 4, Section 4.2 (Integer Representations and Algorithms)
- Online Discrete Math text:
- Chapter 3 Intro
- 3.1 Propositional Logic
Week 2: Functions and variables. Integer functions.
- Rosen: 2.3-- Functions
- Online Discrete Math: Chapter 0.1, 0.2, 0.4 (Intro, Functions)
Week 3: Sums and sequences. Arithmetic and geometric progressions.
- Rosen: 2.4-- Sequences and Summations.
Week 4: Sets
- Rosen: Chapter 2
- 2.1: Sets
- 2.2: Set Operations
- 2.5: Cardinality of Sets
- 2.6: Matrices
- Online Discrete Math: Chapter 0.3 (Sets)
Week 5: Arrays, number theory. Divisibility, primes, etc.
- Rosen: Chapter 4
- 4.1: Divisibility and Modular Arithmetic
- 4.2: Integer Representations
- 4.3: Primes and GCD
- 4.4: Solving Congruences
- Online Discrete Math: Chapter 5.2 (Intro to Number Theory)
Week 6: Relations and recurrences.
- Rosen: Chapter 9 (Relations)
- Online Discrete Math: Chapter 2.4 (Solving Recurrence Relations)
Week 7: Lists, Stacks and Queues
- A friendly intro to data structures
- Data structures in Python
- Chapter 3.2, 3.3, 3.4, 3.10, 3.11, 3.19, 3.20, 3.21, 3.22, 3.23
Resources/Optional ReadingsThese readings may provide a slightly different description of the data structures, and may be helpful.
- Helpful Overview (Ignore the code, or treat it as pseudocode):
- Intro to Data Structures. From MIT's intro to programming for Civil Engineers. A nice overview of the data structures we care about, but does use Java to show implementaton. We aren't worried about implementation yet, so ignore the code.
- Data Structures in Python (Chapters 3.5, 3.12). Chapters from the Python reading that's part of the required reading, but these sections start talking about implementation. Read this if you are ready to start thinking about the code related to these ideas, but we aren't worrying about implementation.
LinkedList: (ignore the code, or at least, treat it like pseudocode)
- Doubly-Linked List
- Stacks. Another good overview of a stack, with some real-world applications.
Queue (ignore the code/treat it like pseudocode):
- Queue Data Structure Implementation. Again, same guy who did the Linked List reading above. No code in this one (but it's provided if you want to look at some, just no Python).
- Sample exams questions and previous exams will be made available for practice.
- Rosen: Chapter 6
- 6.1: The Basics of Counting
- 6.2: The Pigeonhole Principle
- 6.3: Permutations and Combinations
- 6.4: Binomial Coefficients and Identities
- 6.5: Generalized Permutations and Combinations
- Algorithms Unlocked:
- Chapter 1: What are Algorithms and Why Should You Care?
- Chapter 2: How to Describe and Evaluate Algorithms
- Chapter 3.2: Growth of Functions
- Rosen, Chapter 3.3: Complexity of Functions
- Rosen, Chapter 3.1: Algorithms
- CLRS Chapter 3 (Growth of Functions)
- CLRS Chapter 1 (The Role of Algorithms in Computing)
- Cormen: Algorithms Unlocked, pp 40-59 (mergesort, quicksort)
- Rosen: Chapter 8.3: Divide-and-Conquer Algorithms and Recurrence Relations
- CLRS 3e: Chapter 7, Quicksort
- CLRS 3e: pg 30-39 (Mergesort)
- Rosen: Chapter 5 (Induction and Recursion)