CS 61B Data Structures, Spring 2023 UC Berkeley

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

> 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

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.

Data structures are often the key to making things fast. Knowing which and why is important. Courses like this are also very well organized and delivered making time spent learning this content more rewarding.

Cool! Peter Sanders is the same person who invented the awesome DC3 linear time suffix array construction algorithm (aka Kärkkäinen-Sanders).

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

Probably the software book that has influenced my practice the most. Fantastic writing, and not too long either.

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.

I also took 61B with Hug. I had Denero for 61A. Great professors. Berkeley is lucky to have to them.

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)

Or perhaps UC Berkeley's Structure and Interpretation of Computer Programs Course https://cs61a.org/

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?

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.

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?

If you're volunteering to write a curriculum and teach classes there are plenty of places that could use your help.

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

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)

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.

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

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

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.

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

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.

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.

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

61B is the second beginners course of Berkeley Computer Science (61A being the first). This is essentially a 102 course.

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.

A CS degree is meant to teach computer science, not just programming. Algorithms and data structures are the most fundamental concepts in computer science.

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.

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.

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

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.