- #公开课
- #入门|算法|数据结构

# [Coursera] Algorithms (princeton) (week3) 讨论帖

sanguine

640323

Honor code. All students in the course must agree to abide by the Coursera honor code. In particular, do

assignments不可以share code，但是exercise和job interview questions是可以的

讨论帖(该贴仅为week3讨论帖，加分贴请点这里)

课程汇总 && 介绍：1point3acres.com

Schedule：Each Friday at 12:01pm EDT, we will release the course materials for the week: two lectures, two sets of exercises, a programming assignment, and two sets of job interview questions.

Week 3

*not*post solutions or partial solutions to programming assignments; however, you are permitted to discuss general ideas and problem-solving approaches. You are also permitted to discuss solutions to exercises and job interview questions.assignments不可以share code，但是exercise和job interview questions是可以的

讨论帖(该贴仅为week3讨论帖，加分贴请点这里)

课程汇总 && 介绍：1point3acres.com

Schedule：Each Friday at 12:01pm EDT, we will release the course materials for the week: two lectures, two sets of exercises, a programming assignment, and two sets of job interview questions.

- Exercises: due two weeks after they are released.
- Programming assignments: due two weeks after they are released.
- Job interview questions: for your own enrichment and not assessed.

Week 3

*Our lectures this week are based on two classic algorithms that were invented over 50 years ago, but are still important and relevant today, as implementations of one or both of them are found in virtually every software system and research on new variants of these classic methods is ongoing. Our treatment ranges from the mathematical models that explain why these methods are efficient to the details of adapting them to real-world applications on modern systems.***Lecture: Mergesort.**We study the*mergesort*algorithm and show that it guarantees to sort any array of N items with at most NlgNcompares. We also consider a nonrecursive, bottom-up version. We prove that any compare-based sorting algorithm must make at least ～NlgN compares in the worst case. We discuss using different orderings for the objects that we are sorting and the related concept of stability.**Lecture: Quicksort.**We introduce and implement the*randomized quicksort*algorithm and analyze its performance. We also consider randomized quickselect, a quicksort variant which finds the kth largest item in linear time. Finally, consider 3-way quicksort, a variant of quicksort that works especially well in the presence of duplicate keys.**Exercises.**Drill exercises on the lecture material.**Programming Assignment: Collinear Points.**Your programming assignment is a typical example of a problem that could not be solved without a fast sorting algorithm, properly applied. It is a classic problem in computational geometry: Given a set of points in the plane, design an algorithm to find all line segments that contain 4 or more points.**Job Interview Questions.**Algorithmic interview questions based on the lecture material.**Suggested readings.**Section 2.2 and 2.3 in*Algorithms, 4th edition*.