CS50x 2024 - Lecture 3 - Algorithms

[@paul6096]

This class is absolutely wonderful. I'm a 75 year old retired computer network engineer with multiple grad degrees in computer science (in the early 80's, long before Windows). I haven't programed in C (I also did Pascal, Dbase, and SPSS) in over 35 years. Network work was rather different. This class has given me the opportunity to revive some dormant brain cells, dormant from age and the effects of a stroke 10 years ago. It's very satisfying to be able to do this work again. Thank you for this class. I look forward to finishing this class and continuing on to the to the Python programing class and any other of these class that are available. One step at a time.

[@davidjmalan]

Glad you've enjoyed so!

[@chamyn8995]

Thanks for your contribution to the computer sciences, grandpa.

[@MadhusudanSinha]

I am 33 and had a feeling that I might be late to programming. Thanks Gramps.

[@504octo]

Same boat here! I'm having lot of fun with this class for the 1st time 25 years Network Engineer with multiple specs. I've learned Cobol and Qbasic for games even before win 3.11. Got into Video Games Dev this year and learning C and then Python. I was stressed by it. However, I guess my prays were listened and the Internet algorithm led me here. The same as you, my programming brain cells were dormant but this course is getting them out of sleep and the results, are impressive!

[@algirdasltu1389]

Damn thats a long time ago... cant imagine getting those degress when there was barely any abstraction and c was the highest level you had...

[@luxxer9591]

I love the fact that they dont put ads, full concetration Mode [on]

[@_Hello_World_]

I think the monopoly game was an ad 😅

[@OuviUmaHistoria2024]

The experience of studying this course is amazing, I feel that I´ve learned more in the last weeks that I´ve learned in a full year of a Technologist Degree

[@MrArkaneMage]

Yes, especially the "training" wheels make things way more clear plus once you try to translate it into "real C" you really learn a lot in the process. No degree here but this course is pure gold for everyone interested in PCs, coding, etc.

[@CườngNguyễnPhú-n2i]

same to me haha 😅

[@Hellmiauz]

What a time to be alive. Thanks David for leaving this legacy to humanity for those who can't attend harvard. I finished CS50P and now fighting my way through CS50X. Hopefully I can complete it before the year ends😊

[@hamidrezaparand4909]

This course is just amazing. And how good of a teacher is he is 🥶

[@divineihemadu3287]

The fact that I'm getting Harvard level of education at no cost( except for the cost of internet connection) is just amazing. David Malan is so awesome and I would love to one day teach the newer generation what I've learned as passionately as this man❤😊

[@shizaikhlaq6096]

WHAT A BOUNDING, what an engagement. i have never used to watch 30 minutes long video and I am watching thee series complete and without getting bord. allah bless the team who are arranging such amazing content for us , blessed people are those who are sitting in different countries and are getting this god gifted channel as a gift becoz normally we are unable to find such amazing and accurate content. Amazing amazing , hats of to David Malon and the teams managing this amazing channel. i don't have words to praise. superb superb and superb. allah gives you the whole world's success

[@sandevv-k7q]

I can't believe this that this level content is free!,

[@toke7342]

Why not?

[@saqib7685]

@@toke7342 because they some course which are shit expensive but are not as good as this

[@valentina7901]

@@toke7342 you have madd comprehension skills

[@purelyjoel6428]

you should, also all education should be ;) like living and food. or at least Basic needs shouldnt be smth you make profit with.

[@MartaBayou]

This video was very great I don't have words for describe my happiness angle on this course

[@GrantReinauer]

Seriously? 4k? HDR? Not only are the lectures amazing but so is the watching experience!!

[@palomasentadaestoysentado9096]

I really like this teacher, its very good capting attention

[@Kylian19]

this guy is my dream teacher, and just for free available on youtube is amazing!

[@stevenlomon]

Having blast going through this and doing the Problem Sets!! David is one of the most enthusiastic teachers I've ever seen and he explains things so wonderfully

[@plague8953]

seriously!

[@deutschWallah]

Nobody, literally nobody on this planet can teach C, Linux and DSA like David Malan. Hats off to you Sir. I have been in this field for around 20 years now and I learnt and cleared a lot of things myself. Respect and love to you Sir :)

