COMP100: Lecture Three

—
COMP100: Lecture Three

1/16
 The story so far ...

Ġ An algorithm is a well-defined, step-by-step procedure to solve a

problem or achieve a specific goal. It’s a concept in mathematics
and computer science that specifies a series of actions to be
executed, typically including conditions, loops, and termination
rules.
—
COMP100: Lecture Three

2/16
 The story so far ...

Ġ An algorithm is a well-defined, step-by-step procedure to solve a

problem or achieve a specific goal. It’s a concept in mathematics
and computer science that specifies a series of actions to be
executed, typically including conditions, loops, and termination
rules.
—
COMP100: Lecture Three

2/16
 The story so far ...

Ġ An algorithm is a well-defined, step-by-step procedure to solve a

problem or achieve a specific goal. It’s a concept in mathematics
and computer science that specifies a series of actions to be
executed, typically including conditions, loops, and termination
rules.
Ġ A program is an implementation of one or more algorithms in a
specific programming language. It’s a set of instructions written
to perform a specific task on a computer.
—
COMP100: Lecture Three

2/16
 The story so far ...

Ġ An algorithm is a well-defined, step-by-step procedure to solve a

problem or achieve a specific goal. It’s a concept in mathematics
and computer science that specifies a series of actions to be
executed, typically including conditions, loops, and termination
rules.
Ġ A program is an implementation of one or more algorithms in a
specific programming language. It’s a set of instructions written
to perform a specific task on a computer.
—
COMP100: Lecture Three

2/16
 The story so far ...

Ġ An algorithm is a well-defined, step-by-step procedure to solve a

problem or achieve a specific goal. It’s a concept in mathematics
and computer science that specifies a series of actions to be
executed, typically including conditions, loops, and termination
rules.
Ġ A program is an implementation of one or more algorithms in a
specific programming language. It’s a set of instructions written
to perform a specific task on a computer.
—

Ġ The key difference is that an algorithm represents a concept or

COMP100: Lecture Three

general procedure to solve a problem, irrespective of language or

platform, while a program is a practical realization or
implementation of an algorithm(s) in a specific language that
may be executed automatically.

2/16
 Key takeaways: What is an Algorithm?

Ġ Algorithms are processes

—
COMP100: Lecture Three

3/16
 Key takeaways: What is an Algorithm?

Ġ Algorithms are processes

Ġ Algorithms are executed
—
COMP100: Lecture Three

3/16
 Key takeaways: What is an Algorithm?

Ġ Algorithms are processes

Ġ Algorithms are executed
Ġ Algorithms are built from simple operations
—
COMP100: Lecture Three

3/16
 Key takeaways: What is an Algorithm?

Ġ Algorithms are processes

Ġ Algorithms are executed
Ġ Algorithms are built from simple operations
Ġ Algorithms are finite and unambiguous
—
COMP100: Lecture Three

3/16
 High Level Languages

Ġ More convenient for humans to express algorithms:

—
COMP100: Lecture Three

4/16
 High Level Languages

Ġ More convenient for humans to express algorithms:

Ġ Statements in a high-level language needs to be translated into
machine code.
—
COMP100: Lecture Three

4/16
 High Level Languages

Ġ More convenient for humans to express algorithms:

Ġ Statements in a high-level language needs to be translated into
machine code.
Ġ Translators (Compilers and Interpreters): are programs that take
programs as input and produce translated programs as output.
—
COMP100: Lecture Three

4/16
 Programming is ...?

Ġ Design/Devise an algorithm
—
COMP100: Lecture Three

5/16
 Programming is ...?

Ġ Design/Devise an algorithm
Ġ Write it in a Programming Language
—
COMP100: Lecture Three

5/16
 Programming is ...?

Ġ Design/Devise an algorithm
Ġ Write it in a Programming Language
Ġ Run
—
COMP100: Lecture Three

5/16
 Programming is ...?

Ġ Design/Devise an algorithm
Ġ Write it in a Programming Language
Ġ Run
Ġ Test and debug
—
COMP100: Lecture Three

5/16
 Programming is ...?

Ġ Design/Devise an algorithm
Ġ Write it in a Programming Language
Ġ Run
Ġ Test and debug
—

Ġ Profit
COMP100: Lecture Three

5/16
 This Lecture ...

What are the building blocks of Algorithms?

—
COMP100: Lecture Three

6/16
 This Lecture ...

What are the building blocks of Algorithms?

1 A few algorithms:
—
COMP100: Lecture Three

