HN Books @HNBooksMonth

The best books of Hacker News.

Hacker News Comments on
Mastering Algorithms with C: Useful Techniques from Sorting to Encryption

Kyle Loudon · 4 HN comments
HN Books has aggregated all Hacker News stories and comments that mention "Mastering Algorithms with C: Useful Techniques from Sorting to Encryption" by Kyle Loudon.
View on Amazon [↗]
HN Books may receive an affiliate commission when you make purchases on sites after clicking through links on this page.
Amazon Summary
There are many books on data structures and algorithms, including some with useful libraries of C functions. Mastering Algorithms with C offers you a unique combination of theoretical background and working code. With robust solutions for everyday programming tasks, this book avoids the abstract style of most classic data structures and algorithms texts, but still provides all of the information you need to understand the purpose and use of common programming techniques. Implementations, as well as interesting, real-world examples of each data structure and algorithm, are included. Using both a programming style and a writing style that are exceptionally clean, Kyle Loudon shows you how to use such essential data structures as lists, stacks, queues, sets, trees, heaps, priority queues, and graphs. He explains how to use algorithms for sorting, searching, numerical analysis, data compression, data encryption, common graph problems, and computational geometry. And he describes the relative efficiency of all implementations. The compression and encryption chapters not only give you working code for reasonably efficient solutions, they offer explanations of concepts in an approachable manner for people who never have had the time or expertise to study them in depth. Anyone with a basic understanding of the C language can use this book. In order to provide maintainable and extendible code, an extra level of abstraction (such as pointers to functions) is used in examples where appropriate. Understanding that these techniques may be unfamiliar to some programmers, Loudon explains them clearly in the introductory chapters. Contents include: Pointers Recursion Analysis of algorithms Data structures (lists, stacks, queues, sets, hash tables, trees, heaps, priority queues, graphs) Sorting and searching Numerical methods Data compression Data encryption Graph algorithms Geometric algorithms
HN Books Rankings

Hacker News Stories and Comments

All the comments and stories posted to Hacker News that reference this book.
If you consider C to be language-agnostic, here are some gems. These are personal favorites as much for their excellent writing as for their content.

The Unix Programming Environment was published in 1984. I read it over 20 years later and was astonished at how well it had aged. For a technical book from the 80's, it is amazingly lucid and well-written. It pre-dates modern unix, so things have changed but much that goes unstated in newer books (for brevity) is explicit in UPE. (Plus, the history itself is illuminating.) It gave me a much deeper understanding of how programs actually run over computer hardware. Examples in C are old-school and take a bit of close reading but oh so rewarding. https://www.amazon.com/Unix-Programming-Environment-Prentice...

Mastering Algorithms in C. Another fantastically well-written book that shows (with practical examples) how to implement common algorithms. This is just such a great book! https://www.amazon.com/Mastering-Algorithms-Techniques-Sorti...

Also:

Code (Petzold). This one is truly language-agnostic. Others have mentioned it already. Can't recommend enough if you're iffy on the internals of computers and programming. https://www.amazon.com/Code-Language-Computer-Hardware-Softw...

Write Great Code (Volumes I and II). Randall Hyde's books are fantastic explications of the underlying computer operations. Examples are in assembly or pseudo-code but easy to understand. https://www.amazon.com/Write-Great-Code-Understanding-Machin...

