Administrivia and how to describe an algorithm.
Hi, I'm Emily, and welcome to CS 4349, Advanced Algorithm Design and Analysis.Today, we’re going to discuss what you should expect from a course on algorithm design and analysis, and what I’ll be expecting from you.In short, we’ll be working on the design and analysis of algorithms that are provably correct for every input and giving running time bounds which also hold for every input.
Administrivia
But let’s start with some administrative stuff.This is a section of CS 4349. All sections have essentially the same goals of understanding and designing algorithms of various types.Being a 4xxx level course, there's some base knowledge expected from prerequesite courses.I expect you to understand basic matters on discrete structures, proofs, asymptotic notation, and so on, and to have at least been exposed to some basic commonly used algorithms. However, I’ll still go over many of these basics again with an emphasis on their use in algorithm design.Please don’t be surprised when we revisit some CS topics you may have seen a while ago, including sorting.Sometimes seemingly basic things make for great examples of complicated topics.You may also be surprised to see some math you'd long since forgotten about such as series (from calculus) and log/exponent rules.
Lectures and office hours
We'll be spending a lot of time together in a single room.I highly encourage you to wear a mask while you are here, and please be conscientious of your classmates that need to wear a mask or need others to wear masks for the health of themselves or others.If you're able to, please make sure you're fully vaccinated.That said, I am not allowed to require these things.
All lectures will be in-person, but I will record them as best I can and post them on MS Streams. Feel free to watch those videos as a review or as your primary source if you have to miss a lecture. You do not need to offer me a warning or explanation if you need to miss lectures. That said, students who attend in person will be able to ask questions instead of hoping I discuss whatever they're wondering about.I'll hold office hours twice a week:
- Tuesdays in person in my office ECSS 4.224 from 4:00pm to 5:00pm.These office hours will be shared with CS 3345.HON.
- Wednesdays over MS Teams from 3:00pm–4:00pm.These office hours will be exclusive to this class/section.
We can also agree to different arrangements ahead of time.I've not seen it happen, but I encourage you to use MS Teams as a discussion board.There’s probably tools in eLearning for this sort of thing too, but that system is such a pain to use that I’d rather avoid it as much as we can.
Website
There’s a rather long page on course policies and suggested readings on the course webpage and in the syllabus at https://personal.utdallas.edu/~emily.fox/courses/cs4349.004.24f/. You may even be reading that page right now! I’ll go over a few key points.
I'll use the website to do pretty much anything a static site can do. About the only thing I won't use it for is posting grades or accepting homework.eLearning will be the one place to submit homework and check your grades.I also understand some of you may enjoy having one location for all things related to your classes, so I'll post announcements on eLearning as well.
I'm closely following some lecture notes that I've made available to you as well on the course website.Along with listening to me babble on, your responsibilities include reading these lectures notes.I also highly highly highly encourage you to read from at least one of the texts I suggest.All sections of 6363 share a “required” textbook by Cormen and others called “Introduction to Algorithms”.This book is usually called CLRS.The "suggested" text for this class is a freely available textbook by Jeff Erickson that he simply calls "Algorithms".
CLRS is an excellent resource used by many, and it contains far more material than I might possibly be able to cover during the semester.However, I’m personally more fond of Erickson, because it strikes a better balance between rigor and readability than CLRS, and it puts more emphasis on what you need to know and do to design algorithms using different techniques.I’ll generally follow Erickson when designing lectures, although I may pull examples or proofs from CLRS.I promise I’ll always write out each homework problem I want to assign instead of pointing directly to either book’s problem sets.I'm not a fan of making students pay money for books when equally good free alternatives exist.
Grades
Grades will be determined by weighing homework 20%, two midterms at 25% each, and a cumulative final exam 30%.I’ll release a homework assignment about once a week and make it due one week later.We’ll probably do nine or ten assignments total.All the assignments are weighted equally, except I'll drop your lowest score.You get one bad week for "free" essentially.You may work in formal groups of up to three people if you’d like, but it is not a requirement to group up.Each group should turn in one copy of the homework on eLearning (although the TA will probably figure things out if you submit two).I’ll give everybody in the group the same grade.If you need extra time past the deadline, you must ask for an extension.I will automatically approve all extensions of up to 24 hours, but you still need to ask.I might give you longer if there are extenuating circ*mstances.
DO YOUR HOMEWORK.Designing algorithms and proving things about them is hard.Like really hard.I can show you what others have done before.I can show the paradigms others have used to make algorithm design easier.But sadly, I cannot truly “teach” you algorithm design by just talking at you.In other words, there is no algorithm for designing algorithms.The only way to truly learn the art or even to understand the examples I provide is to practice practice practice, and that’s what the homework is for.
Grades will be assigned based on how well you do relative to the class average and the difficulty of assignments and exams.There is no predetermined curve, and in principle, everybody can get top marks regardless of the class average if everybody does well enough.Talk to me if you’re concerned about your grades.
You’ll turn in homework as individuals or small groups, but I also don't want you to be afraid of collaboration.And going further, finding a solution to a problem somehow is always better than giving up without finding a solution at all.So, if you need outside help, you may seek it.However, you must cite all outside sources, including other students you work with, and write solutions in your own words.Otherwise, I consider it an act of plagiarism.And if you use a website, please actually give me the full address and not just the domain.
Finally, I’m going to go over it today, but be sure to read up on the website what I mean by “describe an algorithm”.This includes justifying correctness through a short proof sketch and analyzing running time.You’ll be expected to go through the whole design process in several homework problems.I'll let you know more precisely what I need on exam problems.
OK, so let’s actually learn something about algorithms now.
Algorithms
An algorithm is an explicit, precise, unambiguous, mechanically-executable sequence of elementary instructions.Erickson gives a pretty good summary on where the term came from.One interesting thing to note is that algorithm at one point referred to general pencil-and-paper methods for numerical calculations. And the people who did these calculations were called computators or more simply, computers.Of course, now we have digital computers to run our algorithms for us, but the principal remains the same.The algorithms we design in this class should be simple enough to be read and executed by humans, even if you have no plans to do so yourself.
A Simple Example
Here’s an algorithm for multiplying two numbers $x$ and $y$ together which probably resembles the one you learned in grammar school.Granted, the operations may be happening in a different order from what you learned. This family of multiplication algorithms is called lattice multiplication.The input is two arrays of decimal digits $X[0 .. m - 1]$ and $Y[0 .. n - 1]$ representing the natural numbers:
$$x = \sum_{i=0}^{m-1} X[i] \cdot 10^i \text{ and } y = \sum_{j=0}^{n-1} Y[j] \cdot 10^j $$
Note that I’m explicitly telling you how I’m indexing the arrays. I usually start arrays on index $1$ (gasp).But that $10^i$ there makes it more convenient to start on index $0$.The output will be a single array $Z[0 .. m + n - 1]$ representing the product:
$$z = x \cdot y = \sum_{k=0}^{m+n-1} Z[k] \cdot 10^k $$
Here’s the pseudocode. All I am assuming is that you know how to add two numbers together and multiply two decimal digits together. The version of lattice multiplication I’m showing is actually due to Fibonacci. Yes, that Fibonacci. I am not expecting you to learn this particular algorithm. We won't discuss it's correctness or even its running time (today). This algorithm is only here as a nice example of pseudocode for doing some math.
The general rule is that if you can expect nearly any CS student to do something by hand without further explanation, it’s safe to write it as a single line of pseudocode.You can add any standard control-flow operations you're used to, and even calls into other procedures.We'll do a lot of calling into other procedures this semester.
Designing and Analyzing Algorithms
My main goal in this course is to teach you how to design and analyze your own algorithms for a variety of problems while also showing you some of the “classics”.They’ll serve as good examples and be directly useful in case you need to use or refer to them in the future.Of course, after designing and analyzing any algorithm, you still need to describe it to others, including me and the TA.And it turns out both skills complement each other nicely.When describing an algorithm, you generally need to specify four things:
- What: A precise specification of the problem that the algorithm solves.
- How: A precise description of the algorithm itself.
- Why: A proof that the algorithm solves the problem it is supposed to solve.
- How fast: An analysis of the running time of the algorithm.
For certain homework or exam problems, I may ask you to do only some of these things, but all four are necessary if all you know is what you’re trying to design an algorithm for.
Now, you may develop these concepts in any particular order.For example, you may start thinking about running time and realize a recursive solution is best.But then you need to tweak the specification so recursion is possible.That said, it’s usually easiest to write these four things separately, and usually in that order.
Like other kinds of writing, how you describe an algorithm depends on who your audience is.I must emphasize that your audience is not a computer for this class.Instead, I want to you aim at a competent but skeptical programmer who is not as experienced as you are.Think about yourself before you started this semester.This programer you’re writing for is a novice and will interpret the how of your algorithm exactly as written.They don’t want to solve anything for you or even do much high level thinking.So you’re forced to work through the finer details yourself and present them to the programmer.The programmer is also skeptical that you’re correct; you’ll need to develop robust arguments for correctness of your algorithm and its running time.
During lectures, I want to treat you all as skeptical novices as well, at least as much as time allows.Please hold me to this.If I talk about something you haven’t seen, press me for details.If I don’t explain why something is correct, press me for details. Feel free to point out mistakes or omissions when I’m proving things.Rarely, I’ll ask you to just trust me on something, but especially when I’m describing an algorithm you’ve not seen before, act as if I might be making things up or forgetting to tell you something.
Let’s go over each of these four things to specify in some more detail for the rest of today.Thursday, we'll review the most common way of analyzing algorithm run time, and next week we'll discuss the main "techniques" that we'll lean heavily on throughout the course.
What: Specifying the problem
Often, you’ll be asked to design an algorithm for a real world scenario, or at least something I'd like to pretend is a real world scenario.And before you can precisely describe an algorithm for that scenario, you need to specify what formal problem the algorithm is supposed to solve.So when asked to do something in terms of real world object, first restate the problem in terms of mathematical objects like numbers, arrays, lists, graphs, trees, and so on that you can reason about formally.In particular, specify your algorithms’ inputs and output and their types.For example, $FibonacciMultiply(X[0 .. m - 1], Y[0 .. n - 1])$ returns the product of $x$ and $y$ where $x$ and $y$ are both non-negative integers represented by $X$ and $Y$ as specified above.
Generally, your specification should give enough information that somebody could use your algorithms as a black-box or subroutine without needing to understand how or why the algorithm works.Pretend you’re library authors who are actually good at writing documentation.
How: Describing the algorithm
Computer programs are concrete representations of algorithms, but algorithms are not programs, and they should not be described in any particular programming language.The algorithms you design should work in any programming language, and if you describe them using a particular language, then you’ll focus more on the language’s nuances instead of what is really going on.Do you really want me reasoning about lifetimes or ownership in Rust when I should be focusing on the higher level idea?Do you want me parsing nested parentheses in a Lisp?What if we don't speak the same dialect?
On the other hand, pure English isn’t the best thing for all cases, either.There are lots of subtleties and ambiguities in the language, and it’s really hard to describe conditionals, loops, and recursion without being confusing.So I highly suggest you use pseudocode, preferably combined with a brief high level description of what you’re going for.Pseudocode uses the structure of programming languages and math to break algorithms into primitive steps, but the primitive steps themselves can be written in English, math, or some combination of the two; whatever is the clearest.I think the $FibonacciMultiply$ example provides a good balance between math and English.Erickson Chapter 0 has many more examples.Please look at them.
Why: Proving correctness
Often, it’s enough to design an algorithm that work for “most” inputs or work “well enough” for all inputs.In this class, though, we’ll be focusing on algorithms that are correct for all inputs.Meaning they find the thing we’re looking for or find a best solution every, single, time.With very few exceptions, no algorithm I present or algorithm you’re asked to describe will be obviously correct.So you’ll need to justify correctness of your algorithm.This is not the same as restating your pseudocode descriptions in plain English.Instead, you’ll need to explain why your algorithm does the thing it does.Why did adding numbers in this way give the correct thing?What led to this iterative procedure?When you made that recursive call, how did you know you're satisfying right assumptions about the input?Finding the right level detail and things to focus on in a proof is unfortunately one of those things you have to practice until you get a good feel for it.Hopefully the many examples you'll see in class will help.
How fast: Analyzing running time
There may be many different algorithms that solve the same problem, and the most common way of ranking those algorithms is by running time.You’ve probably already seen this and done it using big-Oh notation.We’ll review running time analysis in more detail this Thursday.
