Archived

This topic is now archived and is closed to further replies.

Algorithms that would make your mother proud

This topic is 4944 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

    I propose a thread that contains a round-table discussion of common algorithms and data structures, their implementation, and their performance. The idea is quite simple, and only contains one caveat: any code you post should be in C#, unless it is pseudocode. The reason being, C# is clean and pretty looking, and in general, would be easily understood in most cases. Not only that, but C++ and plain-old C have many books and papers and websites devoted to this topic. C# being new, has less documentation in this regard. Basically, it would be nice to provide code in a language that has fewer examples to choose from. I, and I am sure many others, have looked far and wide for algorithms in C# and don''t find a whole lot of great examples. Anyways, that''s not the point...     The point is that it would be nice to have everyone contribute code to build a simple linked list, or a binary search tree, or a string tokenizer, or something of the like (random tricks and neat tips, optimizations... all welcome). We could then, if necessary, comment and improve on each other''s work. Uninformed folk will learn a great deal, and mastery folk might learn a few new tricks as well.     Basically, let''s create a tutorial thread containing common algorithms and data structures in C#, to help people learn, and to help people improve.     I thank anyone who can contribute. I''m sure many will appreciate it. I will start... this is a string reverse function I made. I am quite aware I could call the string.Reverse() method, but that would be lame, and I would have learned nothing from doing it. Please, feel free to comment. Add something interesting of your own as well.
public static char[] RevStr(string x)
	{
		int xPerm = x.Length;
		int xSize = xPerm;
		char[] x_copy = new char[xSize];
		int idx = 0;
		
		while(idx < xPerm)
		{
			--xSize;
			x_copy[idx] = x[xSize];
			++idx;
		}
		
		return x_copy;
	}

Share this post


