BSc: Data Structures Algorithms

From IU
Jump to navigation Jump to search

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

Prerequisite topics

Course Topics

Course Sections and Topics
Section Topics within the section
Elementary Data Structures, Algorithmic Complexity and Approaches
  1. Algorithms and Their Analysis
  2. Elementary Data Structures
  3. Hashing Map and Collision Handling
  4. Algorithmic Strategies
Sorting Algorithms and Trees
  1. Comparison and Non-comparison Sort
  2. Binary Search Tree
  3. Balanced Binary Search Trees
  4. Tree Traversals
  5. Priority Queues and Binary Heaps
Graphs
  1. Graph Representations
  2. Searching in Graphs
  3. Minimum Spanning Tree
  4. Shortest Path
  5. 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

Recommendations for students on how to succeed in the course

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.

Closed access resources

Software and tools used within the course

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