Check server response of
Server response
NS records
Whois domain
301 Moved Permanently - cs251.com
HTTP Status: 301
User-Agent: Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; [email protected])
Date: Wed, 30 Apr 2025 19:49:58 GMT
Content-Type: text/html
Content-Length: 167
Connection: keep-alive
Cache-Control: max-age=3600
Expires: Wed, 30 Apr 2025 20:49:58 GMT
Location: https://www.cs251.com/
Report-To: {"endpoints":[{"url":"https:\/\/a.nel.cloudflare.com\/report\/v4?s=bYn4tqqG9aKSoRPvsc%2Fzv9bZDZ%2BOh2E2t2Gc7TfMNnbDRv2zC3pQoTKDYwzUcq6di3Y8vKN75tvQRcqToF3VBz5wdf4707RkjAcd9pqrhfdbz7390aVVonxDQYyFNeLt21hhIZsoBUA%3D"}],"group":"cf-nel","max_age":604800}
NEL: {"success_fraction":0,"report_to":"cf-nel","max_age":604800}
Server: cloudflare
CF-RAY: 938990c15f219fe1-AMS
alt-svc: h3=":443"; ma=86400
server-timing: cfL4;desc="?proto=TCP&rtt=27070&min_rtt=27070&rtt_var=13535&sent=1&recv=3&lost=0&retrans=0&sent_bytes=0&recv_bytes=165&delivery_rate=0&cwnd=249&unsent_bytes=0&cid=0000000000000000&ts=0&x=0"
HTTP Code 301 Moved Permanently
301 status code means that the requested resource has been permanently moved to a new URL. All future requests should use the new address.
When is Code 301 used?
- When changing a website domain
- When modifying URL structures
- When setting up redirects for SEO
What does Code 301 mean for the user?
The browser will automatically redirect the user to the new address, and search engines will update their indexes.
200 OK - https://www.cs251.com/
HTTP Status: 200
User-Agent: Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; [email protected])
Date: Wed, 30 Apr 2025 19:49:58 GMT
Content-Type: text/html
Transfer-Encoding: chunked
Connection: keep-alive
x-guploader-uploadid: AAO2VwpekUxDkqH3_P_4XGyTsI3SIgW3y_kEN3X32OMzpbrXppyMlwxV3Y_XtpR7dpOu1PQT
x-goog-generation: 1682157865195077
x-goog-metageneration: 1
x-goog-stored-content-encoding: identity
x-goog-stored-content-length: 59348
x-goog-hash: crc32c=zYHgXw==
x-goog-hash: md5=2Nmr0nh/vBCgWV0MS+W9Ew==
x-goog-storage-class: STANDARD
accept-ranges: bytes
expires: Wed, 30 Apr 2025 20:21:24 GMT
Cache-Control: public, max-age=3600
Age: 1714
last-modified: Sat, 22 Apr 2023 10:04:25 GMT
alt-svc: h3=":443"; ma=86400
cf-cache-status: DYNAMIC
Report-To: {"endpoints":[{"url":"https:\/\/a.nel.cloudflare.com\/report\/v4?s=M4PaXBzCMTm8Z%2F6a7NUFLJ39gE315YcG4GR8apl3qhpEhbqxekFiXG0zz%2BmIfyaogdK%2BlOSL8%2BUHvbLXID4%2BFT924ANPVbVD7cXyBKMB05tkKStwrtn0%2FgrJVuJrEbX8ZrK%2FLgqQVTQ84tsB"}],"group":"cf-nel","max_age":604800}
NEL: {"success_fraction":0,"report_to":"cf-nel","max_age":604800}
Server: cloudflare
CF-RAY: 938990c21cf7c13c-AMS
server-timing: cfL4;desc="?proto=TCP&rtt=27068&min_rtt=26991&rtt_var=7643&sent=5&recv=7&lost=0&retrans=0&sent_bytes=2834&recv_bytes=788&delivery_rate=149572&cwnd=252&unsent_bytes=0&cid=daf43f80cde24892&ts=50&x=0"
HTTP Code 200 OK
200 status code is a standard successful HTTP server response. It means that the client’s request (e.g., from a browser) was successfully processed, and the server is delivering the requested data.
When is Code 200 used?
- When loading a web page
- When successfully receiving an API response
- When processing a form or another HTTP request
What does Code 200 mean for the user?
The user receives content without errors, and the page or application functions properly. If Code 200 is accompanied by data, the browser or program processes and displays it to the user.
GET / HTTP/1.1 Host: cs251.com Accept: */* User-Agent: Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; [email protected])
<!DOCTYPE html>
<html lang="en">
<head>
<!-- Global site tag (gtag.js) - Google Analytics -->
<script async src="https://www.googletagmanager.com/gtag/js?id=G-4EZVL7C0B4"></script>
<script>
window.dataLayer = window.dataLayer || [];
function gtag(){dataLayer.push(arguments);}
gtag('js', new Date());
gtag('config', 'G-4EZVL7C0B4');
</script>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>
CS251
</title>
<base href="https://www.cs251.com/">
<link rel="icon" href="static/images/cs251_tab_icon.jpg">
<link rel="stylesheet" href="static/css/bootstrap.min.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/[email protected]/font/bootstrap-icons.css">
<link rel="stylesheet" href="static/css/fontawesome.min.css" >
<link rel="stylesheet" href="static/css/all.min.css">
<link href="https://unpkg.com/[email protected]/dist/aos.css" rel="stylesheet">
<link rel="preconnect" href="https://fonts.gstatic.com">
<link href="https://fonts.googleapis.com/css2?family=Open+Sans:ital,wght@0,300;0,400;0,600;0,700;0,800;1,300;1,400;1,600;1,700;1,800&display=swap" rel="stylesheet">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/[email protected]/dist/katex.min.css" integrity="sha384-AfEj0r4/OFrOo5t7NnNe46zW/tFgW6x/bCJG8FqQCEo3+Aro6EYUG4+cU+KJWu/X" crossorigin="anonymous">
<script defer src="https://cdn.jsdelivr.net/npm/[email protected]/dist/katex.min.js" integrity="sha384-g7c+Jr9ZivxKLnZTDUhnkOnsh30B4H0rpLUpJ4jAIKs4fnJI+sEnkvrMWph2EDg4" crossorigin="anonymous"></script>
<script defer src="https://cdn.jsdelivr.net/npm/[email protected]/dist/contrib/auto-render.min.js" integrity="sha384-mll67QQFJfxn0IYznZYonOWZ644AWYC+Pt2cHqMaRhXVrursRwvLnLaebdGIlYNa" crossorigin="anonymous"></script>
<script>
document.addEventListener("DOMContentLoaded", function() {
renderMathInElement(document.body, {
delimiters: [
{left: "$$", right: "$$", display: true},
{left: "\\(", right: "\\)", display: false},
{left: "\\[", right: "\\]", display: true},
],
ignoredClasses: ["ignore-math"]
});
});
</script>
<link rel="stylesheet" href="static/css/general.css">
<link rel="stylesheet" href="static/css/modules.css">
</head>
<body style=" background-color: black;">
<nav class="navbar navbar-expand-lg navbar-dark bg-dark fixed-top" style="padding-top:2px; padding-bottom: 2px; background-color: black !important;">
<div class="container-fluid">
<a class="" href="index.html" style="margin-left:10px; margin-right:5px;">
<img class="" src="static/images/cs251_navbar_pic.jpg" style="width:40px">
</a>
<a class="navbar-brand navbar-brand-course" href="index.html">CS251</a>
<button class="navbar-toggler" type="button" data-bs-toggle="collapse" data-bs-target="#navbarsExampleDefault" aria-controls="navbarsExampleDefault" aria-expanded="false" aria-label="Toggle navigation">
<span class="navbar-toggler-icon"></span>
</button>
<div class="collapse navbar-collapse" id="navbarsExampleDefault">
<ul class="navbar-nav me-auto mb-2 mb-md-0">
<li class="nav-item dropdown" style="padding-top: 10px; padding-bottom: 10px;">
<a class="nav-link nav-link-icon-text dropdown-toggle" href="#" id="dropdown-1" data-bs-toggle="dropdown" aria-expanded="false">
<span class="nav-text ">Lectures</span>
</a>
<ul class="dropdown-menu" aria-labelledby="dropdown-1" style="background-color: white;">
<h6 class="dropdown-header">Part 1: Formalizing Computation</h6>
<li><a class="dropdown-item navbar-menu-item semi-strong maroon hover-highlight " href="https://www.youtube.com/watch?v=BKyWvce2yAY" style="margin-right: 1.5rem;"><i class="fas fa-video"></i> Introduction</a></li>
<li><a class="dropdown-item navbar-menu-item semi-strong maroon hover-highlight " href="https://www.youtube.com/watch?v=lnGYfVxFnnI" style="margin-right: 1.5rem;"><i class="fas fa-video"></i> Mathematical Reasoning and Proofs</a></li>
<li><a class="dropdown-item navbar-menu-item semi-strong maroon hover-highlight " href="https://www.youtube.com/watch?v=CQ6uSitbLtE" style="margin-right: 1.5rem;"><i class="fas fa-video"></i> What Is Information</a></li>
<li><a class="dropdown-item navbar-menu-item semi-strong maroon hover-highlight " href="https://www.youtube.com/watch?v=FmQBWlDMh9A" style="margin-right: 1.5rem;"><i class="fas fa-video"></i> Deterministic Finite Automata 1</a></li>
<li><a class="dropdown-item navbar-menu-item semi-strong maroon hover-highlight " href="https://www.youtube.com/watch?v=Cma4FjmFWSw" style="margin-right: 1.5rem;"><i class="fas fa-video"></i> Deterministic Finite Automata 2</a></li>
<li><a class="dropdown-item navbar-menu-item semi-strong maroon hover-highlight " href="https://www.youtube.com/watch?v=aaRvSWTRjGA" style="margin-right: 1.5rem;"><i class="fas fa-video"></i> Turing Machines</a></li>
<li><a class="dropdown-item navbar-menu-item semi-strong maroon hover-highlight " href="https://www.youtube.com/watch?v=apQbGf3gnF0" style="margin-right: 1.5rem;"><i class="fas fa-video"></i> Universality of Computation</a></li>
<li><a class="dropdown-item navbar-menu-item semi-strong maroon hover-highlight " href="https://www.youtube.com/watch?v=A-XdxZfAxhY" style="margin-right: 1.5rem;"><i class="fas fa-video"></i> Limits of Computation, Part 1</a></li>
<li><a class="dropdown-item navbar-menu-item semi-strong maroon hover-highlight " href="https://www.youtube.com/watch?v=yBMqsFf3M7Y" style="margin-right: 1.5rem;"><i class="fas fa-video"></i> Limits of Computation, Part 2</a></li>
<li><a class="dropdown-item navbar-menu-item semi-strong maroon hover-highlight " href="https://www.youtube.com/watch?v=qit_D-mFrF0" style="margin-right: 1.5rem;"><i class="fas fa-video"></i> Limits of Computation, Part 3</a></li>
<li><a class="dropdown-item navbar-menu-item semi-strong maroon hover-highlight " href="https://www.youtube.com/watch?v=IaX6B-CIUmE" style="margin-right: 1.5rem;"><i class="fas fa-video"></i> Limits of Human Reasoning</a></li>
<h6 class="dropdown-header">Part 2: Computational Complexity</h6>
<span style="padding-left:15px">To be added...</span>
<h6 class="dropdown-header">Part 3: Highlights of Theoretical Computer Science</h6>
<span style="padding-left:15px">To be added...</span>
</ul>
</li>
<li class="nav-item" style="padding-top: 10px; padding-bottom: 10px;">
<a class="nav-link nav-link-icon-text" href="Staff/Ch_Staff/contents.html">
<span class="nav-text">Staff</span>
</a>
</li>
</ul>
<ul class="navbar-nav navbar-right">
</ul>
</div>
</div>
</nav>
<main class="container-fluid">
<div class="row" style="padding-top:40px; background-color: white">
<div class="col-12 text-center">
<h1 class="display-2 d-none d-sm-none d-md-none d-lg-none d-xl-none d-xxl-block" style="font-weight:200;">Great Ideas in Theoretical Computer Science</h1>
<h1 class="display-3 d-none d-sm-none d-md-none d-lg-none d-xl-block d-xxl-none" style="font-weight:200;">Great Ideas in Theoretical Computer Science</h1>
<h1 class="display-4 d-none d-sm-none d-md-none d-lg-block d-xl-none d-xxl-none" style="font-weight:200;">Great Ideas in Theoretical Computer Science</h1>
<h1 class="display-5 d-none d-sm-none d-md-block d-lg-none d-xl-none d-xxl-none" style="font-weight:200;">Great Ideas in Theoretical Computer Science</h1>
<h1 class="display-6 d-block d-sm-block d-md-none d-lg-none d-xl-none d-xxl-none" style="font-weight:200;">Great Ideas in Theoretical Computer Science</h1>
</div>
</div>
<div class="row" style="padding-top: 60px; padding-bottom: 70px; background-color: white">
<div class="col-12 col-sm-12 col-md-10 col-lg-5 col-xl-5 col-xxl-5 offset-0 offset-sm-0 offset-md-1 offset-lg-1 offset-xl-1 offset-xxl-1 text-center">
<img class="" src="static/images/cs251_pic.jpg" style="width: 75%; padding-top: 10px">
</div>
<div class="col-12 col-sm-12 col-md-12 col-lg-5 col-xl-5 col-xxl-5 offset-0 offset-sm-0 offset-md-0 offset-lg-0 offset-xl-0 offset-xxl-0" style="padding-top:10px;">
<p class="bold lead">Welcome to <span class="maroon">CS251</span> at <a href="https://www.cmu.edu">CMU</a>!</p>
<p>This course is about the rigorous study of computation, which is a fundamental component of our universe, the societies we live in, the new technologies we discover, as well as the minds we use to understand these things. Therefore, having the right language and tools to study computation is important. In this course, we explore some of the central results and questions regarding the nature of computation.</p>
</div>
</div>
<div class="row" style="padding-top: 30px; padding-bottom: 80px; background-color: #f9f9f9">
<div class="col-xl-12 col-xxl-10 offset-xl-0 offset-xxl-1">
<div class="row text-center" style="margin-top: 60px;">
<div class="col" style="padding-left:0px;">
<hr>
</div>
<div class="col-auto part-num">
PART 1
</div>
<div class="col" style="padding-right:0px;">
<hr>
</div>
</div>
<div class="row text-center">
<div class="col-12 part-title">
Formalizing Computation
</div>
</div>
<div class="row">
<div class="col-12" style="padding:0px;">
<hr>
</div>
</div>
<div class="row align-items-center modules-module-title-container">
<div class="col-lg-2 col-xl-3 d-none d-sm-none d-md-none d-lg-block text-center">
<span class="modules-module-tag">MODULE 1</span>
</div>
<div class="col-lg-10 col-xl-9">
<span class="modules-module-tag d-block d-sm-block d-md-block d-lg-none" style="padding-left:15px;">MODULE 1</span>
<span class="modules-module-title">Introduction</span>
</div>
</div>
<div class="row" style="margin-top: 10px">
<div class="col-lg-2 col-xl-3 d-none d-sm-none d-md-none d-lg-block">
<div class="row">
<div class="col-12">
<img class="img-thumbnail shadow-depth-1" src="static/images/Module_Introduction.jpg">
</div>
</div>
</div>
<div class="col-lg-10 col-xl-9">
<div class="row" style="padding-right:15px; padding-left:15px;">
<div class="col-12 shadow-depth-1" style="background-color:white; padding-top: 20px; padding-bottom: 25px; padding-left: 25px; padding-right: 25px; border: 1px solid #dee2e6; border-radius: 0.25rem">
<div class="row">
<div class="col-12" style="text-align: justify;">
<p>Welcome to CS251! In this module, our main goal is to explain at a high-level what theoretical computer science is about and set the right context for the material covered in the future.</p>
<p>In the first part of the course, we want to build up formally/mathematically, the important notions related to computation and algorithms. We start this journey here by discussing how to formally represent data and how to formally define the concept of a computational problem.</p>
</div>
</div>
<div class="row">
<div class="col-12" style="margin-bottom: 5px;">
<strong>Contents:</strong>
</div>
</div>
<div class="row">
<div class="col-12">
<div class="row">
<a href="https://www.youtube.com/watch?v=BKyWvce2yAY" style="text-decoration:none;">
<div class="col-12 maroon hover-highlight" style="padding-top: 3px; padding-bottom: 3px;">
<div class="row">
<div style="width: 25px;">
<i class="fas fa-video" style="margin-left: 5px; font-size: 20px; vertical-align: sub;"></i>
</div>
<div class="col" style="padding-left:25px;">
<span class="module-chapter-title">Introduction</span>
</div>
</div>
</div>
</a>
</div>
<div class="row">
<a href="https://www.youtube.com/watch?v=lnGYfVxFnnI" style="text-decoration:none;">
<div class="col-12 maroon hover-highlight" style="padding-top: 3px; padding-bottom: 3px;">
<div class="row">
<div style="width: 25px;">
<i class="fas fa-video" style="margin-left: 5px; font-size: 20px; vertical-align: sub;"></i>
</div>
<div class="col" style="padding-left:25px;">
<span class="module-chapter-title">Mathematical Reasoning and Proofs</span>
</div>
</div>
</div>
</a>
</div>
<div class="row">
<a href="https://www.youtube.com/watch?v=CQ6uSitbLtE" style="text-decoration:none;">
<div class="col-12 maroon hover-highlight" style="padding-top: 3px; padding-bottom: 3px;">
<div class="row">
<div style="width: 25px;">
<i class="fas fa-video" style="margin-left: 5px; font-size: 20px; vertical-align: sub;"></i>
</div>
<div class="col" style="padding-left:25px;">
<span class="module-chapter-title">What Is Information</span>
</div>
</div>
</div>
</a>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
<div class="row align-items-center modules-module-title-container">
<div class="col-lg-2 col-xl-3 d-none d-sm-none d-md-none d-lg-block text-center">
<span class="modules-module-tag">MODULE 2</span>
</div>
<div class="col-lg-10 col-xl-9">
<span class="modules-module-tag d-block d-sm-block d-md-block d-lg-none" style="padding-left:15px;">MODULE 2</span>
<span class="modules-module-title">Finite Automata</span>
</div>
</div>
<div class="row" style="margin-top: 10px">
<div class="col-lg-2 col-xl-3 d-none d-sm-none d-md-none d-lg-block">
<div class="row">
<div class="col-12">
<img class="img-thumbnail shadow-depth-1" src="static/images/Module_Finite_Automata.jpg">
</div>
</div>
</div>
<div class="col-lg-10 col-xl-9">
<div class="row" style="padding-right:15px; padding-left:15px;">
<div class="col-12 shadow-depth-1" style="background-color:white; padding-top: 20px; padding-bottom: 25px; padding-left: 25px; padding-right: 25px; border: 1px solid #dee2e6; border-radius: 0.25rem">
<div class="row">
<div class="col-12" style="text-align: justify;">
<p>The goal of this module is to introduce you to a simple (and restricted) model of computation known as <em>deterministic finite automata</em> (DFA). This model is interesting to study in its own right, and has very nice applications, however, our main motivation to study this model is to use it as a stepping stone towards formally defining the notion of an <em>algorithm</em> in its full generality. Treating deterministic finite automata as a warm-up, we would like you to get comfortable with how one formally defines a model of computation, and then proves interesting theorems related to the model. Along the way, you will start getting comfortable with using a bit more sophisticated mathematical notation than you might be used to. You will see how mathematical notation helps us express ideas and concepts accurately, succinctly and clearly.</p>
</div>
</div>
<div class="row">
<div class="col-12" style="margin-bottom: 5px;">
<strong>Contents:</strong>
</div>
</div>
<div class="row">
<div class="col-12">
<div class="row">
<a href="https://www.youtube.com/watch?v=FmQBWlDMh9A" style="text-decoration:none;">
<div class="col-12 maroon hover-highlight" style="padding-top: 3px; padding-bottom: 3px;">
<div class="row">
<div style="width: 25px;">
<i class="fas fa-video" style="margin-left: 5px; font-size: 20px; vertical-align: sub;"></i>
</div>
<div class="col" style="padding-left:25px;">
<span class="module-chapter-title">Deterministic Finite Automata 1</span>
</div>
</div>
</div>
</a>
</div>
<div class="row">
<a href="https://www.youtube.com/watch?v=Cma4FjmFWSw" style="text-decoration:none;">
<div class="col-12 maroon hover-highlight" style="padding-top: 3px; padding-bottom: 3px;">
<div class="row">
<div style="width: 25px;">
<i class="fas fa-video" style="margin-left: 5px; font-size: 20px; vertical-align: sub;"></i>
</div>
<div class="col" style="padding-left:25px;">
<span class="module-chapter-title">Deterministic Finite Automata 2</span>
</div>
</div>
</div>
</a>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
<div class="row align-items-center modules-module-title-container">
<div class="col-lg-2 col-xl-3 d-none d-sm-none d-md-none d-lg-block text-center">
<span class="modules-module-tag">MODULE 3</span>
</div>
<div class="col-lg-10 col-xl-9">
<span class="modules-module-tag d-block d-sm-block d-md-block d-lg-none" style="padding-left:15px;">MODULE 3</span>
<span class="modules-module-title">Formalizing Computation</span>
</div>
</div>
<div class="row" style="margin-top: 10px">
<div class="col-lg-2 col-xl-3 d-none d-sm-none d-md-none d-lg-block">
<div class="row">
<div class="col-12">
<img class="img-thumbnail shadow-depth-1" src="static/images/Module_Formalizing_Computation.jpg">
</div>
</div>
</div>
<div class="col-lg-10 col-xl-9">
<div class="row" style="padding-right:15px; padding-left:15px;">
<div class="col-12 shadow-depth-1" style="background-color:white; padding-top: 20px; padding-bottom: 25px; padding-left: 25px; padding-right: 25px; border: 1px solid #dee2e6; border-radius: 0.25rem">
<div class="row">
<div class="col-12" style="text-align: justify;">
<p>In this module, our main goal is to introduce the definition of a Turing machine, which is the standard mathematical model for any kind of computational device. As such, this definition is very foundational. As we discuss in lecture, the physical Church-Turing thesis asserts that any kind of physical device or phenomenon, when viewed as a computational process mapping input data to output data, can be simulated by some Turing machine. Thus, rigorously studying Turing machines does not just give us insights about what our laptops can or cannot do, but also tells us what the universe can and cannot do computationally. This module kicks things off with examples of computable problems. In the next module, we will start exploring the limitations of computation.</p>
</div>
</div>
<div class="row">
<div class="col-12" style="margin-bottom: 5px;">
<strong>Contents:</strong>
</div>
</div>
<div class="row">
<div class="col-12">
<div class="row">
<a href="https://www.youtube.com/watch?v=aaRvSWTRjGA" style="text-decoration:none;">
<div class="col-12 maroon hover-highlight" style="padding-top: 3px; padding-bottom: 3px;">
<div class="row">
<div style="width: 25px;">
<i class="fas fa-video" style="margin-left: 5px; font-size: 20px; vertical-align: sub;"></i>
</div>
<div class="col" style="padding-left:25px;">
<span class="module-chapter-title">Turing Machines</span>
</div>
</div>
</div>
</a>
</div>
<div class="row">
<a href="https://www.youtube.com/watch?v=apQbGf3gnF0" style="text-decoration:none;">
<div class="col-12 maroon hover-highlight" style="padding-top: 3px; padding-bottom: 3px;">
<div class="row">
<div style="width: 25px;">
<i class="fas fa-video" style="margin-left: 5px; font-size: 20px; vertical-align: sub;"></i>
</div>
<div class="col" style="padding-left:25px;">
<span class="module-chapter-title">Universality of Computation</span>
</div>
</div>
</div>
</a>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
<div class="row align-items-center modules-module-title-container">
<div class="col-lg-2 col-xl-3 d-none d-sm-none d-md-none d-lg-block text-center">
<span class="modules-module-tag">MODULE 4</span>
</div>
<div class="col-lg-10 col-xl-9">
<span class="modules-module-tag d-block d-sm-block d-md-block d-lg-none" style="padding-left:15px;">MODULE 4</span>
<span class="modules-module-title">Limits of Computation</span>
</div>
</div>
<div class="row" style="margin-top: 10px">
<div class="col-lg-2 col-xl-3 d-none d-sm-none d-md-none d-lg-block">
<div class="row">
<div class="col-12">
<img class="img-thumbnail shadow-depth-1" src="static/images/Module_Limits_of_Computation.jpg">
</div>
</div>
</div>
<div class="col-lg-10 col-xl-9">
<div class="row" style="padding-right:15px; padding-left:15px;">
<div class="col-12 shadow-depth-1" style="background-color:white; padding-top: 20px; padding-bottom: 25px; padding-left: 25px; padding-right: 25px; border: 1px solid #dee2e6; border-radius: 0.25rem">
<div class="row">
<div class="col-12" style="text-align: justify;">
<p>In this module, we prove that most problems are undecidable, and give some explicit examples of undecidable problems. The two key techniques we use are diagonalization and reductions. These are two of the most fundamental concepts in mathematics and computer science.</p>
</div>
</div>
<div class="row">
<div class="col-12" style="margin-bottom: 5px;">
<strong>Contents:</strong>
</div>
</div>
<div class="row">
<div class="col-12">
<div class="row">
<a href="https://www.youtube.com/watch?v=A-XdxZfAxhY" style="text-decoration:none;">
<div class="col-12 maroon hover-highlight" style="padding-top: 3px; padding-bottom: 3px;">
<div class="row">
<div style="width: 25px;">
<i class="fas fa-video" style="margin-left: 5px; font-size: 20px; vertical-align: sub;"></i>
</div>
<div class="col" style="padding-left:25px;">
<span class="module-chapter-title">Limits of Computation, Part 1</span>
</div>
</div>
</div>
</a>
</div>
<div class="row">
<a href="https://www.youtube.com/watch?v=yBMqsFf3M7Y" style="text-decoration:none;">
<div class="col-12 maroon hover-highlight" style="padding-top: 3px; padding-bottom: 3px;">
<div class="row">
<div style="width: 25px;">
<i class="fas fa-video" style="margin-left: 5px; font-size: 20px; vertical-align: sub;"></i>
</div>
<div class="col" style="padding-left:25px;">
<span class="module-chapter-title">Limits of Computation, Part 2</span>
</div>
</div>
</div>
</a>
</div>
<div class="row">
<a href="https://www.youtube.com/watch?v=qit_D-mFrF0" style="text-decoration:none;">
<div class="col-12 maroon hover-highlight" style="padding-top: 3px; padding-bottom: 3px;">
<div class="row">
<div style="width: 25px;">
<i class="fas fa-video" style="margin-left: 5px; font-size: 20px; vertical-align: sub;"></i>
</div>
<div class="col" style="padding-left:25px;">
<span class="module-chapter-title">Limits of Computation, Part 3</span>
</div>
</div>
</div>
</a>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
<div class="row align-items-center modules-module-title-container">
<div class="col-lg-2 col-xl-3 d-none d-sm-none d-md-none d-lg-block text-center">
<span class="modules-module-tag">MODULE 5</span>
</div>
<div class="col-lg-10 col-xl-9">
<span class="modules-module-tag d-block d-sm-block d-md-block d-lg-none" style="padding-left:15px;">MODULE 5</span>
<span class="modules-module-title">Limits of Human Reasoning</span>
</div>
</div>
<div class="row" style="margin-top: 10px">
<div class="col-lg-2 col-xl-3 d-none d-sm-none d-md-none d-lg-block">
<div class="row">
<div class="col-12">
<img class="img-thumbnail shadow-depth-1" src="static/images/Module_Limits_of_Human_Reasoning.jpg">
</div>
</div>
</div>
<div class="col-lg-10 col-xl-9">
<div class="row" style="padding-right:15px; padding-left:15px;">
<div class="col-12 shadow-depth-1" style="background-color:white; padding-top: 20px; padding-bottom: 25px; padding-left: 25px; padding-right: 25px; border: 1px solid #dee2e6; border-radius: 0.25rem">
<div class="row">
<div class="col-12" style="text-align: justify;">
<p>The late 19th to early 20th century was an important time in mathematics. With various problems arising with the usual way of doing mathematics and proving things, it became clear that there was a need to put mathematical reasoning on a secure foundation. In other words, there was a need to mathematically formalize mathematical reasoning itself. As mathematicians took on the task of formalizing mathematics, two things started to become clear. First, a complete formalization of mathematics was not going to be possible. Second, formalization of mathematics involves formalizing what we informally understand as “algorithm” or “computation”. This is because one of the defining features of mathematical reasoning is that it is a computation. In this module we will make this connection explicit and see how the language of theoretical computer science can be effectively used to answer important questions in the foundations of mathematics.</p>
</div>
</div>
<div class="row">
<div class="col-12" style="margin-bottom: 5px;">
<strong>Contents:</strong>
</div>
</div>
<div class="row">
<div class="col-12">
<div class="row">
<a href="https://www.youtube.com/watch?v=IaX6B-CIUmE" style="text-decoration:none;">
<div class="col-12 maroon hover-highlight" style="padding-top: 3px; padding-bottom: 3px;">
<div class="row">
<div style="width: 25px;">
<i class="fas fa-video" style="margin-left: 5px; font-size: 20px; vertical-align: sub;"></i>
</div>
<div class="col" style="padding-left:25px;">
<span class="module-chapter-title">Limits of Human Reasoning</span>
</div>
</div>
</div>
</a>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
<div class="row text-center" style="margin-top: 60px;">
<div class="col" style="padding-left:0px;">
<hr>
</div>
<div class="col-auto part-num">
PART 2
</div>
<div class="col" style="padding-right:0px;">
<hr>
</div>
</div>
<div class="row text-center">
<div class="col-12 part-title">
Computational Complexity
</div>
</div>
<div class="row">
<div class="col-12" style="padding:0px;">
<hr>
</div>
</div>
<div class="row align-items-center modules-module-title-container">
<div class="col-lg-2 col-xl-3 d-none d-sm-none d-md-none d-lg-block text-center">
<span class="modules-module-tag">MODULE 6</span>
</div>
<div class="col-lg-10 col-xl-9">
<span class="modules-module-tag d-block d-sm-block d-md-block d-lg-none" style="padding-left:15px;">MODULE 6</span>
<span class="modules-module-title">Time Complexity</span>
</div>
</div>
<div class="row" style="margin-top: 10px">
<div class="col-lg-2 col-xl-3 d-none d-sm-none d-md-none d-lg-block">
<div class="row">
<div class="col-12">
<img class="img-thumbnail shadow-depth-1" src="static/images/Module_Time_Complexity.jpg">
</div>
</div>
</div>
<div class="col-lg-10 col-xl-9">
<div class="row" style="padding-right:15px; padding-left:15px;">
<div class="col-12 shadow-depth-1" style="background-color:white; padding-top: 20px; padding-bottom: 25px; padding-left: 25px; padding-right: 25px; border: 1px solid #dee2e6; border-radius: 0.25rem">
<div class="row">
<div class="col-12" style="text-align: justify;">
<p>So far, we have formally defined what a computational/decision problem is, what an algorithm is, and saw that most (decision) problems are undecidable. We also saw some explicit and interesting examples of undecidable problems. Nevertheless, it turns out that many problems that we care about are actually decidable. So the next natural thing to study is the computational complexity of problems. If a problem is decidable, but the most efficient algorithm solving it takes vigintillion computational steps even for reasonably sized inputs, then practically speaking, that problem is still undecidable. In a sense, computational complexity is the study of practical computability.</p>
<p>Even though computational complexity can be with respect to various resources like time, memory, randomness, and so on, we will be focusing on arguably the most important one: time complexity. In this module, we will set the right context and language to study time complexity.</p>
</div>
</div>
<div class="row">
<div class="col-12" style="margin-bottom: 5px;">
<strong>Contents:</strong>
</div>
</div>
<div class="row">
<div class="col">
To be added (under construction).
</div>
</div>
</div>
</div>
</div>
</div>
<div class="row align-items-center modules-module-title-container">
<div class="col-lg-2 col-xl-3 d-none d-sm-none d-md-none d-lg-block text-center">
<span class="modules-module-tag">MODULE 7</span>
</div>
<div class="col-lg-10 col-xl-9">
<span class="modules-module-tag d-block d-sm-block d-md-block d-lg-none" style="padding-left:15px;">MODULE 7</span>
<span class="modules-module-title">Graph Theory</span>
</div>
</div>
<div class="row" style="margin-top: 10px">
<div class="col-lg-2 col-xl-3 d-none d-sm-none d-md-none d-lg-block">
<div class="row">
<div class="col-12">
<img class="img-thumbnail shadow-depth-1" src="static/images/Module_Graph_Theory.jpg">
</div>
</div>
</div>
<div class="col-lg-10 col-xl-9">
<div class="row" style="padding-right:15px; padding-left:15px;">
<div class="col-12 shadow-depth-1" style="background-color:white; padding-top: 20px; padding-bottom: 25px; padding-left: 25px; padding-right: 25px; border: 1px solid #dee2e6; border-radius: 0.25rem">
<div class="row">
<div class="col-12" style="text-align: justify;">
<p>In the study of computational complexity of languages and computational problems, graphs play a very fundamental role. This is because an enormous number of computational problems that arise in computer science can be abstracted away as problems on graphs, which model pairwise relations between objects. This is great for various reasons. For one, this kind of abstraction removes unnecessary distractions about the problem and allows us to focus on its essence. Second, there is a huge literature on graph theory, so we can use this arsenal to better understand the computational complexity of graph problems. Applications of graphs are too many and diverse to list here, but we’ll name a few to give you an idea: communication networks, finding shortest routes in various settings, finding matchings between two sets of objects, social network analysis, kidney exchange protocols, linguistics, topology of atoms, and compiler optimization.</p>
<p>This module introduces basic graph theoretic concepts as well as some of the fundamental graph algorithms.</p>
</div>
</div>
<div class="row">
<div class="col-12" style="margin-bottom: 5px;">
<strong>Contents:</strong>
</div>
</div>
<div class="row">
<div class="col">
To be added (under construction).
</div>
</div>
</div>
</div>
</div>
</div>
<div class="row align-items-center modules-module-title-container">
<div class="col-lg-2 col-xl-3 d-none d-sm-none d-md-none d-lg-block text-center">
<span class="modules-module-tag">MODULE 8</span>
</div>
<div class="col-lg-10 col-xl-9">
<span class="modules-module-tag d-block d-sm-block d-md-block d-lg-none" style="padding-left:15px;">MODULE 8</span>
<span class="modules-module-title">P vs NP</span>
</div>
</div>
<div class="row" style="margin-top: 10px">
<div class="col-lg-2 col-xl-3 d-none d-sm-none d-md-none d-lg-block">
<div class="row">
<div class="col-12">
<img class="img-thumbnail shadow-depth-1" src="static/images/Module_P_vs_NP.jpg">
</div>
</div>
</div>
<div class="col-lg-10 col-xl-9">
<div class="row" style="padding-right:15px; padding-left:15px;">
<div class="col-12 shadow-depth-1" style="background-color:white; padding-top: 20px; padding-bottom: 25px; padding-left: 25px; padding-right: 25px; border: 1px solid #dee2e6; border-radius: 0.25rem">
<div class="row">
<div class="col-12" style="text-align: justify;">
<p>In this module, we introduce the complexity class NP and discuss the most important open problem in computer science: the P vs NP problem. The class NP contains many natural and well-studied languages that we would love to decide in polynomial time. In particular, if we could decide the languages in NP efficiently, this would lead to amazing applications. For instance, in mathematics, proofs to theorems with reasonable length proofs would be found automatically by computers. In artificial intelligence, many machine learning tasks we struggle with would be easy to solve (like vision recognition, speech recognition, language translation and comprehension, etc). Many optimization tasks would become efficiently solvable, which would affect the economy in a major way. Another main impact would happen in privacy and security. We would say “bye” to public-key cryptography which is being used heavily on the internet today. (We will learn about public-key cryptography in a later module.) These are just a few examples; there are many more.</p>
<p>Our goal in this module is to present the formal definition of NP, and discuss how it relates to P. We also discuss the notion of NP-completeness (which is intimately related to the question of whether NP equals P) and give several examples of NP-complete languages.</p>
</div>
</div>
<div class="row">
<div class="col-12" style="margin-bottom: 5px;">
<strong>Contents:</strong>
</div>
</div>
<div class="row">
<div class="col">
To be added (under construction).
</div>
</div>
</div>
</div>
</div>
</div>
<div class="row align-items-center modules-module-title-container">
<div class="col-lg-2 col-xl-3 d-none d-sm-none d-md-none d-lg-block text-center">
<span class="modules-module-tag">MODULE 9</span>
</div>
<div class="col-lg-10 col-xl-9">
<span class="modules-module-tag d-block d-sm-block d-md-block d-lg-none" style="padding-left:15px;">MODULE 9</span>
<span class="modules-module-title">Randomized Algorithms</span>
</div>
</div>
<div class="row" style="margin-top: 10px">
<div class="col-lg-2 col-xl-3 d-none d-sm-none d-md-none d-lg-block">
<div class="row">
<div class="col-12">
<img class="img-thumbnail shadow-depth-1" src="static/images/Module_Randomized_Algorithms.jpg">
</div>
</div>
</div>
<div class="col-lg-10 col-xl-9">
<div class="row" style="padding-right:15px; padding-left:15px;">
<div class="col-12 shadow-depth-1" style="background-color:white; padding-top: 20px; padding-bottom: 25px; padding-left: 25px; padding-right: 25px; border: 1px solid #dee2e6; border-radius: 0.25rem">
<div class="row">
<div class="col-12" style="text-align: justify;">
<p>Randomness is an essential concept and tool in modeling and analyzing nature. Therefore, it should not be surprising that it also plays a foundational role in computer science. For many problems, solutions that make use of randomness are the simplest, most efficient and most elegant solutions. And in many settings, one can prove that randomness is absolutely required to achieve a solution. (We mention some concrete examples in lecture.)</p>
<p>One of the primary applications of randomness to computer science is randomized algorithms. A randomized algorithm is an algorithm that has access to a randomness source like a random number generator, and a randomized algorithm is allowed to err with a very small probability of error. There are computational problems that we know how to solve efficiently using a randomized algorithms, however, we do not know how to solve those problems efficiently with a deterministic algorithm (i.e. an algorithm that does not make use of randomness). In fact, one of the most important open problems in computer science asks whether every efficient randomized algorithm has a deterministic counterpart solving the same problem. In this module, we start by reviewing probability theory, and then introduce the concept of randomized algorithms.</p>
</div>
</div>
<div class="row">
<div class="col-12" style="margin-bottom: 5px;">
<strong>Contents:</strong>
</div>
</div>
<div class="row">
<div class="col">
To be added (under construction).
</div>
</div>
</div>
</div>
</div>
</div>
<div class="row align-items-center modules-module-title-container">
<div class="col-lg-2 col-xl-3 d-none d-sm-none d-md-none d-lg-block text-center">
<span class="modules-module-tag">MODULE 10</span>
</div>
<div class="col-lg-10 col-xl-9">
<span class="modules-module-tag d-block d-sm-block d-md-block d-lg-none" style="padding-left:15px;">MODULE 10</span>
<span class="modules-module-title">Cryptography</span>
</div>
</div>
<div class="row" style="margin-top: 10px">
<div class="col-lg-2 col-xl-3 d-none d-sm-none d-md-none d-lg-block">
<div class="row">
<div class="col-12">
<img class="img-thumbnail shadow-depth-1" src="static/images/Module_Cryptography.jpg">
</div>
</div>
</div>
<div class="col-lg-10 col-xl-9">
<div class="row" style="padding-right:15px; padding-left:15px;">
<div class="col-12 shadow-depth-1" style="background-color:white; padding-top: 20px; padding-bottom: 25px; padding-left: 25px; padding-right: 25px; border: 1px solid #dee2e6; border-radius: 0.25rem">
<div class="row">
<div class="col-12" style="text-align: justify;">
<p>The quest for secure communication in the presence of adversaries is an ancient one. From Caesar shift to the sophisticated Enigma machines used by Germans during World War 2, there have been a variety of interesting cryptographic protocols used in history. But it wasn’t until the computer science revolution in the mid 20th century when the field of cryptography really started to flourish. In fact, it is fair to say that the study of computational complexity completely revolutionized cryptography. The key idea is to observe that any adversary would be computationally bounded just like anyone else. And we can exploit the computational hardness of certain problems to design beautiful cryptographic protocols for many different tasks. In this module, we will first review the mathematical background needed (modular arithmetic), and then present some of the fundamental cryptographic protocols to achieve secure communication.</p>
</div>
</div>
<div class="row">
<div class="col-12" style="margin-bottom: 5px;">
<strong>Contents:</strong>
</div>
</div>
<div class="row">
<div class="col">
To be added (under construction).
</div>
</div>
</div>
</div>
</div>
</div>
<div class="row text-center" style="margin-top: 60px;">
<div class="col" style="padding-left:0px;">
<hr>
</div>
<div class="col-auto part-num">
PART 3
</div>
<div class="col" style="padding-right:0px;">
<hr>
</div>
</div>
<div class="row text-center">
<div class="col-12 part-title">
Highlights of Theoretical Computer Science
</div>
</div>
<div class="row">
<div class="col-12" style="padding:0px;">
<hr>
</div>
</div>
<div class="row align-items-center modules-module-title-container">
<div class="col-lg-2 col-xl-3 d-none d-sm-none d-md-none d-lg-block text-center">
<span class="modules-module-tag">MODULE 11</span>
</div>
<div class="col-lg-10 col-xl-9">
<span class="modules-module-tag d-block d-sm-block d-md-block d-lg-none" style="padding-left:15px;">MODULE 11</span>
<span class="modules-module-title">Extra Topics</span>
</div>
</div>
<div class="row" style="margin-top: 10px">
<div class="col-lg-2 col-xl-3 d-none d-sm-none d-md-none d-lg-block">
<div class="row">
<div class="col-12">
<img class="img-thumbnail shadow-depth-1" src="static/images/Module_Extra_Topics.jpg">
</div>
</div>
</div>
<div class="col-lg-10 col-xl-9">
<div class="row" style="padding-right:15px; padding-left:15px;">
<div class="col-12 shadow-depth-1" style="background-color:white; padding-top: 20px; padding-bottom: 25px; padding-left: 25px; padding-right: 25px; border: 1px solid #dee2e6; border-radius: 0.25rem">
<div class="row">
<div class="col-12" style="text-align: justify;">
<p>In this module, we present a selection of highlights from theoretical computer science.</p>
</div>
</div>
<div class="row">
<div class="col-12" style="margin-bottom: 5px;">
<strong>Contents:</strong>
</div>
</div>
<div class="row">
<div class="col">
To be added (under construction).
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
<div class="row" style="background-color: black; height: 100px">
<div class="col-12 text-center" style="color:silver; padding-top: 40px;">
<a rel="license" href="http://creativecommons.org/licenses/by-nc-nd/4.0/"><img alt="Creative Commons License" style="border-width:0" src="https://i.creativecommons.org/l/by-nc-nd/4.0/88x31.png" /></a> <span style="margin-left: 10px;">This work is licensed under a <a rel="license" href="http://creativecommons.org/licenses/by-nc-nd/4.0/">Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License</a>.</span>
</div>
</div>
</main>
<script src="static/js/jquery-3.5.1.min.js"></script>
<script src="static/js/bootstrap.bundle.min.js"></script>
<script src="static/js/all.min.js"></script>
<script src="static/js/main.js"></script>
</body>
</html>
Whois info of domain
Domain Name: CS251.COM
Registry Domain ID: 2646161457_DOMAIN_COM-VRSN
Registrar WHOIS Server: whois.squarespace.domains
Registrar URL: http://domains2.squarespace.com
Updated Date: 2024-09-22T20:29:27Z
Creation Date: 2021-10-07T17:40:32Z
Registry Expiry Date: 2025-10-07T17:40:32Z
Registrar: Squarespace Domains II LLC
Registrar IANA ID: 895
Registrar Abuse Contact Email: [email protected]
Registrar Abuse Contact Phone: +1.6466935324
Domain Status: clientDeleteProhibited https://icann.org/epp#clientDeleteProhibited
Domain Status: clientTransferProhibited https://icann.org/epp#clientTransferProhibited
Name Server: BJORN.NS.CLOUDFLARE.COM
Name Server: KATE.NS.CLOUDFLARE.COM
DNSSEC: unsigned
URL of the ICANN Whois Inaccuracy Complaint Form: https://www.icann.org/wicf/
>>> Last update of whois database: 2025-04-30T19:49:36Z <<<
For more information on Whois status codes, please visit https://icann.org/epp
NOTICE: The expiration date displayed in this record is the date the
TERMS OF USE: You are not authorized to access or query our Whois
by the following terms of use: You agree that you may use this Data only
to: (1) allow, enable, or otherwise support the transmission of mass