Sorting and searching chapter

CONTENTS

NO.	TOPIC	PAGE
	Introduction and overview of module	3
	Module duration, credits and NQF level	3
	Learning outcomes and assessment criteria for the module	3-4
	Learning Content	4
	Learning outcomes and assessment standards for each unit	4-6
	Lecture plan	7-8
	Prescribed reading and study material	9
	Suggested reading	9
	Open Education Resource (OER) Links	9
	Stationery requirements	9
	Assessment strategy	9
	Assessment due dates	10
	Assignment	10
	Oval Assignment marking rubric	11
	Notional study hour map	12
	Lecturers contact information	12
	Assignment cover sheet	13

The total contact time will be 4 periods a week
Please see the Notional Study Hours table on page 12 which provides a breakdown of the learning hours for the module.

Specifying a Bag
Measuring an Algorithm Efficiency

Resizing and Core methods of Arrays

UNIT 3: Stacks and Queues (Chapter 5, 6, 10 and 11)

UNIT 4: Recursion, Sorting and Searching (Chapter 7, 8, 18)

What is Recursion?

List Types
List Implementation

Graphs and its Types
Graph Implementation

On successful completion of this unit, the student will be able to:

Describe how to specify Bags

We know this when the student:

Knows how to start Bags

Chapter from Prescribed Textbook: 2

Learning Outcome:

Discuss implementation of an Array using ADT

Assessment Criteria:

Understands to apply the code
Creates Resizing an Array

Define Stacks
Know Stack implementation

Knows Stack Operations
Understands Push and Pop

Chapter from Prescribed Textbook: 7, 8 and 18

Learning Outcome:

Explain Searching
Understand the Searching Techniques

Understands Sorting
Describes Sorting methods

On successful completion of this unit, the student will be able to:

Define List

Assessment Criteria:

We know this when the student:

Understands List Implementation

Unit 6: Trees and Graphs

Understand Tree Concepts
Describe Traversal

Understands Tree Interfaces
Manages General Trees

This lesson plan is subject to change.

Wk			Unit and Topics	Teaching and Learning Strategy	Homework /
SEMESTER TWO- TERM FOUR
1			Unit 1: Bags and Efficiency of Algorithms	Power point slides for lecture. Practical Examples	Review Questions to be confirmed in class.
2		- 11/08/2017	Describe how to specify Bags Understand the concept of ADT	Power point slides for lecture. Practical Examples	Review Questions to be confirmed in class.
3			Chapter: 2 Describe the features of an Array	Power point slides for lecture. Practical Examples	Review Questions to be confirmed in class.
4			Unit 2: Bag Implementation that Use Arrays Chapter: 2 Explore the Types of Arrays	Power point slides for lecture. Practical Examples	Review Questions to be confirmed in class.
5			Unit 3: Stacks and Queues Chapter: 5 and 6	Power point slides for lecture. Practical Examples	Review Questions to be confirmed in class.
		01/09/2017	Spring Ball – Normal Lectures
6		08/09/2017	Unit 3: Stacks and Queues	Power point slides for lecture. Practical Examples	Review Questions to be confirmed in class.
11/09/2017 -15/09/2017			TEST WEEK
22/09/2017			HOLIDAY
SEMESTER TWO-TERM FOUR
7	26/09/2017		Chapter: 7 and 8 Define Recursion	Power point slides for lecture. Practical Examples	Review Questions to be confirmed in class.
8			Unit 4: Recursion, Sorting and Searching Chapter: 18 Describe Sorting	Power point slides for lecture. Practical Examples	Review Questions to be confirmed in class.
9	13/10/2017		Revision	Previous questions.	Questions for discussion.
10	16/10/2017		Revision	Previous questions.	Questions for discussion.
23/10/2017			Study Leave
			SECOND SEMESTER EXAMINATION
04/12/2017- 06/12/2017			SUPPLEMENTARY EXAMINATION

Michael T. Goodrich and Michael H. Goldwasser. (2015) Data Structures and Algorithms in Java. Sixth Edition. United States of America: Wiley

Drake. P, (2013) Data Structures and Algorithms in Java. First Edition.

STATIONERY REQUIREMENTS

You will need:

Continuous Assessment (CASS)

Test 20%

ASSESSMENT DUE DATES

DATE DUE: 4th September 2017

QUESTIONS

Explain the time complexity to search an element in a Binary Tree with n nodes. (20)

NOTE:

The assignment cover page appears on the last page of this student guide. Student to make a copy, complete the relevant details and staple on the front of your assignment when handing in.

Criteria		Maximum Marks	Student’s Marks
Structure and Layout		10%
Appropriate Content		60%
Appropriate Examples		10%
Academic Excellence		10%
Algorithm Structure		05%
Reference List		05%
FINAL MARK		100%
Lecturer’s Comments

Lecturer Name
Lecturer Signature
Date
Internal Moderator’s Comments

Internal Moderator’s Name
Internal Moderator’s Signature
Date

NOTIONAL STUDY HOUR MAP

Staff	Lecturer
Name	Ravin Baburam
Office	2^nd Floor, IT Staff Room
Campus	Durban
Consultation Times	Please contact the lecturer to make an appointment
Telephone Number	031 305 6192

ASSIGNMENT COVER SHEET