Learning data structures and algorithms in different programming languages

[jedishrfu]

To be clear javascript was originally called livescript. Its focus was to create interactive webpages.

When java and its applet code became popular livescript changed its name to javascript to catch some of the glory of java applets.

When applets became too large and too slow then javascript gained some traction and surpassed java applets.

MS killed java applets on its windows-based browser by not supporting the full runtime library of java. This ticked off Sun since they knew what MS was doing, trying to break java’s write once run anywhere philosophy.

There was a battle for dominance the MS Extend, Embrace, Extinguish philosophy and loss of the court battle to Sun split the developer community once MS released .NET and C# to compete with java on windows the dominant OS cutting Sun out of the picture.

 

[jedishrfu]

I don't know what "space invaders equivalent" means. That seems to be a foreign idea in the subject of computer languages.

I think he means code and indentation via spaces or tabs.

 

[elias001]

@jedishrfu I mean by running a python script feels like playing a video game. To add two numbers in C, you have to write a program, ccompile, then run whatever it is you wrote. In python, well, just type in 1+1:. Actually I don't even remember the proper syntax. But you folks know what i am trying to get at.

 

[jedishrfu]

Yeah, that's just a nice convenience feature of the Python interactive shell.

Many other languages support an interactive shell. Julia is one such example.

Interactive shells may not support the full language. I recall Julia and Python have limitation on what language features may work.

 

[elias001]

@jedishrfu can i ask if once upon a time, programmers had to learn all the data structures and algorithms and learn to write it in assembly? Also is it worth learning to write programs that have the equivalent of few to ten thousand lines of code in C? i have seen from youtubets where neural networks were wtitten in assembly.

 

[jedishrfu]

Simple answer is no. The most complex structure would usually be a simple array. We never got any formal instruction beyond reading macro assembler reference and learning from others how they coded.

Formal data structures theory wasn't defined rather coders followed their instincts and the problem at hand. Fortran offered 2 or 3 dimensioned arrays, while Cobol offered simple record structures and tables ie simple arrays and would have been the primary influence to assembler coders.

The OS was basically a set of tables of record structures to handle batch job run info. I wrote one major assembler based program that read the system tables and displayed the info on screen rather like the Linux top command of today.

It ran in supervisory mode and had access to all memory. Any mistake of mine could overwrite important job data and crash the system.

Mine did and it was discovered that a user routine I used could not run in supervisory mode.

Many coders wrote code that reused the initialization code area meaning if your program crashed after looping thru some algorithm you could not look at initialization code and what it did. The notion of separation of code and data came later as people realized many error were a result of this coding decision.

Memory was limited and considered expensive and assembly language coders were frugal. Their program was data mixed with opcodes.

Bottom line there was no stack or queues or more complex data structures. only tabular data.

It was a simpler time.

 

[elias001]

@jedishrfu wait, isn't C/C++ one of those write once, run anywhere language? I mean I have never heard of Mac having Java virtual machines being installed on them.

So data structures and algorithms already matured by the time of algol came on the scene. And for all the simpler times, they were able to do a lot with so little. Kind of like what Euler and his contemporaries had to work with in math for solving applied math problems.

Oh before I forget, for the topic of pointers, there are quite a few books written on it for C, and also C++. Are there significant difference between how C and C++ handles this topics. I assume whatever i learn for C carries over to C++, but not necessarily the other way around.

Also i found a book that have the topic of smart pointers. I should learn about the topic of pointers pre "smart pointers" era before I go onto learning about smart pointers??

Also i don't know if i you have seen this: object oriented C. Can i learn about pointers for oop setting in C before moving onto learning about it for C++. Would it make sense easier in the sense of learning to write safer code?

 

[FactChecker]

@jedishrfu can i ask if once upon a time, programmers had to learn all the data structures and algorithms and learn to write it in assembly? Also is it worth learning to write programs that have the equivalent of few to ten thousand lines of code in C? i have seen from youtubets where neural networks were wtitten in assembly.

The series of books by Donald Knuth, "The Art of Computer Programming" were not "had to learn", but were considered standard classics to study. Knuth used a hypothetical assembly language called MIX.
Even if you do not get those books or study them, you should be aware of their existence and importance in the history of computer algorithms. IMO, they are very inexpensive for such classic books. (about $205 for 5 books on Amazon) But studying them is a very significant amount of work.

 

