DOC PREVIEW
UD CISC 320 - CISC 320 algorithms, midterm exam review notes

This preview shows page 1 out of 2 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CISC320 algorithms, 10S, midterm exam review notesChapter 0:Definitions of estimation tools: big-O, Ω, Θ.Key points:• the inequalities between functions defining these must hold up to a positive constant factor.For instance, f (n) is O(g(n)) requires f(n) ≤ c ∗ g(n), for some positive c. Often the firstchallenge in proving a big-O relationship is guessing c, i.e. finding a c that will work.• The inequalities may be wrong for a few small values of n. It is only required that they betrue for all values of n after some threshold. For instance, n is O(n ∗ log(n)) even though whenn = 1, we see that n > c ∗ n ∗ log(n), regardless of c. On the other hand – and what counts –for all n ≥ 2, we see that n ≤ n ∗ log (n) is true because log(n) ≥ 1 for n ≥ 2.Chapter 1:Topics:• integer multiplication and division with remainder• modular arithmetic• testing for primality• RSA encriptionTheme: public key encryption (RSA in particular) is based on the fact that some things are hard(factoring the product of two large prime numbers) and some are tractable (basic integer arithmetic,modular arithmetic including exponentiation (modexp), determining if a number is prime) // //Algorithms:• multiply (p15)• divide (quotient and remainder) (p15)• modexp (p19)• Euclid (p20)• extended-Euclid (p21)• primality (1.1) (p25)• primality2 (1.1) (p27)• RSA (build keys, encrypt, decrypt) (p34)Chapter 2:• Master theorem (applies to recurrences diving down to n/b) and Muster theorem (applies torecurrences stepping down to n − b)• divide and conquer integer (also polynomial) multiplication (Karatsuba algorithm) (p47)• divide and conquer sorting (merge sort) (p50)• lower bound for sorting (p51)1• divide and conquer selection (randomized median) (section 2.4)• divide and conquer matrix multiplication (Strassen’s algorithm) (section 2.5)• divide and conquer p olynomial (also integer) multiplication (fast Fourier transform) (p68)Themes: divide and conquer algorithms may b e organized around applicable case of Master theorem(see algorithms list below).Also notice that the tractable problems of chapter 1 can be done even faster than we first thought:integer, polynomial, and matrix multiplication, thus also mo dexp and primality are faster.Algorithms:• Case 1 of Master theorem: binary search (p50), selection (randomized median) (section2.4).• Case 2 of Master theorem: merge sort (p50), FFT, use of FFT (p68) in polynomial mul-tiplication (p60)• Case 3 of Master theorem: integer multiplication (Karatsuba algorithm) (p47), Strassen’smatrix multiplication algorithm (section 2.5),Chapter 3:• Depth first search in (undirected) graphs and digraphs (directed graphs). Tree, forward, back,and cross edge categorization with respect to a depth first search.• DAGs (directed acyclic graphs) and linearization• strongly connected components and the DAG of strongly connected components.Themes: basic graph representation and terminology, dfs is basis of solving some problems.Chapter 4: Dijkstra’s algorithm (assuming a priority queue) for single source shortest paths.Overall: Things to know about each algorithm:• Why is it correct (vis a vis it’s input/output specification)? What are the theorems andproperties used to explain it’s workings?• What measure, n, of it’s input is used as basis for analysis (for instance, n = bound on numberof bits in numbers, or n = size of an array)?• What formula (function of that n) estimates it’s runtime? Usually the formula is a recurrencerelation.• What is the solution of that formula/recurrence?Kinds of questions: multiple choice, short answer, write algorithm, track


View Full Document

UD CISC 320 - CISC 320 algorithms, midterm exam review notes

Download CISC 320 algorithms, midterm exam review notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view CISC 320 algorithms, midterm exam review notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view CISC 320 algorithms, midterm exam review notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?