Talk:Programming Fundamentals/Arrays

Definition of an array

I think it's important to explain and emphasize here that arrays are little more than a block of memory whose length is a multiple of the length of its data type. Since index notation is just syntactic sugar for some simple pointer arithmetic, perhaps it's a good idea to explain the pointer arithmetic first. The description in the intro (before my edit) doesn't give the reader any real idea of what an array actually is, it only tells the reader what they are used for. Also, a dynamic array isn't merely a "resizable array", it's a more complex data structure built from arrays, using amortized analysis to strike a reasonable balance between fast random access, "resizablility", and space efficiency. AP295 (discuss • contribs) 17:19, 1 April 2021 (UTC)

I started a new intro. It could be fleshed out with something along these lines: If $a$ is the start of the array, and $c$ is the size of each individual item, then the location of the $i$th item (starting with 0) can be computed as $a+c\cdot i$. Most programming languages support the use of index notation, so that the $i$th element can be accessed with a[i]. AP295 (discuss • contribs)

@AP295: This is an active real-world course currently in use, as indicated at Talk:Programming Fundamentals. Please don't make any more bold edits while students are actively engaged in the content.

The target audience is truly fundamental. These are information systems and information technology students rather than computer science students. Many don't have the math background, and an overwhelming majority are not using a programming language that uses arrays as you wish to present them. Most students are using languages that implement lists rather than arrays, and trying to explain the differences between these data structures does not add value for the target audience. What they need to understand is the practical application of the concepts that the course content previously included. Also, please be aware that most of the content included in this course was added by the students themselves, meaning that it specifically targets their understanding and their interests.

Please continue to use the Talk pages to share your suggestions. There is a very short window in May where I can update the course sequence and content without disrupting active learners. Thanks! -- Dave Braunschweig (discuss • contribs) 23:49, 1 April 2021 (UTC)

I figured that, but do we have a convention for editing frequently used resources? "Also, please be aware that most of the content included in this course was added by the students themselves, meaning that it specifically targets their understanding and their interests." I figured that too. Indeed, students (particularly undergraduates) are often more concerned with how to use something rather than with what it is. However, I think they'll still be better served if the resource states what an array is at the outset. I'm fairly certain most of them can (and must) understand the linear pointer arithmetic behind arrays. I am a community college alumnus myself, you know. AP295 (discuss • contribs) 00:11, 2 April 2021 (UTC)

Also, understanding the difference between an array and a (linked) list is very important. While both structures may support (more or less) the same set of operations, they are not identical in terms of time complexity or space complexity. These differences are usually covered more thoroughly in a data structures course but the resource should still emphasize that they are distinct structures. It's unfortunate that some languages (python) add to the confusion by calling their dynamic arrays "lists", but I digress. As far as I'm aware, few languages actually implement true lists instead of arrays as their "primary" linear data structure. Scheme and common lisp are two of them, but they also support arrays. AP295 (discuss • contribs) 01:43, 2 April 2021 (UTC)

One more remark: I notice that this resource does not seem to target any specific language. I know certain in-person freshman/sophomore-level programming courses that let students use whatever they want, but in my experience it's a royal pain in the ass. To be blunt, I think the best approach is to start them off with C and save other languages for more advanced courses. The problem with using java or python is that some students never seem to fully grasp the concept of a "reference"/pointer or how certain data structures actually work. Then they end up graduating with only a vague conception of the fundamentals. The thought that someone who doesn't understand pointers, lists, the call stack, etc. could go on to write code for automobiles, public transportation, medical equipment, etc. is honestly terrifying. AP295 (discuss • contribs) 14:21, 3 April 2021 (UTC)

@AP295: By convention Wikiversity works collaboratively, and generally with deference to the primary author of a resource, particularly when editing subpages. When there is disagreement, the main page will provide an introduction, and separate subpages are established so that editors who can't agree are able to present their views on separate subpages. (I will note that this isn't always the case. There are some editors whose chosen topics and/or approaches violate the Net Negative Effect aspects of Wikiversity:Blocking policy and they are blocked.) To work collaboratively, we use Talk pages rather than content pages and either come to agreement or agree to disagree and then agree on how the different approaches might be handled as separate subpages or perhaps separate learning projects.

The design of this course, embracing and supporting dozens of programming languages, is intentional. The focus of the course is on programming logic and design rather than specific language implementation and expertise. Students completing the course for credit are required to use multiple programming environments (one visual (Flowgorithm) and one traditional). Course discussions highlight the similarities and differences across programming languages and platforms, so that students become aware of standard programming concepts and commonalities, as well as various implementation differences that inspire people to create and/or choose different languages. It is a broad introduction to programming designed to meet the needs of the target audience. It has been embraced and supported by both employers in our area and transfer institutions who articulate this course.

