Notes on Data Structures and Programming Techniques | Hacker News Reader

Notes on Data Structures and Programming Techniques

cs.yale.edu

276 pointsaportnoy27 comments

Is teaching people data structures and programming techniques in C really useful today? Yes I know C is used in many things still and in Linux. But there is far more variety in what people are paying programmers to use these days, most of them OO or Functional in nature, neither of which C is. Maybe there is no other common denominator language one could use that is more generally applicable? If you ignore Objective-C I haven't used plain C for anything at all since 1999 even though I used it for more than a decade from the mid 80's on as my only language.

I recommend reading the section on why C: section 1.4.1

Seems reasonable to me. We learn math by doing by hand, so we can understand the whys and how’s. This doc (and course), correctly or not, draws the same parallel with C.

I don't know of a better way to teach people how pointers work, and all the other low-level details that higher-level languages gloss over. Day to day, I agree, you're probably not going to want to be fiddling raw pointers unless you have to, but for pedadogic purposes, it's worth knowing. Particularly with so many languages building on C and C-isms.

> "I don't know of a better way to teach people how pointers work, and all the other low-level details that higher-level languages gloss over"

I definitely agree, but I'm not sure that a data structures/algorithms course is the best place to be teaching that. I don't know anything about Yale's CS curriculum, but I'd hope there's at least one systems programming course in there.

DSA problem set: http://www.techiedelight.com/list-of-problems/

UC Berkeley's class: http://datastructur.es/sp17/

This semester's: http://inst.eecs.berkeley.edu/~cs61b/fa17/

Like to mention this is with Java, and not C.

I've been pure C developer for 5+ years (worked with codebase of ~2.5 million lines of code) and I took a quick look (just out of curiosity) at the content and one thing immediately strikes me:

http://cs.yale.edu/homes/aspnes/classes/223/notes.html#What....

7.1 What's wrong with C

a) C doesn't have a garbage collector

Disagree that's it's wrong. If you code is well structured, then it's no big problem to avoid memory leaks. On top of that, you can use RAII if you are willing to use C-extensions like this one:

https://lwn.net/Articles/589433/

Garbage collector just helps you to write semi-workable messy code (a dream of industrial developers).

b) C doesn't support any kind of polymorphism

If you use type cast in well structured code, it's no big problem.

c) C doesn't have exceptions

This may be a bit tricky but you still can use exceptions in C using longjmp/setjmp:

http://www.di.unipi.it/~nids/docs/longjump_try_trow_catch.ht...

Although __cleanup__ extension doesn't work in this case.

It's worth to take a look at this stack unwinding library:

http://www.nongnu.org/libunwind/

Quote:

With libunwind, it is possible to implement an extremely efficient version of setjmp(). Effectively, the only context that needs to be saved consists of the stack-pointer(s).

In general, if you look at C as a high level assembler and willing to write or use existing low-level framework for "meta-language" primitives (like pointer virtualization), then you can write nice programs in your "meta-language".

For example, I wrote some project for fun using pure C with bare minimum libraries. And I needed to make sure that I could detect the following bug as soon as possible:

1. Object X is created and owned by some code OWNER_X;

2. Pointer to this object X is passed to some code USER_OF_X;

3. Object X is freed in OWNER_X;

4. New object Y is created in OWNER_X which happens to have the same address as recently freed object X;

5. Because of some bug USER_OF_X still uses pointer to object X;

I wanted USER_OF_X to fail on asserts as soon as possible if this happens. It would be hasty bug and hard to detect in unprepared code if X and Y happens to be the same type. When people are saying that it's nearly impossible to detect such bugs in C, they just don't consider using framework which cleverly detects this issue.

By the way, this is my implementation pointer virtualization which helps to detect this sorts of bugs:

https://github.com/hal9000xp/euclid/blob/master/core/main.h

Look at PTRID.

https://github.com/hal9000xp/euclid/blob/master/core/linked_...

Look at usage of PTRID in LL_CHECK

This is how I use them together:

https://github.com/hal9000xp/euclid/blob/master/core/network...

When do these frameworks become language extensions? There are always caveats to assertions about language features.