[jedishrfu]

@jedishrfu wait, isn't C/C++ one of those write once, run anywhere languages? I mean I have never heard of Mac having Java virtual machines being installed on them.

So data structures and algorithms already matured by the time of algol came on the scene. And for all the simpler times, they were able to do a lot with so little. Kind of like what Euler and his contemporaries had to work with in math for solving applied math problems.

Oh before I forget, for the topic of pointers, there are quite a few books written on it for C, and also C++. Are there significant difference between how C and C++ handles this topics. I assume whatever i learn for C carries over to C++, but not necessarily the other way around.

Also i found a book that have the topic of smart pointers. I should learn about the topic of pointers pre "smart pointers" era before I go onto learning about smart pointers??

Also i don't know if i you have seen this: object oriented C. Can i learn about pointers for oop setting in C before moving onto learning about it for C++. Would it make sense easier in the sense of learning to write safer code?

No. While it appears that C/C++ is like that, you can't just compile and run when switching from a Unix system to a Windows system. Programmers would look for cross-system libraries to solve some of this. For example, Windows uses the \ for pathnames of directories and files, whereas Linux uses the / separator. Knowing that C programmers would factor it into their code.

One problem with your question is that these concepts developed over time. Early coders didn't know the formal names of data structures, but may have built them into their code, and as no libraries existed at the time, at least none that I knew of.

Fortran, Basic, or COBOL didn't have stacks until much later. This meant you couldn't do recursive programming. For FORTRAN doing a recursive solution could put in an I finite loop until the compiler guys fixed it via warning not to call the function you're defining. However, some assembly coders could hand code a custom solution.

 

[elias001]

@jedishrfu what about the issues of pointers that I mentioned. If I know C pointers, transitioning to C++ pointers should not be much of a problem?

 

[FactChecker]

You could use pointers in C++ the same way as in C, but that would miss out on some very important advantages of C++ and OOP.
Suppose you were making a data structure of a tree, where each node has an undetermined number of children. In C, you might define the structure with a pre-set maximum number of children, say 5, and have an array of up to 5 children. That would allocate a lot of space in memory that might be unused at some nodes and might not be enough at other nodes. Alternatively, you might allocate memory space each time a child is created and free it when the child is terminated. That requires careful programming and bookkeeping.
A concrete example (although not a tree structure) would be a simulation of traffic in a road network. Vehicles are entering and leaving the simulated network as simulation time progresses and each road section and intersection keeps track of vehicles on/at it. Intersections with traffic lights need to keep track of an undetermined number of vehicles.
In C, it gets messy.
In C++ using OOP, you can create (instanciate) new vehicles (objects) easily and follow them through the road network until they leave the area. The memory allocation and freeing is done by C++, with much less effort on your part.

PS. There are many other advantages of OOP that can be/are addressed in other threads.

 

[elias001]

@FactChecker wait I thought dealing with and learning about pointers has to do with memory management and dynamic memory management. I only care about that issue and would worry about OOP complicated the issue further or make things simpler?

 

[FactChecker]

@FactChecker wait I thought dealing with and learning about pointers has to do with memory management and dynamic memory management. I only care about that issue and would worry about OOP complicated the issue further or make things simpler?

Good question. OOP helps to facilitate memory management. For the time being, you can ignore other features of OOP if you want to.
Keep in mind that the memory allocation can get very complicated. You might be allocating memory for an entire structure and structures containing structures of variable sizes.

 

[elias001]

@FactChecker later on as I get more advanced into learning about programming. For languages like python that evangelize that is a memory safe language. One can write a program in python that can cause a buffer overflow? I mean basically to show that its memory management safety feature doesn't work 100% of all cases.

 

[jedishrfu]

Not to muddy the waters here but have you looked at Google’s golang programming language?

https://go.dev/

It’s C for the internet age containing some protection from errant or uninitialized pointers.

Look at the examples on this website

https://gobyexample.com/

Go was developed for google server-side operations by a team who also worked on C decades before.

