CIT216

Fundamentals of Data Structures

Sciences
200 level
2 credit units
225 pages
31 units

This course introduces the fundamental concepts of data structures and algorithms. It covers basic data types, including lists, stacks, and queues, and explores their underlying principles. The course also delves into object-oriented programming concepts using Java, focusing on implementing various data structures. Additionally, it examines algorithm design techniques such as greedy algorithms, divide-and-conquer, and dynamic programming, providing a comprehensive understanding of data organization and problem-solving strategies.

Start reading

About this course

Difficulty: Intermediate
Study hours: 45 hours
Maths: Basic
Content: Theoretical, practical, problem solving
Practical work: Yes

How it is assessed

Assignments
Tutor marked assessments
Final examination

What you'll read

The real module and unit structure of CIT216, taken from the course material NOUN publishes.

Module 1 · FOUNDATIONAL DATA STRUCTURES

Module 2 · HASHING AND TREES

Module 3 · INTRODUCTION TO JAVA PROGRAMMING

Module 4 · JAVA PROGRAMMING

Module 5 · ALGORITHMS

Module 6 · GRAPHS AND SORTING

What you should be able to do

Describe basic operations on stacks, lists, and queues.
Explain trees, hashing, and binary search trees.
Identify object-oriented programming concepts.
Develop Java programs for simple applications.
Discuss basic data types: lists, stacks, and queues.
Describe structures and algorithms for external storage.
Identify directed and undirected graphs.
Discuss sorting algorithms.
Describe algorithm efficiency and recursion.
Discuss algorithm design techniques.

What it prepares you for

Careers

Software Developer
Data Analyst
Algorithm Engineer
Database Administrator
System Designer

Where it is applied

Software Development
Data Science
Web Development
Mobile Application Development
Database Management

Where it gets hard

The units students slow down on, and what makes each one heavy.

Module 2: Hashing and Trees
Unit 3: Search Trees
Understanding the concepts of AVL tree implementation requires grasping tree balancing and rotation techniques, which can be challenging for students without a strong foundation in tree data structures.
Module 5: Algorithms
Unit 5: Dynamic Programming Algorithm
Dynamic programming involves understanding overlapping subproblems and optimal substructure, requiring a shift in thinking from more straightforward algorithmic approaches.

A suggested way through it

Suggested

13 weeks, about 45 hours in total. Yours will differ.

Week 1Module 1: Foundational Data Structures
- Unit 1: Fundamentals · 3 hours
  Understand the definitions of data type, abstract data type, and data structure.. Classify different data types and provide examples.. Explain the relevance of data structures in programming..
Week 2Module 1: Foundational Data Structures
- Unit 2: Arrays · 3 hours
  Describe arrays, their dimensionality, and declaration.. Explain the terms element and array name.. Express a two-dimensional array linearly.. Distinguish between static and dynamic arrays.. Explain the importance of arrays in computer applications..
Week 3Module 1: Foundational Data Structures
- Unit 3: The List Data Structure · 3 hours
  Describe a List.. Identify the elements of a List.. Explain the operations and implementations of Lists..
Week 4Module 1: Foundational Data Structures
- Unit 4: The Stack Data Structure · 3 hours
  Describe the stack data structure.. Identify two basic modes of implementing a stack.. Outline the applications of stacks in computing.. Explain the two methods of storing a stack..
Week 5Module 1: Foundational Data Structures
- Unit 5: The Queue Data Structure · 3 hours
  Describe a queue data structure.. Give at least three applications of queues.. Explain the operations on a queue.. Describe two basic modes of queue storage..
Week 6Module 2: Hashing and Trees
- Unit 1: Hashing · 3 hours
  Explain the basic idea of hashing.. Describe hash keys and functions.. Give the basic implementation of hash functions.. Define a hash table.. Explain the applications of hash tables..
Week 7Module 2: Hashing and Trees
- Unit 2: Trees · 3 hours
  Give a basic definition of a tree.. Describe binary trees.. Explain tree traversals.. Evaluate arithmetic expressions by means of tree traversals..
Week 8Module 2: Hashing and Trees
- Unit 3: Search Trees · 3 hours
  Explain what a search tree is.. Describe a successful search.. Describe an unsuccessful search.. Explain the implementation of AVL search trees..
Week 9Module 2: Hashing and Trees
- Unit 4: Garbage Collection and Other Heap · 3 hours
  Describe garbage.. Explain garbage collection.. Describe the mark-and-sweep garbage collection.. Explain the fragmentation problem..
Week 10Module 2: Hashing and Trees
- Unit 5: Memory Allocation · 3 hours
  Explain the concept of memory allocation.. Discuss the first fit allocation technique.. Explain the best fit allocation technique.. Describe the buddy system..
Week 11Module 3: Introduction to Java Programming
- Unit 1: Object-Oriented Programming Concepts · 3 hours
  Define an object.. Explain what a class is.. Define an Inheritance.. Explain the term 'object-oriented programming'..
Week 12Module 3: Introduction to Java Programming
- Unit 2: Variables · 3 hours
  Define a variable.. Describe types of java programming variables.. Explain the naming conventions of variables..
- Unit 3: Operators · 3 hours
  Explain the term 'operators'.. Describe simple assignment operators.. Explain arithmetic operators.. Discuss unary operators.. Explain equality and relational operators.. Discuss the conditional operators..
Week 13Module 3: Introduction to Java Programming
- Unit 4: Expressions, Statements and Blocks · 3 hours
  Define an expression.. Describe statements, giving typical examples of expression statements.. Discuss the concept of blocks..
- Unit 5: Control Flow Statements · 3 hours
  Describe control flow statements.. Gain knowledge of the decision-making statements.. Explain the looping statements..

Preparing for the exam

What to do

Create flashcards for key data structure definitions (stacks, queues, trees).
Practice implementing basic data structures in Java without reference materials.
Review and understand the time complexity of different sorting algorithms.
Focus on understanding the core concepts of object-oriented programming in Java.
Work through examples of greedy, divide-and-conquer, and dynamic programming algorithms.
Create a cheat sheet of common Java syntax and data structure methods.
Allocate specific time slots for practicing coding problems related to data structures and algorithms.
Review all tutor-marked assignments (TMAs) and address any areas of weakness.
Form a study group to discuss challenging concepts and practice problem-solving together.
Prioritize understanding over memorization - focus on applying concepts to solve problems.
Practice writing code by hand to simulate exam conditions.
Review graph algorithms and their applications, such as shortest path problems.
Create concept maps linking different data structures and algorithms to understand their relationships.

Questions students ask about this course

What is CIT216 about?

How many units does CIT216 have?

CIT216, Fundamentals of Data Structures, has 31 units across 6 modules, over 225 pages of course material. You can read it one unit at a time.

How many credit units is CIT216?

CIT216 carries 2 credit units, at 200 level in Sciences.

Is CIT216 hard?

CIT216 is rated intermediate level, with basic mathematical content. It is mostly theoretical, practical and problem solving work, and it has a practical component.

How long does CIT216 take to study?

About 45 hours of study, spread across its 31 units.

How is CIT216 assessed?

CIT216 is assessed by assignments, tutor marked assessments and final examination.

What can I do with CIT216?

Software Developer, Data Analyst, Algorithm Engineer, Database Administrator and System Designer.