Difference between revisions of "BSc: Data Structures Algorithms"

From IU
Jump to navigation Jump to search
 
(8 intermediate revisions by 4 users not shown)
Line 1: Line 1:
  +
 
= Data Structures and Algorithms =
  
= Data Structures and Algorithms =
  +
* '''Course name''': Data Structures and Algorithms
  +
* '''Code discipline''': —
  +
* '''Subject area''':
   
  +
== Short Description ==
−
* <span>'''Course name:'''</span> Data Structures and Algorithms
  
  +
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.
−
* <span>'''Course number:'''</span> —
  
   
−
== Course characteristics ==
 +
== Prerequisites ==
   
−
=== Key concepts of the class ===
 +
=== Prerequisite subjects ===
  +
* CSE101 - Introduction to Programming: OOP, Pointers, and Functional Programming
  +
* CSE201 - Mathematical Analysis I
  +
* CSE113 - Logic and Discrete Mathematics
   
  +
=== Prerequisite topics ===
−
* Algorithms
  
−
* Algorithm Analysis
  
−
* Algorithmic Strategies
  
−
* Data Structures
  
   
−
=== What is the purpose of this course? ===
  
   
  +
== Course Topics ==
−
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.
  
  +
{| class="wikitable"
  +
|+ 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? ===
−
== Prerequisites ==
  
  +
This course helps you master the following concepts: Algorithms; Algorithm Analysis; Algorithmic Strategies; Data Structures.
   
  +
=== ILOs defined at three levels ===
−
* [https://eduwiki.innopolis.university/index.php/BSc:IntroductionToProgrammingI.F21 CSE101 Introduction to Programming]
  
−
* [https://eduwiki.innopolis.university/index.php/BSc:MathematicalAnalysisI.F21 CSE201 Mathematical Analysis I]
  
−
* [https://eduwiki.innopolis.university/index.php/BSc:Logic_and_Discrete_Mathematics CSE113 Logic and Discrete Mathematics]
  
−  
−
=== Course Objectives Based on Bloom’s Taxonomy ===
  
−  
−
==== - What should a student remember at the end of the course? ====
  
−  
−
By the end of the course, the students should be able to recognize and define
  
   
  +
==== Level 1: What concepts should a student know/remember/explain? ====
  +
By the end of the course, the students should be able to ...
 
* Algorithms
  
* Algorithms
 
* Abstract Data Types
  
* Abstract Data Types
Line 36: Line 60:
 
* Amortized Analysis
  
* Amortized Analysis
   
−
==== - What should a student be able to understand at the end of the course? ====
 +
==== 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 ...
−  
−
By the end of the course, the students should be able to describe and explain (with examples)
  
−  
 
* Difference between different abstract data types and data structures
  
* Difference between different abstract data types and data structures
 
* How to perform asymptotic and amortized analysis
  
* How to perform asymptotic and amortized analysis
Line 47: Line 69:
 
* Graphs, their properties, and related algorithms
  
* Graphs, their properties, and related algorithms
   
−
==== - What should a student be able to apply at the end of the course? ====
 +
==== 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 ...
−  
−
By the end of the course, the students should be able to apply
  
−  
 
* Algorithmic strategies to solve real-life problems
  
* Algorithmic strategies to solve real-life problems
 
* Asymptotic analysis to Analyze algorithms and software’s complexity
  
* Asymptotic analysis to Analyze algorithms and software’s complexity
−
* Trees and Graphs (and their theory) to solve complex problems
 +
* Trees and Graphs (and their theory) to solve complex problems
  +
== Grading ==
−  
−
=== Course evaluation ===
  
   
  +
=== Course grading range ===
−
{|
  
  +
{| class="wikitable"
−
|+ Course grade breakdown
  
  +
|+
−
!
  
−
!
  
−
!align="center"| '''Proposed points'''
  
 
|-
  
|-
  +
! Grade !! Range !! Description of performance
−
| Labs/seminar classes
  
−
| 20
  
−
|align="center"| 0
  
 
|-
  
|-
  +
| A. Excellent || 90-100 || -
−
| Interim performance assessment
  
−
| 30
  
−
|align="center"| 30
  
 
|-
  
|-
  +
| B. Good || 75-89 || -
−
| Exams
  
−
| 50
 +
|-
  +
| C. Satisfactory || 60-74 || -
−
|align="center"| 70
  
  +
|-
  +
| D. Poor || 0-59 || -
 
|}
  
|}
   
  +
=== Course activities and grading breakdown ===
−
If necessary, please indicate freely your course’s features in terms of students’ performance assessment: None
  
  +
{| class="wikitable"
−  
  +
|+
−
=== Grades range ===
  
−  
−
{|
  
−
|+ Course grading range
  
−
!
  
−
!
  
−
!align="center"| '''Proposed range'''
  
 
|-
  
|-
  +
! Activity Type !! Percentage of the overall course grade
−
| A. Excellent
  
−
| 90-100
  
−
|align="center"|
  
 
|-
  
|-
  +
| Labs/seminar classes || 0
−
| B. Good
  
−
| 75-89
  
−
|align="center"|
  
 
|-
  
|-
  +
| Interim performance assessment || 30
−
| C. Satisfactory
  
−
| 60-74
  
−
|align="center"|
  
 
|-
  
|-
−
| D. Poor
 +
| Exams || 70
−
| 0-59
  
−
|align="center"|
  
 
|}
  
|}
   
  +
=== Recommendations for students on how to succeed in the course ===
−
If necessary, please indicate freely your course’s grading features: The semester starts with the default range as proposed in the Table [[#tab:MLCourseGradingRange|[tab:MLCourseGradingRange]]], but it may change slightly (usually reduced) depending on how the semester progresses.
  
   
−
=== Resources and reference material ===
  
   
  +
== Resources, literature and reference materials ==
−
* T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. ''<span>Introduction to Algorithms. The MIT Press 2009.</span>''
  
−
* M. T. Goodrich, R. Tamassia, and M. H. Goldwasser. ''<span>Data Structures and Algorithms in Java. WILEY 2014.</span>''
  
   
−
== Course Sections ==
 +
=== 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 ===
−
The main sections of the course and approximate hour distribution between them is as follows:
  
   
  +
−
{|
  
  +
=== Software and tools used within the course ===
−
|+ Course Sections
  
  +
−
!align="center"| '''Section'''
  
  +
= Teaching Methodology: Methods, techniques, & activities =
−
! '''Section Title'''
  
  +
−
!align="center"| '''Teaching Hours'''
  
  +
== Activities and Teaching Methods ==
  +
{| class="wikitable"
  +
|+ Teaching and Learning Methods within each section
 
|-
  
|-
  +
! Teaching Techniques !! Section 1 !! Section 2 !! Section 3
−
|align="center"| 1
  
−
| Elementary Data Structures, Algorithmic Complexity and Approaches
  
−
|align="center"| 28
  
 
|-
  
|-
  +
| Development of individual parts of software product code || 1 || 1 || 1
−
|align="center"| 2
  
−
| Sorting Algorithms and Trees
  
−
|align="center"| 24
  
 
|-
  
|-
  +
| Homework and group projects || 1 || 1 || 1
−
|align="center"| 3
  
  +
|-
−
| Graphs
  
  +
| Midterm evaluation || 1 || 1 || 1
−
|align="center"| 28
  
  +
|-
  +
| Testing (written or computer based) || 1 || 1 || 1
  +
|-
  +
| Discussions || 1 || 1 || 1
 
|}
  
|}
  +
{| class="wikitable"
  +
|+ Activities within each section
  +
|-
  +
! Learning Activities !! Section 1 !! Section 2 !! Section 3
  +
|-
  +
| Question || 0 || 1 || 0
  +
|}
  +
== Formative Assessment and Course Activities ==
   
−
=== Section 1 ===
 +
=== Ongoing performance assessment ===
−  
−
==== Section title: ====
  
−  
−
Elementary Data Structures, Algorithmic Complexity and Approaches
  
−  
−
=== Topics covered in this section: ===
  
−  
−
* Algorithms and Their Analysis
  
−
* Elementary Data Structures
  
−
* Hashing Map and Collision Handling
  
−
* Algorithmic Strategies
  
−  
−
=== What forms of evaluation were used to test students’ performance in this section? ===
  
−  
−
<div class="tabular">
  
−  
−
<span>|a|c|</span> &amp; '''Yes/No'''<br />
  
−
Development of individual parts of software product code &amp; 1<br />
  
−
Homework and group projects &amp; 1<br />
  
−
Midterm evaluation &amp; 1<br />
  
−
Testing (written or computer based) &amp; 1<br />
  
−
Reports &amp; 0<br />
  
−
Essays &amp; 0<br />
  
−
Oral polls &amp; 0<br />
  
−
Discussions &amp; 1<br />
  
−  
−  
−  
−
</div>
  
−
==== Typical questions for ongoing performance evaluation within this section ====
  
   
  +
==== Section 1 ====
  +
{| class="wikitable"
  +
|+
  +
|-
  +
! 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 ====
  +
{| class="wikitable"
  +
|+
  +
|-
  +
! 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 ====
  +
{| class="wikitable"
  +
|+
  +
|-
  +
! 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'''
 
# For a given function give an asymptotic upper bound using “big-Oh” notation
  
# For a given function give an asymptotic upper bound using “big-Oh” notation
 
# Compute the worst case running time of a given algorithm.
  
# Compute the worst case running time of a given algorithm.
 
# Insert items into a hashmap given a hash function and a collision handling scheme.
  
# Insert items into a hashmap given a hash function and a collision handling scheme.
 
# Given an algorithm, identify its algorithmic strategy
  
# Given an algorithm, identify its algorithmic strategy
  +
'''Section 2'''
−  
−
==== Typical questions for seminar classes (labs) within this section ====
  
−  
−
# How to implement various data structures?
  
−
# Implement an algorithm for a given task having a desired worst case time complexity
  
−
# Describe the difference between different types algorithmic strategies
  
−
# Implement a hashmap
  
−
# Solve various practical problems using different algorithmic strategies
  
−  
−
==== Test questions for final assessment in this section ====
  
−  
−
# For a given function give an asymptotic upper bound using “big-Oh” notation
  
−
# Compute the worst case running time of a given algorithm.
  
−
# Insert items into a hashmap given a hash function and a collision handling scheme.
  
−
# Given an algorithm, identify its algorithmic strategy
  
−  
−
=== Section 2 ===
  
−  
−
==== Section title: ====
  
−  
−
Sorting Algorithms and Trees
  
−  
−
=== Topics covered in this section: ===
  
−  
−
* Comparison and Non-comparison Sort
  
−
* Binary Search Tree
  
−
* Balanced Binary Search Trees
  
−
* Tree Traversals
  
−
* Priority Queues and Binary Heaps
  
−  
−
=== What forms of evaluation were used to test students’ performance in this section? ===
  
−  
−
<div class="tabular">
  
−  
−
<span>|a|c|</span> &amp; '''Yes/No'''<br />
  
−
Development of individual parts of software product code &amp; 1<br />
  
−
Homework and group projects &amp; 1<br />
  
−
Midterm evaluation &amp; 1<br />
  
−
Testing (written or computer based) &amp; 1<br />
  
−
Reports &amp; 0<br />
  
−
Essays &amp; 0<br />
  
−
Oral polls &amp; 0<br />
  
−
Discussions &amp; 1<br />
  
−  
−  
−  
−
</div>
  
−
==== Typical questions for ongoing performance evaluation within this section ====
  
−  
−
# 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?
  
−
# Similar question as above but for other types of balanced binary search trees, including randomly built binary search trees.
  
−
# Questions related to tree algorithms, such as tree traversals
  
−
# Given a sorting problem defined under some constraints, what sorting algorithm will you use and why?
  
−  
−
==== Typical questions for seminar classes (labs) within this section ====
  
−  
−
# Implement different types of binary search trees
  
−
# Implement tree traversals
  
−
# Implement different sorting algorithms, such as quicksort, countsort, bucketsort, etc.
  
−  
−
==== Test questions for final assessment in this section ====
  
−  
 
# Given an unbalanced AVL tree, perform double rotation and show the resulting tree.
  
# Given an unbalanced AVL tree, perform double rotation and show the resulting tree.
 
# 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.
  
# 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.
 
# Implement a sorting algorithm given a problem and specify the big-Oh running time for your algorithm.
  
# Implement a sorting algorithm given a problem and specify the big-Oh running time for your algorithm.
  +
'''Section 3'''
−  
−
=== Section 3 ===
  
−  
−
==== Section title: ====
  
−  
−
Graphs
  
−  
−
=== Topics covered in this section: ===
  
−  
−
* Graph Representations
  
−
* Searching in Graphs
  
−
* Minimum Spanning Tree
  
−
* Shortest Path
  
−
* Max-flow Min-cut
  
−  
−
=== What forms of evaluation were used to test students’ performance in this section? ===
  
−  
−
<div class="tabular">
  
−  
−
<span>|a|c|</span> &amp; '''Yes/No'''<br />
  
−
Development of individual parts of software product code &amp; 1<br />
  
−
Homework and group projects &amp; 1<br />
  
−
Midterm evaluation &amp; 1<br />
  
−
Testing (written or computer based) &amp; 1<br />
  
−
Reports &amp; 0<br />
  
−
Essays &amp; 0<br />
  
−
Oral polls &amp; 0<br />
  
−
Discussions &amp; 1<br />
  
−  
−  
−  
−
</div>
  
−
==== Typical questions for ongoing performance evaluation within this section ====
  
−  
−
# Given a graph with a certain number of vertices and connected components, compute the largest number of edges that it might have?
  
−
# What is the difference between adjacency list and adjacency matrix representation of a graph?
  
−  
−
==== Typical questions for seminar classes (labs) within this section ====
  
−  
−
# Implement various graph representations
  
−
# Given a computing problem, devise an algorithm to solve it using Graphs and then implement your algorithm.
  
−  
−
==== Test questions for final assessment in this section ====
  
−  
 
# Give pseudocode for performing a certain operation in a required time complexity using the adjacency list representation.
  
# Give pseudocode for performing a certain operation in a required time complexity using the adjacency list representation.
 
# Give pseudocode for performing a certain operation in a required time complexity using the adjacency list representation.
  
# Give pseudocode for performing a certain operation in a required time complexity using the adjacency list representation.
 
# Calculate the maximum flow for a given flow network
  
# Calculate the maximum flow for a given flow network
   
−
== Exams and retake planning ==
 +
=== The retake exam ===
  +
'''Section 1'''
−  
−
=== Exam ===
  
−  
−
Exams will be paper-based and will be conducted in a form of problem solving, where the problems will be similar to those mentioned above and will based on the contents taught in lecture slides, lecture discussions (including white-board materials), lab materials, reading materials (including the text books), etc. Students will be given 1-3 hours to complete the exam.
  
−  
−
=== Retake 1 ===
  
−  
−
First retake will be conducted in the same form as the final exam. The weight of the retake exam will be 5% larger than the passing threshold of the course.
  
   
  +
'''Section 2'''
−
=== Retake 2 ===
  
   
  +
'''Section 3'''
−
Second retake will be conducted in the same form as the final exam. The weight of the retake exam will be 5% larger than the passing threshold of the course.
  

Latest revision as of 15:49, 18 August 2022

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

Retrieved from "https://eduwiki.innopolis.university/index.php?title=BSc:_Data_Structures_Algorithms&oldid=7420"