It was designed to be general purpose, and meet Google’s need for a common language for the millions of lines of code they maintain.

 

[Filip Larsen]

what about the issues of pointers that I mentioned. If I know C pointers, transitioning to C++ pointers should not be much of a problem?

While the abstract concept of pointing to or referencing data (as opposed to work directly with the "value" of the data) is similar in C and C++ and share a bit of the same syntax, the actual patterns and mechanisms for memory/ownership management is almost completely different even for raw pointers. E.g. in C you would use malloc() and free(), whereas in C++ you would use new and delete (on very rare occasions) and preferably smart-pointers (in most cases).

I would say that while it doesn't hurt to know about pointer management in C before going to C++ it probably won't really help much either beyond the absolute basics.

 

[elias001]

@jedishrfu and @FactChecker Factch thank you both. You two's advice has helped me a lot.

 

[FactChecker]

@FactChecker later on as I get more advanced into learning about programming. For languages like python that evangelize that is a memory safe language. One can write a program in python that can cause a buffer overflow? I mean basically to show that its memory management safety feature doesn't work 100% of all cases.

I can't answer that question. I don't know enough about Python. If I were to guess, I would guess that it makes memory errors less likely but not perfect. Those errors are the type that crooks try to exploit for fraud. They will work hard to find any little vulnerability. A lot depends on the operating system that the code is running on.

 

[elias001]

@FactChecker I have read some of Knuth's first volume. I would not say his books are hard. I would say it takes a bit more time than other math books. He tried his best to be clear and meticulous. Too bad it was not like Feymann's lecture notes where you can hear his lectures.

 

[sysprog1]

I would think that the mathematical subject of graph theory is not very helpful in computer programming of data structures, except for terminology and basic concepts.

I found this book very helpful in my student days -- its content is still comp-sci foundational, and by it the applicability of graph theory to computer programming of/or/and data structures is clearly shown:

https://www.cambridge.org/us/univer...tional-g/algorithmic-graph-theory#description

from the description at Cambridge University Press:

"This is a textbook on graph theory, especially suitable for computer scientists but also suitable for mathematicians with an interest in computational complexity. Although it introduces most of the classical concepts of pure and applied graph theory (spanning trees, connectivity, genus, colourability, flows in networks, matchings and traversals) and covers many of the major classical theorems, the emphasis is on algorithms and thier complexity: which graph problems have known efficient solutions and which are intractable. For the intractable problems a number of efficient approximation algorithms are included with known performance bounds. Informal use is made of a PASCAL-like programming language to describe the algorithms. A number of exercises and outlines of solutions are included to extend and motivate the material of the text."

 

[FactChecker]

@sysprog1 , Thanks. I stand corrected. And I see in the link you gave that the author has several books on parallel algorithms and computations. I can see the connection to graph theory in that subject.

 

[sbrothy]

I know it's been made somewhat... obsolete, but it's still worth a read in my opinion:

Design Patterns - Elements of Reusable Object-Oriented Software (Gamma et al)

Has it been released into the public domain? It almost looks like it:

https://www.grch.com.ar/docs/unlu.poo/Gamma-DesignPatternsIntro.pdf

EDIT: Nah, it's hardly the entire book,.

 

[.Scott]

I have a quick questions. I am going through a book on C programming on my own. Afterwards, I plan to go through something call data structures and algorithms on my own also in C.

Regardless of what language you use to implement your data structures, I suggest you brief yourself on database normalization. The one thing that is seldom covered in texts on this topic is that normalization is a design process. If, during your system design, you describe the data you will be working with in normal form, then you will be driven to ask design-critical questions about that data - questions that you would otherwise fail to run into until you were deep into the implementation. Once you have a fully normalized (or at least 3NF) description your data structures, then you might continue the design process by opting to selectively denormalizing parts of those database relations to optimize certain DB transactions over others.

 

[FactChecker]

@.Scott , That's a very good point. One treacherous thing about data bases is that the need for normalization may not be obvious until a database is implemented and the data keeps changing, needing consistent updating. The only thing I would disagree about is that the texts I learned from (long ago) discussed this a great deal.

 

[elias001]

