Lecture 1: Introduction

CSC 320: Foundations of Computer Science

Quinton Yong
quintonyong@ [Link]
Lectures and Tutorials
• Instructor: Quinton Yong
• Email: quintonyong@[Link] (please use your UVic email)
• Office: ECS 621

• Lectures:
• Synchronous, in-person delivery
• A01, A02: 11:30 am – 12:50 pm on M, Th (HHB 105)

• Office Hours (ECS 621):

• M, Th: 1:00 pm – 2:30 pm
• By appointment
• Extra hours for assignments / exams

• Course Website:
• Brightspace: [Link]
• Course outline: [Link]
PowerPoint Passcode Game

Try and guess the 3-digit passcode:

• The game is “implemented” by having each button link to a different slide

• How many slides are needed?

PowerPoint Passcode Game
• Suppose we added an enter button to enter a passcode

• We want the passcode 0’s followed by an equal number of 1’s (e.g 000111)

• How can we create a DFA which accepts these passcodes?

Pushdown Automata
• Increase the computational power of a DFA by adding stack memory

• Pushdown Automata: Can push / pop symbols and read the top symbol

000111

• Using a pushdown automata, we can accept passcodes of form 0’s followed by

an equal number of 1’s
Pushdown Automata
• Pushdown automata for 0’s followed by an equal number of 1’s passcode
(we will learn this notation later in the course):

𝟎, 𝝐 → 𝟎 𝟏, 𝟎 → 𝝐

𝝐, 𝝐 → $ 𝝐, 𝝐 → 𝝐 𝝐, $ → 𝝐

• With pushdown automata, we can determine if a text file contains proper

syntax for code in a programming language

• There are still limits to what is computable

Turing Machines
• We give a state machine unlimited memory and unlimited read / write access

• Turing machine: infinite tape and can read / write symbols anywhere

• A Turing machine is an abstract computational model for a classical computer

• The computational limits of a Turing machine are the limits of classical computers

1 0 1 1 0 …

• There are problems that are unsolvable / undecidable on a classical computer

• The Halting Problem
• The Bugged Code Problem
P v.s NP
For problems which are solvable on a Turing machine:
• There are problems which can be solved efficiently
• There are also problems which we don’t know if there exist efficient solutions

P: Problems which have polynomial time solutions (multiplication, sorting, etc.)

NP: Problems which, given a potential solution, can be verified in polynomial time

NP

P
P v.s NP
• The P v.s NP problem: “Are the problems in P the same as the problems in NP?”
• In other words, if the solution to a problem is easy to check for correctness, must
the problem be easy to solve?

P = NP ?
CSC 320 Timeline

Regex’s PDA’s TM’s Reductions

DFA’s and Pumping CFG’s Undecidability NP Completeness

NFA’s Lemma
Textbook (Required)

• Introduction to the Theory of Computation, 3th Edition

Michael Sipster
Lectures
• All slides presented in class will be posted

• Lectures not recorded live

• A video covering lecture content will be posted later on
• Videos are meant for review if you miss a lecture and to supplement studying,
but not intended to replace attendance to lectures

• Please ask questions if you have them at any point

• If something is confusing, it is my fault for not explaining it clearly and I will
gladly explain again
• More than likely, other students have the exact same question

Tutorials
• Weekly tutorials going over practice questions which are similar to
assignment / midterm questions
Evaluation

• Assignments (30%)
• There will be 6 assignments worth 5% each
• You will be given around 2 weeks to complete them
• There are 2 assignments before each midterm for practice
• Assignments will be given and submitted through BrightSpace

• Midterms (40%)
• Midterm 1 (20%): in class on February 8th
• Midterm 2 (20%): in class on March 14th
• You are allowed one single sided handwritten cheatsheet of A4 (8.5’’ x 11’’) paper

• Final (30%)
• To be scheduled by the University
• You must pass the final exam to pass the course
Policy on Collaboration / Online Resources

Assignments:
• Students are encouraged to discuss assignments together
• All solutions must be individually written and no sharing of any solutions
• (Don’t look at any other student’s paper)
• You may use online resources to help you on your assignments, but your
submission must clearly display that you understand the solution

ChatGPT:
• You may use ChatGPT to help you on your assignments
• WARNING: ChatGPT is pretty bad at CSC320…
Countable and Uncountable
A set is countable if it is finite or countably infinite
• elements of a countable set can be counted one at a time without missing any
• every element is associated with a unique natural number

There exists a bijection between any countably infinite set and the set of natural
numbers ℕ

1
2
3
4
5
…

A set that is neither finite nor countably infinite is uncountable

Countable and Uncountable

Is the set of integers ℤ countable?

… -5 -4 -3 -2 -1 0 1 2 3 4 5 …

We can enumerate the elements of ℤ as follows:

0 1 -1 2 -2 3 -3 4 -4 5 -5 …
1 2 -3 4 - 5 6 …

The set of integers ℤ is countably infinite

