Course Outline
Description
This introductory computer science course explores essential data structures and algorithms for their efficient manipulation. Students will learn how to represent values and associations in computer memory and evaluate key characteristics such as efficiency, time complexity, and space complexity. The course emphasizes practical implementations in C++, covering a range of data structures and algorithms.
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
Sorting Algorithms: Bubble Sort, Insertion Sort, Selection Sort, AVL Sort, Heap Sort, Merge Sort, and Quick Sort By the end of this course, students will have a solid foundation in data structures and algorithms, enabling them to write efficient and effective C++ programs.
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 Ireton Liu
Email: 2089889@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 – FNB102
- 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 – MSL005
Learning Management System
We will use Moodle for this course. Please go to https://courses.ms.wits.ac.za/moodle/course/view.php?id=380. Log in with your student number and usual Wits password. You should already be enrolled in the course - if you are not, please confirm your registration with the faculty.
We will not use Ulwazi in this course at all.
Communication
All official communication will be posted on the announcements forum on Moodle. While Moodle will email these announcements to you, it is your responsibility to ensure you are receiving and reading them. It will be assumed that all students have seen an announcement 24 hours after it is posted.
For general inquiries and discussions, please use public channels. This allows others to benefit from the answers to your questions. Avoid emailing questions directly to me unless they pertain solely to you or are sensitive in nature. To facilitate efficient communication in a large class, I prioritize responding to queries posted in the Questions & Answers forum on Moodle Overflow over emails. If you know the answer to a question someone else has asked, feel free to help them out! I will always be checking the forum and will make corrections where necessary.
Please note that while unofficial student WhatsApp groups may exist, they are not monitored by the university. However, participation in these groups is still subject to the principles of the Wits Code of Conduct and Social Media Policy — always act with respect.
Consultations
I will be available during the 3 hour lab session on Thursdays. Should there be a large number of other queries that I am not able to assist with during that time, then I will make another consultation time available.
Textbook
The structures presented in this course are fairly common and you will find many resources that cover this content online. I try to avoid prescribing a textbook for this course because of the associated costs. However, if you can buy a book or are funded by a bursary, then I recommend trying to get a copy of:
- Mark Allen Weiss, Data Structures and Algorithm Analysis in C++ (Fourth Edition), Pearson, 2014 (Weiss 2014)
I also recommend the following 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)
The best, most comprehensive book about algorithm analysis is Cormen et al. (2009) and is prescribed by almost every major Computer Science course worth attending. They use the phrase “introduction” fairly liberally, this book is advanced and covers most of the major algorithms. It is also a prescribed textbook in honours, so it might be worth getting if you are planning to stick around:
- TH Cormen, CE Leiserson, RL Rivest, and C Stein. Introduction to Algorithms. MIT press. 2009. (Cormen et al. 2009)
For a book on introductory programming in C++ see:
- Bjarne Stroustrup, Programming – Principles and Practice Using C++ (2nd Edition), Addison-Wesley, 2014 (Stroustrup 2014)
Other Resources
While these textbooks are useful, they can be expensive and there are many fantastic resources online.
Where relevant I will post links to other resources as well. I encourage you to use Google, StackOverflow and YouTube generally. For particularly good content on data structure and algorithms, see these sites:
- MIT OpenCourseware: Intro to Algorithms,
- GeeksForGeeks: Data Structures, and
- GeeksForGeeks: Fundamentals of Algorithms
For general C++ assistance these are worth checking out as well:
If you find any other good resources, please share these resources with others in the class as well using the forums.
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: https://docs.google.com/spreadsheets/d/17qICHXQ9saQRPwGoFFhApgRjeyO3HW9A7iwWDgP8Kdg.
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 |
| 4 | Arrays & Vectors |
| 5 | Linked Lists (IDSA Lectures on both Monday and Tuesday; No DCS lecture that week) |
| 6 | Stacks & Depth First Search |
| 7 | N/A (DCS Lectures on both Monday and Tuesday; No IDSA lecture that week) |
Block 4 Lectures
| Week | Topics |
|---|---|
| 1 | Queues and Breadth First Search |
| 2 | Binary Search Trees |
| 3 | Balanced Trees (AVL Trees) |
| 4 | N/A (Public Holiday) |
| 5 | Priority Queues & Binary Heaps |
| 6 | Sorting Algorithms (AVL Heap Sorts, Mergesort & Quicksort) |
Assessment Dates
| Assessment | Full-Time | Part-Time | Topics |
|---|---|---|---|
| Lab Test 1 | 15 Aug 2024 | 14 Aug 2024 | C++, Searching, Sorting, Vectors |
| Theory Test 1 | 22 Aug 2024 | 26 Aug 2024 | C++, Searching, Sorting, Vectors, Linked Lists |
| Lab Test 2 | 29 Aug 2024 | 02 Sep 2024 | Linked Lists |
| Theory Test 2 | 03 Oct 2024 | 07 Oct 2024 | Stacks, Queues, DFS, BFS, BST |
| Lab Test 3 | 10 Oct 2024 | 14 Oct 2024 | BST |
Satisfactory Performance
This outline extends the general undergraduate computer science course outline.
- FSUB: There are both practical (lab test 1, lab test 2, and lab exam) and theory (theory test 1, theory test 2, and theory exam) components to this course, you must achieve at least 35% for both components to pass the course, regardless of your overall average.
- FNQL: To qualify to write the final exams, you need a coursework average of at least 35%.
Academic Integrity
Academic integrity is of utmost importance. Any form of communication during quizzes, sharing of answers, practicals, or engaging in plagiarism will be taken very seriously by the university. Such actions will result in failing the course (FCM) and/or being reported to the legal office.
While collaboration during labs and projects is encouraged, it is crucial to understand the boundary between helping someone and providing them with the answers. A good rule of thumb: if you are struggling, you can show someone a section of your code for assistance, but you should not look at their code. We will monitor Moodle and network logs closely and will check all submissions for plagiarism. You may not use sites like Chegg for assistance with any submissions. Anyone found submitting assessments to such sites will be referred to the legal office.
Tools like ChatGPT can generate and interpret source code effectively. I encourage you to use these tools to help you understand code concepts. However, resist the temptation to use them to solve lab or project problems for you. While they might help you complete labs and projects, developing your problem-solving skills independently is essential for success in tests, exams, future courses, and your career.
If you are suspected of plagiarism or using AI tools for any hand-ins, you may be required to do an oral assessment, and the mark from this assessment will replace the original.