syllabus: Algorithms and Data Structures 1 [CM1035]

Algorithms and Data Structures 1 [CM1035]

Course Description

The study of algorithms and data structures is central to an undergraduate degree in computer science. This course will introduce you to your first algorithms and data structures, as well as the tools of abstraction required to help you decide which of these concepts to use. In this way you will not only enhance your box of problem solving tools, you will be able to critically compare, and assess the advantages and disadvantages, of these tools.

The course starts at a basic level by describing problems and algorithms in computer science. It then goes on to introduce the tools for describing algorithms: flowcharts and pseudocode. You will then build on these basics to cover a wide range of topics:

• Abstract data structures such as vectors, queues and stacks.
• Implementation of abstract data structures with arrays and linked lists.
• Searching algorithms: Linear Search and Binary Search.
• Sorting algorithms: Bubble Sort, Insertion Sort, Quicksort and Mergesort.
• Recursion as a technique for algorithm design.
• Worst-case time complexity: the RAM model of computation, Big O notation and computational complexity.

In this course you will be solving problems both at an abstract level and in the form of coding activities. The techniques required for problem solving will touch upon, and utilise, the concepts covered in the topics. For example, in this course, every topic ends with a problem, and the solution will be the launching pad for the next topic.

Course Goals and Objectives

Upon successful completion of this module, you will be able to:

1. Utilise pseudocode and flowcharts to describe algorithmic processes.
2. Compare and outline the functionality of both abstract and concrete data structures.
3. Describe and implement various sorting and searching algorithms.
4. Explain the concept of recursion and implement a recursive algorithm.
5. Analyse the worst-case performance of algorithms in terms of a model of computation.

Textbook and Readings

Specific essential readings for this course will be taken from the following text book:

1. Cormen, T.H., C.E. Leierson, R.L. Rivest and C. Stein Introduction to Algorithms. (Cambridge, MA: MIT Press, 2009) 3rd edition.

The specific pages for the reading activities will be given in the platform, and there is no need to read beyond to recommended pages.

In addition to the text book, there are additional reading activities written by the course author, some of which involve coding exercises.

There will also be discussion prompts asking you to do some independent research using online sources.

Course Outline

The course consists of ten topics divided into 20 weeks that focus on key concepts. The last 2 weeks of the 22 week session will involve final assessment preparation.

Topics Covered	Key Concepts	Learning Outcomes
Topic 1. Problems, algorithms and flowcharts	Problems in computer science (CS), algorithms in CS and flowcharts.	Explain in broad strokes what are problems and algorithms in Computer Science.
		Explain the basic elements and construction of flowcharts.
		Express elements of simple algorithms as flowchart.
Topic 2. Pseudocode	Pseudocode, iteration and conversion from flowcharts to pseudocode.	Explain the necessity and concept of pseudocode.
		Describe the concept of iteration and how it is represented in pseudocode.
		Convert flowchart (if possible) to pseudocode.
Topic 3. Vectors, stacks and queues	Vectors, stacks and queues.	Describe the basic elements of an abstract data structure.
		Explain queues, stacks and vectors in terms of their structure and operations.
		Compare these three different abstract data structures of vectors, stacks and queues.
Topic 4. Data structures and searching	Arrays, dynamic arrays, the linear search algorithm and linked lists.	Explain the difference between an abstract data structure and a concrete data structure.
		Explain how abstract data structures can be implemented by arrays and linked lists.
		Describe the linear search algorithm.
Topic 5. Sorting data I	Bubble sort, insertion sort and iteration in JavaScript.	Explain the bubble sort in terms of comparisons.
		Explain insertion sort and how it is different from bubble sort.
		Relate and translate iteration in pseudocode to iteration in JavaScript.
Topic 6. What makes a good algorithm?	random access machines, growth of functions and time complexity of algorithms.	Explain the model of random access machines.
		Explain asymptotic growth of functions and worst-case time complexity.
		Describe worst-case time complexity of bubble and insertion sort.
Topic 7. Searching data II	Binary search, speeding up search with sort and logarithmic time complexity.	Explain the binary search algorithm and the importance of sorting.
		Describe the worst-case time complexity of binary search and compare it with that of linear search.
		Explain how search algorithms can be used in contexts beyond searching a data structure.
Topic 8. Recursion	Decrease and conquer, recursion, and the call stack.	Explain the general concept of decrease and conquer.
		Apply the tool of recursion to algorithms.
		Explain how recursion is implemented using the call stack.
Topic 9. Sorting data II	Divide and conquer, quicksort, and merge sort.	Explain the concept of divide and conquer.
		Explain and implement merge sort and quicksort.
		Compare the worst-case time complexity of certain sorting algorithms.
Topic 10. Computational Complexity	Decision problems, complexity classes, NP-complete problems.	Explain what is a decision problem.
		Explain the basic concept of a complexity class.
		Explain why NP-complete problems are an obstace to general-purpose efficient algorithms.

Learning Activities of This Course

The course is comprised of the following elements:

• Lecture Videos - In each topic the key concepts will be presented through a collection of short video lectures. You may stream these videos for playback within the browser by clicking on their titles or download the videos.
• Readings - Each topic may include several suggested readings. These are a core part of your learning, and, together with the videos, will cover all of the concepts you need for this course.

• Practice Quizzes - Each module will include practice quizzes, intended for you to assess your understanding of the topics. You will be allowed unlimited attempts at each practice quiz. There is no time limit on how long you take to complete each attempt at the quiz. These quizzes do not contribute toward your final score in the class.

• Graded Quizzes - In topics 1-5, there is an end-of-topic quiz that will contribute to your coursework grade. You will be allowed maximum two attempts per each quiz, and 50 minutes per quiz. Your highest score will be used when calculating your final score.
• Discussion Prompt - Each topic includes discussion prompts. You will see the discussion prompt alongside other items in the lesson. Each prompt provides a space for you to respond. After responding, you can see and comment on your peers' responses. All prompts and responses are also accessible from the general discussion forum and the module discussion forum.
• Programming Activities- There are multiple programming activities for a few of the topics, more so in the second half of the course. These involve completing JavaScript files and uploading them to the platform to be auto-graded. You will receive feedback saying whether tasks were correctly completed.
• Interactive Simulations- Some of the topics will include interactive software that help you understand sorting algorithms and stacks. Some of these will be like game-like. They should be fun and will not be graded, but they also aim to provide you with valuable practical learning.

• Revision Exercises - To revise for the exam there are examples of exam questions.

How to Pass This Course

The course has two major assessments each worth 50% of your grade:

• Coursework:  this consists of several activities that you do on the Coursera platform and which will be assessed half way through course (after week 11)
• Written examination: you will take this at an examination centre in your country.

The mark shown on the Coursera platform is your coursework mark and you should remember that the exam counts for another 50%.

The coursework consists of five quizzes and one written, staff graded assignment consisting of exercises in writing pseudocode and analysing algorithms

This is a detailed breakdown of all of the marks:

Activity	Required	Deadline week	Estimated time per week	% of final grade
End of topic quizzes for topics 1-5	Yes	1-10	10 hours	10%
Written, staff graded coursework	Yes	11	Approximately 10 hours	40%
Written Examination	Yes	22	2 hours 15 minutes	50%