The detailed approach you propose can also be effective. Our Computer Science department follows an approach similar to the one you suggest, based on C++ rather than C. Students with a strong math background often go directly into the CS curriculum and transfer on into computer science bachelor's degrees. Business students and students with a weaker math background complete this course instead or before enrolling in CS courses.

If you believe that a C-based introduction to programming with pointers and data structures is the way to go, I encourage you to start by editing C Programming or by creating an 'Introduction to Programming Using C' or similar learning project. You are welcome to borrow from any of the existing resources, including this course. If you create a new course, we can add it to the Computer Programming resource list. -- Dave Braunschweig (discuss • contribs) 14:40, 3 April 2021 (UTC)

Got it, I won't edit the course without running it by you. This is just my two cents. Most imperative languages are pretty similar in terms of the basic techniques and programming logic. I don't know how much there is to be gained by a "language agnostic" approach. It makes it harder to explain certain concepts and personally I don't fancy grading a hundred assignments written in twenty different languages. Also, I don't think you have to be any more proficient in math to learn c than to learn java or python. It's not as though you have to access array elements with pointer arithmetic or anything like that, but surely you can see the value in being able to easily demonstrate such things. The absence of OOP stuff and its associated boilerplate code also makes c somewhat less overwhelming to look at, in my opinion. AP295 (discuss • contribs) 15:17, 3 April 2021 (UTC)

@Dave Braunschweig: I see you updated it a bit. Personally, I would really not group Dynamic Arrays / Lists in the same activity section. They're quite different animals. For example, binary search (alluded to in activity 2) would be $O(log_{2}(n))$ in a sorted ordinary array or dynamic array, but $O(n\cdot log_{2}(n))$ in a sorted linked list, and in the latter case you'd be better off performing a linear $O(n)$ search. This was something I always tried to emphasize, because it's a good (and relatively simple) example of: time complexity, a good algorithm (binary search), and the importance of using the right data structure for the job. It's useful to characterize these structures by the operations they support and the time/space complexity of performing those operations. "defined-value arrays", "fixed length arrays" and "dynamic arrays" all have much more in common than a linked list. Students probably won't fully understand this right off the bat, but it still emphasizes that there's a functional difference between them. AP295 (discuss • contribs) 15:04, 20 April 2021 (UTC)

And if linked lists are beyond the scope of this particular resource, then I would stick to using the term "dynamic arrays" and explain that python (and possibly others) use "list" to mean dynamic array. In many contexts "list" means "linked list", but the term is now unfortunately somewhat ambiguous. Also, "dynamic arrays" are also not the same thing as dynamically allocated arrays, and I'd also make a small note of this to warn students. I'm certainly no expert on python internals or what exactly we should be calling these things, but the distinction should be made in any case, and that's how I did it as a TA. AP295 (discuss • contribs) 15:28, 20 April 2021 (UTC)

This is actually one of the reasons I found the "language agnostic" approach somewhat counterproductive. It's difficult to communicate these things since lots of languages use different terminology. I always found myself doubling back to explain that some languages use the term X for Y, but Z uses W, etc. etc. Using C, the difference between these structures is plain as day and can be easily demonstrated. And I'm not necessarily suggesting the resource should cover asymptotic complexity or anything like that, but just that content should be organized in such a way that reflects similarities and differences between structures. Small things like that may make a big difference in building a useful/accurate conception of the material and preparing one for subsequent courses. AP295 (discuss • contribs) 16:03, 20 April 2021 (UTC)

@AP295: I appreciate your perspective. I understand what you are saying, but this discussion is beyond the course objectives. Students just need to understand and be able to use variables which contain multiple data values accessed using an index. How it is implemented internally in any given language doesn't matter in this course. Predefined, fixed-length, and dynamic arrays help them see and apply three different approaches.

For those who take this as their only programming course, the take-away is sufficient. For those who go on into a traditional or applied CS1 course, they will have a frame of reference they can build on. Students completing this course are successful in the following courses at our college and after transfer to four-year institutions. It works as intended.

Please feel free to create a separate resource which goes into the detail you are looking for. You might check with User:Thomas E. Pearson, who was working on Advanced C Programming with what I understood to be a similar perspective to the one you describe. -- Dave Braunschweig (discuss • contribs) 22:27, 20 April 2021 (UTC)

Just sharing my experience from my brief stint as a TA. These things wouldn't normally be covered in depth until a data structures course, so I see what you mean. AP295 (discuss • contribs) 00:11, 21 April 2021 (UTC)

While I've only looked at a few of Young1lim's resources, they seem very well made with a lot of attention to detail. Most of them are in presentation format which is nice for a lecture. I think it might be a bit much for an introductory course, but I like their approach in general. Lacking course material with such attention to detail, many students get to their third or fourth year of college and still have a foggy understanding of procedural programming in general, much less OOP. If your course is working for you and your students, then okay. This is just my take on the subject in general. AP295 (discuss • contribs) 12:25, 3 May 2021 (UTC)