CS50x 2024 - Lecture 3

CS50x 2024 - Lecture 3 - Algorithms

Рет қаралды 216,612

Күн бұрын

***
This is CS50, Harvard University's introduction to the intellectual enterprises of computer science and the art of programming.
***
TABLE OF CONTENTS
00:00:00 - Introduction
00:01:01 - Overview
00:02:58 - Attendance
00:09:40 - Linear Search
00:24:58 - Binary Search
00:28:25 - Running Time
00:38:06 - search.c
00:51:29 - phonebook.c
00:53:42 - Structs
01:05:26 - Sorting
01:12:43 - Selection Sort
01:24:50 - Bubble Sort
01:33:10 - Recursion
01:46:28 - Merge Sort
02:00:23 - Sort Race
***
HOW TO SUBSCRIBE
kzfaq.info_c...
HOW TO TAKE CS50
edX: cs50.edx.org/
Harvard Extension School: cs50.harvard.edu/extension
Harvard Summer School: cs50.harvard.edu/summer
OpenCourseWare: cs50.harvard.edu/x
HOW TO JOIN CS50 COMMUNITIES
Discord: / discord
Ed: cs50.harvard.edu/x/ed
Facebook Group: / cs50
Faceboook Page: / cs50
GitHub: github.com/cs50
Gitter: gitter.im/cs50/x
Instagram: / cs50
LinkedIn Group: / 7437240
LinkedIn Page: / cs50
Medium: / cs50
Quora: www.quora.com/topic/CS50
Reddit: / cs50
Slack: cs50.edx.org/slack
Snapchat: / cs50
SoundCloud: / cs50
Stack Exchange: cs50.stackexchange.com/
TikTok: / cs50
Twitter: / cs50
KZfaq: / cs50
HOW TO FOLLOW DAVID J. MALAN
Facebook: / dmalan
GitHub: github.com/dmalan
Instagram: / davidjmalan
LinkedIn: / malan
Quora: www.quora.com/profile/David-J...
TikTok: / davidjmalan
Twitter: / davidjmalan
***
CS50 SHOP
cs50.harvardshop.com/
***
LICENSE
CC BY-NC-SA 4.0
Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International Public License
creativecommons.org/licenses/...
David J. Malan
cs.harvard.edu/malan
malan@harvard.edu

Пікірлер: 206

@luxxer9591 4 ай бұрын

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

@badguy7432 18 күн бұрын

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 18 күн бұрын

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 18 күн бұрын

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

@barmiro 5 күн бұрын

@@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 5 күн бұрын

@@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.

@user-ju1sn6xo8g 4 ай бұрын

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

@The.Oh1183 Ай бұрын

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

@noah26blanco 29 күн бұрын

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

@user-ow8im4dd5o 5 ай бұрын

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

@toke7342 4 ай бұрын

Why not?

@saqib7685 3 ай бұрын

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

@valentina7901 2 ай бұрын

@@toke7342 you have madd comprehension skills

@hamidrezaparand4909 4 ай бұрын

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

@ViniSouza93 4 ай бұрын

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 2 ай бұрын

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.

@user-wm1ix4ej4h Ай бұрын

same to me haha 😅

@freelance-writer 11 сағат бұрын

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

@shizaikhlaq6096 4 күн бұрын

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

@palomasentadaestoysentado9096 Ай бұрын

I really like this teacher, its very good capting attention

@seeblu 6 ай бұрын

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

@aneurismike 6 ай бұрын

Wish you the best 👊.

@chekhovslasergun9175 6 ай бұрын

I'm with you, started in Dec too

@sefonefinpsefnpefn4191 5 ай бұрын

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

@ginniosikisama 3 ай бұрын

started this week let's go

@kyan6985 2 ай бұрын

How's your progress?

@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 :)

@marveII0us 6 ай бұрын

Thanks prof David

@reynonquirimit6075 6 ай бұрын

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

@misterguy 4 ай бұрын

And did you?

@reynonquirimit6075 4 ай бұрын

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

@misterguy 4 ай бұрын

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

@Pranav-ie1ik 4 ай бұрын

@@misterguy assignment

@reynonquirimit6075 4 ай бұрын

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

@FigueMonk 2 ай бұрын

Learning all this free is awesome, God bless Internet

@stevenlomon 3 ай бұрын

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 2 ай бұрын

seriously!

@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

@MaximeFontaine-ou3qc Ай бұрын

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

@mr_riyajath 6 ай бұрын

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

@noah26blanco 29 күн бұрын

Are still as excited after 5 Months? 😏

@GenZ_01_ 15 күн бұрын

Nothing short of gold!

@sk45293 5 ай бұрын

Recursion is wild

@BaraBarabere. 5 ай бұрын

intro music GOAT!

@WizeChoice 4 ай бұрын

Amazing 👉🏾✨✨✨

@victorfds 4 ай бұрын

Amazing!!!! 🥇

@bwaco7004 5 ай бұрын

