Models of Computation

by | Dec 29, 2018 | Computers and Technology | 0 comments

These are lecture notes that I wrote for the course ‘Algorithms and Models of Computation’ at the University of Illinois, Urbana-Champaign for the first time in Fall 2014. This course is a broad introduction to theoretical computer science, aimed at third-year computer science and computer engineering majors, that covers both fundamental topics in algorithms, for which I already have copious notes, and fundamental topics on formal languages and automata, for which I wrote the notes you are reading now.

These notes assume the reader has mastered the material covered in the first two years of a strong undergraduate computer science curriculum, and that they have the intellectual maturity to recognize and repair any remaining gaps in their mastery. In particular, for most students, these notes are not suitable for a first course in data structures and algorithms.

  • 1 Strings
  • 2 Regular Languages
  • 3 Finite-State Machines
  • 4 Nondeterministic Automata
  • 5 Context-Free Languages
  • 6 Turing Machines
  • 7 Universal Models
  • 8 Undecidability
  • 9 Nondeterministic Turing Machines

Models of Computation

by Jeff Erickson (PDF) – 1,250 pages

Models of Computation by Jeff Erickson

Related Posts

57 Computer History Videos, Documentaries and Ebooks

57 Computer History Videos, Documentaries and Ebooks

Computing is the bedrock technology that fuels the homes of billions of people around the world. It offers endless possibilities for producing, sharing, and saving information. In this article, a list originally maintained by Thomas Watson, recompiled and cleaned, takes a look at some of the most important innovations in computing history. It covers information from as early as 1953, right down to 2016, in various forms of folklores, recordings, documentaries, interviews, lectures and movies.

136 Free Scientific Articles, Thesis and Reports on Deep Learning for Music

136 Free Scientific Articles, Thesis and Reports on Deep Learning for Music

Over the last several years, a new area of research called deep learning has taken the machine learning community by storm, delivering very promising results in all areas of speech and image recognition. However, one missing link is the lack of an accessible and easy-to-use open-source deep learning library for the music and/or audio research community. In this post we will introduce you to scientific articles, thesis and reports that use deep learning approaches applied to music. The documents are generally in PDF formats, sorted by years and paired with source codes if they’re available.

181 Articles, Websites and Resources about Diversity and Inclusion in Technology

181 Articles, Websites and Resources about Diversity and Inclusion in Technology

This collection includes postings, articles, talks, actionable tools, conferences, social media advocates, and other resources on diversity, specifically diversity in technology. The list’s goal is to provide quick access to diversity information to tech companies and communities that want to do more in their everyday actions to make the tech industry a more inclusive place, as well as to individuals who want to learn more about topics related to diversity and equity in the tech field.