I read the Dynamic Programming section & I must say that it is very well explained.

Found a small issue. In Binary search section, it says ```{.c include=examples/binarySearch/binarySearch.h}```

Instead of the original code. I guess the page generator messed up a little.

Its messed up in a few places; the vim command descriptions for example.

Anyone know about a similar tutorial that's based around Rust?

good grief can we not have even a rudimentary CSS file to make this look at least a little bit readable?

I prefer this. It’s perfectly readable, scalable, and in the worst case I can apply my own styling.

I’m on an iPad, fwiw. Ironically one that usually gets some of the worst styling due to someone else’s opinion of readable.

Wouldn't it be fantastic if web documents had a simple set of well-defined markup elements, and you could choose to apply your own, user-defined styling on top? /s

This looks like the class I was hoping to get when I took algorithms and data structures, rather than a semester of CLRS being scrawled on the blackboard every lecture, mountains of proofs, and 0 lines of code.

Not that you are wrong for you opinion, but I feel differently. My data structures class was all programming, essentially just the professor writing code on the board for a linked list / trie / etc. after briefly describing it conceptually, and then having to implement the data structure and perhaps solve a problem with it for homework. My algorithms classes were all proof based / theoretical (the most applied problems asking you to come up with a "novel" algorithm to solve something, but still written). I felt cheated out of an actual class once I realized my data structures class could have been designed the same way. Coding the algorithms is usually the trivially boring or frustrating part to me; it's the actual design or concepts that I enjoyed.

Couldn't agree more. The data structures class I'm taking currently (which is unfortunately a prerequisite for most other CS classes) is simply a bunch of trivial programming exercises that take almost no effort to do. While I understand that everyone has different preferences and is at different levels of comfort with the concepts, I feel that a proof-based class would be much more fun.

Sounds like universities would benefit from having separate "learning tracks" for students of varying ability like in many high schools.

Or more realistically, taking a more layered approach to each course. So you could have the basic "code algorithm X to pass the tests" level (the kind of work most people will be doing later anyway), and then the "let's prove properties of X / come up with an alternative with the same properties" for people who can pass the first part in their sleep.

The best courses I've taken work like that already, plenty of extra challenges if you finish early. But it takes a dedicated instructor to make it work, and most of them unfortunately seem dedicated to getting by with minimum effort.

Maybe they should introduce a class about implementing algorithms and data structures for those who don’t find it straightforward.

My experience was that most people who ripped through the proofs were subseqently completely lost when they had to actually implement things in C later. They are different skills, and downplaying the importance of implementing on real hardware and programming languages and under real conditions does a disservice.

For instance, I recall my professor being wired up about some esoteric sorting algorithm, that had better asymptotic performance than qsort. Except, the constant factors involved in a real implementation made it slower for anything but stupidly big datasets. We spent like a week going over that one...

Just curious, did you already know how to code when you took your data structures class? And I mean not just write some basic programs, but really know how to code.

I ask because data structures usually comes in the 2nd or 3rd semester of a CS curriculum, and for most CS students, they can't apply the proofs and theory because it obscures where it applies in the problem domain. They can't draw the line between the theory and practical application, unless they already have written a good bit of code.

Maybe this doesn't apply to all CS students, but I would say the majority.

I enjoyed my Data Structures class quite a bit because the "thinking to programming" ratio was very high. More time thinking, less time working through the mechanics of the languages involved.

I think the OP is great for reading after you've taken the more formal class. The formal class deals with theory and pseudocode which gives you foundation, and the OP gives implementation in specific language.

I really think the two-semester approach works well. The first semester covers basics and intuition and tasks students to implement and extend. The second semester formalizes the material and tasks students to analyze and design algorithms to solve various problems. The first can be taught to first-years and the second to second- or third-years depending on when it's standard to take discrete maths.

What software did they use to generate this page? My first guess was org-mode, but it doesn't look like that. Maybe markdown + pandoc?

Ooop yep, pandoc. Don't know what the source format was yet though.

    <meta name="generator" content="pandoc" />

Reply on news.ycombinator.com