WELCOME: Welcome to Algorithms: Design and Analysis, Part I! Here's an overview of the first few sections of material.
INTRODUCTION: The first set of lectures for this week is meant to give you the flavor of the course, and hopefully get you excited about it. We begin by discussing algorithms in general and why they're so important, and then use the problem of multiplying two integers to illustrate how algorithmic ingenuity can often improve over more straightforward or naive solutions. We discuss the Merge Sort algorithm in detail, for several reasons: it's a practical and famous algorithm that you should all know; it's a good warm-up to get you ready for more intricate algorithms; and it's the canonical introduction to the "divide and conquer" algorithm design paradigm. These lectures conclude by describing several guiding principles for how we'll analyze algorithms in this course.
ASYMPTOTIC ANALYSIS: The second set of lectures for this week is an introduction to big-oh notation and its relatives, which belongs in the vocabulary of every serious programmer and computer scientist. The goal is to identify a "sweet spot" of granularity for reasoning about algorithms --- we want to suppress second-order details like constant factors and lower-order terms, and focus on how the running time of an algorithm scales as the input size grows large.
DIVIDE AND CONQUER ALGORITHMS: The final set of lectures for this week discusses three non-trivial examples of the divide and conquer algorithm design paradigm. The first is for counting the number of inversions in an array. This problem is related to measuring similarity between two ranked lists, which in turn is relevant for making good recommendations to someone based on your knowledge of their and others' preferences ("collaborative filtering"). The second algorithm is Strassen's mind-blowing recursive algorithm for matrix multiplication, which improves over the obvious iterative method. The third algorithm, which is more advanced and is optional material, is for computing the closest pair of points in the plane.
PREREQUISITES: This course is not an introduction to programming, and it assumes that you have basic programming skills in a language such as Python, Java, or C. There are several outstanding free online courses that teach basic programming. We also use mathematical analysis as needed to understand how and why algorithms and data structures really work. If you need a refresher on the basics of proofs (induction, contradiction, etc.), I recommend the lecture notes "Mathematics for Computer Science" by Lehman and Leighton (see separate Resources pages).
DISCUSSION FORUMS: The discussion forums play a crucial role in massive online courses like this one, which is an all-volunteer effort. If you have trouble understanding a lecture or completing an assignment, you should turn to the forums for help. After you've mastered the lectures and assignments for a given week, I hope you'll contribute to the forums and help out your fellow students. While I won't have time to carefully monitor the discussion forums, I'll check in and answer questions whenever I find the time.
VIDEOS AND SLIDES: Videos can be streamed or downloaded and watched offline (recommended for commutes, etc.). We are also providing PDF lecture slides (typed versions of what's written in the lecture videos), as well as subtitle files. And if you find yourself wishing that I spoke more quickly or more slowly, note that you can adjust the video speed to accommodate your preferred pace.
HOMEWORK #1: The first problem set consists of 5 problems, mostly about Merge Sort and asymptotic notation. The first programming assignment asks you to implement the counting inversions algorithm (see the third set of lectures) in whatever programming language you please, run it on a quite large input, and enter the answer.
RELATED READINGS: Algorithms Illuminated (Part 1), Chapters 1, 2, and 3.
欢迎您：欢迎来到算法：设计与分析，第一部分！这是材料的前几个部分的概述。
简介： 本周的第一套讲座旨在为您提供课程的味道，并希望让您对此感到兴奋。我们首先讨论一般的算法以及它们为何如此重要，然后使用将两个整数相乘的问题来说明算法的独创性通常可以通过更直接或更幼稚的解决方案进行改进。由于以下几个原因，我们将详细讨论合并排序算法：这是大家都应该知道的实用而著名的算法；这是一个很好的热身，可以帮助您准备更复杂的算法；这是“分而治之”算法设计范例的规范介绍。这些讲座以描述如何在本课程中分析算法的几个指导原则作为结尾。
渐近分析： 本周的第二套讲座是对big-oh表示法及其亲属的介绍，它属于每位认真的程序员和计算机科学家的词汇。目标是确定粒度的“最佳点”以进行算法推理---我们要抑制诸如常量因子和低阶项之类的二阶细节，并着重于算法的运行时间如何按比例缩放尺寸变大。
分而治之算法： 本周的最后一组演讲讨论了分而治之算法设计范式的三个非平凡的例子。第一个是用于计算数组中反转的次数。此问题与测量两个排名列表之间的相似性有关，而这又与根据您对某人和其他人的偏好的了解向某人做出好的推荐（“协作过滤”）有关。第二种算法是Strassen令人惊奇的矩阵乘法递归算法，它对明显的迭代方法进行了改进。第三种算法是更高级的并且是可选材料，用于计算平面中最接近的一对点。
先决条件： 本课程不是编程入门，它假设您具有Python，Java或C等语言的基本编程技能。有几门出色的免费在线课程教授基础编程。我们还根据需要使用数学分析来了解算法和数据结构如何真正起作用以及为什么起作用。如果您需要复习证明的基础知识（归纳，矛盾等），我推荐雷曼（Lehman）和莱顿（Leighton）撰写的讲义“计算机科学数学”（请参见单独的参考资料页面）。
讨论论坛： 讨论论坛在像这样的大规模在线课程中起着至关重要的作用，这是一项全自愿的工作。如果您在听讲座或完成任务时遇到困难，则应寻求论坛的帮助。掌握了一周的讲课和作业之后，希望您能为论坛做出贡献并为同学提供帮助。虽然我没有时间仔细监视论坛，但只要有时间，我都会签入并回答问题。
视频和幻灯片： 可以流式传输或下载视频，也可以脱机观看（建议上下班等）。我们还提供PDF讲座幻灯片（讲座视频中所写内容的打字版本）以及字幕文件。而且，如果您希望我说得更快或更慢，请注意，您可以调整视频速度以适应您的喜好。
作业1： 第一个问题集包括5个问题，主要涉及合并排序和渐近符号。第一个编程任务要求您以自己喜欢的任何一种编程语言来实现计数反转算法（请参阅第三组讲座），在很大的输入上运行它，然后输入答案。
相关阅读：启发性的算法（第1部分）第1、2和3章。
网友评论