Impact of COVID-19 on Vulnerable Children & Young People in Scotland
This content delves into the impact of the COVID-19 pandemic on vulnerable children and young people in Scotland, exploring their experiences during lockdown and the challenges faced by parent/carers. Insights from surveys and studies provide a glimpse into the effects on mental health, social interactions, and support systems. The ASPEP Secretary, Morven Graham, sheds light on the definition of vulnerable children and the support they require during these unprecedented times.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Final Exam Review Slides by Dan Fu
Final Thu April 29, 9am 12:30 pm Covers all primary lecture material prior to April 8 Lecture #23, Intro to Quantum Computation Includes secondary material where the topic is the same Mix of True/False, Short Answer, and Proof problems Exam is 2 parts Each part is 90 minutes exam + 15 minutes scan You can take a break if finishing Part A early
General Define and understand differences/properties of decision, optimization, approximation Understand the difference between deterministic, non-deterministic, and probabilistic models Regular and context-free languages Describe or draw and follow the operation of a Turing Machine, state diagrams, push down automata Diagonalization, countability
Complexity Classes Define the class in terms of space, time, or operation of a simulating Turing Machine Identify typical problems in the class and specific challenges of solving problems in the class Prove or discuss implications of particular relationships between classes P, NP, PSPACE, PH, L, RL, NL, EXP, NEXP, P/poly, AC0, BPP, RP, ZPP, NC, #P, FP IP, PCP SAT, TQBF Completeness (NP, PSPACE, P, #P) and how to perform reductions
Oracles An oracle machine is some black box machine capable of solving any specified problem (decision or other) eg PSATis a polynomial time deterministic Turing machine with access to an oracle for SAT What does it mean for a proof to relativize? Baker-Bill-Solovoy theorem How do oracles build the PH and what does it imply about the relationship between P, NP, coNP, and PSPACE?
Kolmogorov Complexity How to reason about the randomness and information density of a string Invariance theorem, incompressibility method,
Circuit Complexity and Branching Programs Class P/poly, what is uniformity and advice? Implications for randomized complexity and P = NP? SPACE complexity of functions How do these constructions help define class NC and probabilistic models of computation? From Mar 9 From Feb 25
Randomized Complexity, Parallel Computation Explain models for two-, one-, and zero-sided error. What is error amplification/reduction? Important results: Polynomial identity testing See Recitation #3
One-way functions, permutations, and PRGs Difference between one-way functions and permutations See solution in Recitation 6 Homework is different because it is a permutation Describe construction of PRGs and discuss relationship to one-way functions and permutations
See Mar 25 Landmark Results Yao s Lemma Slight variation also helps to describe PRGs Goldreich-Levin hard bit Proves the randomness of PRGs Valiant-Vazirani Theorem Randomized construction of a SAT solution if a polynomial-time algorithm is given (also note downward self-reducibility, and various proofs See Recitation #5, #7 Schwartz-Lippel Lemma Specific construction using probabilistic model to solve polynomial identity testing
#P Decision vs counting Implications: Or P=NP if for any #L #P, #L FP implies L P
Interactive Proofs Proofs based on the exchange of information Implications Typical problem: Prove graphs are not isomorphic See recitation 7
Probabilistically Checkable Proofs Implications of PCP to P=NP and its significance towards the existence of polynomial-time approximation algorithms within some ?. From Arora How to calculate error bounds See April 1, Bulatov Exercise: Unless ? = ??, there is no 7 8+ ? -approximation algorithm for Max-3SAT, for any ? > 0. See Recitation 7
Communication Complexity How much information has to be exchanged? Define communication complexity: Important techniques: Fooling set argument, Lower bound argument, Crossing sequence argument
