CSCE courses summary PDF

Preview

Summary

CSCE courses summary...

Description

312● ● ● ● ● 470● ● ● ● ● ● 411● ● ● ● ● ●

Processor architecture is key Go to office hours Memory matters (fun topic)-cpu,register,memory Cycles, Turing machine,von neuman Office hrs: MW 4-5 pm An introduction to mathematical cryptography 2nd edition Paper exam-final is comprehensive Practice exam is given Chptr. 1 is foundational No proofs in exams

3rd edition Hw1 due tuesday (turn in paper/scan/type latex) Thrs quizzes Office hrs tues/thurs before class x=A\ b c(M)=A ■ O(|C|^2) ○ 10^7 10^3 10^3 ○ (|A|) ○ O(A log M) ○ O(|C|) ● Input ● Well defined -> sequence -> output “the solution” ■ Algorithm ■ “Turing complete” ■ Can be done on a FSM finite state machine (halting problem cannot be computed) ■ RAMmachine (doesn’t exist) ● RAM: access any entry in O(1) constant time ● In problem size O(n) (bigger means slower) ● The bigger the chip the slower (time) ● sqrt(n) Locality, locality, locality Big-O: f(n) is O(g(n)) if ∃ const c>0 , n0 >0, f(n) =n0

Big Ω : Ω(g(n)) f(n)>=c(g(n) ∀n>=n0 Is Θ (g(n)) n^2/2 * n is

O(n^2)

P problem Given an unorderedd array A, size n , X Find k s.t. X = A(k) or “not found” O(n) Ω (1) Θ(1) Davissian Search (already know last place you looked/someone told you) NP problem P = NP? Or P⊂NP - prime factorization in encryption ● Encoded in some form x=A\b gaussian elimiantion -turing machine, ram , non deterministic model, locality,proof by induction, mathematical induction in a design sense loop...