Link to post
Share on other sites
I''ll be the first rule breaker, my code is in Scheme (mainly because it was easier than in C#, and it wouldn''t have made my mommy proud).

I wrote two functions. The first one is called filter. It takes two parameters: a predicate and a list. The function returns a new list containing every element of the original list which met the predicate. The second function removes all duplicates items in a list (keeping the original order).

Both functions are written in a purely functional way. They have not been optimised to use tail-recursion for example, so don''t use that in production code (though I doubt there''s much Scheme "production" code nowadays )


(define (filter pred lst)
(if (null? lst)
()
(if (pred (car lst))
(cons (car lst) (filter pred (cdr lst)))
(filter pred (cdr lst)))))

(define (uniq lst)
(if (null? lst)
()
(if (member (car lst) (cdr lst))
(cons (car lst) (uniq (filter (lambda (e) (not (equal? e (car lst)))) (cdr lst))))
(cons (car lst) (uniq (cdr lst))))))

Share this post


Link to post
Share on other sites
Guest Anonymous Poster

char *reverse(const char *s)
{
char *sp = 0;
if (s) {
size_t l = ::strlen(s);
char c;
sp = new char[l+1];
sp += l;
*sp = ''\0'';
while (c = *s++) *(--sp) = c;
}
return sp;
}


So I don''t know C#. Sue me. If anyone knows how to do this without the variable c, post the solution. I couldn''t get rid of it because the null winds up on the other side of the string if you simply do *(--sp) = *s++. I suppose I could make an extra byte in front of the reversed string and write nulls on both ends of the string, but that''s tacky.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Here''s an alternate version filter that''s tail-recursive.


(define (filter pred lst k)
(if (null? lst)
(k ())
(if (pred (car lst))
(filter pred (cdr lst) (lambda (c) (k (cons (car lst) c))))
(filter pred (cdr lst) k))))

Share this post


Link to post
Share on other sites
Way to ruin a good thing by limitting it to a Microsoft language that actually in reality isn't that clean and doesn't look that good.

EDIT: I'll post some assembly language (x86, intel style) or some Lisp later.

[edited by - Puzzler183 on May 31, 2004 9:23:38 AM]

Share this post


Link to post
Share on other sites
This doesn''t have to start a flame war, that''s simply ridiculous. The point was, C++ and C and every other language like that has dozens of websites and books on algorithm implementation and such. C#, does not . Thus, it would be nice if you could post in C#, since most examples could be easily converted to C++, or possibly to C. However, C and C++ often use lots of pointers, and I wanted to avoid that if possible. If you don''t like C#, I''m sorry, I certainly don''t want to stand in the way of progress.

Anyways, keep it going if you can. In any language that suits your fancy if it needs to be that way.

Share this post


Link to post
Share on other sites
quote:
Original post by Puzzler183
[...]limitting it to a Microsoft language[...]


It may have been invented by Microsoft, but it was standardized by the ISO, just like C++ or C was. And therefore, it is an open language for people like the Mono Foundation to freely recreate. C# is no longer limited to Microsoft platforms, so that statement is unnecessarily harmful.

I appreciate people posting in any language (even in Scheme, I found that interesting), but the point of the thread was to be a reference to basic algorithm and data structures. I don't think many novice programmers are going to rush over to a Common Lisp implementation of a binary search tree. However, if they saw C# code, I think they might understand it to an extent, if not only to port it to another language. I'm sure you can understand what I mean, lest we turn this into a stupid discussion of meaningless terms.

C# is first choice.
...Java too.
C++ or C with minimal pointers/memory management issues.
BASIC type language.
Pseudocode of sorts.
Lisp-ish languages.
Cobol and FORTRAN.
Piet.
D.

Edit: Added Java...

[edited by - khaos on May 31, 2004 9:56:50 AM]

Share this post


Link to post
Share on other sites
I''m using pseudocode... much easier than anything else...

Breadth-first search in a graph : finding if there is a path from a to b.



procedure BFS( a : node, b : node )

s : node queue (FIFO)
v : node list

push a onto s
while s is not empty do
pop n from s
if n = b then return true
for all children c of n do
if c is not in v then
add c to v
push c onto s
return false


And why not a classic? Insertion sort :


procedure ISORT( a : array of size N )

if N <= 1 then do nothing
ISORT( a[2..N] )
t <-- a[1]
for i = 1 to N-1 do
if t > a[i+1] then
a[i] <-- a[i+1]
a[i+1] <-- t


There you go...

Share this post


Link to post
Share on other sites
quote:
Original post by ToohrVyk
There you go...


Absolutely perfect job.
Keep up the positive work anyone!

And don''t forget discussing better solutions to the already-posted.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by Puzzler183
Way to ruin a good thing by limitting it to a Microsoft language that actually in reality isn''t that clean and doesn''t look that good.

EDIT: I''ll post some assembly language (x86, intel style) or some Lisp later.

<SPAN CLASS=editedby>[edited by - Puzzler183 on May 31, 2004 9:23:38 AM]</SPAN>
It''s obvious that you''re not used to modern languages such as C#/.NET/Java so please be quiet.

Share this post


Link to post
Share on other sites
No, Lisp is not difficult to understand. It simply does not have a huge base behind it enough that novice can understand an insertion sort written in it.

Gah! Please. Let''s build a good reference for people to use that discusses optimal solutions to common problems. Job interview problems even. Let''s do that... just, something constructive always please.

I''d rather not like to see this thread dead in the first page or start of the second, when dumber, more pointless threads can get up to nine pages. Let''s be positive and make a complete reference to common interviewing questions, or to everyday algorithms and data structures... in a _kind_ language, as you can see in the aforementioned list I wrote.*




*This is not to say I think C# is a more kind language when compared to C++, or any combination thereof. Just be reasonable.

Share this post


Link to post
Share on other sites
A reason I like posting algorithms in Scheme is that if they are written in a functional style, they can be easily tested and proved without a compiler. Sure you can do it with other languages, but it''s harder to keep track of it because the state of variables changes.

While I''m here, here''s a scheme implementation of map (called my-map to avoid name conflicts):


(define (my-map f lst)
(if (null? lst)
()
(cons (f (car lst)) (my-map f (cdr lst)))))


I hope that you guys can appreciate the simplicity of this function (as well as the treendous usefulness of a map function.)

Souriez,

Vince.

Share this post


Link to post
Share on other sites
quote:
Original post by GnuVince


side question
Where can I learn more about Scheme? Any well-known tutorials that are excellent resources if one wanted to learn more about Scheme? How is Scheme compared to Lisp?
end side question

Keep on trucking...

[edited by - khaos on May 31, 2004 10:37:22 AM]

Share this post


Link to post
Share on other sites
quote:
Original post by Khaos
side question
Where can I learn more about Scheme? Any well-known tutorials that are excellent resources if one wanted to learn more about Scheme? How is Scheme compared to Lisp?
end side question


Scheme is a dialect of Lisp. It's a lot smaller than Common Lisp. It's excellent for pedagogical purposes because it's very good at clearly expressing algorithms like the ones you're looking for in this thread. There's an awesome online book about it here.

I'll post something interesting in a while, maybe.

[edited by - twix on May 31, 2004 10:42:59 AM]

Share this post


Link to post
Share on other sites
quote:
Original post by Khaos
quote:
Original post by GnuVince


side question
Where can I learn more about Scheme? Any well-known tutorials that are excellent resources if one wanted to learn more about Scheme? How is Scheme compared to Lisp?
end side question

Keep on trucking...

[edited by - khaos on May 31, 2004 10:37:22 AM]


As already suggested, How To Design Programs is a great online (and free) book to get you started in Scheme. It starts a little slow, because it assumes no knowledge of programming whatsoever. It uses the excellent DrScheme environment (based on the popular PLT Scheme implementation).

If you want stuff that''s a little (well, a whole lot) more hardcore, you want to check these two links out:
Structure and Interpretation of Computer Programs (the standard introductary programming textbook at MIT, one of the most influencal book every written on CS)
Videos of SICP: videos of the class that goes with the book previously linked. The teachers are the author of SICP (Hal Abelson and Gerry Sussman (co-inventor of Scheme)).

These should get you started real good

Cheers,

Vince

Share this post


Link to post
Share on other sites
Out of curiosity, is it a rule that any code written in functional languages must use absolutely useless naming conventions throughout the code? I realize the symbols in the common lisp package are intentionally obfuscated (caaddr, defsetf, lognor, etc, etc, etc.. ) but can''t modern programmers using the outdated language at least bother to try to use naming conventions that are somewhat coherent?

Share this post


Link to post
Share on other sites
quote:
Original post by haro
Out of curiosity, is it a rule that any code written in functional languages must use absolutely useless naming conventions throughout the code?

Yes!

(actually, I think it might have more to do with a tendency to make useless names when writing small isolated utilities, which is what people always use as code snippets from functional languages).

Out of curiosity, why do you say that "defsetf" and "lognor" are obfuscated? If you have some basic knowledge of the standard libraries, they're perfectly clear. Hell, even "caaddr" is clear, although if you use it you're probably doing something wrong.

[edited by - twix on May 31, 2004 12:00:33 PM]

Share this post


Link to post
Share on other sites

This topic is 4944 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Guest
This topic is now closed to further replies.