Notes on Data Structures and Programming Techniques

[coldcode]

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.

[falcolas]

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.

[megaman22]

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.

[abhimt]

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

[rosstex]

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

[QML]

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

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

[hal9000xp]

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

[xapata]

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

[abhas9]

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.

[Normal_gaussian]

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

[sigttin]

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

[plg]

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

[falcolas]

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.

[megaman22]

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

[megaman22]

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.

[opportune]

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.

[mathattack]

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.

[TrueSelfDao]

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.

[smashem]

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.

[codemac]

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?

[codemac]

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

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