drio
+1 to Code (Petzold). I would absolutely start with that. One of my favorite books. The build a computer course from coursera (https://www.coursera.org/learn/build-a-computer) is the natural next step after reading code.
Nov 27, 2012 · robomartin on I’m writing my own OS
OK, if you don't have any real experience in low-level embedded coding (relevant to device drivers), RTOS or OS design in general, file systems, data structures, algorithms, interfaces, etc. And, if you have "hobby level" experience with Assembler, C and C++. And, if your intent is to write a desktop OS, from the ground up, without making use of existing technologies, drivers, file systems, memory management, POSIX, etc. Here's a list of books that could be considered required reading before you can really start to write specifications and code. Pick twenty of these and that might be a good start.

In no particular order:

1- http://www.amazon.com/C-Programming-Language-2nd-Edition/dp/...

2- http://www.amazon.com/The-Answer-Book-Solutions-Programming/...

3- http://www.amazon.com/The-Standard-Library-P-J-Plauger/dp/01...

4- http://www.amazon.com/C-Traps-Pitfalls-Andrew-Koenig/dp/0201...

5- http://www.amazon.com/Expert-Programming-Peter-van-Linden/dp...

6- http://www.amazon.com/Data-Structures-In-Noel-Kalicharan/dp/...

7- http://www.amazon.com/Data-Structures-Using-Aaron-Tenenbaum/...

8- http://www.amazon.com/Mastering-Algorithms-C-Kyle-Loudon/dp/...

9- http://www.amazon.com/Code-Complete-Practical-Handbook-Const...

10- http://www.amazon.com/Design-Patterns-Elements-Reusable-Obje...

11- http://www.amazon.com/The-Mythical-Man-Month-Engineering-Ann...

12- http://www.amazon.com/The-Programming-Language-4th-Edition/d...

13- http://www.amazon.com/The-Standard-Library-Tutorial-Referenc...

14- http://www.amazon.com/API-Design-C-Martin-Reddy/dp/012385003...

15- http://www.amazon.com/The-Linux-Programming-Interface-Handbo...

16- http://www.amazon.com/Computer-Systems-Programmers-Perspecti...

17- http://www.amazon.com/System-Programming-Unix-Adam-Hoover/dp...

18- http://www.amazon.com/Memory-Programming-Concept-Frantisek-F...

19- http://www.amazon.com/Memory-Management-Implementations-Prog...

20- http://www.amazon.com/UNIX-Filesystems-Evolution-Design-Impl...

21- http://www.amazon.com/PCI-System-Architecture-4th-Edition/dp...

22- http://www.amazon.com/Universal-Serial-System-Architecture-E...

23- http://www.amazon.com/Introduction-PCI-Express-Hardware-Deve...

24- http://www.amazon.com/Serial-Storage-Architecture-Applicatio...

25- http://www.amazon.com/SATA-Storage-Technology-Serial-ATA/dp/...

26- http://www.amazon.com/Beyond-BIOS-Developing-Extensible-Inte...

27- http://www.amazon.com/Professional-Assembly-Language-Program...

28- http://www.amazon.com/Linux-Kernel-Development-3rd-Edition/d...

29- http://www.amazon.com/Version-Control-Git-collaborative-deve...

30- http://www.amazon.com/Embedded-Software-Primer-David-Simon/d...

31- http://www.amazon.com/Programming-Embedded-Systems-C/dp/1565...

32- http://www.amazon.com/Making-Embedded-Systems-Patterns-Softw...

33- http://www.amazon.com/Operating-System-Concepts-Abraham-Silb...

34- http://www.amazon.com/Performance-Preemptive-Multitasking-Mi...

35- http://www.amazon.com/Design-Operating-System-Prentice-Hall-...

36- http://www.amazon.com/Unix-Network-Programming-Sockets-Netwo...

37- http://www.amazon.com/TCP-Illustrated-Volume-Addison-Wesley-...

38- http://www.amazon.com/TCP-IP-Illustrated-Vol-Implementation/...

39- http://www.amazon.com/TCP-Illustrated-Vol-Transactions-Proto...

40- http://www.amazon.com/User-Interface-Design-Programmers-Spol...

41- http://www.amazon.com/Designing-Interfaces-Jenifer-Tidwell/d...

42- http://www.amazon.com/Designing-Interfaces-Jenifer-Tidwell/d...

43- http://www.amazon.com/Programming-POSIX-Threads-David-Butenh...

44- http://www.intel.com/p/en_US/embedded/hwsw/software/hd-gma#d...

45- http://www.intel.com/content/www/us/en/processors/architectu...

46- http://www.intel.com/p/en_US/embedded/hwsw/hardware/core-b75...

47- http://www.hdmi.org/index.aspx

48- http://en.wikipedia.org/wiki/Digital_Visual_Interface

49- http://www.amazon.com/Essential-Device-Drivers-Sreekrishnan-...

50- http://www.amazon.com/Making-Embedded-Systems-Patterns-Softw...

51- http://www.amazon.com/Python-Programming-Introduction-Comput...

52- http://www.amazon.com/Practical-System-Design-Dominic-Giampa...

53- http://www.amazon.com/File-Systems-Structures-Thomas-Harbron...

54- ...well, I'll stop here.

Of course, the equivalent knowledge can be obtained by trial-and-error, which would take longer and might result in costly errors and imperfect design. The greater danger here is that a sole developer, without the feedback and interaction of even a small group of capable and experienced programmers could simply burn a lot of time repeating the mistakes made by those who have already trenched that territory.

If the goal is to write a small RTOS on a small but nicely-featured microcontroller, then the C books and the uC/OS book might be a good shove in the right direction. Things start getting complicated if you need to write such things as a full USB stack, PCIe subsystem, graphics drivers, etc.

tagada
The guy don't want to write a perfectly designed OS, neither he wants to design a RTOS by the way ... He didn't even specify whether his OS would be multitask. If not, no need for any scheduling at all, huh ... he just "writes his own OS". It's a fun experience, very rich and very teaching. But at least now, we all can admire the wideness of all your "unlimited knowledge" especially in terms of titles of books. Afterall, no needs for creating a new OS, if you get all your inspiration from things that already exists. You will end with Yet Another Nix ... Not sure he wants a YanOS, though.

Without talking about filesystems, drivers, memory managment or existing norms and standards (which it seems he wants to avoid ... which is not that stupid ... all having been designed 40 years ago ... who knows maybe he'll have a revolutionary idea, beginning from scratch), going from scratch with no exact idea of where you go could be a good thing. Definitely. You solve the problem only when you face them. Step by step, sequentially. Very virile, man.

I would advice the guy to start obviously with the boot loader. Having a look at the code of GRUB (v1), LILO, or better yet, on graphical ones (BURG, GAG or this good one XOSL which is completely under GUI - mouse pointer, up to 1600x1200 screens, and many supported filesystems, written in ASM ... it could actually be a hacking basis for a basic OS on itself) could be a great source of inspiration, and beginning to play directly with the graphical environment.

You could also have a look on these things http://viralpatel.net/taj/tutorial/hello_world_bootloader.ph... and of course on Kolibri OS http://kolibrios.org/en/?p=Screenshots

tagada
Blah, blah, blah ...

Better advice would be: Try, make mistakes, learn from them, continue.

Way, way, way less discouraging, pessimistic and above all pedantic.

derefr
> If the goal is to write a small RTOS on a small but nicely-featured microcontroller, then the C books and the uC/OS book might be a good shove in the right direction. Things start getting complicated if you need to write such things as a full USB stack, PCIe subsystem, graphics drivers, etc.

I've always wondered if there could be created some way to skip this step in [research] OS prototyping, by creating a shared library (exokernel?) of just drivers, while leaving the "design decisions" of the OS (system calls, memory management, scheduling, filesystems, &c.--you know, the things people get into OS development to play with) to the developer.

People already sort of do this by targeting an emulator like VirtualBox to begin with--by doing so, you only (initially) need one driver for each feature you want to add, and the emulator takes care of portability. But this approach can't be scaled up to a hypervisor (Xen) or KVM, because those expect their guest operating systems to also have relevant drivers for (at least some of) the hardware.

I'm wondering at this point if you could, say, fork Linux to strip it down to "just the drivers" to start such a project (possibly even continuing to merge in driver-related commits from upstream) or if this would be a meaningless proposition--how reliant are various drivers of an OS on OS kernel-level daemons that themselves rely on the particular implementation of OS process management, OS IPC, etc.? Could you code for the Linux driver-base without your project growing strongly isomorphic structures such as init, acpid, etc.?

Because, if you could--if the driver-base could just rely on a clean, standardized, exported C API from the rest of the kernel, then perhaps (and this is the starry-eyed dream of mine) we could move "hardware support development" to a separate project from "kernel development", and projects like HURD and Plan9 could "get off the ground" in terms of driver support.

robomartin
A lot depends on the platform. If the OS is for a WinTel motherboard it is one thing. If, however, the idea is to bypass driver development for a wide range of platforms it gets complicated.

In my experience one of the most painful aspects of bringing up an OS on a new platform is exactly this issue of drivers as well as file systems. A little google-ing quickly reveals that these are some of the areas where one might have to spend big bucks in the embedded world in order to license such modules as FFS (Flash File System) with wear leveling and other features as well as USB and networking stacks. Rolling your own as a solo developer or even a small team could very well fit into the definition of insanity. I have done a good chunk of a special purpose high-performance FFS. It was an all-absorbing project for months and, realistically, in the end, it did not match all of the capabilities of what could be had commercially.

This is where it is easy to justify moving into a more advanced platform in order to be able to leverage Embedded Linux. Here you get to benefit and leverage the work of tens of thousands of developers devoted to scratching very specific itches.

The down-side, of course, is that if what you need isn't implemented in the boad support package for the processor you happen to be working with, well, you are screwed. The idea that you can just write it yourself because it's Linux is only applicable if you or your team are well-versed in Linux dev at a low enough level. If that is not the case you are back to square one. If you have to go that route you have to hire an additional developer that knows this stuff inside out. That could mean $100K per year. So now your are, once again, back at square one: hiring a dev might actually be more exoensive than licensing a commercial OS with support, drivers, etc.

I was faced with exactly that conundrum a few years ago. We ended-up going with Windows CE (as ugly as that may sound). There are many reasons for that but the most compelling one may have been that we could identify an OEM board with the right I/O, features, form factor, price and full support for all of the drivers and subsystems we needed. In other words, we could focus on developing the actual product rather than having to dig deeper and deeper into low-level issues.

It'd be great if low level drivers could be universal and platform independent to the degree that they could be used as you suggest. Obviously VM-based platforms like Java can offer something like that so long as someone has done the low-level work for you. All that means is that you don't have to deal with the drivers.

To go a little further, part of the problem is that no standard interface exists to talk to chips. In other words, configuring and running a DVI transmitter, a serial port and a Bluetooth I/F are vastly different even when you might be doing some of the same things. Setting up data rates, clocks, etc. can be day and night from chip to chip.

I haven't really given it much thought. My knee-jerk reaction is that it would be very hard to crate a unified, discoverable, platform-independent mechanism to program chips. The closest one could possibly approach this idea would be if chip makers were expected to provide drivers written to a common interface. Well, not likely or practical.

Not an easy problem.

derefr
> It'd be great if low level drivers could be universal and platform independent to the degree that they could be used as you suggest. Obviously VM-based platforms like Java can offer something like that so long as someone has done the low-level work for you. All that means is that you don't have to deal with the drivers.

Another thought: if not just a package of drivers, then how stripped down (for the purpose of raw efficiency) could you make an operating system intended only to run an emulator (IA32, JVM, BEAM, whatever) for "your" operating system? Presumably you could strip away scheduling, memory security, etc. since the application VM could be handling those if it wanted to. Is there already a major project to do this for Linux?

I will second the vote for Mastering Algorithms in C. This book will bring you right into the details you want: http://www.amazon.com/Mastering-Algorithms-C-Kyle-Loudon/dp/...

Accelerated C++ was also mentioned and I just love this book. It brought me back to C++ after years of being away: http://www.acceleratedcpp.com/

I highly recommend _C: A Reference Manual_ by Harbinson and Steele. It has many tiny examples, but it is mainly used as a reference manual (as the title suggests).

http://www.amazon.com/Reference-Manual-Samuel-P-Harbison/dp/...

A good book for learning C is _Mastering Algorithms with C_ by Loudon. The source code is over-commented and contains too much white space, which is a bit annoying, but the content is quite nice.

http://www.amazon.com/Mastering-Algorithms-C-Kyle-Loudon/dp/...

HN Books is an independent project and is not operated by Y Combinator or Amazon.com.
~ yaj@
;laksdfhjdhksalkfj more things
yahnd.com ~ Privacy Policy ~
Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.