6/16
 This Lecture ...

What are the building blocks of Algorithms?

1 A few algorithms:
a. Calculate the day of the week from a day,month,year.
—
COMP100: Lecture Three

6/16
 This Lecture ...

What are the building blocks of Algorithms?

1 A few algorithms:
a. Calculate the day of the week from a day,month,year.
b. Tell if a given year is a leap year
—
COMP100: Lecture Three

6/16
 This Lecture ...

What are the building blocks of Algorithms?

1 A few algorithms:
a. Calculate the day of the week from a day,month,year.
b. Tell if a given year is a leap year
Building Blocks of algorithm
—

2
COMP100: Lecture Three

6/16
 How do we tell if a year is a leap year?

Every year that is exactly divisible by four is a leap year, except for
years that are exactly divisible by 100, but these centurial years are
leap years if they are exactly divisible by 400. For example, the years
1700, 1800, and 1900 are not leap years, but the years 1600 and 2000
are
—
COMP100: Lecture Three

7/16
 Leap Year

A leap year is any year that is

Ġ exactly divisible by 4,
—
COMP100: Lecture Three

8/16
 Leap Year

A leap year is any year that is

Ġ exactly divisible by 4,
Ġ except for years that are exactly divisible by 100
—
COMP100: Lecture Three

8/16
 Leap Year

A leap year is any year that is

Ġ exactly divisible by 4,
Ġ except for years that are exactly divisible by 100
Ĝ which must be divisible by 400
—
COMP100: Lecture Three

8/16
 Leap Year

A leap year is any year that is

Ġ exactly divisible by 4,
Ġ except for years that are exactly divisible by 100
Ĝ which must be divisible by 400
Ġ This means that the year 2000 was a leap year, although 1900
—

was not.
COMP100: Lecture Three

8/16
 Leap Year Algorithm

Algorithm is_leap_year:
year ← input year

if year mod 4 != 0 then,

answer ← False
else if year mod 100 != 0 then,
answer ← True
—

else if year mod 400 != 0 then,

answer ← False
COMP100: Lecture Three

else
answer ← True

9/16
 Zeller’s Congruence

What day of the week is a certain date?

—
COMP100: Lecture Three

10/16
 Zeller’s Congruence

What day of the week is a certain date?

Ġ INPUT: day, month, year

—
COMP100: Lecture Three

10/16
 Zeller’s Congruence

What day of the week is a certain date?

Ġ INPUT: day, month, year

Ġ OUTPUT: day of the week
—
COMP100: Lecture Three

10/16
 DAY OF WEEK Algorithm
Algorithm: Zellers_Congruence:

month ← input month

day ← input day of month
year ← input year

if month < 3 then:

month ← month + 12
year ← year − 1
—

h ← (day
COMP100: Lecture Three

+ ((13 ∗ (month + 1)) div 5)

+ year
+ (year div 4)
− (year div 100)
+ (year div 400)) mod 7

output day 11/16

 Zeller’s Congruence
—
COMP100: Lecture Three

12/16
 Zeller’s Congruence

Algorithm: Zellers_Congruence:

month ← input month

day ← input day of month
year ← input year

if month < 3 then:

month ← month + 12
year ← year − 1

h ← (day
+ ((13 ∗ (month + 1)) div 5)
—

+ year
+ (year div 4)
− (year div 100)
COMP100: Lecture Three

+ (year div 400)) mod 7

output day
0 − 6 where 0 = Saturday, 1 = Sunday ...

12/16
 Zeller’s Congruence

Algorithm: Zellers_Congruence:

month ← input month

day ← input day of month
year ← input year

if month < 3 then:

month ← month + 12
year ← year − 1

h ← (day
+ ((13 ∗ (month + 1)) div 5)
—

+ year
+ (year div 4)
− (year div 100)
COMP100: Lecture Three

+ (year div 400)) mod 7

output day
0 − 6 where 0 = Saturday, 1 = Sunday ...

12/16
 Zeller’s Congruence

Ġ ’h’ is the day of the week (0 =

Algorithm: Zellers_Congruence: Saturday, 1 = Sunday, 2 =
Monday, ..., 6 = Friday).
month ← input month
day ← input day of month
year ← input year

if month < 3 then:

month ← month + 12
year ← year − 1

h ← (day
+ ((13 ∗ (month + 1)) div 5)
—

+ year
+ (year div 4)
− (year div 100)
COMP100: Lecture Three

+ (year div 400)) mod 7

