Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

Control Flow

2 (2.2%)

Arrays, Strings, Pointers, and References

8 (9%)

Functions

4 (4.5%)

Basic object-oriented programming

30 (33.7%)

A bit more advanced OOP (Composition, Operator overloading, Inheritance, Virtual Functions)

18 (20.2%)

Templates

8 (9%)

Other (Explain)

4 (4.5%)

Working with files?  (Streams)

15 (16.9%)

Total Members Voted: 89

[eerr]

<
Yes, I was wrong. I have been wrong before, but I knew this time there was a strong chance I was wrong.
Why did I say something I clearly don't know? I don't know C++ I have learned nothing about it. The only thing that I could really be certain of is saying that objects should not be treated like structures.

Blacken is just a dude who knows what he's doing.

[DrPizza]

The only thing that I could really be certain of is saying that objects should not be treated like structures.

That doesn't really make a lot of sense. What do you mean by "object", since clearly your terminology is not that used in C++.

[Normandy]

I think he's referring to making a clear delineation between POD-types and object types.

[Blacken]

Back on topic....  Something Blacken pointed out to me via PM, the more coding-trick-based challenges (I.E. "write a quine") aren't particularly helpful as far as actually progressing your skill.  They're far from useless, I thoroughly enjoy them, but if you're only doing the challenges to try to further yourself, you'd probably be better off tackling more generally applicable challenges, I.E. algorithm design, or data structures (such as linked-lists, trees, etc) and how they work.

