Lecture Notes and Reading Assignments
- Lecture 24: (03/10)
- Lecture 18: HW2
- Reading Assignments: 4.1-4.2
- Lecture 17: Time complexity in recursion form (02/22)
- Reading Assignments: 3.1-3.4
- T(n) = aT(n/b) + f(n)
- Master theorem (2.2)
- Lecture 16: Search (02/20)
- Linear search
- Binary search
- kth small element selection
- Lecture 15: Revisit of Heap Sort (02/18)
- Reading Assignments: ch2.4, 2.1,2.5
- Binary Tree: recursion definition
- Binary Balance Tree
- Heap
- Heap Sort
- Basic component of algorithm: heapify (O(log n))
- Heap construction : O(n)
- Selection sorting through root deletion: O(n log n)
- Lecture 14: Summary of All Sorting Algorithms (02/15)
- Lecture 13: Sorting Algorithm (02/13)
- Heap Sort (James, Ben and Tierney)
- Lecture 12: Sorting Algorithm (02/11)
- Merge Sort (Alex and Brian)
- Quick Sort (Neil, Jilien and Eric)
- Lecture 11: Sorting Algorithm (02/08)
- Selection Sort (Phil and Chris)
- Insertion Sort (Bob and William)
- Lecture 10: Prime test and Grade school multiplication and division (02/06)
- Lecture 9: Extended Euclid's Algorithm for Modular Inverse (02/04)
- Lecture 8: Euclid's Algorithm (02/01)
- Lecture 7: Modular exponentiation (01/30)
- Reading Assignments: ch1
- What is GCD? How to calculate GCD (Euclid's algorithm)
- How to calculate modular inverse using Euclid's algorithm
- Implementation of RSA needs to answer the following questions:
- How to generate large prime: p, q
- How to choose e
- How to calculate d, inverse of e modular (p-1)(q-1)
- How to calculate modular exponentiation
- Modular exponentiation
- Algorithm: use divide and conquer idea and recursion implementation
- Complexity: O(n^3) where n is the number of bits of the operands. It need O(n) multiplications or divisions, and each multiplication/division needs O(n^2).
- Lecture 6: Cryptography (01/28)
- Reading Assignments: ch1
- Fermat's little theorem
- Chinese Remainder theorem
- Correctness proof of RSA algorithm
- Lecture 5: Cryptography (01/25)
- Reading Assignments: ch1
- Basic theorem on prime (Fermat's little theorem)
- How to calculate modular exponential?
- How to calculate modular inverse?
- What is GCD? How to calculate GCD (Euclid's algorithm)?
- Cryptograph: the practical and study of hiding information. Provide confidentiality, integrity checking, identity authentication, digital signatures, etc.
- Symmetric-key algorithms: a class of algorithms for cryptography that use trivially related, often identical, cryptographic keys for both decryption and encryption. (simple, not very secure)
- Public-key cryptography, also known as asymmetric cryptography, is a form of cryptography in which a user has a pair of cryptographic keys - a public key and a private key.
- RSA algorithm
- message x, two primes p, q, N= pq, (m = N) e: relative prime to (p-1)(q-1) (otherwise, no d), d: inverse of e modulo (p-1)(q-1), ed mod (p-1)(q-1) = 1. encrypt: m^e, decrypt: (m^e)^d
- correctness? m^(ed) mod N = m mod N (?)
- Complexity?
- Number theory
- Based on modular arithmetic (properties on modular addition, multiplication and exponentiation)
- Lecture 4: Big-O notation (01/23)
- Reading Assignments: ch1
- What is cryptograph? What are the applications?
- What is private-key cryptosystem? Problems?
- What is public-key scheme? How to implement?
- What is basic idea of RSA algorithm?
- How to prove the correctness of RSA algorithm?
- Related number theroems. basic modular arithemetic
- Assumptions of RSA algorithm?
- The time complexity of RSA algorithm?
- Review of asymptotic notation of algorithm complexity
- Exercises
- Lecture 3: Big-O notation(01/21)
- Lecture 2: Fibonacci, iterative and recursive (01/18)
- Reading Assignments: ch0
- Fibonacci sequence of numbers: each number is the sum of its two immediate predecessors.
- Two different algorithms to generate Fibonacci numbers. (See pseduocode in the book)
- Compare recursion and iteration.
- Recursion: base cases (conquer), generate simpler version of the original problem (divide)
- iterative: incremental steps towards the result. loop invariant is the assumption that should be true at the top of loop body in every iteration. Need check if the loop invariant is true for initial condition, if the loop invariant is maintained in each iteration. If the loop can be terminated.
- Analysis of time efficiency: # of basic operations as a function of input size.
- Recursion: set up recurrence relationship
- Iteration: sum up the number of basic operations in all iterations
- Lecture 1: course overview (01/16)
- Reading Assignments: ch0
- How to represent algorithm complexity:
- How to describe the Fibonacci problem
- Two different algorithms: iterative, recursive, (similiarity, difference)
- How to prove their correctness
- How to analyze their complexity
- What is an algorithm? (about problem solving)
- step by step instructions to solve a problem, (precise(unambiguous), finite steps( will be terminated)
- an algorithm has to solve a general, specified problem. An algorithmic problem is specified by describing the set of instances it must work on and what desired properties the output must have.
- How to describe the problem, including inputs and output.
- Abstract a specific problem to a general problem
- Show examples of a general problem to a specific problem
- Examples: shortest path problem, knapsack problem, scheduling problem.
- Algorithm Evaluation:
- correctness
- efficiency(scalability):
- time complexity, (best, worst, average)
- space complexity
- tradeoff
- P/NP
- Control flow:
- sequencing
- selection (if/else, switch)
- iteration (loops) (brute force) (imperative language)(our focus)
- method call
- recursion (methdo call) (divide/decrease & conquer) (functional language) (our focus)
- concurrency
- nondeterminacy
- Data structure
- List
- Stack
- Queue
- Heap
- sets
- Table (hash)
- Tree
- Graph
- Methology (Thinking pattern)
- brute force
- divide and conquer (decrease and conquer, transform and conquer)
- greedy
- dynamic programming (linear programming)
- Classic problems
- sorting (Topoligical sort)
- searching (min, max, nth max) (tree search)
- string match
- knapsack problem
- Assignment problem (e.g. stable marriage)
- Traval Sell man
- Matrix Multiplication (large multiplication)
- closest pair
- set cover
- ...
- Applications
- cryptography
- network routing
- CPU scheduling in OS, or packet scheduling in networks
- ...
- Related Thereoy
- Number theory
- graphic theory
- Probability
- High level Thinking ability: abstract thinking, original thinking
- Problem analysis:(application –> abstract problems (model, math , symbol representation) -> relationship to the existing problems(difference, similarity))
- Understand existing algorithms
- Solution development: develop new algorithms