[@reynonquirimit6075]

I vow to complete this program this 2024 No more excuses!

[@misterguy]

And did you?

[@reynonquirimit6075]

@@misterguy Sadly not yet, currently stucked on week 5. It's difficult but i'd still keep going forward

[@misterguy]

@@reynonquirimit6075 stuck on what, understanding the lecture, or doing the assignment that comes with it?

[@PranawwWW]

@@misterguy assignment

[@reynonquirimit6075]

@@misterguy yeahh, currently stucked on pset5. Been quite busy

[@MatthewIrizarry-4]

Talking during 44:00 about return values…. In C, you can also return EXIT_SUCCESS or EXIT_FAILURE to make the code more readable

[@mtarik0]

That's a useful tip! I think it would be nice in small projects like we do in this course but in case of a large project, you may need to see what value the program returns with, like returning 1132 could help a programmer point which code snippet to deal with. Is that capable of doing so?

[@MatthewIrizarry-4]

@@mtarik0 You could just define a constant value to accomplish this. Say you wanted Error 653 to be an I/O error or BufferOverflow, whatever you wanted. #define BUFFER_OVERFLOW_ERROR 653 And when you used the BUFFER_OVERFLOW_ERROR it will return 653😁

[@mtarik0]

Is it possible to use both? If so, in the context of returning values as well as being helpful to a programmer, I feel like it becomes a bit redundant with this way. I might have missed your point though.@@MatthewIrizarry-4

[@Nunoflashy]

@@mtarik0 If your question is whether you can use both the number and the #define (constant), then yes, you can use both. The point of using #defines and constants in general is to make the code more readable. If you were to return that "653" code any time you had an I/O error for example, you probably wouldn't know what it meant, whereas with a descriptive name such as BUFFER_OVERFLOW_ERROR, you'd know exactly what it means and where it should be used.

[@mtarik0]

I wanted to ask whether it is possible to use EXIT_FAILURE and BUFFER_OVERFLOW_ERROR by #define (constant)@@Nunoflashy

[@seeblu]

I vow to complete this program this year. Started in December of 2023.

[@aneurismike]

Wish you the best 👊.

[@chekhovslasergun9175]

I'm with you, started in Dec too

[@sefonefinpsefnpefn4191]

I am with you. I started last week. Keep going!

[@ginniosikisama]

started this week let's go

[@kyan6985]

How's your progress?

[@이이이-g4f2y]

1:53:28 How to merge: The computer points to the first value in each of Lists (3 6) and Lists (1 4). Compare the two pointers and place the smaller value between 3 and 1 in the new list above. The left pointer still points to 3, and the right cursor now points to 4 . (num 1 went up) Compare the size of the two 3 and 4. Of the two, 3 is smaller, so put 3 in the list above, to the right of 1. Repeat this...

[@FigueMonk]

Learning all this free is awesome, God bless Internet

[@badguy7432]

they briefed through everything without touching the codes yet. Sorting, binary search, recursion, structs, even 'scanf and fgets' are simplified with get_string. Man, the amount of stuff they teach yet the depths of it being touched in lectures is insane

[@badguy7432]

arrays are introduced without the talk about pointers too, culture shock for yall if yall go on into cs facing passing by reference and value

[@ludwigthedwarf7678]

Indeed, i do have no idea what pointers are and what you mean by reference and value

[@barmiro]

@@badguy7432 the next lecture is about pointers, also the problem sets go much deeper. I'd say the lectures just touch on the basics and all the learning is actually done by coding. I'm also not a fan of the cs50 library, especially stuff like get_string and get_int, but I get why they decided to do it I guess.

[@badguy7432]

@@barmiro yeah figured, speak of the devil. Albeit, the sorting methods should’ve been way more in-depth in the lectures. This is way too fast for freshmen to comprehend especially mergesort in anything but c.

[@besegawG]

@@badguy7432 where do you suggest I go learn about this in depth?

[@marveII0us]

Thanks prof David

[@The.Oh1183]

