Course Outline
Description
This course provides a foundational introduction to data structures and algorithms — the essential tools for designing efficient computer programs. Students will learn how to represent, organise, and manipulate data in memory, while developing the ability to reason about algorithm performance in terms of time complexity and space complexity. Emphasis is placed on practical implementation in C++, supported by a strong conceptual understanding of the underlying structures and techniques.
Topics include:
- Arrays and Vectors
- Linked Lists
- Stacks and Queues
- Binary Search Trees and Balanced Trees (AVL Trees)
- Priority Queues and Binary Heaps
- Depth and Breadth First Searches
- Backtracking Algorithms
- Sorting Algorithms: Bubble Sort, Insertion Sort, Selection Sort, AVL Sort, Heap Sort, Merge Sort, and Quick Sort
By the end of the course, students will be equipped to design and implement efficient solutions to a wide range of computational problems.
Lecturer
Full-Time Lecturer: Prof. Richard Klein
Office: UG07, Upper Ground, TWK Mathematical Sciences Building
Email: richard.klein@wits.ac.za
- Please always include COMS1017A or COMS1021A in the subject of your email and make sure to provide your student number in all communication. This will help prioritise it in my mailbox.
*Part-Time Lecturer: Mr Muhammad Goolam
Email: 2454262@students.wits.ac.za
Timetable
In the full-time timetable there is a double lecture and triple lab for IDSA each week:
- Tuesday: 10:15-12:00 – WSS2 (Wits Science Stadium)
- Thursday: 14:15-17:00 – MSL Labs
In the part-time timetable there is a single contact session per week:
- Monday: 17:30-21:00 – MSL004
Learning Management System
We will use Moodle as the primary platform for this course. Please visit https://courses.ms.wits.ac.za/moodle/course/view.php?id=38 and log in using your student number and usual Wits password. You should already be enrolled — if not, please confirm your registration with the faculty.
Note: We will not use Ulwazi for this course.
Communication and Consultations
All official announcements will be posted on the Announcements Forum on Moodle. While Moodle will email these to you, it is your responsibility to check that you are receiving and reading them. It will be assumed that all students have seen an announcement 24 hours after it is posted.
We will also be using Discord for communication within tutorial groups. Please join the course server at https://discord.gg/7bkgCQEMJg. Once you’ve joined, you must set your nickname to the format:
Firstname Lastname (StudentNumber)
Each tutorial group will have its own channel on the server. You may post messages there to communicate with your group and your tutor. There is also a tutor-support button that allows you to open a ticket for assistance — these will be monitored regularly by tutors, and you can expect a response. Once your query is resolved, please mark the ticket as closed.
You should still use the Questions & Answers Forum on Moodle for more general course-related queries. This allows other students to benefit from shared answers, and the forum is actively monitored by the teaching team.
Please try to start by asking your tutor (via Discord or in person), or by posting to the Moodle Q&A Forum before emailing me directly. With over 500 students, email should be a last resort for general queries, as individual messages may be missed.
If your question is personal, sensitive, or not suitable for a public forum, you may email me directly — just make sure to include COMS1017A or COMS1021A in the subject and your student number in the body. If you would like to speak with me one-on-one, you can book a consultation using this link: https://app.reclaim.ai/m/kleinric/consultation. I am also usually in the lab on Thursday afternoons, and you are welcome to speak to me then.
Textbook
This course does not require students to purchase a textbook — the content is widely available online and we will provide links to high-quality free resources. However, if you are funded or prefer to work from a physical book, the following are recommended:
Recommended Primary Text:
- Mark Allen Weiss, Data Structures and Algorithm Analysis in C++ (Fourth Edition), Pearson, 2014. (Weiss 2014) A solid and accessible text that balances theory and practical implementation in C++.
Other Recommended Books:
- M. Goodrich, R. Tamassia, D. Mount, Data Structures & Algorithms (Second Edition), Wiley & Sons, 2011. (Goodrich, Tamassia, and Mount 2011)
- N. Dale, C. Weems, T. Richards, C++ Plus Data Structures (Sixth Edition), Jones & Bartlett Learning, 2018. (Dale, Weems, and Richards 2018)
Advanced Reference:
- Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, MIT Press, 2009. (Cormen et al. 2009) Widely known as CLRS, this book is more advanced and rigorous. It is also prescribed in the Honours-level algorithms course and is worth investing in if you plan to continue in Computer Science.
For C++ Programming:
- Bjarne Stroustrup, Programming – Principles and Practice Using C++ (2nd Edition), Addison-Wesley, 2014. (Stroustrup 2014) An excellent and readable introduction to C++ by the language’s creator.
Other Resources
While textbooks are useful, they can be expensive — and there are many excellent free resources online that cover the course content thoroughly. I will link to specific resources during the semester, but you are encouraged to explore on your own as well. Useful resources include:
Algorithms and Data Structures
- MIT OpenCourseWare: Introduction to Algorithms (6.006) High-quality video lectures from MIT’s undergraduate algorithms course.
- GeeksforGeeks – Data Structures
- GeeksforGeeks – Fundamentals of Algorithms Detailed explanations and pseudocode for most data structures and algorithms we cover.
C++ Programming Help
- GeeksforGeeks – C++
- MIT OCW – Introduction to C++ (6.096)
- LearnCpp.com A very readable and well-organised free online C++ textbook.
Discussion and Troubleshooting
- Stack Overflow Ask and search for specific programming errors.
- YouTube Channels — Many tutorials and walkthroughs are available for C++, algorithms, and debugging.
If you find additional resources that help you understand the content, please consider sharing them on the Moodle Q&A forum or Discord.
Grading
The provisional mark breakdown is as follows:
| Item | Weight |
|---|---|
| Projects | 5% |
| Labs | 5% |
| Lab Tests | 25% |
| Theory Tests | 25% |
| Exam (Lab) | 20% |
| Exam (Theory) | 20% |
Tentative Schedule
This provisional schedule and is subject to change. A detailed schedule can be found here.
Block 3 Lectures
| Week | Topics |
|---|---|
| 1 | C++ Revision: abstraction, functions, recursion, static/dynamic memory allocation, pointers and arrays, structures, classes, unit testing. |
| 2 | Searching (Linear and Binary Search) and Sorting Algorithms (Bubble, Insertion, and Selection Sorts) |
| 3 | Arrays & Vectors 1 |
| 4 | Arrays & Vectors 2 |
| 5 | Linked Lists |
| 6 | Linked Lists |
| 7 | Stacks & Depth First Search |
Block 4 Lectures
| Week | Topics |
|---|---|
| 8 | Queues and Breadth First Search |
| 9 | Binary Search Trees |
| 10 | Binary Search Trees |
| 11 | Balanced Trees (AVL Trees) |
| 12 | Priority Queues & Binary Heaps |
| 13 | Sorting Algorithms (AVL Sort, Heap Sort, Mergesort & Quicksort) |
| 14 | Sorting Algorithms (AVL Sort, Heap Sort, Mergesort & Quicksort) |
Assessment Dates
| Test | Full-Time | Part-Time | Topics |
|---|---|---|---|
| Lab 1 | Thu 21 Aug 2025 | Sat 23 Aug 2025 | C++, Searching, Sorting, Vectors |
| Theory 1 | Thu 28 Aug 2025 | Mon 01 Sep 2025 | C++, Searching, Sorting, Vectors, Linked Lists |
| Lab 2 | Thu 18 Sep 2025 | Mon 22 Sep 2025 | Linked Lists |
| Theory 2 | Thu 09 Oct 2025 | Mon 13 Oct 2025 | Stacks, Queues, DFS, BFS, BST |
| Lab 3 | Thu 16 Oct 2025 | Mon 20 Oct 2025 | BST |
Satisfactory Performance
This outline extends the general undergraduate computer science course outline which fully defines the various outcome codes for different courses.
- FNQL: To qualify to write the final exams, you need a coursework average of at least 35% for the invigilated components of the course (the lab and theory tests). An FNQL is a fail for the course.
- FSUB: There are both practical (lab test 1, lab test 2, lab test 3, and the lab exam) and theory (theory test 1, theory test 2, and the theory exam) components to this course, you must achieve at least 35% for both components to pass the course, regardless of your overall average. An FSUB is a fail for the course.
Academic Integrity
Academic integrity is of utmost importance. Any form of academic dishonesty — including plagiarism, sharing answers, copying during invigilated assessments, or submitting work that is not your own — will be taken very seriously and may result in failing the course and/or being reported to the legal office.
While collaboration is encouraged during labs and projects, it’s essential to understand the line between them helping you learn, and someone doing the work for you. A good rule of thumb:
When you need help: They can look at your code to help you — but you should not look at theirs.
This ensures that you are the one doing the learning, thinking through the problem, and writing the solution. Copying someone else’s code — even with minor changes — is plagiarism, but worse, when you sit down alone in the tests you will not be able to do the work without them.
All lab, test, and project submissions will be monitored for plagiarism using a combination of automated tools and manual checks. Moodle and network activity logs will also be audited. Submitting material to platforms like Chegg or similar services is strictly prohibited and will be referred for disciplinary action.
On the Use of Language Models (e.g. ChatGPT, Copilot, Claude, Gemini, etc.)
Language models are powerful tools for learning — but like all tools, they must be used responsibly. A useful way to think about them is this:
Treat language models the same way you would treat a helpful friend.
You can ask them questions. You can brainstorm with them. You can learn from them.
But you should not ask them to do your work for you.
You are expected to learn how to code independently. If you rely on a model to write your solutions, you are not developing the skills you’ll need in invigilated assessments — or in future courses and your career. Use language models to learn, not to submit.
Debugging is also a fundamental part of becoming a good programmer. Don’t treat every error message as something to immediately copy and paste into a language model. Take the time to read your code, understand the error, and reason through the problem. This skill — reading and understanding your own code — is essential not just for tests, but for almost everything you will do in computing going forward.
If we suspect that a submission was generated (in full or part) by a language model, we may require you to complete a follow-up oral assessment. In such cases, your oral performance will determine your mark for that task.