@.Scott Isn't database normalization covered if students are taking an university course in database and get taught how to actually build one from scratch. I briefly look up the term and I is discussed in books on database systems and management.

 

[sbrothy]

[…] Almost anything has structures.
Javascript, C++, and some other languages (but not C) allow you to put functions within structures (or classes). […]

I’m just teasing here, but technically you can have function pointers in C structs. Although it doesn’t help towards proper encapsulation. Also, I can’t off the top of my head, find a good reason for doing so.

typedef int (*PFooFunc)(int, int);
typedef struct _foo {
    int bar;
    char baz;
    PFooFunc func;
} FOO, *PFOO;

EDIT: hmm the typedefs are artifacts from my Windows days. Bad habit.

 

[Filip Larsen]

technically you can have function pointers in C structs. Although it doesn’t help towards proper encapsulation. Also, I can’t off the top of my head, find a good reason for doing so.

It has been used quite a lot for adding polymophism and similar constructions to allow object-oriented design. For example, I recall the X11/Xlib client/server system written (originally) in C made extensive use of this to extend behavior.

 

[.Scott]

@.Scott , That's a very good point. One treacherous thing about data bases is that the need for normalization may not be obvious until a database is implemented and the data keeps changing, needing consistent updating. The only thing I would disagree about is that the texts I learned from (long ago) discussed this a great deal.

In reading Codd's original work, wiki articles, and quite a few more recent articles, I see very good technical descriptions of what a normalized DB looks like; what some of the technical procedures are to achieve that normalization description; and what the "selling points" are of a normalized DB over one that is not.

But that last item is the problem. There is a selling point to the normalization exercise that is unrelated to the characteristics of a normalized database. Even if you know that you will denormalize your DB (or even if you have a DB that you will not be normalizing), a normalization should be performed (or should have been performed) and documented on that data.

The "new" information that a normalization document will describe could include keys or fields that are not atomic with parts that do not belong in the same relation or which require checks or other processing.

More generally, the minimal amount of information required to determine whether a DB design is fully normalized requires a crystal-clear understanding of what that data is and how it is used - something that is quite beyond the technical skills of your "customers" to unambiguously describe. When the designers are confronted with the highly technical requirements for how normalization applies to a particular data field, they will find themselves carefully recasting these technical questions into "telling" questions digestible to their customers.

In the mid-1980's, I was tasked to lead a small team to design a relational DB for the Air Force procurement center - which, at the time, was an extensive part of the Wright-Patterson AFB in Ohio. I was eventually able to identify (all numbers are approximated from memory) 4200 originally-identified fields representing 1700 actual fields in 180 record types. The process involved interviews with over a hundred users and managers of the procurement process. The final document became a kind of "procurement bible" with Wright-Patterson immediately requesting 200 copies for distribution across the procurement center. It allowed anyone to find their datasets and trace out how it was connected to the overall procurement process.

That document did eventually result in both changes to the procurement process and further automation of that process - although the DB was so large and active that with 1980's technology it was several years before they could break away from a "batch" like process.

 

[elias001]

@Filip Larsen @.Scott, @FactChecker There was this post about learning C++. What i want to know is i know there is something call managed/smart pointers in C++ and null pointers in C. Is the former better than the later. If deciding between using C vs C++ bases on memory safety issues is comparing buying best armor before going on your fantasy dragon/griffin/wyvern slaying or goblin/troll/orc/ogre/mega slime hunting adventure. Then choosing C because of null pointer feature is like choosing the best armor because of the material is made of and will max out your defense points. But choosing C++ because of smart or managed pointers is like picking the best armor that give you the most defense point increase but also increase points for your other attributes like your health and wisdom stats for magic casting as well as give you an increase immunity to various status effects that will kick in automatically should you experience any of those nasty status effects.

 

[.Scott]

@.Scott Isn't database normalization covered if students are taking an university course in database and get taught how to actually build one from scratch. I briefly look up the term and I is discussed in books on database systems and management.

The last time I took any kind of data processing course was in 1973 - so I can't address your question directly.

There is certainly a limit on what can be presented in a classroom. In that sense, I was very fortunate to have the entire US Air Force procurement system available for interrogation - and had a paycheck coming in so I could spend my time on it.