BSc: Data Structures Algorithms

Data Structures and Algorithms

• Course name: Data Structures and Algorithms
• Code discipline: —
• Subject area:

Short Description

This course provides an intensive treatment of a cross-section of the key elements of algorithms and data-structures, with an emphasis on implementing them in modern programming environments, and using them to solve real-world problems. The course will begin with the fundamentals of searching, sorting, lists, stacks, and queues, but will quickly build to cover more advanced topics, including trees, graphs, and algorithmic strategies. It will also cover the analysis of the performance and tractability of algorithms and will build on the concept of Abstract Data Types. A key focus of the course is on effective implementation and good design principles.

Prerequisites

Prerequisite subjects

• CSE101 - Introduction to Programming: OOP, Pointers, and Functional Programming
• CSE201 - Mathematical Analysis I
• CSE113 - Logic and Discrete Mathematics

Course Topics

Course Sections and Topics

Section	Topics within the section
Elementary Data Structures, Algorithmic Complexity and Approaches	Algorithms and Their Analysis Elementary Data Structures Hashing Map and Collision Handling Algorithmic Strategies
Sorting Algorithms and Trees	Comparison and Non-comparison Sort Binary Search Tree Balanced Binary Search Trees Tree Traversals Priority Queues and Binary Heaps
Graphs	Graph Representations Searching in Graphs Minimum Spanning Tree Shortest Path Max-flow Min-cut

Intended Learning Outcomes (ILOs)

What is the main purpose of this course?

This course helps you master the following concepts: Algorithms; Algorithm Analysis; Algorithmic Strategies; Data Structures.

ILOs defined at three levels

Level 1: What concepts should a student know/remember/explain?

By the end of the course, the students should be able to ...

• Algorithms
• Abstract Data Types
• Data Structures
• Algorithmic Strategies
• Asymptotic Analysis
• Amortized Analysis

Level 2: What basic practical skills should a student be able to perform?

By the end of the course, the students should be able to ...

• Difference between different abstract data types and data structures
• How to perform asymptotic and amortized analysis
• Difference between various algorithmic strategies
• Different algorithms: such as sorting, searching, etc.
• Different types of tree ADTs, their properties related algorithms
• Graphs, their properties, and related algorithms

Level 3: What complex comprehensive skills should a student be able to apply in real-life scenarios?

By the end of the course, the students should be able to ...

• Algorithmic strategies to solve real-life problems
• Asymptotic analysis to Analyze algorithms and software’s complexity
• Trees and Graphs (and their theory) to solve complex problems

Grading

Course grading range

Grade	Range	Description of performance
A. Excellent	90-100	-
B. Good	75-89	-
C. Satisfactory	60-74	-
D. Poor	0-59	-

Course activities and grading breakdown

Activity Type	Percentage of the overall course grade
Labs/seminar classes	0
Interim performance assessment	30
Exams	70

Resources, literature and reference materials

Open access resources

• T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press 2009.
• M. T. Goodrich, R. Tamassia, and M. H. Goldwasser. Data Structures and Algorithms in Java. WILEY 2014.

Teaching Methodology: Methods, techniques, & activities

Activities and Teaching Methods

Teaching and Learning Methods within each section

Teaching Techniques	Section 1	Section 2	Section 3
Development of individual parts of software product code	1	1	1
Homework and group projects	1	1	1
Midterm evaluation	1	1	1
Testing (written or computer based)	1	1	1
Discussions	1	1	1

Activities within each section

Learning Activities	Section 1	Section 2	Section 3
Question	0	1	0

Formative Assessment and Course Activities

Ongoing performance assessment

Section 1

Activity Type	Content	Is Graded?
Question	For a given function give an asymptotic upper bound using “big-Oh” notation	1
Question	Compute the worst case running time of a given algorithm.	1
Question	Insert items into a hashmap given a hash function and a collision handling scheme.	1
Question	Given an algorithm, identify its algorithmic strategy	1
Question	How to implement various data structures?	0
Question	Implement an algorithm for a given task having a desired worst case time complexity	0
Question	Describe the difference between different types algorithmic strategies	0
Question	Implement a hashmap	0
Question	Solve various practical problems using different algorithmic strategies	0

Section 2

Activity Type	Content	Is Graded?
Question	Given a BST, answer different questions, such as (a) is the tree an AVL tree? What is the predecessor of a certain node? (b) Will after the removal of a certain node, the resulting tree will be a AVL tree or not?	1
Question	Similar question as above but for other types of balanced binary search trees, including randomly built binary search trees.	1
Question	Questions related to tree algorithms, such as tree traversals	1
Question	Given a sorting problem defined under some constraints, what sorting algorithm will you use and why?	1
Question	Implement different types of binary search trees	0
Question	Implement tree traversals	0
Question	Implement different sorting algorithms, such as quicksort, countsort, bucketsort, etc.	0

Section 3

Activity Type	Content	Is Graded?
Question	Given a graph with a certain number of vertices and connected components, compute the largest number of edges that it might have?	1
Question	What is the difference between adjacency list and adjacency matrix representation of a graph?	1
Question	Implement various graph representations	0
Question	Given a computing problem, devise an algorithm to solve it using Graphs and then implement your algorithm.	0

Final assessment

Section 1

1. For a given function give an asymptotic upper bound using “big-Oh” notation
2. Compute the worst case running time of a given algorithm.
3. Insert items into a hashmap given a hash function and a collision handling scheme.
4. Given an algorithm, identify its algorithmic strategy

Section 2

1. Given an unbalanced AVL tree, perform double rotation and show the resulting tree.
2. Given a sequence of elements to be sorted, explain which sorting algorithm you would use to sort the input the fastest and why you chose this sorting algorithm.
3. Implement a sorting algorithm given a problem and specify the big-Oh running time for your algorithm.

Section 3

1. Give pseudocode for performing a certain operation in a required time complexity using the adjacency list representation.
2. Give pseudocode for performing a certain operation in a required time complexity using the adjacency list representation.
3. Calculate the maximum flow for a given flow network

The retake exam

Section 1

Section 2

Section 3