Introduction to Algorithms
> Click or hit Control-Enter to run Example.main above
Algorithms
Algorithm: a set of steps taken to achieve some desired result.
This is About the Future
Our goal is to help you succeed in later courses, while also taking care of you this semester.
Our Desired Result
You learn computer science.
Our (Modified) Algorithm
When possible we’re going to continue doing what we do.
However, there are a few places where we rely on your proximity on campus. So we’ll need to make a couple of adjustments to:
-
Quizzes
-
Office Hours
-
Participation
Course Meetings
-
Class: will be live streamed on Monday and Friday at 10AM CST. On Wednesday you will have a video lecture to watch asynchronously.
-
Lab: the lab activity will be available for completion all day on Tuesdays, our usual lab day.
-
Office Hours: we are working on several ways to hold virtual office hours, which we will run during normal office hour time slots and potentially at other times.
Assessments
-
Quizzes and Midterms: will be held online on Wednesday from 10–10:50AM CST.
-
Participation: lab participation will remain frozen where it stands today. How to handle lecture participation is still being discussed.
-
MP, Homework, Final Project: these will continue as planned. Obviously there will not be a final project fair, but final project grading will (somewhat) normally.
Exceptions and Special Cases
If you are significantly time-gapped we will make accommodations for quizzes and lecture participation.
We’ll have a form to fill out later today.
Grading
If Pass-Fail grading is an option I will use it.
(It looks like it will be.)
Cheating
There is really not much we can do to stop you from cheating on the quizzes.
But keep in mind—at some point things will be normal again, and you will be in some other course or some other place and need to know this stuff.
Particularly if we go pass-fail, please just do your own work. Let’s all trust each other and get through this together.
Questions?
Algorithms
Algorithm: a process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer.
As computer scientists, we implement algorithms by having computers:
-
Perform simple calculations
-
Store the results
-
Make simple decisions
-
Do things over and over again as fast as possible
Data Structures
Data structure: a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.
As Java programmers we implement more complicated data structures using a mix of:
-
Primitive types and objects to store and organize data values
-
Existing data structures like arrays
-
References to reflect relationships among objects
Algorithms and Data Structures
Algorithms and data structures are highly complementary:
-
We will implement algorithms that utilize specific features of data structures
-
We will implement data structures to support specific algorithms
-
We will use our existing imperative and object-oriented ideas along the way
-
And we’ll introduce a few more important ideas along the way
Example: Greatest Common Denominator
In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers.
But If We’re In A Hurry…
What’s a simpler approach?
Brute Force Solution
Brute force solution: a very general problem-solving technique that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem’s statement.
-
Computers today are very, very fast
-
So try the simple thing first
-
If it’s too slow, try something a bit more sophisticated
> Click or hit Control-Enter to run Example.main above
Announcements
-
Discussions of how to make the best of this semester are continuing. Please participate.
-
We have a anonymous feedback form to the course website. Use it to give us feedback!