Introduction to Algorithms - Problem Session 1: Asymptotic Behavior of Functions and Double-ended...

Sdílet
Vložit
  • čas přidán 12. 09. 2021
  • MIT 6.006 Introduction to Algorithms, Spring 2020
    Instructor: Jason Ku
    View the complete course: ocw.mit.edu/6-006S20
    CZcams Playlist: • MIT 6.006 Introduction...
    Four examples of worked problems on the asymptotic behavior of functions and double-ended sequence operations.
    License: Creative Commons BY-NC-SA
    More information at ocw.mit.edu/terms
    More courses at ocw.mit.edu
    Support OCW at ow.ly/a1If50zVRlQ
    We encourage constructive comments and discussion on OCW’s CZcams and other social media channels. Personal attacks, hate speech, trolling, and inappropriate comments are not allowed and may be removed. More details at ocw.mit.edu/comments.

Komentáře • 126

  • @famguy218
    @famguy218 Před 2 měsíci +14

    I had undiagnosed ADHD until I was 22 and ruined my college experiences. I was not able to properly learn computer science in college and it heavily affected my ability to strengthen my career. These videos and open courseware is helping me re-learn the material I never properly learned and giving me another chance at learning computer science and how to be a better programmer. I don’t know why these amazing videos and coursework are posted for free, but I can’t thank you enough for it

  • @The-Funk35
    @The-Funk35 Před 4 měsíci +12

    Me, wanting to revisit algorithms and data structures.
    Lecture 1: Course introduction, alright makes sense.
    Lecture 2: Data structures. Alright cool. This is all making sense. I coulda gone to MIT.
    Lecture 3: Jason, " *math* Does that make sense?" Me: "Absolutely not, I haven't taken a math class in over 10 years."

  • @Michael-ur3zs
    @Michael-ur3zs Před 2 lety +124

    I really wish the OCW camera people would stop zooming in and out and not showing the problems as they're discussing. They always seem to put a strong focus on zooming tracking the professors movements as they pace around. Not sure what they think makes that style better when recording a lecture for students.

    • @thinkGrey_
      @thinkGrey_ Před 2 lety +7

      I think it is automated system

    • @Christopher_Cole
      @Christopher_Cole Před 2 lety +15

      I agree. Some people might not know, but the problem set is given in the video description. "View the complete course" is the link, and then the Problem set will be under "Course Features." I've only gotten ten minutes into the video, but I've basically just been looking at the problem set and listening to his input.

    • @Christopher_Cole
      @Christopher_Cole Před 2 lety +7

      Turns out they aren't using the Problem Sets in this video. They are using the practice problems. (Listed on the left hand side of course page) Problem Sessions use Practice Problems, which are meant to help with understanding/solving the Problem Set which is probably harder.

    • @ravierkonan1694
      @ravierkonan1694 Před 2 lety

      Maybe it is automatic based on facial recognition. For this case we can't really understand.

    • @Xaminn
      @Xaminn Před 2 lety +1

      Agreed. I left the video for this reason alone.

  • @kz_cbble9670
    @kz_cbble9670 Před 2 lety +43

    00:00 problem 1
    23:19 problem 2
    36:48 problem 2.1
    45:41 problem 3
    1:07:40 Problem 4

  • @manoloeso2633
    @manoloeso2633 Před 11 dny

    This is incredible! I can attend the best university lectures without spending a penny. I can't believe it!. You are contributing to the development of the whole world.
    Thank you.

  • @DmitryStepanov-mo6wt
    @DmitryStepanov-mo6wt Před rokem +17

    You have so amazing atmosphere of lecture, it is really exciting... I want to go MIT since that...

  • @LEI8037
    @LEI8037 Před rokem +3

    Loved the way you are teaching Jason Ku

    • @MegaDonaldification
      @MegaDonaldification Před 2 měsíci

      for those new to algorithm, this is definitely not fun. If you struggle with pointers, dynamic arrays, proof, and geometric series, including not following or preparing ahead of time, it becomes very difficult to follow.

  • @anuragbhakuni3494
    @anuragbhakuni3494 Před 2 lety +59

    Those who still have doubt on Amortised time:- let take an example of the dynamic array, we usually insert operation in O(1)(constant time) but at the end of the array, we need to take an array (double the size of the present array), copy all element to it and then insert. so this particular operation takes a liner time, but as we doing the insertion many times,, this bad operation(in terms of time) has less effect on the time complexity of the complete insertion process.

    • @sarmadsultan7981
      @sarmadsultan7981 Před rokem +1

      ty

    • @vallurudevesh1498
      @vallurudevesh1498 Před rokem

      bro!!!! good explanation

    • @alfredwindslow1894
      @alfredwindslow1894 Před 4 měsíci +1

      To provide a more rigorous proof. We can imagine continuously inserting to the array would have the following sequence w.r.t. the number of operations:
      1, 1, 2, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 8, …
      Inserts usually take constant time, however when we fill the array we need to double the size taking linear time.
      This sequence has a sum such that the sum up to 2^n insertions is ~1+2+4+8+…+2^n
      Taking the sum of the geometric series we get 2^(n+1) - 1, and dividing by the 2^n sums giving the average sum would be 2 - 1/(2^n).
      As n gets large, i.e. as we do more and more insertions, we can see that the average time per insertion would approach 2, and therefore be constant time.

  • @irispallis
    @irispallis Před rokem +6

    I wish the camera could stay where it was on the blackboard. I need to understand what the instructor explains about what he drew/wrote, not where he moves or what his facial expression looks like. However, I like the lecture. please consider this for the next records.

  • @hyunkwak6569
    @hyunkwak6569 Před 2 lety +17

    For those wondering about the relation in 7:02 a proof is provided in recitation1 exercise 5 (page 6 of 7)

  • @supermanwang
    @supermanwang Před 9 měsíci +1

    Mr.Ku's handwriting is great!

  • @jackmiller9829
    @jackmiller9829 Před 2 lety

    this helps my further year courses, thank you

  • @bmatachieve9549
    @bmatachieve9549 Před 2 lety +3

    Thank you professor.

  • @datioepicplaystv2145
    @datioepicplaystv2145 Před 2 lety +27

    Not sure why i clicked on this video, now i know that i know nothing about math

    • @floormop6672
      @floormop6672 Před 2 lety +4

      Same. I’m high asf rn trying to understand this

  • @leomysky
    @leomysky Před rokem +1

    So cool
    Thank you for this knowledge

  • @wingsonthebus
    @wingsonthebus Před 2 lety +2

    10:42 aaaaaaaaaä this makes so clear this formula i’ve always found so confusing

  • @geekyprogrammer4831
    @geekyprogrammer4831 Před 2 lety +28

    This course is going to be legendary as 2011 version 🤓🤓🤓

    • @ricsip
      @ricsip Před rokem +3

      is the 2011 version and this 2020 version talk about the same topics? Are they more than 90% overlap, so its enough to watch only one of them, or the topics were modified for the 2020 version compared to the 2011 sessions?

    • @conchobar0928
      @conchobar0928 Před rokem +2

      @@ricsip Did you figure out an answer?

    • @Leo-io4bq
      @Leo-io4bq Před 8 měsíci +1

      ​@@conchobar0928Did you figure out an answer?

  • @suindude8149
    @suindude8149 Před 2 měsíci

    The linear sequence generator like any function based on the size of a problem set increment.
    As suppossing the increase in number of element in a Linked list or Queue,thus increasing the complexity of a case of problem like a Chess problem or the well known Diners Bankers Reader Writers problem in sync.

  • @w1d3r75
    @w1d3r75 Před 2 lety +6

    Such a likeable guy

  • @brettpowers2748
    @brettpowers2748 Před 2 lety

    Title was vague but I was not disappointed. Great explanations here.

  • @enisten
    @enisten Před 2 lety +20

    Recitation videos are available for the 2011 iteration of the course. I haven't checked, but they may correspond roughly to the unrecorded recitation videos of this iteration. czcams.com/play/PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb.html

  • @cosmicsans3275
    @cosmicsans3275 Před 2 lety +19

    His face in the thumbnail reminds me of nevil from icarly lol

    • @CameronCobb
      @CameronCobb Před 2 lety

      Lol

    • @Alex-xi3bw
      @Alex-xi3bw Před rokem +2

      I was literally going to comment that this guy reminds me of nevil lmao

  • @vam8775
    @vam8775 Před rokem +2

    This playlist is the ultimate resource for every passionate computer science engineer.... 🔥🔥❣❣

  • @sharingan998
    @sharingan998 Před 2 lety +2

    thank you, ocw

  • @muhamadsh4683
    @muhamadsh4683 Před měsícem

    ‏‪11:59‬‏
    Thats the combinations formula not the permutations i think.
    Thanks for the content.

  • @suindude8149
    @suindude8149 Před 2 měsíci

    Its so simple to find out the first and last position in say t times,then the swaping time is T.Thus,we can finish the problem in the summative.

  • @cirilocanganjo7957
    @cirilocanganjo7957 Před rokem

    Congrats!

  • @bidal2248
    @bidal2248 Před 5 měsíci

    It's so interesting class!!!

  • @suindude8149
    @suindude8149 Před 2 měsíci

    so by comparing the growth rate hence the time complexity calculation we can arrange the functions.
    We can say the limit of the n thus the best and worst case complexities.
    Thus,we can make comparison.

  • @think_n_code
    @think_n_code Před 2 lety +4

    I like this lecture.
    There is another approach to reverse a singly linked list (without extra memory space): just pointers, without including the size of the list.
    I think is easier to understand.
    Isn't it?

    • @ShubhamKumar-ex3nk
      @ShubhamKumar-ex3nk Před rokem +2

      yes using extra pointer

    • @pierreollivier1
      @pierreollivier1 Před 10 měsíci +1

      you can also use recursion, you return the current node when your next node is equal to NULL, and then you simply assign to your next node->next the address of the current (aka the previous) node.
      node *list_reverse(node *current, node *next)
      {
      if(next == NULL)
      return (current);
      list_reverse(next, next->next);
      next->next = current;
      return (current);
      }
      this is quite efficient, because you itterate the list once and assign also once.

  • @suindude8149
    @suindude8149 Před 2 měsíci

    The k-1 and so on gives the same pattern hence that will be true for kth value as well.
    Thus,we may get another estimation of how the func progress with the increasing size,its theethod of induction.

  • @suindude8149
    @suindude8149 Před 2 měsíci

    Linked list has a space complexity problem wrt tge Dynamic array.
    The excessive space of 2 or double 4 sometimes creates a huge space complexity in Linked list as the size increases.

  • @terasoft-official
    @terasoft-official Před 8 měsíci +1

    Great lecture, except the black board was never in focus of camera, and that made me uncomfortable.

  • @CandyLemon36
    @CandyLemon36 Před 7 měsíci

    This is a remarkable body of work. I read a matching book that was enlightening. "Game Theory and the Pursuit of Algorithmic Fairness" by Jack Frostwell

  • @AviPars
    @AviPars Před 2 lety

    Amazing

  • @edmbootcamp6188
    @edmbootcamp6188 Před 2 lety +2

    Love this guy hahaha

  • @abdelaziz2788
    @abdelaziz2788 Před 2 lety +28

    i will tell my kids i was here before 300 views

  • @kharraz1713
    @kharraz1713 Před 11 měsíci +1

    Great lecture, but i don't understand problem 3.. can anyone explain it to me

  • @saigowthambabuamburi6158

    Does anyone know, how can we find the videos for Recitation? Thank you.

    • @mitocw
      @mitocw  Před rokem +2

      The recitations aka Problem Sessions are in the CZcams playlist: czcams.com/play/PLUl4u3cNGP63EdVPNLG3ToM6LaEUuStEY.html. Best wishes on your studies!

  • @ashishbhandari8792
    @ashishbhandari8792 Před 2 lety

    Done!!

  • @BAEESCOPE2010
    @BAEESCOPE2010 Před 2 měsíci

    Algorithms is a science, handling a camera is common sense!

  • @sherifatef2906
    @sherifatef2906 Před rokem

    Can anyone explain to me how the first element of a data structure gonna be the last element after applying the algorithm on 00:44:00?

  • @donovantheprogrammer2989
    @donovantheprogrammer2989 Před 2 lety +6

    Why do I feel like there were about 5 lectures missing between the last lecture and this lecture?

    • @mitocw
      @mitocw  Před 2 lety +11

      According to the course calendar, you should have watched lectures 1 and 2. See the course on MIT OpenCourseWare for more info and materials at: ocw.mit.edu/6-006S20. Best wishes on your studies!

    • @platoso
      @platoso Před 2 lety +1

      The course also includes recitations which were not recorded. You can either read the recitation notes (founded under Resource Index) or try watching the recitation vides for the 2011 iteration of this course - hopefully this helps.

    • @Karim-nq1be
      @Karim-nq1be Před rokem +1

      If that's the case, I think you should probably have a look at some of the courses of 6.042J Mathematics for Computer Science.

  • @risithroy4558
    @risithroy4558 Před 2 lety +1

    Can someone pls explain line 11 a1 1:23:13? Thanks

  • @Lol..No.
    @Lol..No. Před 2 lety +6

    Damn, wish I understood 1/4 of this.

    • @mihuhih2186
      @mihuhih2186 Před 2 lety

      try to google keywords from his presentation. there is a lot of better explanations everywhere online

    • @stephan8294
      @stephan8294 Před rokem

      before taking this lectures it's best to learn about discrete maths and linear algebra i think

    • @OhmVibe
      @OhmVibe Před 9 měsíci +1

      conscious incompetency > unconscious incompetency

  • @hellswhite383
    @hellswhite383 Před 2 lety +4

    Got the first problem right, second problem has stumped me so far, as I forgot what those compound(I think) numbers mean. Don’t really remember the ! either for that matter, though I think my guess is pretty good.

  • @petarkonj8979
    @petarkonj8979 Před 9 měsíci +1

    why the fuck is camerman filming him instead of what he writes on the table (when he writes)

  • @kamikamen_official
    @kamikamen_official Před 7 měsíci

    Is there a reason why we'd prefer a recursive implementation to the iterative solution? In this case I feel like the iterative solution is actually more elegant, isn't it? (Problem 1-2 b)

    • @yepstill8773
      @yepstill8773 Před 7 měsíci

      Yeah and then on the singly linked list reverse algorithm he used an iterative version instead of the recursive version which is way more intuitive and elegant for that case(in my opinion anyways). Kinda weird.

  • @itsdavidalonso
    @itsdavidalonso Před 2 lety +1

    I wish the camera man wouldn't be constantly panning and zooming and let us see the blackboard at all times

  • @jonalderson5571
    @jonalderson5571 Před 2 lety

    Wow, JUST before Covid

  • @jayeshwaghmare2989
    @jayeshwaghmare2989 Před 2 lety +3

    Read CLRS along with the lectures, it was helpful for me

  • @user-ib5ml1vz5r
    @user-ib5ml1vz5r Před rokem +1

    Spoiler: this lecture does make sense.

  • @nikhilsannat5429
    @nikhilsannat5429 Před 2 lety +2

    Is there any Recitation Video? Like 2011?

    • @mitocw
      @mitocw  Před 2 lety +7

      There are no recitation videos but there are recitation notes: ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-spring-2020/lecture-notes/. Best wishes on your studies!

    • @dejidevi3990
      @dejidevi3990 Před 2 lety +2

      @mit open courseware,plzz upload recitation videos also.

  • @stepphenschaf668
    @stepphenschaf668 Před 2 lety +1

    This Professor gives me serious Michael Reeves vibes

  • @crylater8200
    @crylater8200 Před rokem +1

    can the public get access to the problem sets?

    • @mitocw
      @mitocw  Před rokem +7

      Yes, the problem sets are available. View the course materials on MIT OpenCourseWare at: ocw.mit.edu/6-006S20. Best wishes on your studies!

  • @MegaDonaldification
    @MegaDonaldification Před 2 měsíci

    First of all, Prof Jason, I appreciate your energy and time you spent pouring your experience on the newbies
    Docky is not living anything apart from the titles and what he wants in the project or coursework. Some students will leave the class to prepare for it - this is a bad idea. Some will read before hand since they have the scheme of work - the best idea. A few will take down keywords and few notes and probably research it on chatGPT right there and then.
    In summary, preparing before hand is the best answer to this professor's lecture. Breath and strength wont find their way into you if you don't walk the longsuffering walk of suffering in patience. You must be 2-3 steps ahead in the Introduction to Algorithms textbook if you want to understand, implement, and have excellent grades in this beautiful, inductive lectures in algorithm. To pass this course, you must swim in it first and walk through the questions later. I looked at the course table of content, then realised it is the same material found in Leetcode or Neetcode.

  • @p3878
    @p3878 Před 2 lety

    Reminds me of Scipio Prime

  • @shimonbrandsdorfer9427

    The last problem works the same for lists with a size of an odd number?

    • @emmafountain2059
      @emmafountain2059 Před rokem +1

      No, but the problem specifies that there are 2n students in line, so we know its an even number. You could slightly modify the approach to make it work with some if else statements but that's kinda just unneeded complexity.

    • @MrJesterboi
      @MrJesterboi Před rokem

      No but it only doesn't work because you're flooring n / 2. You would need to decide what you consider the middle element that will be the end of the first unreversed section of the list.

  • @whicencer8819
    @whicencer8819 Před rokem

    why (n 3) = θ(n^3)? Can someone explain me this moment please?
    On 16:20

    • @LearnMoreBeWater
      @LearnMoreBeWater Před 5 měsíci

      n choose 3 = n(n-1)(n-2)/6.
      So, n choose 3 is big theta of n cubed

  • @brandonwallace8817
    @brandonwallace8817 Před 2 lety

    How does he get n+1 n and n-2 over 6 @ 16:05, I get how that will give us n cubed just how he got that from that I don't follow

    • @charanreddy2113
      @charanreddy2113 Před 2 lety

      I’m asymptotic notation we ignore the smaller terms so we only consider the largest term . In this case it’s n cube

    • @Alex-xi3bw
      @Alex-xi3bw Před rokem

      It's hard to explain in text, but organic chemistry tutor has a good video on factorials on youtube that explains it well. Basically, n! in the numerator can be re-written as n(n-1)(n-2)(n-3). The (n-3) in numerator and denominator then cancel each other out, leaving you with just n(n-1)(n-2) in the numerator.

  • @Pradeeppadmanabanofficial
    @Pradeeppadmanabanofficial Před měsícem

    where are the python files for this problem i searched opencourseware i could not find it

    • @mitocw
      @mitocw  Před měsícem +1

      The problem set python files are in the zip files: ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/pages/assignments/. Best wishes on your studies!

  • @prudhvir3ddy
    @prudhvir3ddy Před 2 lety

    this guy acted in movies ?

  • @howtrue3140
    @howtrue3140 Před 2 lety

    Great content but you need to reformat the videos to reduce data and space complexity because Data is too expensive this side..there is no way i can afford 941mb to download a 1:26:37 minutes video .. atleast if it was

    • @kael7953
      @kael7953 Před 2 lety +4

      May be you don't have to download and just use wifi?

    • @kevinquiroscanales6240
      @kevinquiroscanales6240 Před rokem +1

      @@kael7953 I think he only has access to mobile data where he lives, but I would still just recommend donwloding a slightly worse resolution of the video and it works just fine for many of the problems.

  • @user-bv3gf2ix6c
    @user-bv3gf2ix6c Před 2 lety

    hi guys any one here can tell me why he use theta symbol replace n log(2 pi
    n/e)

    • @Millicx
      @Millicx Před 2 lety

      It's used to explain the time complexity of an algorithm

    • @The_Digamma
      @The_Digamma Před rokem

      because its the tight bound of n log(n).
      tight bound happens when the O(f) = Ω(f)

  • @manishkasera8584
    @manishkasera8584 Před rokem

    30:11 Savage

  • @forheuristiclifeksh7836
    @forheuristiclifeksh7836 Před 7 měsíci

    0:28

  • @Reppintimefitness
    @Reppintimefitness Před 2 lety +1

    I teach fitness

  • @IZIKI-399
    @IZIKI-399 Před 10 měsíci +1

    One moment appreciating the Muslims for inventing algorithms.

    • @FlyingPetal
      @FlyingPetal Před 2 měsíci

      Khwarizmi was persian and so am I(I know our history well). It has nothing to do with the F***ing Islam.

  • @mhd-em6yt
    @mhd-em6yt Před 2 lety +2

    er ist ein Kind ?!!

  • @behrozkarim8588
    @behrozkarim8588 Před 3 měsíci

    Python is the worst programming language to learn data structures

    • @doublelol
      @doublelol Před 3 měsíci +2

      True. But this course focuses more on the theoretical concepts behind data structures and algorithms. With the knowledge you gain by completing psets you should easily be able to implement any data structure in any programming language.

  • @somebodyoncetoldme1704
    @somebodyoncetoldme1704 Před 10 měsíci +1

    Fire the camera man