cant wait to make sense of this through rigorous labs

@user-dz8me4sp8m 2 ай бұрын

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...

@imcalled_ali 4 ай бұрын

amazing!

@MatthewIrizarry-4 6 ай бұрын

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 6 ай бұрын

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 5 ай бұрын

@@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 5 ай бұрын

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 5 ай бұрын

@@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 5 ай бұрын

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

@user-nu3kb8pe6g 6 ай бұрын

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 5 ай бұрын

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

@user-nu3kb8pe6g 5 ай бұрын

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

@troyyey4353 5 ай бұрын

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 @@user-nu3kb8pe6g

@st.bimbam 5 ай бұрын

Because diversity is a good thing@@troyyey4353

@ernie5229 5 ай бұрын

@@user-nu3kb8pe6gYou are so a girl. You are why there were only 15.

@sourabhhsethii7292 23 күн бұрын

Day 3 : Completed!

@not_amanullah 5 ай бұрын

Thanks

@xuenf 2 ай бұрын

Sam is just chaotic adorable

@oanhtuan2408 2 ай бұрын

Amazing 🎉 Wow😮

@user-mm8ml1ku4g 6 ай бұрын

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

@user-mm8ml1ku4g 6 ай бұрын

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 6 ай бұрын

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

@loldoctor 6 ай бұрын

@@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.

@cope4854 6 ай бұрын

1:05:45

@srijanraghavula Ай бұрын

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

@blavikensbutcher Ай бұрын

Now I want to be born again and go to Harvard

@user-kh8jl1kz5w 19 күн бұрын

I'm in love with Sam button ❤

@not_amanullah 5 ай бұрын

Understood++

@sathishp3180 6 ай бұрын

1:22:47

@smsony36 29 күн бұрын

i think i love number 3.

@sci-tech3916 6 ай бұрын

38:06

@zeynepuslu100 Ай бұрын

started on june 2024. good luck everyone

@abdulmelik8337 Ай бұрын

how much time do you spend on learning?

@100drips Ай бұрын

Me too. Good luck to you

@dglesterhardunkichud4287 3 ай бұрын

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?

@angelofinassu4867 4 ай бұрын

The CS50 it's perferct

@amine63404 6 ай бұрын

1:09:00

@anukritis1297 3 ай бұрын

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??????

@brandoncarris9015 10 күн бұрын

1:05:52 insane 180 dap

@botify9400 5 ай бұрын

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.

@姚景曦 10 күн бұрын

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

@ombanerjee2623 3 ай бұрын

finished 17/04/2024, the day before my kcet exam

@phellipecardoso8994 2 күн бұрын

1:15:00

@CordovaHGS 2 ай бұрын

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! 👍

@paolobalestriere1201 17 күн бұрын

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

@manasjajodia5427 Ай бұрын

in binary search what if the doors are even in number

@muhammadzeeshan3911 3 ай бұрын

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 3 ай бұрын

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

@badguy7432 18 күн бұрын

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

@endise1888 6 ай бұрын

logic

@dockwater 21 күн бұрын

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

@quang.luu.179 Ай бұрын

👍👍👍

@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 23 күн бұрын

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!

@Giac_of_all_trades Ай бұрын

1:13:01 Al Pacino moment

@platoschauvet 4 ай бұрын

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

@ex4787 20 күн бұрын

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

@OfficialCodeVoyage 6 ай бұрын

*Merge Sort is Overpowered !*

@veronicasvideodiaries 3 ай бұрын

Omg ✨spoiler alert ✨

@bilalshaikh6603 2 ай бұрын

Bogo sort is best

@anmol__og 6 ай бұрын

Who is from GLA UNIVERSITY 0:20

@poluefemus Ай бұрын

took me a sec to understand the recursion code lol

@jamesbrock7908 3 ай бұрын

Tipe for tideman: watch next lecture to learn how to swap values

@georgimmitev Ай бұрын

34:04

@markmarki9511 Ай бұрын

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

@duanepoettcker5544 4 ай бұрын

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

@hsglator7135 17 күн бұрын

I really don't know what to say but I can do this instead while (true) { printf ("❤️") ; }

@bi4d 12 күн бұрын

Woah, u went from week 3 to 6 in only 2 days?

@hsglator7135 11 күн бұрын

@@bi4d Yeah, but I was just watching and taking notes. By the sixth week, I realized there were also problem sets. 🥲

@saabiqstudios1281 5 ай бұрын

what if the number of doors is even, do you just skip to step 3?

@sergi23 4 ай бұрын

You randomly choose one of the two central doors.

@Bloorp425 Ай бұрын

@@sergi23 no... if you make mid as len / 2.. and let's say we have 10 elements, 10 / 2 = 5 ... we can go to the index 5... which is the 6th element... if we have 11, 11 / 2 = 5 as well... coz it's truncated to be int. That 6th element is the middle.

@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

@SkepticLens 6 ай бұрын

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

