CS50 2017 - Lecture 3 - Algorithms

00:00:00 - Memory Overview
00:02:37 - Null Terminator
00:04:06 - initials.c
00:18:50 - Finding 50
00:27:00 - Linear Search
00:27:53 - Binary Search
00:28:51 - Sorting Blue Books
00:31:19 - Sorting Humans
00:32:51 - Human Bubble Sort
00:34:55 - Human Selection Sort
00:38:13 - Bubble Sort Pseudocode
00:41:52 - Selection Sort Pseudocode
00:43:12 - Insertion Sort Pseudocode
00:45:16 - Algorithmic Running Time
00:47:23 - Analyzing Bubble Sort
00:52:47 - Big-O Notation
00:55:27 - Omega Notation
00:57:43 - Theta Notation
00:59:03 - Visualizing Algorithms
01:03:03 - sigma0.c
01:06:11 - sigma1.c
01:12:20 - Merge Sort Pseudocode
01:14:19 - Merge Sort Step-by-Step
01:25:20 - Formalizing Merge Sort
01:27:57 - Visualizing Merge Sort
01:30:03 - Pset3 Teaser
01:34:38 - The Sounds of Algorithms

[Onomandah]

Education would be so much fun if we had passionate teachers like him.

[bahaa]

This was the best explanation I ever had, I studied C on my own 20 years ago and stopped when I faced a problem because I had no one to ask and no YouTube to learn how Harvard students learn.
Thank you professor David because you teach a method of thinking not only coding, and thank you Harvard University for sharing this out.

[tongxinsun]

This does seem hard at first sight. But I find the right way to watch this lecture is practicing + thinking, not just listening. Some parts that confused us just need a little "pause + think", and others just need a little extra "practice yourself." Learn with a problem-solving method (i.e. conquer each question by thinking or practicing) along the way, and suddenly you'd get the beauty.

[alexanderburlingame]

Not sure what's most impressive in these videos—the passionate and clear teaching or the perfectly minimalist slides

[saipanda]

Thanks David and other staff of cs50.you are doing great job.

[yulinglin]

It is amazing that they combined Algorithms and music together!

[adrianb]

To explain the bubble sort equation (n)(n-1)/2, its quite easy:
You have (n-1)+(n-2)+...+(2)+(1). The 1's cancel with the 1's in the (n-1), and the 2's cancel with the 2's in the (n-1), and so on.
so have n + n + n + n + ... But how many times? (n-1)/2 times, because you started off with n-1 total terms, but halved them by cancelling the 1, 2, 3's etc.
So n*(n-1)/2

[harold]

Superb lecture I grasp the linear search binary search insertion selection and merge sort and their respective running times I understand the big O, omega and thetha notation I understand the recursive code. Overall it was a brilliant lecture. The enthusiasm of the lecturer is phenomenal

[SheikhEddy]

That moment when Christie (Or Chrissy? Not sure) found 50 instantly xD

[jondwyer]

Hint: Turn on captions so you can tell what the students are saying.

[cybersecurityguy]

Thank you, David Sir. You're absolutely amazing!

[jayzee]

Неплохо, довольно хорошо и просто объясняет) Hello, from Russia

[BreceLuu]

Is there a recommended timeline WHEN to do the assignments for the corresponding week?
Twice in a row now they teach you the knowledge "a week later" that you could've needed for the previous assignments. Eventhough I've figured out the solutions by myself, it would make the learning process much more enjoyable if they would place the assigments differently.
I really start to "hate" C because of how tedious it is to work with. Nonetheless giving up is not an option. I can't wait for Python and JS. =)

[brycehickson]

I wanted to hear Brian play us out! D:

[po-hengchen]

Not good at algorithm but I can recognize the piano music(Time Travel Theme) at 01:34:16 is from Jay Chou's movie called "Secret".

[Corgamos]

I love this video, it explains a lot of topics really well, thank you for it!

[braydenooi]

a few questions
1. I understand that as demonstrated different sorting algorithms have different O as data size increase, but on real time at what data size does it really makes impact?
2. Wouldnt it be better if you measure upper and lower bound of an algorithm in real time as opposed to steps??
3. I dont really understand the merge sort thing at 1:17:53, how does the computer know to merge by putting 2 1st before 4? I thought it would work more like concatenation? We need to specify like 'compare the elements in left side and right side and sort in ascending order?' or the computer knows by default?
4. the upper and lower bounds got me thinking, so far we know that the computer have no problem doing basic mathematical operations, how can we implement advanced mathematical operations like calculus?
5. given that the merge sort is the most efficient sorting method, do we still get to use other sorting methods in real life?
6. for bubble sort, will the computer continue to check out the bubbled-up numbers like what you showed in 1:35:26? if yes, couldnt we just tell the computer to skip the bubbled-up numbers?

very very new here so would be great if anyone can share some resources to read on algorithms

[georgymartynovich]

Let me go ahead and go ahead and go ahead and like this video.

[justingehr]

this man clearly knows 42 is the meaning of life :D

[rehamshouman]

i did not get that music part with algorithm ...except the rest is just perfect thank u