Module 00: Welcome to Models of Computing

Introduction

CPSC 121 explores formal modeling systems that help us understand and explore the capabilities of computers and, more generally, any problem solving process. Our exploration of these systems will be guided by the desire to answer the following questions:

1. How can we convince ourselves that an algorithm performs as expected? When is one algorithm better than another?

2. How does the computer decide if the characters of your program represent a name, a number, or something else? How do computers know when we have mismatched quotations or parentheses?

3. As of 2021, processors have 60 billion transistors. How do these transistors work together to execute a user-defined program?

4. Modern computation is founded on the happy coincidence that silicon and other semi-conductors and metals in special configurations execute a logical operation. How do we get from little logical operations to high-level programs like those you write in CPSC 110?

5. What can computational systems do, and not do? The capabilities of computers, combinational circuits, finite state machines, and other formal systems (the human brain?) are constrained by the way they are defined. What kinds of problems can they solve, what kinds of problems are they incapable of solving, and how can we provably delineate those capabilities? What are the strengths of our formal models of real systems, and where do those models break down?

CPSC 121 will take you on a journey to discover how 0s and 1s come together to form a circuit and how circuits can then unite to form a simplified version of a full computer. You will learn how to:

• Construct and recognize valid proofs in a variety of forms
• Express yourself logically and precisely in the manner of a computer
• Demonstrate your models by using a magic box to create working circuits

Expected Prior Mathematical Knowledge

During this course, we will not be programming, so no prior programming language knowledge is expected. When needed, we will try our best to use examples that reference Racket and Python but we will not be programming in this course.

Some math knowledge will be expected. In this section, we will review some mathematical concepts that will be used throughout the course. If these concepts are unfamiliar to you, please take the time to review them now.

Divisibility of Integers

The division m/n, also described as m ÷ n is the inverse of multiplication. When considering only integers, we have that by dividing m by n we have m=nq+r where q is called the quotient and r is called the remainder.

A number n is said to divide a number m if the remainder of the division m/n is 0. In that case, we can also say that m is divisible by n or that n is a factor of m.

Some divisibility properties:

• 0/n = 0
• No number can be divided by 0.
• An integer is even if it is divisible by 2.
• An integer is odd if it is not divisible by 2.
• A positive integer n > 1 is prime if it is only divisible by 1 and itself.
• A positive integer n > 1 is composite if it has at least one factor different than 1 and itself.

Note: the sum and product of integers always result in an integer, but the division of integers does not necessarily result in an integer.

Exponentiation

The exponentiation aⁿ is equal to the multiplication of a repeated n times. For the expression aⁿ, a is called the base, while n is the exponent (also called the power).

Some exponentiation properties:

• a⁰ = 1
• a¹ = a
• a^1/2 = √a
• a^n+m = aⁿ · a^m
• (aⁿ)^m = a^nm
• (a · b)ⁿ = aⁿ · bⁿ
• a^-n = 1/aⁿ
• (a + b)² = a² + 2ab + b²
• (a - b)² = a² - 2ab + b²
• (a + b)(a - b) = a² - b²

Logarithm

The logarithm is the inverse function to exponentiation. If aⁿ = c, then log_a c = n.

Some logarithm properties:

• log_a 1 = 0
• log_a a = 1
• log_a(xy) = log_a x + log_a y
• log_a(x/y) = log_a x - log_a y
• log_ax^b = b log_a x
• log_ax = log_kx ÷ log_ka
• a^log_ax = x

Inequality

An inequality is a relation that makes a comparison between two mathematical expressions:

• a < b: means a is (strictly) less than b.
• a > b: means a is (strictly) greater than b.
• a ≤ b: means a is less than or equal to b.
• a ≥ b: means a is greater than or equal to b.

Some inequality properties for integers different than zero:

• a ≤ b and b ≥ a are equivalent
• If a ≤ b and b ≤ c, then a ≤ c
• If a ≤ b, then a+c ≤ b+c and a−c ≤ b−c
• If a ≤ b, then −a ≥ −b
• If a ≤ b, then 1/a ≥ 1/b
• If a ≤ b and c ≥ 0, then a ≤ b+c
• If a ≥ b and c ≥ 0, then a ≥ b−c