output day
0 − 6 where 0 = Saturday, 1 = Sunday ...

12/16
 Zeller’s Congruence

Ġ ’h’ is the day of the week (0 =

Algorithm: Zellers_Congruence: Saturday, 1 = Sunday, 2 =
Monday, ..., 6 = Friday).
month ← input month
day ← input day of month Ġ The ’div’ operator performs an
year ← input year
integer division and ’mod’ gives the
if month < 3 then:
month ← month + 12
remainder of an integer division.
year ← year − 1

h ← (day
+ ((13 ∗ (month + 1)) div 5)
—

+ year
+ (year div 4)
− (year div 100)
COMP100: Lecture Three

+ (year div 400)) mod 7

output day
0 − 6 where 0 = Saturday, 1 = Sunday ...

12/16
 Zeller’s Congruence

Ġ ’h’ is the day of the week (0 =

Algorithm: Zellers_Congruence: Saturday, 1 = Sunday, 2 =
Monday, ..., 6 = Friday).
month ← input month
day ← input day of month Ġ The ’div’ operator performs an
year ← input year
integer division and ’mod’ gives the
if month < 3 then:
month ← month + 12
remainder of an integer division.
year ← year − 1
Ġ ’year’, ’month’ and ’day’ represent
h ← (day the year, month and day of the
+ ((13 ∗ (month + 1)) div 5)
date for which you want to find the
—

+ year
+ (year div 4) day of the week.
− (year div 100)
COMP100: Lecture Three

+ (year div 400)) mod 7

output day
0 − 6 where 0 = Saturday, 1 = Sunday ...

12/16
 Zeller’s Congruence

Ġ ’h’ is the day of the week (0 =

Algorithm: Zellers_Congruence: Saturday, 1 = Sunday, 2 =
Monday, ..., 6 = Friday).
month ← input month
day ← input day of month Ġ The ’div’ operator performs an
year ← input year
integer division and ’mod’ gives the
if month < 3 then:
month ← month + 12
remainder of an integer division.
year ← year − 1
Ġ ’year’, ’month’ and ’day’ represent
h ← (day the year, month and day of the
+ ((13 ∗ (month + 1)) div 5)
date for which you want to find the
—

+ year
+ (year div 4) day of the week.
− (year div 100)
COMP100: Lecture Three

+ (year div 400)) mod 7 Ġ ’month’ is 1 for March, 2 for April,

..., 12 for February. For January
output day
0 − 6 where 0 = Saturday, 1 = Sunday ... and February, you should use the
months 13 and 14 of the previous
year.

12/16
 Day of the Week: Python
day = int(input(”day−number?␣␣”))
month = int(input(”month−number?␣␣”))
year = int(input(”year␣number?␣”))

if month < 3:
month += 12
year −= 1

