| [HOME](http://www.raghumeka.org) | [RESEARCH](http://raghumeka.github.io/research.html) | [TEACHING](http://raghumeka.github.io/courses.html) | | -------- | -------- | -------- | --- ## Introduction The course is for introducing you to the beautiful and profundly impactful world of ***Theory of Computing*** (TOC). The following three questions encompass our main learning goals: :::spoiler 1. What is computation? How different is the iMac Pro really from Apple III? ::: :::spoiler 2. Can we compute our way out of everything? How about predicting `Stack Overflow` errors at compile time? ::: :::spoiler 3. What can we compute efficiently? The computational version of *are we there yet?* ::: At the end of the course I hope you would have learnt something about the nature of computing, universality in computing, and limitations of computing. You can check last year's version [here](http://hackmd.io/@raghum/intrototcs21). --- ## Logistics and Resources :::spoiler **Lecture hours: M-W 8-9:50:** **Young Hall Room CS24** - [Zoom link](https://ucla.zoom.us/j/98953548534). - Lecture 17 will be held during discussion sesssion on Dec 1 from 2 - 3:50 pm (live broadcasted and recorded). (As we will have Exam 2 during regular class hours on Nov 29). ::: :::spoiler **Course notes**: We will use [ScribbleTogether](https://scribbletogether.com/). - Note that each lecture is on a different sheet within the files. - [Notes for Week 1](https://scribbletogether.com/whiteboard/6A8E1AAE-0EF3-4336-AFB0-AC9D5EC3BBA6) - [Notes for Week 2](https://scribbletogether.com/whiteboard/950472E7-B669-478E-8451-318C92640E22) - [Notes for Week 3](https://scribbletogether.com/whiteboard/FCEE879C-5C12-4584-9F83-739BE48698DF) - [Notes for Week 4](https://scribbletogether.com/whiteboard/4E34104E-2EF5-4249-8C6A-B427580E8F76) - [Notes for Week 5](https://scribbletogether.com/whiteboard/CBBB7989-A065-4009-8979-43F2AAA9DEC2) - [Notes for Week 6](https://scribbletogether.com/whiteboard/4B9CDEC9-9D0D-4D64-B328-0CEEC3F3C321) - [Notes for Week 7](https://scribbletogether.com/whiteboard/848EE700-2379-4423-84D2-FD1B4A2CDD0B) - [Notes for Week 8](https://scribbletogether.com/whiteboard/13ECC877-AA6C-4E9D-8EB9-952D7FCC064A) - [Notes for Week 9](https://scribbletogether.com/whiteboard/5326DBA4-5221-42BE-B493-744E4C3C292E) - [Notes for Week 10](https://scribbletogether.com/whiteboard/59DC452C-A396-4FDE-B94D-DF498AE018D6) ::: :::spoiler **Course team**: - William Cao: I'm a second year MS student working on probabilistic programming and probabilistic modeling. In my free time, I play games and follow sports. Email: williamxcao@cs.ucla.edu - Arvind Vepa: I’m a fourth year PhD student focused on applications of machine learning in health care. In my free time, I enjoy spending time with my partner and going out to try different types of food in LA. Email: amvepa@g.ucla.edu - Yimeng(Kobe) Wang: Hi all!. I'm a second year PhD student interested in probability theory and complexity theory. I read books and watch/play sports in my free time. Feel free to talk to me about anything. Email me at: kobewang1998@gmail.com ::: :::spoiler **Discussion Sections Hours**: Fridays. Expand for hours. - 1A: F 2pm-3:50pm. Moore Hall 100 (Arvind Vepa) - 1B: F 2pm-3:50pm. Broad Art Center 2160E (Yimeng Wang) - 1C: F 2pm-3:50pm. Royce Hall 162 (William Cao) - 1D: F 4pm-5:50pm. Renee and David Kaplan Hall 169 (Arvind Vepa) - 1E: F 4pm-5:50pm. Dodd Hall 170 (Yimeng Wang) - 1F: F 4pm-5:50pm. Renee and David Kaplan Hall 135 (William Cao) ::: :::spoiler **Office Hours:** Exploit these! 1. **Instructor office hours**: M, W - 11:30-12:30. Engineering VI 463. 2. **TA office hours**: - William Cao: Tu, Th 2-3pm; Location: Boelter 3256S - Arvind Vepa: M, W - 7:00pm-8:00pm [Zoom](https://ucla.zoom.us/j/97881407276?pwd=QmltaWxTSjZwNmJucXhESjVQbnA2QT09) - Yimeng Wang: Tu, Th 10:00am-11:00am; Location: Boelter 3256S ::: :::spoiler **edStem:** Our online space for asking, answering questions, and posting links to class material. Register to our class server [here](https://edstem.org/us/join/pyf49b). We will make use of edStem extensively. It will be our main way for communicating with each other. Please ask questions here so that others may also benefit from the knowledge. We will also use it for releasing homework solutions. Homeworks themselves will be posted on the class website. Register using the link emailed to your address on file (with CCLE). You can also register via the link above along with the code provided in first lecture. ::: :::spoiler **Homework submission**: Homework will be released on Gradescope and you will have to submit via Gradescope; Due 9:59PM (Pacific time) on due date. We will use Gradescope for homework and they have to be submitted by 10PM on their due date. Things to keep in mind: 1) Within a week of the course, you should receive a registration link from Gradescope. If you don't receive it before the first homework, contact the TAs immediately; this will give you access to the website. 2) Watch [this](https://www.youtube.com/watch?v=u-pK4GzpId0) one-minute video with complete instructions. Follow them to the letter! The simple guidelines make the process considerably smoother. 3) Make sure you start each problem of a homework on a new page. 4) To generate a PDF scan of the assignments, you can follow the instructions [here](https://raghumeka.github.io/CS180/submitting_hw_guide.pdf); you can also use the scanners in the library. ::: :::spoiler **Homework writing**: LaTeX recommended highly It is strongly recommended to use LaTeX or other word processing software for submitting the homework. Grades will take into account both the correctness and the quality of the solutions. Correctness is a prerequisite but clarity is also important: you are responsible for communicating your solution in a legible and understandable way. Some helpful guidelines: (1) Start early to use office hours. (2) Serious/honest attempts count - there will be reasonable partial credit for attempts that show understanding of the problem/concepts involved. ::: :::spoiler **Textbook**: [Introduction to Theoretical Computer Science by Boaz Barak](https://introtcs.org/public/index.html) The textbook is available for free on the web with many other very useful resources. We will follow this very closely. Another great textbook to peruse is the classical [Introduction to Theory of Computation](https://www.cengage.com/c/introduction-to-the-theory-of-computation-3e-sipser/9781133187790/) by Michael Sipser. If you are interested in learning more about TOC, for advanced but high-level overview these [two](https://www.cambridge.org/core/books/quantum-computing-since-democritus/197A4CD13738E10AAD787DBB78D8E92C) [books](https://www.math.ias.edu/avi/book) are highly recommended. ::: --- ## Homeworks on Gradescope --- ## Grading ::: spoiler **Homeworks: 6 x 4 pts**. Homeworks are released on Monday (by 7PM Pacific). All homeworks will be due the following Monday (by 9:59 PM Pacific). ::: ::: spoiler **Homework Coverage and Dates**: Expand to see details. - HW 1 Oct 9 - 16: Lectures 1,2,3,4. - HW 2 Oct 23 - 30: Lectures 5,6,7,8. - HW 3 Nov 6 - Nov 13: Lectures 9,10,11. - HW 4 Nov 13 - 20: Lectures 12,13,14. - HW 5 Nov 27 - Dec 4: Lectures 15,16,17. - HW 6 Dec 4 - Dec 11: Lectures 18,19 ::: ::: spoiler **Exams: 25, 25, 26 pts**. We will have three non-cumulative exams in the course. Exam 1, Exam 2 will be in class (Mong Learning Center) during lecture hours. Exam 3 will be as per university schedule (but only two hours). ::: ::: spoiler **Exam Coverage and Dates**: Expand to see details. - Exam 1 Nov 8, 8 - 9:50 (Lecture time - Young CS24): Lectures 1,2,3,4,5,6,7,8. - Exam 2 Nov 29, 8-9:50 (Lecture time - Young CS24): Lectures 9,10,11,12,13,14. (The excess gap between exam 1 and exam 2 is to avoid exam during Thanksgiving week.) - Exam 3 Dec 14, 3 - 5pm (university schedule): Lectures 15,16,17,18,19,20. ::: --- ## Syllabus Broad outline of the course content. - Introduction: 2 Lectures (Chapters 0,1,2) - Circuits: 3 Lectures (Chapter 3,5) - Automata: 4 Lectures (Chapter 6) - Turing Machines: 3 Lectures (Chapter 7,8) - Universality and Computability: 3 Lectures (Chapter 9) - Restricted Models of Computation: 2 Lectures (Chapter 10) - Introduction to quantum computing: 3 --- ## Course Policies - There will be no makeup exams for the course. If the above dates do not work for you, you need to talk to me within the first week of classes. - Regrade requests need to be submitted electronically on Gradescope within a week of receiving the graded work. Requests later than a week will not be handled (mainly to keep things flowing). - If you are unsatisfied with the online response for your regrade request, bring it up during TA office hours. If that also does not resolve it, and only then, you can bring it up during instructor office hours (so that we have time to discuss course material during the limited office hours). - We will use edStem for questions and discussions. Please ask questions related to assignments on that platform and not via email. Use this platform so that others can also benefit from your questions; if you want to communicate a private question, you can also do that on edStem. - Collaboration on homeworks is encouraged, but each student must write their solutions independently and should clearly mention the collaborators. Keep in mind that just attempting the homeworks itself will get you reasonable partial credit and will go a long way towards better performance in the exams (which carry significantly more weight). You should never share your written solutions with someone else or copy from someone else's written solutions. Under no circumstances may you use solution sets to problems from previous year courses or from similar courses elsewhere or other resources on the web.
Last changed by  
 
Raghu Meka
9434

Read more

Algorithmic Machine Learning

In this course we will look at a handful of ubiquitous algorithms in machine learning. We will cover several classical tools in machine learning but more emphasis will be given to recent advances and developing efficient and provable algorithms for learning tasks. A tentative syllabus/schedule can be found below; the topics may change based on student interests as well. You can also check last year's course notes for a more details about what's to come.

4/5/2024
Research

My main interests are in complexity theory, learning theory, algorithm design. More generally, I like probability and combinatorics related things. The best resource for up to date publications really is to look up my profile on Google scholar.

2/29/2024
Algorithmic Machine Learning

In this course we will look at a handful of ubiquitous algorithms in machine learning. We will cover several classical tools in machine learning but more emphasis will be given to recent advances and developing efficient and provable algorithms for learning tasks. A tentative syllabus/schedule can be found below; the topics may change based on student interests as well. You can also check last year's course notes for a more details about what's to come.

2/23/2024
Teaching

Here are the courses I have taught or will in the future.

2/23/2024
Read more from Raghu Meka
Published on HackMD