Course Outline
Lecturer
Lecturer: Steve James
Office: UG03, TWK Mathematical Sciences Building
Email: steven.james@wits.ac.za
Teaching Mode
Now that COVID-19 restrictions have been dropped, we will be moving back to in-person lectures, labs and tutorials for this course. However, we will be maintaining some of the tools we have used in previous online iterations of this course. We we will be using Discord to host a virtual “classroom.” You will be sent more information on how to join during the first week of class. I encourage everyone to post regularly on Discord with questions, suggestions and course-related resources that you come across. There are desktop, web and mobile apps available for computer and phone platforms, and the tutors and I will be online as often as possible. In as far as it is possible, I encourage everyone to use our space on Discord for all their course needs. In particular, I suggest that you use the Discord server in place of student WhatsApp groups which are unofficial and are not moderated by the university. Note however, that should you use unofficial students WhatsApp groups you are still subject principles of the Wits code of conduct and social media policy - act with respect.
This online book will be updated regularly with new text, videos, and other resources. There will also practical labs that must be submitted on a near-weekly basis. These will be made available via regular Moodle submissions.
Learning Management System
We will use Moodle for this course. Please go to https://courses.ms.wits.ac.za/moodle/course/view.php?id=221. Log in with your student number and usual Wits password. You should already be enrolled in the course.
We will not use Ulwazi in this course at all.
Communication
All official communication will be posted to the announcements forum on Moodle. Moodle will send you email digests daily, but it is still your responsibility to ensure you’re receiving these emails. You can change your email preferences on Moodle to receive a single email per post if you prefer that.
Course Description
This course provides the student with the theory of computation, and the application and implementation of various algorithms. In particular, several important problem classes are investigated and both theoretical and empirical analysis are performed to come up with an optimal solution for a given problem. This course includes the following topics: advanced search and sort algorithms, greedy algorithms, dynamic programming, closest pair of points problems, complexity classes (P, NP and NP-Completeness), and AI-related algorithms.
Objectives
At the end of this course you should, amongst others, be able to:
- describe the fundamental differences and relationships between various complexity classes
- list the different algorithms available for a given problem;
- perform both empirical and theoretical analysis of a given algorithm;
- identify optimal algorithm based on the time and space complexity for a given problem;
- apply changes to existing algorithms to improve the time and space complexity.
Prerequisites
- Algorithms in this course should be implemented in C++.
- Some of the submissions will require data to be plotted. You need not use C++ for this, and so a more appropriate language (e.g. Python) will be useful here.
- Ideas covered in COMS3003A: Formal Languages and Automata will be useful when discussing complexity classes.
- Content covered in COMS2015A: Advanced Analysis of Algorithms will be assumed.
Textbook
There is no prescribed textbook for this course. All notes, tutorials and labs will be made available on Moodle. However, the following are recommended for those interested:
- T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms (3rd Edition), MIT Press, 2009.
- S. Baase, Computer Algorithms: Introduction to Design and Analysis (2nd Edition), Addison-Wesley, 1993.
- S. Russel, P. Norvig, Artificial Intelligence: A Modern Approach (3rd Edition), Prentice-Hall, 2009.
- G. Brassard, P. Bratley, Fundamentals of Algorithmics, Prentice-Hall, 1996.
Grading
The class mark will constitute 50% of the overall mark, and will consist of weekly labs, two class tests and an assignment. The exam is currently scheduled to be in-person.
| Activity | Weight |
|---|---|
| Labs | 10% |
| Class Test 1 | 10% |
| Class Test 2 | 10% |
| Assignment | 20% |
| Exam | 50% |
Timetable
The table below lists the times allocated in the university’s timetable for this course.
Note that lab and tutorial slots are shared with COMS3010A (Operating Systems). It is up to you to manage your time responsibly. Tutors will be available in both sessions, so you are welcome to ask them about either course.
| Course | Activity | Day | Times |
|---|---|---|---|
| COMS3005A | Lecture | Wednesday | 08h00 — 09h45 |
| COMS3005A | Lab | Monday | 14h15 — 17h00 |
| COMS3005A | Tutorial | Friday | 12h30 — 13h15 |
Tentative Schedule
The following serves as a rough guide for the content we will be covering during the course, but please note that it is subject to change.
Block 3
| Week | Topics |
|---|---|
| 1 | Course introduction |
| 2 | Complexity Classes I |
| 3 | Complexity Classes II |
| 4 | Algorithms for AI I |
| 5 | Algorithms for AI II |
| 6 | Search and Sorting Algorithms I |
| 7 | Sorting Algorithms II |
Block 4
| Week | Topics |
|---|---|
| 8 | Greedy Algorithms |
| 9 | Dynamic Programming I |
| 10 | Dynamic Programming II |
| 11 | Computational Geometry |
| 12 | Advanced Data Structures I |
| 13 | Advanced Data Structures II |
Academic Integrity
There is a zero-tolerance policy regarding plagiarism in the School. Refer to the General Undergraduate Course Outline for Computer Science for more information.
Communication during quizzes, sharing of answers or practicals, and all forms of plagiarism are taken very seriously by the university and will result in failing the course and/or being reported to the legal office. In most cases I encourage you to help each other with problems, but be aware of the line between helping someone and giving them the answer. A good rule of thumb: if I am struggling, I can show someone a section of my code for assistance, but I cannot look at theirs. We will be monitoring Moodle logs closely and will be checking all submissions for plagiarism. You may not make use of sites such as Chegg for assistance with any submission. Anyone found submitting assessments to such a site will be referred to the legal office.