N or Space for next slide, P for previous slide, F for full screen, M for menu
Lec 4: NAND programming language
Boaz Barak (instructor), Salil Vadhan (co-instructor), Juan Perdomo (Head TF).
Team: Aditya Mahadevan, Brian Sapozhnikov (surveys), Chan Kang (extension), Gabe Abrams (Ed Tech), Gabe Montague (NAND web), Jessica Zhu (proof workshops), John Shen, Juan Esteller (NAND implementation), Karl Otness, Katherine Binney, Lisa Lu, Mark Goldstein, Stefan Spataru, Susan Xu, Tara Sowrirajan, Thomas Orton (Advanced Section), Wentong Zhang
Slides will be posted online.
Laptops/phones only on last 3 rows please.
Some survey notes
- Quizzes grades
- Lights, pauses, blackboard vs slides
- Take away messages / learning objectives.
- Psets vs lectures
CS 121 components
- Lecture notes: Read deeply to learn the concepts
- Lectures: Second exposure: go over high level concepts, consolidate understanding.
- Sections: Work through examples and techniques in smaller groups.
- Problem sets: Solidify skills and knowledge through practice.
- Office hours: Individual help in working through concepts.
Tips:
- Make sure you are prepared for lecture
- Start early on psets
- Expect some problems to be challenging.
- Know when and how to seek help.
NAND Programming Language
Focus: Computing finite functions \(F:\{0,1\}^n \rightarrow \{0,1\}^m\)
Goal: Make “computing \(F\) can be done using \(100n^2\) operations” as precisely defined as “\(p\) is a prime number”.
Corollary: Could sometimes prove that this is false.