• a < b and b > a are equivalent
• If a < b and b < c, then a < c
• If a < b, then a+c < b+c and a−c < b−c
• If a < b, then −a > −b
• If a < b, then 1/a > 1/b
• If a < b and c ≥ 0, then a < b+c
• If a > b and c ≥ 0, then a > b−c

Floor and ceiling functions

• ⌊x⌋ means the floor of x, or greatest integer less than or equal to x, e.g., ⌊2.5⌋ = 2
• ⌈x⌉ means the ceiling of x or the smallest integer greater than or equal to x, e.g. ⌈2.5⌉=3
• For any integer x: ⌊x⌋ = ⌈x⌉ = x

Tips for Success

Do a lot of practice. Try to ask as many questions as you can and avoid looking at the solutions until you come up with a solution yourself. Reading the solution gives you a false sense of security, as it is easy to convince yourself that you could also come up with the answer. The most important part is the experience you gain when trying to think about and work through the question, as this is what helps you learn.

Do not focus on grades! If you did not do as well as you expected in an assignment or exam, don't hold on to that. We all have bad days and there are a lot of components in this course that will help compensate for a bad grade. Focusing on a single numerical value will only get in the way of improvement.

Be extremely careful with outside information, specially generative AI tools, such as ChatGPT. Sharing and receiving solutions from others is considered academic misconduct. This includes information found on Google, and using ChatGPT. When in doubt, ask!

Using PrairieLearn

PrairieLearn can be an excellent tool for studying and preparing for exams, but it's important to use it effectively. Each module contains several questions, and it's beneficial to attempt all of them. Students often focus more on the first questions and neglect the later ones, but the order of the questions does not indicate their importance.

Most importantly, you have five attempts for each question to arrive at the correct answer. Do not simply submit the same answer five times to reveal the correct one; this approach will not aid your learning. Instead, think carefully about why your answer might be incorrect. Review the feedback provided for each question, ask questions on Piazza, attend office hours, or discuss with your peers. Simply reading the correct answer might give you the illusion of learning, but it doesn't lead to true understanding. In this course, we assess not only your knowledge but also your ability to critically analyze and correct your mistakes; a crucial skill in computer science and life in general.

Lastly, avoid focusing solely on how to answer a specific type of question or how to answer them quickly. While these are common concerns on Piazza, they often aren't the most helpful. All questions should be approached with a solid understanding of the course material. For example, you shouldn't always rely on the same answering method. You can practice using questions with dropdown options, and we can also ask similar questions in different formats. When practicing, you should focus solely on the content. You will improve your speed and accuracy through practice and applying your knowledge. Remember, being efficient with one particular question in the practice assessments doesn't mean you're fully prepared for the exam if you're relying on shortcuts rather than genuine understanding.

Finally, studying hard does not mean studying smart. Your approach to studying is just as important as the amount of time you spend on course material.

Golden Tips

Read the rules and follow them! We have around 500 students in this course, and it is not possible to personalize the course based on your specific needs and requests.

The main goal of the teaching staff is to be fair to all students; therefore, we have to be strict with rules and deadlines. If you have a long-term issue that impacts your ability to submit work on time, please talk to your faculty advising office. There is a limit to what instructors can do to help you.

Be respectful to all members of our community at all times.

Piazza is a great place to have your questions answered quickly, but that does not mean it is the proper place for all communication with the staff. You should not use it as a place to rant or as an office hour replacement. Course-specific feedback and concerns can be directed to the course instructors.

Questions that require a longer or more detailed explanation should be directed to office hours. Be aware of what you are saying on Piazza and set the visibility (public or private) accordingly. Are you giving away a solution with your question? Ask privately on Piazza. Are you unhappy about something and want to reach out to the instructors? Send an email.

Take the time to search Piazza and Canvas before asking a question. The teaching team spends a significant amount of time writing announcements and organizing Canvas to ensure that information is easily accessible. Please use this.

What to do Next

Now, you are ready to start your CPSC 121 adventure!

Read the syllabus and check the calendar"both found on Canvas and familiarize yourself with the information found there. Notice that reading those pages is mandatory and part of your coursework.

Remember to also enroll on our Piazza page, where you will be able to ask questions and be up-to-date with all the course information posted during the term.

See you soon in lecture! :)