@everestoics 6 ай бұрын

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

@pratikkale5489 3 ай бұрын

Watch the lectures with more concentration bro

@SkepticLens 3 ай бұрын

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

@everestoics 3 ай бұрын

@@SkepticLens your welcome

@p199a 4 ай бұрын

This intro music reminds me something but i cannot remember what.

@abrarkhann71 4 ай бұрын

westworld

@p199a 4 ай бұрын

@@abrarkhann71 ye it feels tiny bit similar to westworld also it gives me same vibes

@abrarkhann71 4 ай бұрын

@@p199a I found it similar to that. It's good. Hope we don't get the Westworld's Delororis.

@PavithraGH30 Ай бұрын

How to get a free certificate after completion of this course? if anyone knows please guide me.

@davidjmalan Ай бұрын

See cs50.harvard.edu/x/2024/certificate/ !

@PavithraGH30 Ай бұрын

@@davidjmalan Thank You Sir 😇

@ashurahman9272 5 күн бұрын

I hate my mind at 37:43

@gideonokwan1785 5 ай бұрын

Do we always have to use the cs50 library to get same results or there are other resources?

@sergi23 4 ай бұрын

You use the cs50 library in order to access the functions it contains (like get_string or get_int). You'll eventually leave the cs50 library. In any case, it's best to check the documentation for every library and every function you use (at least until you know them a bit).

@SageExploit 5 ай бұрын

11:02 the struggle for "contiguous"😭😭

@Miziru Ай бұрын

2:00:15 who else thought its gonna be an earrap💀💀

@valenbozaa Ай бұрын

I want to be the girl on the front that always raises her hand when david makes a question

@pizzzax8 6 ай бұрын

@yugrp2128 2 ай бұрын

28:26 what if there are even number of doors

@NicolasCote-wy6rz 2 ай бұрын

You randomly choose one of the two central doors.

@beaverbot551 3 ай бұрын

Hi Qian

@yblue6116 6 ай бұрын

21:42 - Class shit

@dglesterhardunkichud4287 3 ай бұрын

printf("lol ");

@samrinagul7154 2 ай бұрын

now i am actually jealous of Havard students

@codeandtech77 2 күн бұрын

bro they get free gifts 😭

@taro7145 5 ай бұрын

Why does this guy knows everything?

@ProgrammerPenguin 3 ай бұрын

years of practise and learning.

@Harsh-uh6pf 5 ай бұрын

Please don't call John

@ethanfernandez3395 4 ай бұрын

john pork

@marwanium10 5 ай бұрын

Sam l🫶♥♥

@syedzainulabideen4455 6 ай бұрын

1like = 5pushups in 2024

@mdshahnawazalam4031 6 ай бұрын

😂

@encapsule2220 6 ай бұрын

Upload push ups or reported

@hetmanfoko 6 ай бұрын

Lemme join ya

@seeblu 6 ай бұрын

@@encapsule2220 accountability is key to sucess

@syedzainulabideen4455 6 ай бұрын

@@encapsule2220 okay I will make a video and prove before Feb 8 2023

@anekhan.4442 6 ай бұрын

Kindly make sure urdu caption is available it's hard for me to understand english 😢

@user-xs2ut1sy7i 6 ай бұрын

Does Sam have IG?

@sk45293 5 ай бұрын

Please don’t be creepy

@milanszekely9745 4 ай бұрын

She is annoying AF

@user-kh8jl1kz5w 19 күн бұрын

@@sk45293don't be jelaous, sam melts everyones heart down

@T....602 5 ай бұрын

I really dont like when the lecturers speak so fast .

@insidiousmaximus 5 ай бұрын

not all education can be done at the pace of the slowest members of society.

@milanszekely9745 4 ай бұрын

You can slow down the video.

@Coding-to4zj 5 ай бұрын

is this a kinderarden or university? we dont have enough time on planet to learn simple concepts with all these setups. there are much more complicated things that im sure you will skip even explaining let alone simulating and spending thousands of dollars to teach people. what a joke and waste of time. Thats why I never miss school.

@a23oj28 5 ай бұрын

Then do all the problem sets without watching it and see how you fare..

@Anna-pz9ry 4 ай бұрын

You don't have to be here. You can go to your genius school or wherever you think you belong rather than shitting on people who want to learn and the people who teach them.

@annyt4 4 ай бұрын

just a couple of fun 10 minute activities all of a sudden we have no time.. ok lol

@mariatanya3533 3 ай бұрын

Sounds like your mom didnt give you enough hugs as a child. Is she still alive? You can ask her for more hugs

@sayanbhaa 2 ай бұрын

good luck learning with that attitude

@MrGpButler 4 ай бұрын

I highly recommend that you call John's phone number.

@Magicninja01 3 ай бұрын

What will happen?

@MrGpButler 3 ай бұрын

I don’t want to ruin it for you. But it’s fun!

@user-uq6nk3fx1z 2 ай бұрын

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