The challenges Alexhans wrote up in the original post would be a great launching point for someone fairly new to a language, since they'd teach input/output, parsing (and the high resolution timer thing is just useful in general).  Perhaps we should try to put together some increasingly complex challenges along similar lines?  Seems to me a series of challenges that teach a language, but force the user to learn to "RTFM/STFW" rather than just copying code from a tutorial, would be a far more effective teaching device anyways.  Besides, it'd be a far more constructive way to funnel the talents of the more experienced programmers (which I am most definitely not, although I'd be glad to help in whatever way I can). 

Meh, just my two cents, take it or leave it, for what it's worth.

This is the best post in the span of multiple pages, and not just because I'm cited in it. (Unbunch your panties, you lot, that was a joke!)





Now for the new best post.

Algorithms and data structures, not quines and minor string manipulation, are how you learn to work regardless of language. While I strongly advocate avoiding C/C++ for newbies, this is due mostly to both being terribly inconsistent with themselves and with everybody else; virtually any other modern language (except maybe Perl and PHP) are about equivalent as far as I'm concerned. If you know how to write a binary search tree in Python, you can do it in Java or C# or whatever else very trivially. (You can write it in C++ without too much trouble either.)

If you want a solid, rigorous set of exercises that will drive home most of the core essentials, here's one. If you follow this list, do yourself a favor and don't skip any even if you think you know them; I promise, it'll make sense, I've taught this shit before and this is a slightly simplified port of my outline for when I was teaching this stuff. Reuse of your own code (if you've already written a single-linked list, for example), is fine. Some of them are decidedly nontrivial exercises, but they should all be relatively doable in the given order. If you want to look up others' code to see how they did it--go for it.

This is basically the first three semesters of computer science at my university, so if you can master this, you'll be in a great place if your intention is go to college for computer science or for programming.

I encourage you to post your answers to the non-code questions here (yes, qwertyuiopas, it's still a "programming challenge," about 70% of programming is writing what you think and documenting what you did), but please put them in spoiler tags. (I'd appreciate it if you'd keep my numbering system and mark that outside spoiler tags, so we can all be sure of exactly what you're working on.)

If using C++, use references instead of pointers at all times unless indicated otherwise. There is a reason for this; you'll figure it out as we go along. If your language does not support generics (C++ templates count), then you need a different language--sorry.

• Build a singly-linked list class (should be doable in two classes: list and node). This linked list should accept integers as data values. With this singly-linked list, do the following:
  
  • Read up on Big O notation. Make sure that you're familiar with the difference between Big O runtime and Big O space complexity; both can be important.
  • What is the Big O runtime of searching your list?
  • What is the Big O runtime of inserting an element at the beginning of the list?
  • The end of the list?
  • The middle of the list?
  • (really easy one) What is the Big O space complexity of your list?
  • Build an iterator for this list. This iterator should not have a publicly accessible constructor; a nested class is likely the easiest way. They will be created by the list's main class and returned for user manipulation.
• Build a doubly-linked list, and then an iterator for that list.
• Build a vector of integers (an automatically resizing array). Keep in mind that having to resize with every add kind of sucks; you may want to add some reserve space with every resize.
  
  • Read this explanation about amortized Big O. Why is this relevant to building a vector?
  • What's the amortized Big O of insertions on this vector?
• Build interfaces (abstract classes in C++, interfaces damn near everywhere else) that expose a sane API for a tree. I will stress again that this is an interface; if you have any logic code in this class you did it wrong. This tree should accept integers as data values.
• Build a binary tree that implements your interface from #3.
  
  • Write depth-first traversal algorithms: preorder, in-order, and post-order.
  • Write a breadth-first traversal algorithm.
  • Write an iterative traversal algorithm. (There's pseudocode there, but figure out why you do it that way.)
• Inherit from your binary tree and build a binary search tree. (This will require additional extension of the API. That's OK.) This tree won't balance itself. That's OK. We'll do that next.
  
  • Assume you have a balanced tree. What is the Big O runtime for finding any node (a behavior that I will refer to from now on as "Big O for searching")? (Another way of putting it, to perhaps help with a little confusion, is "what is the Big O runtime to discover that a node is not in the tree?")
  • What is the degenerate case of a binary search tree? What is the Big O for searching of the degenerate case?
• Since we've identified the degenerate case for a binary search tree, let's make sure we don't have that. Inherit from your binary search tree and build an AVL tree. This will be the hardest exercise yet for people without a lot of algorithmic background. Don't worry, they just get nastier from here.
  
  • How does this prevent the degenerate case?
  • Why are the Big O for searching, insertion, and deletion all O(log n)? (I ask this because Wikipedia shows them all on the page I just linked.)
• Hope you liked the AVL tree. We're now going to build the other "easy" binary search tree: the red-black tree. A poem from a professor of mine:
  
  From black root to tips,
  black nodes agree: New leaves turn
  red; from red, all black.
  
  
  • Why are the Big O for searching, insertion, and deletion all O(log n)?
• Go back to your binary tree (not your binary search tree) and inherit from it to build a binary heap. Min-heap or max-heap, doesn't matter to me, although you could do both as separate classes.
• Alright, let's step back from data structures for a moment (don't worry, we'll head back there) and look at algorithms. Using only one array, implement selection sort.
  
  • Selection sort has an O(n²) runtime. Why is it still taught?
  • In what situation is a selection sort going to be useful?
• Implement insertion sort.
  
  • Insertion sort has an O(n²) worst-case. What differentiates it from selection sort? (Hint: read about adaptive sorts.)
  • What is an online sort? Why does this matter?
• Using the binary heap you built earlier, implement heapsort. This can be tricky, but it's important, because it helps you realize the value of proper data storage to create an easier problem (the sorting) for yourself later.
  
• Implement mergesort on your doubly linked list. This one should be very quick to do.
  
  • Mergesort is a great example of a "linearithmic", or O(n log n) function. Explain why it's n log n and not some other order.
  • We haven't covered threads here yet, but if you already know how to use them or want to learn them now--write a parallelized mergesort. This is among the easiest sorts to parallelize; why that is the case is left to you.
• I'm not going to ask you to implement quicksort, as it's kind of tricky, but you can do so optionally. However, you should study the Wikipedia page for it and be able to answer the following:
  
  • Why can quicksort sometimes be quadratic in its runtime?
  • How might you place the pivot to maximize efficiency? (This is not quite a trick question, but it is close.)
• Back to data structures for a bit, but we're going to change it up. If your language supports generic programming (yes, C++ templates count), extend (yes, this means "rewrite") your single and double linked lists, your vector, and your trees/heaps to accept generic types. This can be a little trickier than it appears in the case of trees. Also take into account that many data types may not have a way to compare them with others of their type--many languages have a feature that allows you to constrain generic types to those that implement certain interfaces. Do so. (Hint: trees and binary trees don't have to have comparators; binary search trees and binary heaps do.)
• Write a set interface. Again: if there's operational logic in this interface, urdoinitrong. This interface should be generic.
• Implement a set using your interface, where the backing data store is an array.
  
  • What are the Big O properties of your array-backed set?
  • Why is this a lousy method of building a set?
• Implement a set using your interface, where the backing data store is your binary tree. The reason we're doing a second set here is because it demonstrates code reusability: you can build abstractions atop of other abstractions to actually build the data structure you really want.
• Build an associative array (also called a map). This can be built with a set; as DrPizza noted, (Map<K, V> <=> Set<Pair<K, V>>, Set<K> <=> Map<K, K>). extending your BinaryTreeSet class may not be the best method for you to do so; it's up to you.
• Probably the hardest thing I've suggested so far: build a generic hashtable. (You will need two generic parameters.)
  
  • Why does hashing make the Big O of searching so fast?
  • Analyze your hashing function. Is it an avalanche function? If not, do some research and implement one as your hash. Remember to handle collisions.
  • What are the downsides to hashtables?
  • A Google engineer specifically said to me during an interview, "we use hashtables for more stuff than you'd think." Think about Google's computer infrastructure and the properties of hashtables. Why might Google use hashtables a lot, despite their downsides?

I can't stress enough, however, that this stuff is the foundation of being a kickass programmer. You might never write a hashtable again once you're done with this...but you'll be a much better programmer for following through this, and be better capable of understanding what you're really doing when you're writing code.

I'll expand on this more later and add additional projects if people show signs of getting to the end of this list.

[alway]

the new best post.

Awesome. I think I'll give those a go.

[DrPizza]

I think he's referring to making a clear delineation between POD-types and object types.

PODs are objects, in C++ terminology.

[DrPizza]

(should be doable in a single class)

no. Needs three: list, node, iterator.

Using class inheritance, build a doubly-linked list that inherits from your singly linked list

Doesn't seem a particularly compelling candidate for implementation inheritance, since every method except "examine head" would need to be done from scratch (insertion and removal all needs to maintain back pointers).

Inherit from your binary search tree and build an AVL tree

I would prefer a tree interface, an abstract BST implementing that interface, (that could perform lookup/iteration but neither insertion nor deletion), and then three classes extending the abstract class (BST, RB, AVL).

Implement mergesort on an array. This one should be very quick to do.

Meh. If you want to implement merge sort, do it for the doubly linked list. Much better structure for merge sorting (since it affords easy constant-space implementations), and sorting containers without random access is something a bit different.

Vector should come sooner (before linked list, probably). Set should be followed by map/associative array (Map<K, V> <=> Set<Pair<K, V>>, Set<K> <=> Map<K, K>).

[Blacken]

(should be doable in a single class)

no. Needs three: list, node, iterator.

Iterators were going to be implemented later, but yeah, might as well. If we do iterators, then yes, we need a list class (for a regular list, not so much).

Using class inheritance, build a doubly-linked list that inherits from your singly linked list

Doesn't seem a particularly compelling candidate for implementation inheritance, since every method except "examine head" would need to be done from scratch (insertion and removal all needs to maintain back pointers).

Good point. I'll mod that.

Inherit from your binary search tree and build an AVL tree

I would prefer a tree interface, an abstract BST implementing that interface, (that could perform lookup/iteration but neither insertion nor deletion), and then three classes extending the abstract class (BST, RB, AVL).

This is why I keep you around. I think the current structure is fine, though, given that the binary heap also inherits from the binary tree. (Your way would work fine too, I just don't think it matters too much.

Implement mergesort on an array. This one should be very quick to do.

Meh. If you want to implement merge sort, do it for the doubly linked list. Much better structure for merge sorting (since it affords easy constant-space implementations), and sorting containers without random access is something a bit different.

I was trying to be nice to them, but o-kay.

Vector should come sooner (before linked list, probably). Set should be followed by map/associative array (Map<K, V> <=> Set<Pair<K, V>>, Set<K> <=> Map<K, K>).

Vectors are that late mostly because of people who might not be comfortable with generics; I didn't really want to go with a non-generic vector because that would be weird. But now that I think about it, it'll work fine. I'll tack in maps and associative arrays, pretty much as you wrote them.

[qwertyuiopas]

The point of this innitiative is to be able to help other people progress and learn in the process, have fun and experiment with different concepts and varied ways of doing things.  When you have the opportunity to see different approaches to a specific problem, even if they might not be the most efficient, they might just open your mind a great deal.

I personally don't think that that guide will be bery fun for a beginner, nor give them practice with their language of choice in a simplified environment, nor is it a varied way to learn.

It looks like a great introduction to language-independant abstracted data manipulation in a limited subset of easier topics that starts with what is likely an hour of studying one wikipedia page(big O) just to get a vague concept of it, as wikipedia is one of the better places to find unnessecarily complex definitions where something that you already know will still look confusing and unknown. Then, it assumes a full understanding of the language to be worked with and a desire to learn what is said to be the "right" way despite the time and non-entertainment value that you must endure to follow it.

Not that it is a bad plan to follow as a learning resource, it just exceeds the abilities of at least half of the people coming here primarily to learn and would discourage others because there simply is very little fun evident in it. Clearly, it would be perfect as an overall goal spread over a few months of an educational course that will alternate it with fun and basics so that you are ready and interested when the next step comes along, but for self-directed learning, the average reader will ignore it.

[Blacken]

Of course it's not for someone who doesn't know how to write a for loop. It's for someone who wants to become a good programmer. I expect some basic proficiency to begin with, that should be obvious. If you aren't willing to do some studying, and you aren't willing to learn to develop the right way, then no, it's not going to be worthwhile for you. But, frankly, I don't care about those people, because the topics covered therein are of primary value to anyone serious about programming. People who complain that they don't like the "right" way to do things are of no interest nor use to me, and so they can skip right along and write quines or badly optimized 3D crap they don't really understand or whatever else. Maybe someday they'll mature. Maybe not.

I specifically stated that it's essentially an academic curriculum. People who don't want that? I don't care. I put it out there for the potentially good programmers who might actually read the topic, not dabblers without any real intent to progress as programmers. Complaints that it's not "fun" are a good indication that someone is not a serious programmer. Most of programming is extremely tedious scut-work, even in game development, and I expect that someone who is seriously interested in programming to nut up and just learn it. There are people who've already expressed interest in doing this--it's for them I wrote it. Not people more interested in fooling around.

I did not write it for the average person. I wrote it for the exceptional person.

[Siquo]

It's a 1-1 copy of first-year university stuff. I did those, too, 10 years ago.

Although perhaps not fun, knowing how simple datastructures like vectors, arrays, hashes, trees etc work internally will really help you later on.
Knowing big-O notation isn't necessary, but knowing what it generally means  (constant, logarithmic, linear, quadratic or even worse time), and what it will mean for your program, can make the difference between 1 and 100 FPS. Even for a roguelike.

The path-of-most-fun in learning a language, or programming in general, has been working with the source of a simple a working game, and slowly tweaking it, for me. Instant results, nice slow progress, and you don't get the time to develop nasty coding habits, as you'll take over the habits from the program you're learning from. Although that was over 20 years ago

[DrPizza]

I personally don't think that that guide will be bery fun for a beginner, nor give them practice with their language of choice in a simplified environment, nor is it a varied way to learn.

I think it would give them a decent baseline set of knowledge, suitable to enable them to start tackling Project Euler or similar.

At worst, I'd say it's too much concentration on data structures, not enough on algorithms. Algorithms and data structures are fundamental.

Not that it is a bad plan to follow as a learning resource, it just exceeds the abilities of at least half of the people coming here primarily to learn and would discourage others because there simply is very little fun evident in it.

Sounds like a good introduction to programming, then....

[qwertyuiopas]

Actually, it fits perfectly here, as a challenge. An academic curriculum followed self-educated within a few weeks and fully comprehended, without a teacher, only using the internet as a reference and what is at best an outline?

Anyone who sees it as a learning resource can use it that way, but few will even read to the end of it before giving up, because it gives few visibly appealing results. It will teach skills that will be most useful in large programs that must do massive quantities of data processing where the overhead of using a class(one function pointer lookup per method call, pointer from the vtable pointed to from the class, maybe also a cast/thunk if it was an inherited implementation) is offset by having a "cleaner" interface and faster algorithm(You can use a lower level language that is harder to work with to implement the same algorithm to possibly gain speed at the cost of making it harder to work with, but *adding* classes alone is unlikely to make anything *faster*, unless you accidentally refactor something in the process that could probably have been added without classes).

Second, and this is critical, that outline, though a good procedural introduction, leaves no specific mention that learning when to use a particular algorithm is important, only how.

[Blacken]

Again: this is not for "normal people," this is for "exceptional people." No, it doesn't give a lot of quick results. But I never once said to do this-and-only-this, just to do it in order. If people can't find applications for what doing this will teach, and do that concurrently, that is so very Not My Problem.

And who said it had to be done in a few weeks? People can take as long as they want, who cares about implementation time? Computers will still be there when they're done.

As for "when to use an algorithm": if you know the properties of the algorithm and its domain and range, you can think critically to determine when you need to use them. I am expecting people who think they're exceptional to tackle it, and those people can be expected to figure out that sort of thing themselves. Anyone else--hey, they can ask questions and I or anyone else would be happy to answer them. But spoonfeeding anyone anything retards the learning process, and they can at least spend some time thinking about the data representations and how they shall work before being led toward an answer.

(Also, FWIW, your idea of how functions are actually handled and the speed versus abstraction tradeoff is provincially C++-specific; there's a very good reason I suggested almost anything other than C++ for tackling this series of projects and you just demonstrated one of the most prominent ones in that attempted analysis. Namely, that you try to fit all your problems in the machine workspace that C++ encourages instead of the problem workspace that virtually any other object-oriented language encourages. Obviously all languages have some structural relationship with the machine itself, but C++ has almost nothing but that relationship, confounding the issue considerably. For example, think really hard about how other languages handle polymorphism and functions in general, when they actually have real type information to work with. And even in C++, an optimizing compiler--either GCC or MSVC--will snap a lot of pointers and make the issue considerably less cut-and-dried than you have presented it.)

I think it's probably best to let this one rest, qwertyuiopas, and save your comments. People who will use it, will, people who won't, won't, and frankly, I don't think you really have enough of a grasp of the topic to make meaningful contributions. Sorry, but honesty's a bitch. I'm probably not going to respond to more of this "very concerned commentary", because it isn't going to lead anywhere productive.

[Normandy]

I am curious what coursework you would come up for 'normal people', Blacken. I do not plan to take up programming as anything more than a hobby (I don't think I have the constitution for it. I hear terrible things about EECS); and although I have done one or two things on that list (making my first doubly-linked list was an absolute joy), I'm not sure it would serve to benefit the majority of people, as you yourself have pointed out. If you had to come up with a list of challenges for someone like me, who use programming as a way to offload tasks to a computer (i.e. writing shell scripts or using R), what would you suggest?

And what about for artsy liberal types who might not use anything more than something drag-and-drop like (note: I shuddered too) Game Maker? What would you say are the most important tenets that they would have to learn in order to quickly get up to speed? I think we are well in agreement that "do as I do" lessons and tutorials tend to teach very little, but unfortunately those are the most common out there.

Excuse me for seeming like a noob on IRC or something, but it's been a while since I've had the free time to interrogate programmers.