Countable and Uncountable
Is the set of positive nonzero rational numbers ℚ+ \{0} countable?
1 1 1 1 1 1 1
1 2 3 4 5 6 7
2 2 2 2 2 2 2
• This method of counting lets us enumerate all
1 2 3 4 5 6 7 rational numbers
3 3 3 3 3 3 3 • No missing numbers or getting stuck in infinity
1 2 3 4 5 6 7
…
4 4 4 4 4 4 1
• Note: Counting row by row or column by
1 2 3 4 5 6 7 column would never reach all the numbers
5 5 5 5 5 5 5
1 2 3 4 5 6 7
6 6 6 6 6 6 6
1 2 3 4 5 6 7
…
ℝ is uncountable (Cantor’s Diagonalization)
Proof by contradiction: Assume that the real numbers ℝ is countable.

• If ℝ is countable, then we should be able to enumerate the real numbers just

between 0 and 1.
• Let the enumeration (𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 , …) be written as follows:
𝒙𝟏 = 0. 𝑑11 𝑑12 𝑑13 𝑑14 …
𝒙𝟐 = 0. 𝑑21 𝑑22 𝑑23 𝑑24 …
𝒙𝟑 = 0. 𝑑31 𝑑32 𝑑33 𝑑34 …
𝒙𝟒 = 0. 𝑑41 𝑑42 𝑑43 𝑑44 …

…
• 𝒙𝒏 = 0. 𝑑𝑛1 𝑑𝑛2 𝑑𝑛3 𝑑𝑛4 … is the 𝒏𝒕𝒉 real number in the enumeration

• 𝒙𝒏 has decimal digits 0. 𝑑𝑛1 𝑑𝑛2 𝑑𝑛3 𝑑𝑛4 (since we are enumerating real numbers
between 0 and 1)
ℝ is uncountable (Cantor’s Diagonalization)
• Consider the number 𝒄 = 0. 𝑐1 𝑐2 𝑐3 𝑐4 … where 𝑐𝑖 ≠ 𝑑𝑖𝑖 for each 𝑖

𝒙𝟏 = 0. 𝑑11 𝑑12 𝑑13 𝑑14 … 𝒄 ≠ 𝒙𝟏 since the 1𝑠𝑡 decimal digit is different (𝑐1 ≠ 𝑑11)
𝒙𝟐 = 0. 𝑑21 𝑑22 𝑑23 𝑑24 … 𝒄 ≠ 𝒙𝟐 since the 2𝑛𝑑 decimal digit is different (𝑐2 ≠ 𝑑22 )
𝒙𝟑 = 0. 𝑑31 𝑑32 𝑑33 𝑑34 … 𝒄 ≠ 𝒙𝟑 since the 3𝑟𝑑 decimal digit is different (𝑐3 ≠ 𝑑33 )
𝒙𝟒 = 0. 𝑑41 𝑑42 𝑑43 𝑑44 … 𝒄 ≠ 𝒙𝟒 since the 4𝑡ℎ decimal digit is different (𝑐4 ≠ 𝑑44 )
…

𝒙𝒏 = 0. 𝑑𝑛1 𝑑𝑛2 𝑑𝑛3 𝑑𝑛4 … 𝒄 ≠ 𝒙𝒏 since the 𝑛𝑡ℎ decimal digit is different (𝑐𝑛 ≠ 𝑑𝑛𝑛 )
…

• Since 𝒄 is a number between 0 and 1, it should be enumerated in this list

• However, since it differs from every element, it cannot be in this list
Clarification on 𝒄
• Consider the number 𝒄 = 0. 𝑐1 𝑐2 𝑐3 𝑐4 … where 𝑐𝑖 ≠ 𝑑𝑖𝑖 for each 𝑖
• For example, suppose the numbers (𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 , …) are as follows
𝒙𝟏 = 0. 𝟒031…
𝒙𝟐 = 0.1𝟖93…
𝒙𝟑 = 0.53𝟔7…

…
• We define 𝒄 = 0. 𝑐1 𝑐2 𝑐3 𝑐4 such that the digit 𝒄𝒊 is something different than the 𝒊𝒕𝒉
digit of 𝒙𝒊

• In the example enumeration above:

• 𝒄𝟏 can be any number other than 4
• 𝒄𝟐 can be any number other than 8
• 𝒄𝟑 can be any number other than 6
• So, 𝒄 could be something like 0.597…
Clarification on 𝒄
• You may be wondering, if we enumerate the real numbers between 0 and 1 like
𝒙𝟏 = 0.000 … 00
𝒙𝟐 = 0.000 … 01
𝒙𝟑 = 0.000 … 02

…
then 𝒄 must be in the list somewhere.

• Consider if 𝒄 appears in the list at position 𝒌, that is 𝒙𝒌 = 𝒄

• However, 𝒄 is defined such that digit 𝒄𝒌 is different than the 𝒌𝒕𝒉 decimal digit of 𝒙𝒌

• Thus, 𝒄 can’t possibly be in the list anywhere

ℝ is uncountable (Cantor’s Diagonalization)

• The enumerated list 𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 , … does not contain all real numbers between
0 and 1 since it cannot contain 𝒄

• So, we cannot enumerate all the elements in this subset of ℝ (real numbers
between 0 and 1)

• This is a contradiction since we assumed that ℝ is countable

• Therefore, ℝ is uncountable