David: "Questions?" Me: "Can you repeat EVERYTHING?!"

[@noah26blanco]

Exactly! I wish I could’ve been there to ask some questions myself 😂 because apparently everyone sitting there is a genius

[@mariatanya3533]

@@noah26blanco Lmfaoo exactly! Like wow so y'all just understood that the first time? Ok then

[@Nillipilli]

Amazing video again. Really love the way how you explained running time, especially as I struggled understanding it during my studies but your explanation was really on point, thanks for that :)

[@magma4168]

Amazing lecture! And shout-out to Sam's hair 💖

[@TALHA-hr6xf]

key learning point; The cs50 duck always has been and always will be.

[@sk45293]

Recursion is wild

[@kingillager]

1:45:31 that silence, I felt that 😢

[@lawfpv]

I was a little worried when we brought up recursion with like 30 minutes left to explain it, but the section on merge sort was very enlightening as to the sequence that a recursive algorithm takes when solving a problem. Thanks!

[@riyajath_hmd]

Can't watch the lessons yesterday, as I was travelling. Finished the lecture 3 today and feeling more excited.

[@noah26blanco]

Are still as excited after 5 Months? 😏

[@freelance-writer]

Getting students up on stage and doing these "live body" exercises is such a great teaching method.

[@BaraBarabere.]

intro music GOAT!

[@dimaborovski1865]

The fact that this level of education is absolutely free is mind boggling to me God bless the internet ❤

[@nandinimatham8811]

great lecture. most amazing way to explain sorting algo. Feedback: Bubble sort algo: running time is: (n-1)(n-1) = (n-1)^2, ignoring the -1 for laaaaaarge numbers, we directly get n^2, O(n^2)

[@littlebrotha123]

i've watched some vids on recursion before, but this one, though it took its time, was one of the most eye opening ones. merge sort really gave me an "aha" moment as far as the power of recursive sorting

[@Amauryzau]

