Try   HackMD

Raghu Meka: CS181: Introduction to Theoretical Computer Science, Fall 2020

HOME RESEARCH TEACHING

Introduction

The official title for the course is Formal Languages and Automata Theory. This offering will be geared towards introducing you to the beautiful and profundly impactful world of Theoretical Computer Science (TOC). The following three questions encompass our main learning goals:

1. What is computation?

How different is the iMac Pro really from Apple III?

2. Can we compute our way out of everything?

How about predicting Stack Overflow errors at compile time?

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.

Calendar

The follwing calendar has the links to assignments, notes and other announcements along with brief summaries of each lecture (click 'more details' for each entry - color coded based on exam coverage; could be helpful to subscribe to calendar.).

Logistics and Resources

Lecture hours: Tu-Th 2-3:50: On Zoom and will be recorded.

Zoom session. Exceptions: Lecture in discussion sections from 12 - 2 on Oct 30, and Nov 20. The exact time or format of exam might change depending on student feedback (to accomodate remote learning; note the date is fixed). Strongly recommended to attend live or watch without too much delay.

Course notes: We will use Scribble. See links below.
  • Note that each lecture is on a separate sheet. Keep in mind that these are just transcripts of the whiteboard in class and are not intended to be complete lecture notes.
  • Current scribble page is here. PDF is here
  • Scribble page for Week 9 is here. PDF is here
  • The scribble page for Week 8 is here. PDF is here
  • The scribble page for Week 7 is here. PDF is here
  • The scribble page for Week 6 is here. PDF is here
  • The scribble page for Week 5 - lectures 10,11 is here. PDF is here.
  • The scribble page for Lectures 8,9 is here. PDF is here.
  • The scribble for lectures 5,6,7 is here. PDF is here.
  • The scribble for lectures 1,2,3,4 is here. PDF of lectures 1,2,3,4 is here.
Course team: We will have five TAs roughly one for each of five sections.
  • Ali Pazokitoroudi, a 3nd-year PhD student in Machine Learning and Genomics Lab
  • Boyang Fu, a 2nd-year PhD from UCLA
  • Hadley Black, a PhD student in theory
  • Shaan Mathur, a 2nd-year MS who is into theory, deep learning, and startups! And also Rocket League :)
  • Yuxing Qiu, a 3rd-year PhD from VCLA
Discussion Sections Hours: Fridays. Expand for hours.
  • Section A: 10 - 11:50; TA: Shaan Mathur
  • Section B: 12 - 1:50; TA: Hadley Black
  • Section C: 12 - 1:50; TA: Boyang Fu
  • Section D: 2 - 3:50; TA: Yuxing Qiu
  • Section E: 10 - 11:50 TA: Ali Pazoki
Office Hours: Exploit these!
  1. Instructor office hours: Tu-Th 4-5. (zoom link)
  2. Shaan Mathur: Thu 1pm-2pm, Fri 2pm-3pm (Thursday OH, Friday OH)
  3. Hadley Black: Tue 12-1pm, Wed 4-5pm (zoom link: https://ucla.zoom.us/j/4872080302) (Tue 12/8: 12:30-1:30pm)
  4. Ali Pazokitoroudi: Mon, Wed, 3-4 pm. (zoom link :https://ucla.zoom.us/my/alipazoki )
  5. Boyang Fu: Mon, Wed 9:30-10:30 am. (zoom link: https://ucla.zoom.us/my/boyangfu)
  6. Yuxing Qiu: Wed, Thu, 9-10 am. (zoom link: https://ucla.zoom.us/j/94485831909)
CampusWire: Our online space for asking and answering questions.

We will make use of CampusWire 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 here as well as 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.

Homework submission: On 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 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; you can also use the scanners in the library.

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.

Textbook: Introduction to Theoretical Computer Science by Boaz Barak

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 by Michael Sipser.

If you are interested in learning more about TOC, for advanced but high-level overview these two books are highly recommended.

Homeworks

Grading

Homeworks: 5x6pts + 2x5pts. One each week except for the first week and the weeks with exams.

All are released on Tuesday (by 7PM Pacific) and are due the following Tuesday (by 9:59 PM Pacific) except the last which is due on Saturday (as final is on the next Tuesday).

Homework Coverage and Dates: Expand to see details.
  • HW 1 Oct 13 - 20: Lectures 1,2,3,4.
  • HW 2 Oct 20 - 27: Lectures 5,6,7.
  • HW 3 Nov 3 - 10: Lectures 8,9,10.
  • HW 4 Nov 10 - 17: Lectures 11,12,13.
  • HW 5 Nov 24 - Dec 1: Lectures 15,16.
  • HW 6 Dec 1 - Dec 8: Lectures 17,18.
  • HW 7 Dec 8 - 12: Lectures 19,20.
Exams: 3x20pts. We will have three non-cumulative exams in the course.
Exam Coverage and Dates: Expand to see details.

The time of exam (fixed vs flexible etc.,) might change depending on feedback to account for remote learning and different time zones. Note that the dates of the exams are fixed.

  • Exam 1 Oct 29 Thu 2-3:50 (Lecture time): Lectures 1,2,3,4,5,6,7.
  • Exam 2 Nov 19 Thu 2-3:50 (Lecture time): Lectures 8,9,10,11,12,13,14.
  • Exam 3 Dec 15 Tue 8-9:50 (Finals slot): 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)
  • Cook-Levin Theorem: 3 Lectures (Chapter 14, 15)

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.
  • Students who start more than 15 minutes late for an exam will not be allowed into the exam and will automatically receive 0 credit.
  • 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 CampusWire 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 Campuswire.
  • 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 resoruces on the web.
Last changed by 
 
Raghu Meka
0
14874

Read more

Algorithmic Machine Learning Spring 2025

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.

Apr 26, 2025
Raghu Meka

raghum@cs.ucla.***, Engineering VI 463.

Apr 9, 2025
Teaching

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

Feb 28, 2025
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.

Aug 27, 2024
Read more from Raghu Meka
Published on HackMD