h = (day + ((13 ∗ (month + 1)) // 5)

+ year + (year // 4)
− (year // 100)
+ (year // 400)) % 7

# Return the day of the week (0−6)

match h:
case 0:
day = ”Saturday”
case 1:
—

day = ”Sunday”
case 2:
day = ”Monday”
COMP100: Lecture Three

case 3:
day = ”Tuesday”
case 4:
day = ”Wednesday”
case 5:
day = ”Thursday”
case 6:
day = ”Friday”
case _:
day = ”Invalid␣day␣number”

print(f”The␣day␣is:␣{day}”)
13/16
 Elements of Programming I

They all provide the following:

1 literals: to express the data that the algorithms manipulate.
Literals are things that stand for themselves, such as actual
numbers and characters. These are the actual values (numeric
and text values such as “42”, and “Hello!”.
—
COMP100: Lecture Three

14/16
 Elements of Programming I

They all provide the following:

1 literals: to express the data that the algorithms manipulate.
Literals are things that stand for themselves, such as actual
numbers and characters. These are the actual values (numeric
and text values such as “42”, and “Hello!”.
—
COMP100: Lecture Three

14/16
 Elements of Programming I

They all provide the following:

1 literals: to express the data that the algorithms manipulate.
Literals are things that stand for themselves, such as actual
numbers and characters. These are the actual values (numeric
and text values such as “42”, and “Hello!”.
2 variables: to refer to particular values. The language must
provide a way to create and assign variables. This provides a way
to name values.
—
COMP100: Lecture Three

14/16
 Elements of Programming I

They all provide the following:

1 literals: to express the data that the algorithms manipulate.
Literals are things that stand for themselves, such as actual
numbers and characters. These are the actual values (numeric
and text values such as “42”, and “Hello!”.
2 variables: to refer to particular values. The language must
provide a way to create and assign variables. This provides a way
to name values.
—
COMP100: Lecture Three

14/16
 Elements of Programming I

They all provide the following:

1 literals: to express the data that the algorithms manipulate.
Literals are things that stand for themselves, such as actual
numbers and characters. These are the actual values (numeric
and text values such as “42”, and “Hello!”.
2 variables: to refer to particular values. The language must
provide a way to create and assign variables. This provides a way
to name values.
—

3 arithmetic expressions: The language must provide

COMP100: Lecture Three

operators that are used together with literals and -variables to

form arithmetic expressions such as:
(v ∗ 0.5 ∗ (a / t )).

14/16
 Elements of Programming II

1 logic expressions: The language must provide comparison

operators that are used together with literals and variables to
form boolean expressions that evaluate to true or false .
Boolean expressions are used to test values and variables, for
example (x + y) >= 0.
—
COMP100: Lecture Three

15/16
 Elements of Programming II

1 logic expressions: The language must provide comparison

operators that are used together with literals and variables to
form boolean expressions that evaluate to true or false .
Boolean expressions are used to test values and variables, for
example (x + y) >= 0.
—
COMP100: Lecture Three

15/16
 Elements of Programming II

1 logic expressions: The language must provide comparison

operators that are used together with literals and variables to
form boolean expressions that evaluate to true or false .
Boolean expressions are used to test values and variables, for
example (x + y) >= 0.
2 input functions: to allow us to read input values from the
user.
—
COMP100: Lecture Three

15/16
 Elements of Programming II

1 logic expressions: The language must provide comparison

operators that are used together with literals and variables to
form boolean expressions that evaluate to true or false .
Boolean expressions are used to test values and variables, for
example (x + y) >= 0.
2 input functions: to allow us to read input values from the
user.
—
COMP100: Lecture Three

15/16
 Elements of Programming II

1 logic expressions: The language must provide comparison

operators that are used together with literals and variables to
form boolean expressions that evaluate to true or false .
Boolean expressions are used to test values and variables, for
example (x + y) >= 0.
2 input functions: to allow us to read input values from the
user.
—

3 output functions: to allow us to write results to the screen.

COMP100: Lecture Three

15/16
 Elements of Programming II

1 logic expressions: The language must provide comparison

operators that are used together with literals and variables to
form boolean expressions that evaluate to true or false .
Boolean expressions are used to test values and variables, for
example (x + y) >= 0.
2 input functions: to allow us to read input values from the
user.
—

3 output functions: to allow us to write results to the screen.

COMP100: Lecture Three

15/16
 Elements of Programming II

1 logic expressions: The language must provide comparison

operators that are used together with literals and variables to
form boolean expressions that evaluate to true or false .
Boolean expressions are used to test values and variables, for
example (x + y) >= 0.
2 input functions: to allow us to read input values from the
user.
—

3 output functions: to allow us to write results to the screen.

COMP100: Lecture Three

4 control structures: that allow us to control the execution

of the algorithm.

15/16
 What is a Programming Language?

1 Syntax: How to say things in the language. How to make correct

statements in the language.
—
COMP100: Lecture Three

16/16
 What is a Programming Language?

1 Syntax: How to say things in the language. How to make correct

statements in the language.
2 Syntax: Rules of Grammar.
—
COMP100: Lecture Three

16/16
 What is a Programming Language?

1 Syntax: How to say things in the language. How to make correct

statements in the language.
2 Syntax: Rules of Grammar.
—
COMP100: Lecture Three

16/16
 What is a Programming Language?

1 Syntax: How to say things in the language. How to make correct

statements in the language.
2 Syntax: Rules of Grammar.
3 Semantics: The meaning of the statements.
—
COMP100: Lecture Three

16/16
 What is a Programming Language?

1 Syntax: How to say things in the language. How to make correct

statements in the language.
2 Syntax: Rules of Grammar.
3 Semantics: The meaning of the statements.
4 Semantics: Meaning is what happens when the statement is
—

executed.
COMP100: Lecture Three

16/16
 What is a Programming Language?

1 Syntax: How to say things in the language. How to make correct

statements in the language.
2 Syntax: Rules of Grammar.
3 Semantics: The meaning of the statements.
4 Semantics: Meaning is what happens when the statement is
—

executed.
Semantics: Usually it is how memory changes.
COMP100: Lecture Three

16/16