1:33:00 (Recursion section) Why is the if ( n

[@Filnaei]

do you still need help?

[@MohammedAbbasSyed-k5n]

11:06 i saw a girl most probably trying to raise her hand for answer but unfortunately david didn't saw her as he was looking in another dircetion , i felt the pain of her

[@Gha_210]

bro it's not that serious lmao

[@MohammedAbbasSyed-k5n]

​@@Gha_210ik but just saying

[@MaximeFontaine-ou3qc]

I can't believe you can actually call John Harvard ... Mr Mallan, this was genius.

[@robertdiasmello]

Robert from Brasil 🎉 Another excellent lesson! 🎉

[@Ametherius]

David is an amazing teacher. I’m doing the free EDX course which has assignments and stuff to help you out even more. But the main thing I notice in all these videos is he’s worn the same outfit in every lecture so far

[@4562-j7y]

crazy how mixed the attendance is! Last year in my first CS class at University (in germany) we had like 15 girls and 200 dudes, the atmosphere here seems much more open

[@troyyey4353]

hows is that relevant ? why you even care about that ?

[@4562-j7y]

@@troyyey4353 how is it not relevant? Why should I not care about it?

[@troyyey4353]

im not sure if you are joining the course for the right reasons if one gender is more present than the other can effect your decision , im not sure what are you worried about @@4562-j7y

[@st.bimbam]

Because diversity is a good thing@@troyyey4353

[@ernie5229]

@@4562-j7yYou are so a girl. You are why there were only 15.

[@xuenf]

Sam is just chaotic adorable

[@crypticsios2254]

reals

[@nikosworks]

the best way of teaching

[@BaibhavDeka]

void bubble_sort(int array[], int size) { // size = no of elemnts in the array for (int i = 0; i < size - 1; i++) { // compare adjacenies int no_swaps = 0; for (int j = 0; j < size - 1 - i; j++) { if (array[j] > array[j+1]) { int temp = array[j]; array[j] = array[j+1]; array[j+1] = temp; no_swaps++; } } if (no_swaps == 0) return; } return; } // code for bubble sort

[@BaibhavDeka]

void selection_sort(int array[], int size) { // size = no of elemnts in the array for (int i = 0; i < size - 1; i++) { int smallest = array[i]; int j1 = i; for (int j = i+1; j < size; j++) { if (smallest > array[j]) { smallest = array[j]; j1 = j; } } if (j1 != i) { int temp = array[i]; array[i] = smallest; array[j1] = temp; } } return; } // code for selection sort

[@chongxian7608]

why didnt he teach this tho. im pretty sure there would be better ways, kinda dissapointed about the later part of the lecture......

[@loldoctor]

@@chongxian7608Because he's setting up for the next lecture about memory. There are probably bitwise methods that would be blazing fast, but the point of the class is to teach CS concepts not how to optimize code.

[@Creative_wazz]

love from student aka fan , David! Thankyou

[@sehlkd4r1nc31]

Thank you, you are the best, i have not idea but i am learning

[@zinmyolatt1386]

I love this one! it's so fantastic!

[@bagumamartin]

Watching this one here in preparation for tomorrow's internship interview 🙌

[@akfdglkjadfgjl]

I surely would have finished my CS study, if the teachers and students were this charistmatic. CS at TU Delft in '98 wasn't really the place to be. Great course for learning the basics and history, that I skipped!

[@GenZ_01_]

Nothing short of gold!

[@bwaco7004]

cant wait to make sense of this through rigorous labs

[@dheerajnihalani2430]

20:20 Sam trying to help him, but was the wrong box

[@pi70s]

omega denotes the minimum possible steps to run an algorithm O notation denotes the maximum possible steps to run the algorithm efficiently selection sort :- goes through the array and finds out the least element and puts it on the far left side it keeps repeating this process until all the elements are sorted bubble sort :- the elements compare themselves with the adjacent elements repeatedly to organize themselves modified version of bubble sort :- if already arranged, quit therefore, bubble sort is omega of n whereas selection sort is n^2 merge sort(better than ss and bs) :- sort left half of an array then the right half and merge them O of nlog n recursion:- recalling the function in itself(for example factorial function)

[@Zangetsu-gaTensho]

that draw recurrsion code makes no sense to me its literally calling draw() before ever drawing everthing Edit: so I got it now and this shit blew my mind 😭 (For anyone in my position, it's something like this if you put n = 2... The flow of commands is like I numbered below 1: draw(2) is called 2:N becomes 1 10: from step 9 execution Comes here as draw(1) was called here 11: loop runs 2 times 12: exits (goes back to main) 3:Draw(1) is called 4:N becomes 0 7: 0 is returned from step 6 8: Loop runs 1 times 9: exits 5:Draw (0) 6:Returns 0 to draw(0) place

[@aasrp661]

1:05:51 Gangsta dap up 😎

[@thefloatingrock]

David is the GOAT

[@Tushaar-CSgym]

that recursion easter egg was pretty cool

[@srijanraghavula]

The volunteers are increasing in number as they see some incentives XD

[@TheeInfoBaron]

49:00... The exact same code doesn't work on my editor. The error code points to i as an undeclared identifier.

[@yahyaaswat3939]

Have you put "int i" in the for loop?

[@TheeInfoBaron]

@@yahyaaswat3939 yup...I found the syntax error, though. It was a semi colon I put in the for loop... Mahn .

[@CordovaHGS]

I was not provided brownies, who can I speak to about rectifying this issue????

[@littlebrotha123]

He just gave us John Harvard's number. I am going to leave him an angry voicemail

[@notrps]

@@littlebrotha123 yeah! 👍

[@MuhammadMekaeylBinFaisal]

@@littlebrotha123 does it work?

[@anukritis1297]

The course is awesome.Have reached lecture 3. But I am unable to understand recursion program. I get the theory but not exactly how we are getting the pyramid. If draw(n-1) is implementing value of n should reduce yet on printing value of n instead of # output is 1 22 333 How??????

[@ZiBlogg]

I'm pretty sure you have already got to understand it, but I will explain it the way I understood it anyway in case someone else has the same remark (And good comment btw, I just glanced over the notion, thanks to you I actually tried to understand it by visualizing the process in my head). Since the function starts with a call to the function itself, in this case draw(n-1), for the sake of clarity let's assign n = 5, draw(5) will call draw(5-1) = draw(4) which will call draw(4-1) = draw(3) which will call draw(3-1) .... all the way to draw(1), since draw(1-1) is 0 and we have an if statement that stops 0 from going negative. at draw(1) IS when the for loop actually starts, draw(1) will print ( *for( i = 0; i < 1; i++)* ) the first line of hashes which has n=1, THEN going back to draw(2) and printing ( *for( i = 0; i < 2; i++)* ) the second row of hashes, all the way back to the original draw(5) which will print the last row of hashes aka n=5.

[@brandoncarris9015]

1:05:52 insane 180 dap

[@dockwater]

Somewhere around 1:20:00 a discrepancy between the video and sound begins

[@SkepticLens]

1:07:44 Anyone understand what David Malan said? Did he say we keep looking for you today? Why?

[@virendxr]

Eli was the name he was searching in his phonebook but was not found :)

[@pratikkale5489]

Watch the lectures with more concentration bro

[@SkepticLens]

@@virendxr Thank you, I was confused without the context

[@virendxr]

@@SkepticLens your welcome

[@krishBhardwaj-xz2hl]

did the guy in the front raised his hand for a question at 28:22 probably David couldn't see him

[@NKLGaming01]

23/08/2024. I will finish this course before 2024 !

[@luizashabetnick8059]

i really hope so too, starting aug 30th

[@NKLGaming01]

@@luizashabetnick8059 very lazy and bored. This lesson 14 days and i still not get over it

[@GilbertoGalindez-y8x]

I'm in love with Sam button ❤

[@PerceyIchorre]

we all are bro, shes the official math major mascot

[@markmarki9511]

15:41 Sam didn't get her high five 😢

[@john9908]

She was cringe

[@PhoebeX822]

I really love this course and appreciate all the efforts that’s gone into it!!!! However, I’m a bit confused about the calculations for Selection Sort and Bubble Sort. From what I understand, both should follow the formula: (n - 1) + (n -2) + ... +1 = n^2/2 +n/2; even if Bubble sort is (n-1)^2, Selection Sort is generally more efficient when n > 2. Only in the best-case scenario, where the numbers are already in order, does Bubble Sort achieve O(n), which is better than Selection Sort’s O(n^2). Could someone clarify this for me? I'm feeling so confused. Thanks in advance!

[@sourabhhsethii7292]

Day 3 : Completed!

[@WizeChoice]

Amazing 👉🏾✨✨✨

[@Chrisz0722]

So interesting !

[@姚景曦]

As a college student, I thought it is a well designed course for cs learning.

[@zeynepuslu100]

started on june 2024. good luck everyone

[@abdulmelik8337]

how much time do you spend on learning?

[@100drips]

Me too. Good luck to you

[@muinfinityy]

hey, quick question: i started this course earlier this year but I was unable to finish it, and I don't think ill be able to make it to the deadline. i plan on redoing it in 2025. would I be flagged for plagiarism if I reused my previously finished assignments and submitted them?

[@AsaAdetimirin]

Total Recall (gene) ACTIVE ✅☑️💪🏾

[@x3nomat]

I don't understand how the Draw function ever draws anything, because it calls itself in the beginning and then returns when reaching 0... :/ How does it ever get to the for loop?

[@littlebrotha123]

i was wondering that myself but then i thought about it some more and i think this is what happens. first call to draw calls second call which calls third which calls fourth all the way until n reaches zero and no more calls are made. up to here, when the last call is called, no printing has taken place, but since no more calls are going to be made it begins cascading backwards from the last call, say the 9th call is the last -- the 9th call then prints first (the single block), then the 8th call prints (two blocks), then the 7th and 6th and so on until it cascades or collapses back down to the first call which will then be the last to print 9 blocks.

[@ellieu177]

I was confused about the same thing! I asked DDB and apparently in this case 'return' doesn't exit the outer 'draw' programme yet, because the draw functions are all in a 'stack' at that point waiting to execute (from draw(1) because it was called most recently, upwards.) So return stops 'draw(n-1)' being called again, but all of the draw functions waiting will still execute. I hope that helps!

[@muhammadzeeshan3911]

In merge sort if the length of list is in odd number how can we make 2 equal sections or how can we divide list in two equal lengths please reply

[@Magicninja01]

The halfs dont have to be equal. If its an odd number, one half will be 1 higer than the second

[@badguy7432]

the type is of int genre, in this level of cs. So, when you divide an odd number by half, it will auto omit the float (everything beyond the "."). So, mid index will be this value that has float omitted, left_half is from 0 to mid, right_half is from mid to n-1

[@dglesterhardunkichud4287]

Is anyone else confused about what the lights in the front of the stage say in binary, or did I just mess something up/miss something?

[@blavikensbutcher]

Now I want to be born again and go to Harvard

[@PerceyIchorre]

why do you have to be christian to go to Harvard?

[@victorfds]

Amazing!!!! 🥇

[@PhysicsMalolan-cu8ft]

Why was the selection sort algorithm quicker than bubble sort at the end? Any reasons for it since both have O(N^2)?

[@sandipanjha3]

More swapping. Just take an example of 4 integers and see how many swaps you need in each case

[@paolobalestriere1201]

At 28:25 there was a student that would wanted to ask a question 😭

[@smsony36]

i think i love number 3.

[@PerceyIchorre]

honestly id probably try lockers at random until i found the right one, but what is random?

[@Bilou-Otaku]

Sam is soooo cuteeee ✨✨💫💫✨⭐⭐

[@sci-tech3916]

38:06

[@oanhtuan2408]

Amazing 🎉 Wow😮

[@botify9400]

Summary CS50x 2024 - Lecture 3 focuses on algorithms and implementation. It explores the concept of thinking algorithmically and how to solve problems using code. The lecture uses examples such as searching for a number in an array to demonstrate different algorithms. Highlights The lecture emphasizes the importance of thinking algorithmically. It discusses the concept of dividing and conquering a problem to find a more efficient solution. The lecture introduces the idea of arrays and their characteristics, such as being contiguous and potentially unordered. [🔍] The lecture uses the example of searching for a number in an array to explain algorithms. [📚] It relates the concept of divide and conquer to various real-world scenarios, such as searching contacts in your address book. [🔢] The lecture highlights the importance of understanding how data is stored in memory and how it can be accessed using arrays.

[@programmingguy6081]

I must be missing something Prof. Since when did the C programming language get a 'string' data type? I believe C++, Objective C, and C# all have a string data type but I don't know of a version of C with a string type at least not as a base primitive type. Is this a user defined type that is part of the cs50.h header? Your editor is treating the string word as a known type. Note to students outside this class room none of the code that the Prof presents with the string data type will work in a pure C compiler. The code may work in a C++ compiler.

[@Bloorp425]

it is defined in cs50.h...it is typedef char *string under the hood... I think

[@luckyb0132]

It's part of their own header. You need to use it for the problem sets. He talks about in in the previous lecture

[@yugrp2128]

28:26 what if there are even number of doors

[@NicolasCote-wy6rz]

You randomly choose one of the two central doors.

[@SageExploit]

11:02 the struggle for "contiguous"😭😭

[@ex4787]

Can really see Professor Malan sweat in 4k, lol. But to be less mean, I'm loving this course!

[@anhau7981]

her enery make me want to learn CS50 - lecture 3

[@duanepoettcker5544]

I'm always amazed at how fast he types. Then I remember I'm watching it at 1.5x speed. (still pretty fast though)

[@platoschauvet]

1:43:00 I'm so glad that didn't work, cause I was real confused lol

[@OfficialCodeVoyage]

*Merge Sort is Overpowered !*

[@veronicasmemories]

Omg ✨spoiler alert ✨

[@bilalshaikh6603]

Bogo sort is best

[@Giac_of_all_trades]

1:13:01 Al Pacino moment

[@_Hello_World_]

Really, really awesome lecture. Thank you David! But what is Havard doing that their lecturers always sweet a waterfall. Yes, I know. It is probably super exhausting. But I never saw one of my lecturers sweeting that hard.

[@imcalled_ali]

amazing!