[HN Gopher] CS 61B Data Structures, Spring 2023 UC Berkeley
___________________________________________________________________
CS 61B Data Structures, Spring 2023 UC Berkeley
Author : curious16
Score : 290 points
Date : 2023-05-16 04:40 UTC (18 hours ago)
(HTM) web link (sp23.datastructur.es)
(TXT) w3m dump (sp23.datastructur.es)
| rtheunissen wrote:
| I can't believe they still teach red-black trees. The complexity
| distracts so much from learning. Both AVL and weight-balanced
| trees are simpler to implement and easier to understand.
| tptacek wrote:
| Red-black trees are much more common in the industry and have
| the advantage of building on 2-3-4 trees (though arguably the
| only reason to know 2-3-4 is red-black).
| [deleted]
| [deleted]
| blagie wrote:
| Here's my question:
|
| This seems wonderful for 2010.
|
| It's 2023. We have 3B1B, SoME, Python Tutor (which now does many
| languages), and various types of fairly smart tools to support
| kids as they're coding (e.g. Jupyter/Pluto-notebook style system,
| ones like Khan Academy, and ones with a split pane).
|
| Has this progress been applied to algorithms? If not, why not?
| ericjmorey wrote:
| I don't understand what your question is? How is the 2023
| course material taught at UC Berkeley being publicly accessible
| not exactly the thing you're asking about?
| blagie wrote:
| I'll simplify.
|
| In 2023, there are much more effective ways to teach computer
| science than tossing lecture videos up on a web site with
| homework assignments. MIT pioneered that in the nineties with
| OCW. It was a good idea at the time.
|
| Now, we have ways of doing online learning which are an order
| of magnitude more engaging, and lead to much better learning
| outcomes.
|
| I would never use the Berkeley stuff with kids. I might use
| it to help inspire what I do with kids. I would use many of
| the more animated, interactive things with kids, if
| available. I was asking if anyone has done that. If not, I'm
| surprised no one has done it.
|
| To be clear, I'm not dissing Berkeley for what they did here.
| Posting this sort of thing is great. It's just a tiny
| fraction of the impact of a real learning experience.
| xdavidliu wrote:
| > MIT pioneered that in the nineties with OCW
|
| It was early 2000s
|
| https://en.wikipedia.org/wiki/OpenCourseWare#History
|
| > The OpenCourseWare movement started in 1999 when the
| University of Tubingen in Germany published videos of
| lectures online for its timms initiative (Tubinger Internet
| Multimedia Server).[1] The OCW movement only took off with
| the launch of MIT OpenCourseWare at the Massachusetts
| Institute of Technology (MIT) and the Open Learning
| Initiative at Carnegie Mellon University[2] in October
| 2002.
| wayne-li2 wrote:
| Hi, I used to TA for 61B. This isn't an online course
| though. You'll notice a small detail at the top "245 Li Ka
| Shing" which is the lecture hall used.
|
| Granted most students don't attend because the lectures are
| diligently posted online on the website.
|
| What's not captured on the website are twice a week
| discussion small groups where one TA to 20-30 students work
| through problems in a group setting. There's a lot of
| collaboration and interactivity here. Then there's the once
| a week lab, where about 20-30 students go to a computer
| room and go through an interactive lab exercise.
|
| Then, there are the projects. Every CS 61ABC course is
| defined by their projects. These projects are the opposite
| of traditional learning. And 61B has done some of the most
| innovative projects I've seen in an educational context.
| For example, we had one semester where students grouped up
| and designed a rogue-like from scratch. There was a minimum
| rubric, but students were given the time to be extra
| creative, and we definitely saw that shine. It was a
| nightmare to grade though, but it was experimental and
| cool.
|
| So this website is just a small fraction of what the
| students experience. It's really just a schedule + lecture
| directory.
| cobaltoxide wrote:
| One of the lectures is actually "The Design of CS61B"
| which explains a lot about how the course is structured
| and how it has evolved!
|
| https://docs.google.com/presentation/d/1dWqymxQxZrMWYl76G
| fJo...
|
| In my mind this is the most interesting aspect of this
| course website - the meta reflection aspect.
| kyawzazaw wrote:
| Well, Khan Academy has this:
| https://www.khanacademy.org/computing/computer-science
|
| > It's just a tiny fraction of the impact of a real
| learning experience.
|
| Well, it's mostly intended for their students. The access
| is just open. It seems to work well for their students.
| infocollector wrote:
| I think students will benefit from an updated course for 2023
| for sure.
|
| > Has this progress been applied to algorithms? If not, why
| not?
|
| These are fairly recent and will take time to permeate.
| zamnos wrote:
| If you're volunteering to write a curriculum and teach classes
| there are _plenty_ of places that could use your help.
| tomrod wrote:
| > Has this progress been applied to algorithms? If not, why
| not?
|
| Not much money in academia since MooCs took a lot of the more
| motivated students, I reckon?
| dwrodri wrote:
| Has anyone had any success using course pages like this for
| guiding their FAANG interview prep? thinking about trying some of
| these projects to refresh my brain for an upcoming interview.
| tylerhou wrote:
| I wouldn't do 61B projects to learn how to interview; they
| aren't too relevant because they focus more on writing software
| rather than data structures (and aren't of the greatest quality
| IMO).
|
| The lectures on heaps, arrays, linked lists, and MST are worth
| reviewing. Also, I would try implementing each DS/A from
| scratch, and do Leetcode to brush up. If you want to learn
| algorithms super well, then do the first half of CS170 (stop
| after DP) from Berkeley, including the homeworks, which are
| challenging.
|
| Credentials: did undergrad at Berkeley, also worked at FAANG.
| kleiba wrote:
| Here's an interesting resource for those who like it formal:
| https://people.mpi-inf.mpg.de/~mehlhorn/ftp/Mehlhorn-Sanders...
| Al0neStar wrote:
| My favourite ds/algo book is "Algorithmic Thinking : A Problem-
| Based Introduction" [0] it was published in 2020 and it touches
| on competitive programming techniques in pure modern C (all the
| pure c ds/algo books that i know are outdated). A second
| edition is coming soon with 2 extra chapters [1].
|
| [0] https://nostarch.com/algorithmic-thinking
|
| [1] https://nostarch.com/algorithmic-thinking-2nd-edition
| lannisterstark wrote:
| If you're a starter, I would heavily suggest A Common-Sense
| Guide to Data Structures and Algorithms by Jay Wengrow
| instead. It's written in a fantastic, easy to understand
| style and actually goes over everything as it explains it,
| both code examples and visualizations.
|
| https://pragprog.com/titles/jwdsal2/a-common-sense-guide-
| to-...
| dataflow wrote:
| Cool! Peter Sanders is the same person who invented the awesome
| DC3 linear time suffix array construction algorithm (aka
| Karkkainen-Sanders).
| mailey wrote:
| speaking of, are there any benefits/disadvantages of learning
| data structures in java/python compared to C/C++ ?
| alex_lav wrote:
| Unsure why this is downvoted? This question seems reasonable.
|
| Personally I think Python specifically allows an easier
| understanding of the data structure in principal, but C/C++
| would create a better understanding of data structures as they
| operate with constraints like memory/resource availability.
| Kinda depends what you're after I think.
| cobaltoxide wrote:
| The data structures and algorithms themselves should be the
| same regardless of what language you are using.
|
| The bigger difference here would be C versus C++, as the
| language features present in the latter allow significantly
| more abstraction than the former. Implementing fundamental data
| structures in C can be very instructive but you will also spend
| more time on low-level details.
|
| With Java and Python you can ignore memory management to some
| extent, as these languages are garbage-collected. That could
| also be a plus or a minus depending on your point of view. When
| learning the subject, it might be better to be forced to do
| manual memory management, to learn about the pertinent issues.
| And then once in "production", you can appreciate the
| convenience of a garbage-collected language.
|
| When I studied EECS at Berkeley in the late 20th century, we
| used the following languages:
|
| 1. CS61A "Structure and Interpretation of Computer Programs" -
| Scheme/Lisp. Very highly abstracted from the machine details.
|
| 2. CS61B Algorithms and data structures - C++/Java. Allows
| "just enough" machine details.
|
| 3. CS61C Machine structures - MIPS assembly language and some
| C. All the machine details.
|
| 4. EECS 152 Computer Architecture - Implement a RISC/MIPS CPU
| and SDRAM controller using VHDL.
| SinePost wrote:
| This spring, I completed a data structures course at a large
| state school. We used Java at our university because Princeton
| did, and I imagine Princeton did because of the ease of
| segmenting concepts into classes because Java bytecode is the
| same between the students' devices and the machines which were
| used to grade their assignments (our grades were determined as
| a fraction of the number of test-cases our code would pass).
| markus_zhang wrote:
| I have to appreciate the intelligence of top notch CS school
| students. I once took the equivalent class in CMU and couldn't
| even complete the first assignment. Forgot which one but the last
| problem is too hard for me.
|
| Then I realized I better just study whatever I'm interested in
| and go back to algo if needed.
| mdaniel wrote:
| A reasonable person may ask whether a student's inability to
| complete the _first_ assignment is a failure of the student, or
| of the support structure (materials, lecture style, any
| applicable TA)
| markus_zhang wrote:
| I'm just using the online material, not as a student of CMU
| so I don't blame them.
| wodenokoto wrote:
| 101 is a beginners course. What is 61B?
| ar_lan wrote:
| 61B is the second beginners course of Berkeley Computer Science
| (61A being the first). This is essentially a 102 course.
| __init wrote:
| At Berkeley, course numbers >100 are upper-division, and those
| <100 are lower-division, introductory classes. Especially in
| the CS department, the upper-division courses are far from
| introductory. 61B is the the second in the 61A-B-C series,
| which is required for all CS majors. (A fourth lower-division
| class, CS 70 ("Discrete Mathematics and Probability"), is also
| required, but is independent of the 61 series.)
| cobaltoxide wrote:
| https://docs.google.com/presentation/d/1dWqymxQxZrMWYl76GfJo...
| mdaniel wrote:
| Wow, good for them teaching software engineering, and A++++ for
| the Ousterhout book <https://www.amazon.com/Philosophy-Software-
| Design-John-Ouste...>; I wish everyone would read it
| noobdev9000 wrote:
| Is there a point for working programmer to learn these in 2023,
| rather than just treating them as abstract interfaces?
| Myrmornis wrote:
| Much of the industry uses algorithm and data structure problems
| as a way of assessing "smartness" in interviews -- the idea is
| that even though it's often not needed for the job, giving
| people the challenge of learning that area at the intersection
| of computer science and software engineering correlates with
| how strong a contributor they'll be. I.e. if you don't know it
| but can pick up an area like that, that's a good signal. So a
| course like this (doing all the homework exercises) would
| definitely help with interviewing and getting jobs that people
| are competing for, if that is something that interests you.
|
| The actual content in this data structures course obviously
| will mostly not appear in any interview, but the homework
| exercises will make you stronger in a way that is definitely
| desirable for interviews. And of course, interviews aside, it
| will all be interesting for anyone that has an intellectual
| interest in software engineering.
| specialist wrote:
| Just like with dating preferences, leet code interviews are
| merely a fast rejection heuristic. Because there needs to be
| some kind of filter. And we haven't found any better.
|
| If we took more time, with dating and interviewing, we'd
| probably find a lot more diamonds in the rough. But ain't
| nobody got no time for all that.
| 2devnull wrote:
| "ain't nobody got no time for all that"
|
| Until interest rates get hiked.
| wayne-li2 wrote:
| I would say yes.
|
| The students are learning about lists, sets, and maps. These
| are so common that misusing this stuff can lead to big
| consequences during engineering design.
| Ar-Curunir wrote:
| A CS degree is meant to teach computer science, not just
| programming. Algorithms and data structures are the most
| fundamental concepts in computer science.
| papaver wrote:
| the difference is using tools vs building your own tools when
| you need to. the idea of these algorithms is not to memorize
| them but to understand how they are build and what goals they
| are trying to accomplish. understanding of the basic building
| blocks allows approaching and solving problems in a different
| light.
| jcranmer wrote:
| A working programmer probably needs to have the general
| rudiments of algorithmic analysis to write good code--to
| understand why a O(1) algorithm is usually better than an O(N)
| algorithm, to understand what makes an algorithm O(1) or O(N),
| and to understand the basic properties of the canned library
| functions they use.
|
| The basic list and map datatypes (array list, linked list,
| balanced search tree, hashtable) are good ways to get through
| these concepts, although hashtables and balanced search trees
| are in the oh-god-don't-ever-try-to-implement-these-yourself
| category. Graphs are also a pretty versatile data structure
| that has wide use, it certainly doesn't hurt to learn about all
| the algorithms already solved for graphs and how they might be
| adapted to your use cases. Tries, compression, and disjoint
| sets are I think a little too niche (although I do end up using
| disjoint sets a fair amount).
| Zvez wrote:
| I guess it depends on what you do and your goals. It might be
| not necessary to do average developers job (and full
| disclosure, it wasn't necessary 10 years ago as well). But
| understanding fundamentals gives you insights to be better
| prepared to choose right 'interface' when you need to. Also you
| can see it as a way to stretch your 'programmer muscles'.
|
| After going through lecture topics list, I think most of those
| you actually need to know as a working programmer. Not because
| they are prerequisites, but because after couple of years in
| the field, you will have to touch most of those topics anyway.
| jestarray wrote:
| how does it compare to princetons algorithms part 1 course:
| https://www.coursera.org/learn/algorithms-part1
| DesertVarnish wrote:
| I took this course with Hug many years ago. He's a truly gifted
| educator and I learned so much from the projects.
| slyrus wrote:
| I took this so many years ago I can't remember who taught it.
| Paul Hilfinger maybe? Microvax assembly language was a big part
| of the course, IIRC.
| ev7 wrote:
| I took it two semesters ago with Hilfinger and sadly didn't
| have any Microvax in it. You might be thinking of 61C, which
| deals more with computer architecture.
| slyrus wrote:
| quite possible! It was a long time ago :)
| er4hn wrote:
| A dead assembly language sounds like a Hilfinger thing.
| Taking 61B with him was an experience. He started by asking
| us to look to our left and to our right. He told us that one
| of us would not make it to the end of the class, with pride
| in his voice. He was right about that.
|
| In his defense he would also work very long hours answering
| emails from students. The night before projects were due he
| would hang out in his office all night in case people had
| questions. He'd return submitted code to you with detailed
| comments about how to write clean, readable code. More so
| than data structures I learned how to write readable code in
| that class.
| ssbash wrote:
| I also took 61B with Hug. I had Denero for 61A. Great
| professors. Berkeley is lucky to have to them.
| HammadB wrote:
| Announcements!
| FuckButtons wrote:
| I took it with hilfinger, solving the projects in 61b was
| probably the most fun I had at Berkeley (while actually working
| on class related things)
| projectileboy wrote:
| If you like this, I strongly encourage you to also check out
| Harvard's CS50. Lectures are all on YouTube.
| https://cs50.harvard.edu
| ericjmorey wrote:
| Or perhaps UC Berkeley's Structure and Interpretation of
| Computer Programs Course https://cs61a.org/
| _coveredInBees wrote:
| Highly recommend CS61A. Can't say enough good things about
| it.
| alex_lav wrote:
| I've been curious for a while now, if anyone's had success
| completing these courses via YouTube or open courseware or
| whatever, and citing them as a proxy to an actual undergrad
| degree on a resume. The content seems great, and other than, I
| guess, interaction with professors and other students, I'm
| unsure what the difference would be in outcomes?
| pamelafox wrote:
| For the full CS61A course experience, you would want to do
| the assignments and even try the exams, which are fairly
| difficult (they are the grade differentiator, for the most
| part). I wrote up a post about how to audit 61A as an
| external learner: http://blog.pamelafox.org/2022/07/how-to-
| audit-cs61a.html
|
| (I taught it for a few semesters)
| projectileboy wrote:
| It's a good question. I took it as an Extension student
| working on a degree, but if you made yourself do the
| assignments, you'd have much the same experience. The only
| thing you'd miss are sections with a TA, which is valuable,
| but I think you could replicate with a study group.
| adamangle wrote:
| great course
| bloemheuvel1 wrote:
| could somebody explain how to recreate his coding environment in
| sublime text? looks very nice for learning and following along.
| pigsinzen wrote:
| > in sublime text?
|
| Not sure if you're under the impression that he is using
| Sublime Text or we're looking at different editors. In the
| video from his second class, it looks like he is using a
| Jetbrains[0] product.
|
| [0] https://www.jetbrains.com/
| barbecue_sauce wrote:
| In the first class, he uses Sublime Text.
| game_the0ry wrote:
| Forgive me for the ignorance (I'm a front end dev), but can
| someone explain to me why this made it to the front page of
| hacker news when there are already many resources for learning
| data structures?
|
| I feel like I could just go through the docs for for java /
| kotlin collections lib and cracking the code interview, and get a
| good understanding of DS / algos. What would this offer beyond
| that?
|
| (this is a genuine question, btw, no sarcasm, there is something
| here that is resonating with other folks, but not me and I would
| like to know what that is)
| WoodenChair wrote:
| > I feel like I could just go through the docs for for java /
| kotlin collections lib and cracking the code interview, and get
| a good understanding of DS / algos. What would this offer
| beyond that?
|
| Reading the Java standard library documentation will teach you
| what pre-made data structures are available to you, but will
| not teach you how they work under the covers, or why they work.
| Reading Cracking the Coding interview will help you use data
| structures and algorithms specifically in the context of
| applying for jobs. If you want a deeper understanding you
| should do a course/tutorial/book that is more focused on the
| fundamental problem solving techniques like the linked Berkeley
| course.
|
| In the book realm, I recommend Grokking Algorithms for a gentle
| introduction, or Algorithms by Sedgewick and Wayne for a deeper
| understanding. My own book, Classic Computer Science Problems
| in Java, is a gateway to the wider world of computer science.
| Yet, for sure this deeper understanding is not necessary for
| the majority of day-to-day dev work. However, if you have a
| curiosity, want to work on more fundamental problems, or be
| sure that you are always doing things the most efficient way
| possible, it is necessary.
| quadrifoliate wrote:
| > I feel like I could just go through the docs for for java /
| kotlin collections lib and cracking the code interview, and get
| a good understanding of DS / algos. What would this offer
| beyond that?
|
| It offers video lectures -- did you look at the link?
|
| Not everyone learns the exact same way. Maybe this is upvoted
| because people (on aggregate) prefer the course's contents over
| reading through Java libraries?
|
| Also, honestly, language libraries can be hit-or-miss in terms
| of algos since they reward optimization over simplicity.
| Python's standard sort (apparently Java's too?) for instance is
| Timsort [1] -- not necessarily what you want for an
| introductory course.
|
| ----------------------------------------
|
| [1] https://en.wikipedia.org/wiki/Timsort
| tylerhou wrote:
| CTCI is not really useful for learning data structures, and I
| personally don't think it's a great book for learning how to
| interview either. Leetcode IMO is more effective, and once you
| feel comfortable I would look at classes like 61B and 170
| (another Berkeley CS class) because they teach you the details
| of how data structures and algorithms work.
| Aaronstotle wrote:
| Go bears
| ulfw wrote:
| Oh man that brings back nostalgia from my 1997/98 student days.
| CS61B was okay. But I still have nightmares from CS61A which was
| taught in Scheme back then. I've hated recursions and using an
| ((excessive amount) of brackets) ever since.
| cobaltoxide wrote:
| Oh man I am sorry you had that experience. I look back on CS61A
| with SICP in Scheme (taught by Brian Harvey) as one of the most
| enjoyable and enlightening experiences of my college academic
| career.
___________________________________________________________________
(page generated 2023-05-16 23:02 UTC)